Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/dist/cohort.rs

5.6 KiB, 32 runs

created by r1870400018:11428, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Deterministic HotStuff cohort selection for cohort-backed tables.
2//!
3//! Cohort-backed tables ([`Consistency::Cohort`][c]) serialise writes through
4//! a HotStuff consensus cohort of size `lambda`. Membership is decided
5//! deterministically: every peer computes the same cohort for the same
6//! `(table_name, record_id)` pair without exchanging any selection messages.
7//!
8//! The selection rule uses the existing XOR-distance primitive: mix the table
9//! name into the record id to produce a `NodeId`-shaped seed, and take the
10//! `lambda` closest peers from the peer set (including the local peer) by
11//! XOR distance to the seed. This keeps cohorts tightly clustered in the
12//! identifier space -- a property the spec calls out as desirable for
13//! locality of future reads -- while still spreading membership uniformly
14//! across the network under a well-mixed hash.
15//!
16//! # Leader rotation
17//!
18//! Within a cohort, the leader for a given HotStuff round is chosen by
19//! round-robin indexing over the cohort's sorted member list. The round
20//! counter is owned by the HotStuff instance itself (see
21//! [`fe2o3_hotstuff`][hs]); this module provides only the *membership*
22//! decision and the *initial* leader (round zero) for convenience.
23//!
24//! [c]: crate::dist::config::Consistency::Cohort
25//! [hs]: https://github.com/oxedyne-io/fe2o3/tree/main/fe2o3_hotstuff
26//!
27//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
28//! Anthropic Claude
29
30use super::peer_set::PeerSet;
31use super::record::RecordId;
32
33use oxedyne_fe2o3_core::prelude::*;
34use crate::kademlia::id::NodeId;
35
36
37/// A cohort's membership for a specific record.
38#[derive(Clone, Debug, Eq, PartialEq)]
39pub struct Cohort {
40 pub members: Vec<NodeId>, // ascending XOR distance from the seed
41 pub local_is_member: bool,
42 pub local_is_leader: bool, // round zero
43 pub leader: NodeId, // round zero
44}
45
46impl Cohort {
47 /// The number of members, clamped to the available peer count.
48 pub fn size(&self) -> usize {
49 self.members.len()
50 }
51}
52
53
54/// The cohort is the `lambda` peers closest in XOR distance to the seed
55/// `H(table_name) XOR record_id`, where `H(table_name)` is the deterministic
56/// 32-byte splitmix64-derived hash of the table name used by
57/// [`TableConfig::iblt_seed`][ts] (broadened to 32 bytes). The local peer is
58/// considered a candidate; ties break by [`NodeId`] byte ordering.
59///
60/// `lambda` is the cohort size -- `{5, 7, 9}` in the spec. This function
61/// does not validate the range (that sits on
62/// [`TableConfig::new`][tc]); callers pass whatever `lambda` their table
63/// config declared.
64///
65/// Returns an empty cohort if `lambda == 0`, which corresponds to the
66/// degenerate "no consensus" case.
67///
68/// [ts]: crate::dist::config::TableConfig::iblt_seed
69/// [tc]: crate::dist::config::TableConfig::new
70pub fn select(
71 table_name: &str,
72 record_id: &RecordId,
73 peer_set: &PeerSet,
74 local_id: &NodeId,
75 lambda: u64,
76)
77 -> Outcome<Cohort>
78{
79 if lambda == 0 {
80 let leader = *local_id;
81 return Ok(Cohort {
82 members: Vec::new(),
83 local_is_member: false,
84 local_is_leader: false,
85 leader,
86 });
87 }
88 let seed = seed_for(table_name, record_id);
89
90 // Build the candidate list: local peer plus the peer set. Compute XOR
91 // distance to the seed for each and sort ascending.
92 let mut candidates: Vec<(NodeId, NodeId)> = Vec::with_capacity(
93 peer_set.len() + 1,
94 );
95 candidates.push((*local_id, local_id.distance(&seed).0.into_node_id()));
96 for p in peer_set.as_slice() {
97 candidates.push((*p, p.distance(&seed).0.into_node_id()));
98 }
99 // Sort by distance, tie-break on NodeId byte order for determinism.
100 candidates.sort_by(|a, b| {
101 a.1.as_bytes().cmp(b.1.as_bytes())
102 .then_with(|| a.0.as_bytes().cmp(b.0.as_bytes()))
103 });
104
105 let take = (lambda as usize).min(candidates.len());
106 let members: Vec<NodeId> = candidates.into_iter()
107 .take(take)
108 .map(|(n, _)| n)
109 .collect();
110
111 let leader = res!(members.first().copied().ok_or_else(|| err!(
112 "cohort selection produced no members despite lambda > 0"; Bug)));
113 let local_is_member = members.iter().any(|n| n == local_id);
114 let local_is_leader = leader == *local_id;
115 Ok(Cohort {
116 members,
117 local_is_member,
118 local_is_leader,
119 leader,
120 })
121}
122
123
124/// Deterministic 32-byte seed from the table name XOR the record id.
125///
126/// The table-name contribution uses the same splitmix64-based mixing that
127/// [`TableConfig::iblt_seed`][ts] does, broadened from 64 bits to a full
128/// 256 bits by successive mixing so the seed lives in the same identifier
129/// space as the record id.
130///
131/// [ts]: crate::dist::config::TableConfig::iblt_seed
132fn seed_for(table_name: &str, record_id: &RecordId) -> NodeId {
133 let mut state: u64 = 0x9E3779B97F4A7C15;
134 for byte in table_name.as_bytes() {
135 state = state.wrapping_add(*byte as u64);
136 state = (state ^ (state >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
137 state = (state ^ (state >> 27)).wrapping_mul(0x94D049BB133111EB);
138 state ^= state >> 31;
139 }
140 let mut table_hash = [0u8; 32];
141 for i in 0..4 {
142 state = state.wrapping_mul(0x9E3779B97F4A7C15 ^ (i as u64 + 1));
143 table_hash[i * 8..(i + 1) * 8].copy_from_slice(&state.to_le_bytes());
144 }
145 let mut seed = [0u8; 32];
146 for i in 0..32 {
147 seed[i] = table_hash[i] ^ record_id.as_bytes()[i];
148 }
149 NodeId::from_bytes(seed)
150}
151
152
153/// Sealed extension trait so we can convert a [`Distance`][d] into a
154/// [`NodeId`] for comparison chaining. [`Distance`] already has `Ord`, but
155/// the cohort-selection sort wants [`NodeId`] byte order as a tiebreaker
156/// and re-wrapping is cleaner than duplicating the comparator.
157///
158/// [d]: crate::kademlia::id::Distance
159trait IntoNodeId {
160 fn into_node_id(self) -> NodeId;
161}
162
163impl IntoNodeId for [u8; 32] {
164 fn into_node_id(self) -> NodeId {
165 NodeId::from_bytes(self)
166 }
167}