oxedyne/fe2o3/fe2o3_o3db_sync/src/kademlia/mod.rs
2.5 KiB, 7 runs
created by r1870400018:11192, 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 | //! A Kademlia DHT routing-table primitive for the Hematite distributed Ozone |
| 2 | //! layer. |
| 3 | //! |
| 4 | //! This crate is the *routing* layer only -- pure data structures and |
| 5 | //! algorithms. It has no transport, no asynchrony, no I/O. Higher layers |
| 6 | //! (Shield transport, OAM allocation, IBLT anti-entropy, HotStuff consensus) |
| 7 | //! depend on it but are kept in their own crates. |
| 8 | //! |
| 9 | //! # Identifier space |
| 10 | //! |
| 11 | //! Node identifiers are 256 bits. Distance is XOR -- see [`id::NodeId`] and |
| 12 | //! [`id::Distance`]. A node's routing table holds 256 k-maps, one per bit of |
| 13 | //! XOR distance from the local node; the k-map for bit `i` holds peers whose |
| 14 | //! distance from the local node is in `[2^i, 2^(i+1))`. |
| 15 | //! |
| 16 | //! # Replacement |
| 17 | //! |
| 18 | //! Each k-map holds at most `k` contacts. When a new contact arrives for a |
| 19 | //! full bucket the routing table does *not* evict unilaterally -- it returns |
| 20 | //! the current LRU as a candidate and waits for the caller to probe it. |
| 21 | //! Kademlia's LRU-biased policy is that a responsive LRU stays and the new |
| 22 | //! contact is dropped; only a confirmed-dead LRU is replaced. This crate |
| 23 | //! encodes that contract through [`kmap::InsertOutcome`] and |
| 24 | //! [`table::RoutingTable::keep_lru`] / [`table::RoutingTable::evict_and_insert`]. |
| 25 | //! |
| 26 | //! # What this crate does not do |
| 27 | //! |
| 28 | //! - Send or receive any messages. |
| 29 | //! - Authenticate peers. Public keys, key rotation and signature verification |
| 30 | //! belong to fe2o3_crypto and the distributed Ozone layer above this one. |
| 31 | //! - Store data records. That role belongs to OAM and the local Ozone engine. |
| 32 | //! - Maintain bucket-refresh schedules or iterative lookup state. Those are |
| 33 | //! higher-layer concerns -- they consume [`table::RoutingTable::k_closest`] |
| 34 | //! but own their own state. |
| 35 | //! |
| 36 | //! # Example |
| 37 | //! |
| 38 | //! ``` |
| 39 | //! use oxedyne_fe2o3_core::prelude::*; |
| 40 | //! use oxedyne_fe2o3_o3db_sync::kademlia::{ |
| 41 | //! contact::Contact, |
| 42 | //! id::NodeId, |
| 43 | //! table::RoutingTable, |
| 44 | //! }; |
| 45 | //! use std::net::SocketAddr; |
| 46 | //! |
| 47 | //! # fn main() -> Outcome<()> { |
| 48 | //! let me = NodeId::from_bytes([0u8; 32]); |
| 49 | //! let mut table = res!(RoutingTable::new(me, 20)); |
| 50 | //! |
| 51 | //! let mut peer_id_bytes = [0u8; 32]; |
| 52 | //! peer_id_bytes[31] = 1; |
| 53 | //! let peer_id = NodeId::from_bytes(peer_id_bytes); |
| 54 | //! let addr: SocketAddr = res!("127.0.0.1:60000".parse()); |
| 55 | //! let contact = Contact::new(peer_id, vec![addr]); |
| 56 | //! |
| 57 | //! let _ = res!(table.insert(contact)); |
| 58 | //! assert_eq!(table.len(), 1); |
| 59 | //! # Ok(()) |
| 60 | //! # } |
| 61 | //! ``` |
| 62 | //! |
| 63 | //! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\ |
| 64 | //! Anthropic Claude |
| 65 | |
| 66 | pub mod contact; |
| 67 | pub mod id; |
| 68 | pub mod kmap; |
| 69 | pub mod table; |