Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/src/oam/placement.rs

2.4 KiB, 20 runs

created by r1870400018:11370, 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//! The OAM placement decisions that consume the threshold.
2//!
3//! The three functions here answer the three placement questions a peer asks:
4//!
5//! - Am I, specifically, a holder of this record? ([`is_holder`])
6//! - Which peers, from a known set, are holders of this record? ([`holders`])
7//! - Which peers are closest to this record, regardless of the threshold, so
8//! that a read request can be issued even when my view of the threshold
9//! disagrees with theirs? ([`closest_holders`])
10//!
11//! All three reduce to XOR distance comparisons between 256-bit identifiers.
12//! None of them take locks, issue I/O, or spawn tasks.
13//!
14//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
15//! Anthropic Claude
16
17use super::threshold::Threshold;
18
19use crate::kademlia::id::NodeId;
20
21
22/// A single XOR-distance computation followed by a bytewise comparison against
23/// the stored 256-bit threshold.
24pub fn is_holder(
25 peer_id: &NodeId,
26 record_hash: &NodeId,
27 threshold: &Threshold,
28)
29 -> bool
30{
31 let d = peer_id.distance(record_hash);
32 threshold.contains(&d)
33}
34
35/// The return order mirrors the input order. Duplicates in the input produce
36/// duplicates in the output: callers that keep a canonical peer set should
37/// deduplicate before calling in.
38pub fn holders<'a>(
39 record_hash: &NodeId,
40 peers: &'a [NodeId],
41 threshold: &Threshold,
42)
43 -> Vec<&'a NodeId>
44{
45 match threshold {
46 Threshold::None => Vec::new(),
47 _ => peers.iter()
48 .filter(|p| is_holder(p, record_hash, threshold))
49 .collect(),
50 }
51}
52
53/// The `count` peers closest to the record hash by XOR distance, regardless of
54/// the OAM threshold.
55///
56/// Useful when the local peer is not itself a holder but needs to read the
57/// record: the closest peers are, under a well-mixed hash, the ones most
58/// likely to consider themselves holders -- even when the local view of `N`
59/// disagrees by a small margin with theirs.
60///
61/// If `peers.len()` is less than `count`, every peer is returned, still
62/// sorted from closest to furthest.
63pub fn closest_holders<'a>(
64 record_hash: &NodeId,
65 peers: &'a [NodeId],
66 count: usize,
67)
68 -> Vec<&'a NodeId>
69{
70 if count == 0 || peers.is_empty() {
71 return Vec::new();
72 }
73 let mut indexed: Vec<(_, &NodeId)> = peers.iter()
74 .map(|p| (p.distance(record_hash), p))
75 .collect();
76 indexed.sort_by(|a, b| a.0.cmp(&b.0));
77 indexed.into_iter()
78 .take(count)
79 .map(|(_, p)| p)
80 .collect()
81}