oxedyne/fe2o3/fe2o3_o3db_sync/src/oam/mod.rs
2.5 KiB, 15 runs
created by r1870400018:11368, 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 Oxegen Allocation Mechanism (OAM) primitive for the Hematite distributed |
| 2 | //! Ozone layer. |
| 3 | //! |
| 4 | //! OAM answers a single question without exchanging any routing messages: |
| 5 | //! *"Does peer $p$ hold record $d$?"* It answers it with a deterministic |
| 6 | //! threshold test on the XOR distance between the peer's identifier and the |
| 7 | //! record's hash. |
| 8 | //! |
| 9 | //! A peer $p$ holds record $d$ if and only if |
| 10 | //! |
| 11 | //! $ "XOR"("peer_id"_p, H(d)) < 2^256 dot n / N $ |
| 12 | //! |
| 13 | //! where `n` is the replication factor and `N` is the current estimated |
| 14 | //! network size. Two peers with the same view of `n` and `N` will always |
| 15 | //! agree on which peers hold which records. The expected number of holders |
| 16 | //! per record is `min(n, N)`, with tight concentration when `N` is large. |
| 17 | //! |
| 18 | //! # Identifier space |
| 19 | //! |
| 20 | //! OAM reuses the 256-bit identifier space from [`crate::kademlia`]. |
| 21 | //! Record hashes are interpreted as [`NodeId`]s and compared to peer |
| 22 | //! identifiers by XOR distance. This keeps the Kademlia routing layer and the |
| 23 | //! OAM placement layer consistent: the same hash that identifies a record for |
| 24 | //! storage also identifies its neighbourhood for lookup. |
| 25 | //! |
| 26 | //! # What this crate does not do |
| 27 | //! |
| 28 | //! - Hash records. Callers bring a cryptographic hash -- SHA-3, BLAKE3, or |
| 29 | //! whatever their application dictates -- and hand in the resulting 32 bytes |
| 30 | //! as a [`NodeId`]. |
| 31 | //! - Estimate the network size. OAM consumes an `N` value that the caller |
| 32 | //! obtains from the HyperLogLog layer (see [`oxedyne_fe2o3_data::hll`]). |
| 33 | //! - Route, replicate, or transport data. OAM only decides *who should hold*; |
| 34 | //! the distributed Ozone engine decides *how to get the record there*. |
| 35 | //! |
| 36 | //! # Example |
| 37 | //! |
| 38 | //! ``` |
| 39 | //! use oxedyne_fe2o3_core::prelude::*; |
| 40 | //! use oxedyne_fe2o3_o3db_sync::kademlia::id::NodeId; |
| 41 | //! use oxedyne_fe2o3_o3db_sync::oam::{ |
| 42 | //! config::OamConfig, |
| 43 | //! placement, |
| 44 | //! }; |
| 45 | //! |
| 46 | //! # fn main() -> Outcome<()> { |
| 47 | //! // Twenty replicas on a network of five hundred peers. |
| 48 | //! let cfg = res!(OamConfig::new(20, 500)); |
| 49 | //! let threshold = cfg.threshold(); |
| 50 | //! |
| 51 | //! // A peer asks: do I hold the record with this hash? |
| 52 | //! let my_peer_id = NodeId::from_bytes([0u8; 32]); |
| 53 | //! let record_hash = NodeId::from_bytes([0u8; 32]); |
| 54 | //! assert!(placement::is_holder(&my_peer_id, &record_hash, &threshold)); |
| 55 | //! # Ok(()) |
| 56 | //! # } |
| 57 | //! ``` |
| 58 | //! |
| 59 | //! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\ |
| 60 | //! Anthropic Claude |
| 61 | |
| 62 | pub mod config; |
| 63 | pub mod placement; |
| 64 | pub mod threshold; |
| 65 | |
| 66 | pub use self::{ |
| 67 | config::OamConfig, |
| 68 | threshold::Threshold, |
| 69 | }; |