oxedyne/fe2o3/fe2o3_data/src/iblt/mod.rs
2.2 KiB, 5 runs
created by r1870400018:11216, 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 | //! An Invertible Bloom Lookup Table primitive for the Hematite distributed |
| 2 | //! Ozone layer. |
| 3 | //! |
| 4 | //! An IBLT is a fixed-size sketch that supports insert, delete, subtract and |
| 5 | //! peeling-decode over fixed-length byte keys. Two IBLTs with the same |
| 6 | //! configuration subtract cell-wise into a third IBLT that encodes their |
| 7 | //! symmetric difference; the peeling decoder recovers the distinct keys (and |
| 8 | //! optional values) from that difference, in time linear in the difference's |
| 9 | //! size, not the input's. IBLTs shine when the expected difference is small |
| 10 | //! compared to the total dataset -- which is the steady-state case for |
| 11 | //! Ozone anti-entropy. |
| 12 | //! |
| 13 | //! # Sizing rule of thumb |
| 14 | //! |
| 15 | //! For a target symmetric difference of at most `d` entries, allocate |
| 16 | //! `num_cells ≈ 1.5 × d` with `num_hashes = 3`, or `num_cells ≈ 1.3 × d` |
| 17 | //! with `num_hashes = 4`. Below these thresholds the decode succeeds with |
| 18 | //! high probability; above them the peeling stalls and the caller must fall |
| 19 | //! back to a larger IBLT or a bulk transfer. See |
| 20 | //! [`iblt::DecodeOutcome::Incomplete`] for the failure path. |
| 21 | //! |
| 22 | //! # Example |
| 23 | //! |
| 24 | //! ``` |
| 25 | //! use oxedyne_fe2o3_core::prelude::*; |
| 26 | //! use oxedyne_fe2o3_data::iblt::{DecodeOutcome, Iblt, IbltConfig}; |
| 27 | //! |
| 28 | //! # fn main() -> Outcome<()> { |
| 29 | //! let cfg = IbltConfig { |
| 30 | //! num_cells: 80, |
| 31 | //! num_hashes: 3, |
| 32 | //! key_len: 8, |
| 33 | //! value_len: 0, |
| 34 | //! seed: 0xabcd_1234, |
| 35 | //! }; |
| 36 | //! |
| 37 | //! let mut a = res!(Iblt::new(cfg)); |
| 38 | //! let mut b = res!(Iblt::new(cfg)); |
| 39 | //! |
| 40 | //! // A has {1..20}, B has {10..30}. Symmetric difference = 20 keys. |
| 41 | //! for i in 1u64..20 { |
| 42 | //! res!(a.insert(&i.to_le_bytes(), &[])); |
| 43 | //! } |
| 44 | //! for i in 10u64..30 { |
| 45 | //! res!(b.insert(&i.to_le_bytes(), &[])); |
| 46 | //! } |
| 47 | //! |
| 48 | //! // Diff = A minus B. |
| 49 | //! res!(a.subtract(&b)); |
| 50 | //! match res!(a.decode()) { |
| 51 | //! DecodeOutcome::Complete { inserted, deleted } => { |
| 52 | //! // `inserted` = keys in A but not B; `deleted` = keys in B but not A. |
| 53 | //! assert_eq!(inserted.len() + deleted.len(), 19); |
| 54 | //! }, |
| 55 | //! DecodeOutcome::Incomplete { .. } => panic!("unexpected overload"), |
| 56 | //! } |
| 57 | //! # Ok(()) |
| 58 | //! # } |
| 59 | //! ``` |
| 60 | mod hash; |
| 61 | mod imp; |
| 62 | |
| 63 | pub use imp::{ |
| 64 | DecodeOutcome, |
| 65 | Iblt, |
| 66 | IbltConfig, |
| 67 | }; |