Skip to main content

qualia_core_db/net/qdnf/resolve/qsr/
hot.rs

1//! Hot exact-key coalescing, stable secondary partitioning, acyclic commitments
2//! (E07.6).
3//!
4//! A single exact key is not split by re-hashing its identity. Replica count is
5//! 1..=3. Large postings partition on the full 48-byte record id. Parent
6//! pointers that would cycle are Conflict.
7
8use crate::net::qdnf::errors::QdnfError;
9use crate::net::qdnf::types::StrongDigest;
10
11/// Admitted replica count for a hot exact key.
12pub const MAX_HOT_REPLICAS: u8 = 3;
13/// Small parent table for acyclic primary/secondary/checkpoint commitments.
14pub const PARENT_CAP: u8 = 8;
15const NO_PARENT: u8 = 0xff;
16
17/// Secondary partition of a full record identity.
18#[repr(C)]
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub struct Partition {
21    pub part: u8,
22    pub of: u8,
23}
24
25/// Parent pointers for an 8-node commitment DAG. `0xff` means no parent.
26#[repr(C)]
27#[derive(Clone, Copy, Debug)]
28pub struct ParentTable {
29    parent: [u8; 8],
30}
31
32impl ParentTable {
33    /// Creates a default `ParentTable`.
34    pub const fn new() -> Self {
35        Self {
36            parent: [NO_PARENT; 8],
37        }
38    }
39
40    #[inline]
41    /// `ParentTable::parent_of`.
42    pub const fn parent_of(&self, node: u8) -> Option<u8> {
43        if node >= PARENT_CAP {
44            return None;
45        }
46        let p = self.parent[node as usize];
47        if p == NO_PARENT {
48            None
49        } else {
50            Some(p)
51        }
52    }
53}
54
55/// Coalesce identical scoped reads onto one replica in `1..=replicas`.
56///
57/// `replicas` must be 1..=3. Same key always maps to the same replica index.
58pub fn coalesce_hot(key: &StrongDigest, replicas: u8) -> Result<u8, QdnfError> {
59    if replicas < 1 || replicas > MAX_HOT_REPLICAS {
60        return Err(QdnfError::Range);
61    }
62    let slot = mix_key(key) % (replicas as u32);
63    Ok(slot as u8 + 1)
64}
65
66/// Stable full-record partition. `parts == 0` is Range. Same key → same part.
67pub fn partition_record(key: &StrongDigest, parts: u8) -> Result<Partition, QdnfError> {
68    if parts == 0 {
69        return Err(QdnfError::Range);
70    }
71    let part = (mix_key(key) % (parts as u32)) as u8;
72    Ok(Partition { part, of: parts })
73}
74
75fn mix_key(key: &StrongDigest) -> u32 {
76    let mut acc = 2166136261u32;
77    let mut i = 0usize;
78    while i < 48 {
79        acc = acc.wrapping_mul(16777619).wrapping_add(key.0[i] as u32);
80        i += 1;
81    }
82    acc
83}
84
85/// Bind `child` to `parent` (0..8). A cycle is Conflict.
86pub fn insert_parent(table: &mut ParentTable, child: u8, parent: u8) -> Result<(), QdnfError> {
87    if child >= PARENT_CAP || parent >= PARENT_CAP {
88        return Err(QdnfError::Range);
89    }
90    if child == parent {
91        return Err(QdnfError::Conflict);
92    }
93    let mut cur = parent;
94    let mut steps = 0u8;
95    while steps < PARENT_CAP {
96        if cur == child {
97            return Err(QdnfError::Conflict);
98        }
99        let next = table.parent[cur as usize];
100        if next == NO_PARENT {
101            break;
102        }
103        cur = next;
104        steps = steps + 1;
105    }
106    table.parent[child as usize] = parent;
107    Ok(())
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113
114    fn key_tail(b47: u8) -> StrongDigest {
115        let mut k = StrongDigest::ZERO;
116        k.0[0] = 0xab;
117        k.0[47] = b47;
118        k
119    }
120
121    #[test]
122    fn coalesce_rejects_zero_and_more_than_three() {
123        let k = StrongDigest::ZERO;
124        assert_eq!(coalesce_hot(&k, 0), Err(QdnfError::Range));
125        assert_eq!(coalesce_hot(&k, 4), Err(QdnfError::Range));
126        let r = coalesce_hot(&k, 3).unwrap();
127        assert!(r >= 1 && r <= 3);
128    }
129
130    #[test]
131    fn coalesce_is_stable_for_same_key() {
132        let k = key_tail(0x11);
133        assert_eq!(coalesce_hot(&k, 2).unwrap(), coalesce_hot(&k, 2).unwrap());
134    }
135
136    #[test]
137    fn partition_is_stable_for_same_key() {
138        let k = key_tail(0x22);
139        let a = partition_record(&k, 7).unwrap();
140        let b = partition_record(&k, 7).unwrap();
141        assert_eq!(a, b);
142        assert_eq!(a.of, 7);
143        assert!(a.part < 7);
144    }
145
146    #[test]
147    fn partition_uses_later_bytes() {
148        let a = key_tail(0x01);
149        let b = key_tail(0x02);
150        assert_eq!(a.0[0], b.0[0]);
151        let pa = partition_record(&a, 16).unwrap();
152        let pb = partition_record(&b, 16).unwrap();
153        assert_eq!(pa.of, pb.of);
154        assert_ne!(pa.part, pb.part);
155    }
156
157    #[test]
158    fn partition_zero_parts_is_range() {
159        assert_eq!(
160            partition_record(&StrongDigest::ZERO, 0),
161            Err(QdnfError::Range)
162        );
163    }
164
165    #[test]
166    fn parent_cycle_is_conflict() {
167        let mut t = ParentTable::new();
168        insert_parent(&mut t, 1, 0).unwrap();
169        insert_parent(&mut t, 2, 1).unwrap();
170        assert_eq!(insert_parent(&mut t, 0, 2), Err(QdnfError::Conflict));
171        assert_eq!(insert_parent(&mut t, 3, 3), Err(QdnfError::Conflict));
172        assert_eq!(t.parent_of(1), Some(0));
173        assert_eq!(t.parent_of(0), None);
174    }
175
176    #[test]
177    fn parent_out_of_table_is_range() {
178        let mut t = ParentTable::new();
179        assert_eq!(insert_parent(&mut t, 8, 0), Err(QdnfError::Range));
180        assert_eq!(insert_parent(&mut t, 0, 8), Err(QdnfError::Range));
181    }
182
183    #[test]
184    fn acyclic_chain_is_ok() {
185        let mut t = ParentTable::new();
186        insert_parent(&mut t, 2, 1).unwrap();
187        insert_parent(&mut t, 1, 0).unwrap();
188        assert_eq!(t.parent_of(2), Some(1));
189        assert_eq!(t.parent_of(1), Some(0));
190    }
191}