Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/tests/oam_placement.rs

9.8 KiB, 15 runs

created by r1870400018:11374, 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//! Integration tests for the OAM placement primitive.
2//!
3//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
4//! Anthropic Claude
5#![cfg(feature = "dist")]
6
7use oxedyne_fe2o3_core::prelude::*;
8use oxedyne_fe2o3_o3db_sync::kademlia::id::{
9 Distance,
10 NodeId,
11};
12use oxedyne_fe2o3_o3db_sync::oam::{
13 config::OamConfig,
14 placement,
15 threshold::Threshold,
16};
17
18
19/// A reproducible source of "random-looking" 256-bit identifiers, without
20/// depending on any particular RNG crate.
21struct Rng { state: u64 }
22
23impl Rng {
24 fn new(seed: u64) -> Self {
25 Self { state: seed }
26 }
27
28 fn next_u64(&mut self) -> u64 {
29 self.state = self.state.wrapping_add(0x9E3779B97F4A7C15);
30 let mut z = self.state;
31 z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
32 z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
33 z ^ (z >> 31)
34 }
35
36 fn next_id(&mut self) -> NodeId {
37 let mut bytes = [0u8; 32];
38 for i in 0..4 {
39 let word = self.next_u64().to_le_bytes();
40 bytes[i * 8..(i + 1) * 8].copy_from_slice(&word);
41 }
42 NodeId::from_bytes(bytes)
43 }
44}
45
46
47fn node_id_from_u8(b: u8) -> NodeId {
48 let mut bytes = [0u8; 32];
49 bytes[31] = b;
50 NodeId::from_bytes(bytes)
51}
52
53
54#[test]
55fn threshold_none_excludes_everything() -> Outcome<()> {
56 let t = Threshold::from_params(0, 100);
57 assert!(matches!(t, Threshold::None));
58 let p = node_id_from_u8(1);
59 let h = node_id_from_u8(2);
60 assert!(!placement::is_holder(&p, &h, &t));
61 Ok(())
62}
63
64#[test]
65fn threshold_all_includes_everything() -> Outcome<()> {
66 let t = Threshold::from_params(20, 20);
67 assert!(matches!(t, Threshold::All));
68 let mut rng = Rng::new(0xa5a5a5);
69 for _ in 0..50 {
70 let p = rng.next_id();
71 let h = rng.next_id();
72 assert!(placement::is_holder(&p, &h, &t));
73 }
74 Ok(())
75}
76
77#[test]
78fn threshold_half_network_top_bit_set() -> Outcome<()> {
79 let t = Threshold::from_params(1, 2);
80 let bytes = match &t {
81 Threshold::Bounded(b) => b,
82 _ => return Err(err!("expected Bounded threshold"; Bug, Mismatch)),
83 };
84 assert_eq!(bytes[0], 0x80);
85 for b in &bytes[1..] {
86 assert_eq!(*b, 0);
87 }
88 Ok(())
89}
90
91#[test]
92fn threshold_quarter_network_second_bit_set() -> Outcome<()> {
93 let t = Threshold::from_params(1, 4);
94 let bytes = match &t {
95 Threshold::Bounded(b) => b,
96 _ => return Err(err!("expected Bounded threshold"; Bug, Mismatch)),
97 };
98 assert_eq!(bytes[0], 0x40);
99 for b in &bytes[1..] {
100 assert_eq!(*b, 0);
101 }
102 Ok(())
103}
104
105#[test]
106fn config_rejects_zero_network_with_positive_replication() -> Outcome<()> {
107 assert!(OamConfig::new(20, 0).is_err());
108 Ok(())
109}
110
111#[test]
112fn config_accepts_zero_replication_zero_network() -> Outcome<()> {
113 let cfg = res!(OamConfig::new(0, 0));
114 assert!(matches!(cfg.threshold(), Threshold::None));
115 Ok(())
116}
117
118#[test]
119fn config_default_replication_is_twenty() -> Outcome<()> {
120 let cfg = res!(OamConfig::default_replication(1_000));
121 assert_eq!(cfg.replication, 20);
122 assert_eq!(cfg.network_size, 1_000);
123 assert_eq!(cfg.expected_holders(), 20);
124 Ok(())
125}
126
127#[test]
128fn config_expected_holders_clamps_at_network() -> Outcome<()> {
129 let cfg = res!(OamConfig::new(100, 10));
130 assert_eq!(cfg.expected_holders(), 10);
131 Ok(())
132}
133
134#[test]
135fn is_holder_for_zero_distance_matches_threshold_positivity() -> Outcome<()> {
136 // Equal peer id and record hash -> zero XOR distance. A Bounded threshold
137 // of any positive value covers zero distance, so the peer always holds.
138 let cfg = res!(OamConfig::new(1, 1_000));
139 let t = cfg.threshold();
140 assert!(matches!(t, Threshold::Bounded(_)));
141 let same = node_id_from_u8(42);
142 assert!(placement::is_holder(&same, &same, &t));
143 Ok(())
144}
145
146#[test]
147fn is_holder_is_deterministic() -> Outcome<()> {
148 let cfg = res!(OamConfig::new(20, 500));
149 let t = cfg.threshold();
150 let mut rng = Rng::new(0x1234_5678);
151 for _ in 0..1000 {
152 let p = rng.next_id();
153 let h = rng.next_id();
154 let a = placement::is_holder(&p, &h, &t);
155 let b = placement::is_holder(&p, &h, &t);
156 assert_eq!(a, b);
157 }
158 Ok(())
159}
160
161#[test]
162fn is_holder_is_symmetric_in_operands() -> Outcome<()> {
163 // XOR is symmetric, so is_holder(p, h, t) == is_holder(h, p, t).
164 let cfg = res!(OamConfig::new(20, 500));
165 let t = cfg.threshold();
166 let mut rng = Rng::new(0xdead_beef);
167 for _ in 0..100 {
168 let p = rng.next_id();
169 let h = rng.next_id();
170 assert_eq!(
171 placement::is_holder(&p, &h, &t),
172 placement::is_holder(&h, &p, &t),
173 );
174 }
175 Ok(())
176}
177
178#[test]
179fn uniform_sampling_converges_to_fraction() -> Outcome<()> {
180 // For well-mixed ids and hashes, the fraction of holders should approach
181 // n/N. Sample ten thousand random (peer, record) pairs at n=20, N=500 and
182 // count holders; expected = 10 000 * 20 / 500 = 400, standard deviation
183 // sqrt(400 * (1 - 20/500)) ~ 19.6. Accept a +/- 15% window (60 holders,
184 // ~3 sigma) which is tight enough to catch bugs and loose enough not to
185 // flake.
186 let cfg = res!(OamConfig::new(20, 500));
187 let t = cfg.threshold();
188 let mut rng = Rng::new(0xaaaa_bbbb);
189 let mut hits = 0usize;
190 let trials = 10_000usize;
191 for _ in 0..trials {
192 let p = rng.next_id();
193 let h = rng.next_id();
194 if placement::is_holder(&p, &h, &t) {
195 hits += 1;
196 }
197 }
198 let expected = trials as f64 * cfg.replication as f64 / cfg.network_size as f64;
199 let diff = (hits as f64 - expected).abs();
200 assert!(
201 diff / expected < 0.15,
202 "uniform sampling off: hits={} expected={:.1} diff={:.1} (>15%)",
203 hits, expected, diff,
204 );
205 Ok(())
206}
207
208#[test]
209fn holders_filters_by_threshold() -> Outcome<()> {
210 let cfg = res!(OamConfig::new(50, 500));
211 let t = cfg.threshold();
212 let mut rng = Rng::new(0xc0de_babe);
213 let mut peers: Vec<NodeId> = (0..200).map(|_| rng.next_id()).collect();
214 peers.sort_by(|a, b| a.as_bytes().cmp(b.as_bytes()));
215 peers.dedup();
216
217 let record = rng.next_id();
218 let hs = placement::holders(&record, &peers, &t);
219 // Every peer in hs must pass is_holder; every peer not in hs must fail.
220 let picked: std::collections::HashSet<_> =
221 hs.iter().map(|n| *n.as_bytes()).collect();
222 for p in &peers {
223 let expected = placement::is_holder(p, &record, &t);
224 let actual = picked.contains(p.as_bytes());
225 assert_eq!(
226 expected, actual,
227 "holders() disagreed with is_holder() for peer {}.", p,
228 );
229 }
230 // The fraction should roughly match the configured ratio.
231 let expected_count = peers.len() as f64 * 50.0 / 500.0;
232 let diff = (hs.len() as f64 - expected_count).abs();
233 assert!(
234 diff / expected_count < 0.5,
235 "holders() count off: got {} expected ~{:.1}",
236 hs.len(), expected_count,
237 );
238 Ok(())
239}
240
241#[test]
242fn holders_preserves_order() -> Outcome<()> {
243 let cfg = res!(OamConfig::new(100, 200));
244 let t = cfg.threshold();
245 let mut rng = Rng::new(0x1111_2222);
246 let peers: Vec<NodeId> = (0..50).map(|_| rng.next_id()).collect();
247 let record = rng.next_id();
248 let hs = placement::holders(&record, &peers, &t);
249 // Scan peers in input order, collect those that pass; should match hs.
250 let expected: Vec<&NodeId> = peers.iter()
251 .filter(|p| placement::is_holder(p, &record, &t))
252 .collect();
253 assert_eq!(hs.len(), expected.len());
254 for (a, b) in hs.iter().zip(expected.iter()) {
255 assert_eq!(a.as_bytes(), b.as_bytes());
256 }
257 Ok(())
258}
259
260#[test]
261fn holders_none_threshold_returns_empty() -> Outcome<()> {
262 let t = Threshold::None;
263 let mut rng = Rng::new(0);
264 let peers: Vec<NodeId> = (0..10).map(|_| rng.next_id()).collect();
265 let record = rng.next_id();
266 assert!(placement::holders(&record, &peers, &t).is_empty());
267 Ok(())
268}
269
270#[test]
271fn holders_all_threshold_returns_all() -> Outcome<()> {
272 let t = Threshold::All;
273 let mut rng = Rng::new(0);
274 let peers: Vec<NodeId> = (0..10).map(|_| rng.next_id()).collect();
275 let record = rng.next_id();
276 let hs = placement::holders(&record, &peers, &t);
277 assert_eq!(hs.len(), peers.len());
278 Ok(())
279}
280
281#[test]
282fn closest_holders_orders_by_xor_distance() -> Outcome<()> {
283 let mut rng = Rng::new(0xfeed_face);
284 let peers: Vec<NodeId> = (0..100).map(|_| rng.next_id()).collect();
285 let record = rng.next_id();
286 let closest = placement::closest_holders(&record, &peers, 10);
287 assert_eq!(closest.len(), 10);
288 // Distances must be non-decreasing.
289 let mut prev: Option<Distance> = None;
290 for p in &closest {
291 let d = p.distance(&record);
292 if let Some(last) = prev {
293 assert!(d >= last, "closest_holders not sorted by distance");
294 }
295 prev = Some(d);
296 }
297 // The first closest must be the global minimum across all peers.
298 let global_min = peers.iter()
299 .map(|p| p.distance(&record))
300 .min();
301 assert_eq!(Some(closest[0].distance(&record)), global_min);
302 Ok(())
303}
304
305#[test]
306fn closest_holders_returns_all_when_requested_exceeds_set() -> Outcome<()> {
307 let mut rng = Rng::new(0x9876);
308 let peers: Vec<NodeId> = (0..5).map(|_| rng.next_id()).collect();
309 let record = rng.next_id();
310 let closest = placement::closest_holders(&record, &peers, 100);
311 assert_eq!(closest.len(), 5);
312 Ok(())
313}
314
315#[test]
316fn closest_holders_count_zero_is_empty() -> Outcome<()> {
317 let mut rng = Rng::new(0);
318 let peers: Vec<NodeId> = (0..5).map(|_| rng.next_id()).collect();
319 let record = rng.next_id();
320 assert!(placement::closest_holders(&record, &peers, 0).is_empty());
321 Ok(())
322}
323
324#[test]
325fn threshold_as_bytes_roundtrips_via_node_id() -> Outcome<()> {
326 let t = Threshold::from_params(7, 1000);
327 let bytes = res!(t.as_bytes().ok_or_else(|| err!(
328 "Bounded threshold had no bytes"; Bug, Missing)));
329 let nid = res!(t.as_node_id().ok_or_else(|| err!(
330 "Bounded threshold had no NodeId view"; Bug, Missing)));
331 assert_eq!(nid.as_bytes(), bytes);
332 Ok(())
333}
334
335#[test]
336fn monotone_in_replication_factor() -> Outcome<()> {
337 // Larger n should yield a larger or equal threshold; a peer that holds at
338 // n=k must still hold at n=k+1 (all else equal).
339 let cfg_small = res!(OamConfig::new(10, 1000));
340 let cfg_large = res!(OamConfig::new(30, 1000));
341 let ts = cfg_small.threshold();
342 let tl = cfg_large.threshold();
343 let mut rng = Rng::new(0x1234);
344 for _ in 0..500 {
345 let p = rng.next_id();
346 let h = rng.next_id();
347 let s = placement::is_holder(&p, &h, &ts);
348 let l = placement::is_holder(&p, &h, &tl);
349 if s {
350 assert!(l, "holder at n=10 but not at n=30");
351 }
352 }
353 Ok(())
354}