Skip to main content

consistent_choose_k/
node_map.rs

1use std::collections::HashSet;
2
3use crate::{ConsistentChooseKHasher, ManySeqBuilder};
4
5/// A consistent node map that supports dynamic addition and deletion of nodes.
6///
7/// Slots are tracked by storing the total number of slots and a set of deleted
8/// slots. To find the slot associated with a key, the consistent choose-k
9/// iterator yields positions in a consistent order; the first non-deleted slot
10/// is returned.
11///
12/// # Comparison with AnchorHash, MementoHash, and DxHash
13///
14/// This solves the same problem as [AnchorHash], [MementoHash], and [DxHash]:
15/// consistently mapping keys to a dynamic set of nodes where nodes can be
16/// added and removed, with minimal key reassignment. All of these algorithms
17/// guarantee that when a node is removed, only keys assigned to that node are
18/// redistributed — and they are redistributed uniformly among the remaining
19/// nodes.
20///
21/// The key difference is history. AnchorHash, MementoHash, and DxHash keep
22/// redirect/replacement state so that when lookup hits a deleted node, it can
23/// replay enough of the prior removal process to find the correct replacement.
24/// MementoHash, for example, defines its state as `<n, R, l>`, where `R` is a
25/// set of replacement tuples and `l` is the last removed bucket. This
26/// implementation is history-independent: it only needs to know which slots are
27/// currently deleted. Lookup simply iterates the consistent choose-k sequence
28/// until it hits an active slot.
29///
30/// This implementation takes a much simpler approach: it leverages the
31/// consistent choose-k algorithm, which already provides both n-consistency
32/// and k-consistency by construction. No auxiliary redirect structures are
33/// needed beyond the current set of deleted slots.
34///
35/// Let `total` be the number of slots, `active` the number of active slots, and
36/// `h` the number of deleted slots hit during a lookup before the first active
37/// slot is found. For AnchorHash and DxHash, `total` is the predefined capacity;
38/// for MementoHash and this implementation, it is the current slot count.
39/// MementoHash bounds the expected number of deleted-node hits by harmonic
40/// sums, e.g. `1 + H_total - H_active`, which is at most
41/// `1 + ln(total / active)`.
42///
43/// In this implementation, the choose-k iterator never returns the same slot
44/// twice, so a deleted slot can be hit at most once during a lookup. Thus the
45/// scan has the same deleted-hit behavior as the history-based algorithms, but
46/// without storing the deletion history.
47///
48/// The current choose-k iterator costs O(k) to produce the k-th candidate, so a
49/// lookup that skips `h` deleted slots costs O((h + 1)^2), and the corresponding
50/// expected total lookup cost is O((1 + ln(total / active))^2). This is in the
51/// same practical complexity regime as history-based redirection schemes: the
52/// cost grows roughly quadratically with the number of deleted-node hits, while
53/// the expected number of such hits stays small unless many slots are deleted.
54///
55/// | Algorithm | Total lookup time | State | Predefined capacity? | History-dependent? |
56/// | --- | --- | --- | --- | --- |
57/// | `ConsistentNodeMap` | `O((h + 1)^2)`, expected `O((1 + ln(total / active))^2)` | `O(deleted)` deleted-slot set | No | No |
58/// | AnchorHash | `O((h + 1)^2)`, expected `O((1 + ln(total / active))^2)` | `O(capacity)` anchor/removal state | Yes | Yes |
59/// | MementoHash | `O((h + 1)^2)`, expected `O((1 + ln(total / active))^2)` | `O(deleted)` replacement tuples | No | Yes |
60/// | DxHash | `O((h + 1)^2)`, expected `O((1 + ln(total / active))^2)` | `O(capacity)` redirect/displacement state with smaller constants than AnchorHash | Yes | Yes |
61///
62/// The MementoHash paper explicitly notes that AnchorHash and DxHash keep an
63/// internal data structure for all cluster nodes, both working and not working,
64/// and require the overall capacity to be fixed during initialization.
65/// MementoHash reduces memory by storing only replacement information for
66/// removed buckets, but that replacement information still encodes the removal
67/// history. This implementation has the same O(deleted) storage shape as that
68/// idea, but stores only the deleted set.
69///
70/// [AnchorHash]: https://arxiv.org/abs/1812.09674
71/// [MementoHash]: https://arxiv.org/abs/2306.09783
72/// [DxHash]: https://doi.org/10.1145/3631708
73///
74/// # Example
75/// ```
76/// use std::hash::{DefaultHasher, Hash};
77/// use consistent_choose_k::ConsistentNodeMap;
78///
79/// let mut map = ConsistentNodeMap::new();
80/// let a = map.add();
81/// let b = map.add();
82/// let c = map.add();
83///
84/// let mut h = DefaultHasher::default();
85/// 42u64.hash(&mut h);
86/// let slot = map.get(h).unwrap();
87/// assert!(slot == a || slot == b || slot == c);
88/// ```
89pub struct ConsistentNodeMap {
90    total: usize,
91    deleted: HashSet<usize>,
92}
93
94impl Default for ConsistentNodeMap {
95    fn default() -> Self {
96        Self::new()
97    }
98}
99
100impl ConsistentNodeMap {
101    /// Create an empty node map.
102    pub fn new() -> Self {
103        Self {
104            total: 0,
105            deleted: HashSet::new(),
106        }
107    }
108
109    /// Add a slot and return its index.
110    ///
111    /// If there is a previously deleted slot, it will be reused.
112    pub fn add(&mut self) -> usize {
113        if let Some(i) = self.deleted.iter().next().copied() {
114            self.deleted.remove(&i);
115            i
116        } else {
117            let i = self.total;
118            self.total += 1;
119            i
120        }
121    }
122
123    /// Remove the slot at the given index. Returns true if it was active.
124    pub fn remove(&mut self, index: usize) -> bool {
125        if index >= self.total || self.deleted.contains(&index) {
126            return false;
127        }
128        if index == self.total - 1 {
129            self.total -= 1;
130        } else {
131            self.deleted.insert(index);
132        }
133        true
134    }
135
136    /// Returns the number of active slots.
137    pub fn len(&self) -> usize {
138        self.total - self.deleted.len()
139    }
140
141    /// Returns true if there are no active slots.
142    pub fn is_empty(&self) -> bool {
143        self.total == self.deleted.len()
144    }
145
146    /// Returns the total number of slots (including deleted ones).
147    pub fn slot_count(&self) -> usize {
148        self.total
149    }
150
151    /// Returns whether the slot at the given index is active.
152    pub fn is_active(&self, index: usize) -> bool {
153        index < self.total && !self.deleted.contains(&index)
154    }
155
156    /// Look up which slot a key maps to using consistent hashing.
157    ///
158    /// The `builder` should be a hasher seeded with the key. The consistent
159    /// choose-k iterator yields positions in a consistent order; the first
160    /// active slot is returned.
161    pub fn get<H: ManySeqBuilder>(&self, builder: H) -> Option<usize> {
162        if self.is_empty() {
163            return None;
164        }
165        let mut iter = ConsistentChooseKHasher::new(builder, self.total);
166        iter.find(|pos| !self.deleted.contains(pos))
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use std::hash::{DefaultHasher, Hash};
173
174    use super::*;
175
176    fn hasher_for_key(key: u64) -> DefaultHasher {
177        let mut hasher = DefaultHasher::default();
178        key.hash(&mut hasher);
179        hasher
180    }
181
182    #[test]
183    fn test_add_remove() {
184        let mut map = ConsistentNodeMap::new();
185        let a = map.add();
186        let b = map.add();
187        assert_eq!(map.len(), 2);
188
189        assert!(map.remove(a));
190        assert_eq!(map.len(), 1);
191        for key in 0..100 {
192            assert_eq!(map.get(hasher_for_key(key)), Some(b));
193        }
194
195        assert!(map.remove(b));
196        assert!(map.is_empty());
197        assert_eq!(map.len(), 0);
198        assert!(map.get(hasher_for_key(0)).is_none());
199    }
200
201    #[test]
202    fn test_remove_returns_false_for_inactive() {
203        let mut map = ConsistentNodeMap::new();
204        let a = map.add();
205        assert!(map.remove(a));
206        assert!(!map.remove(a));
207        assert!(!map.remove(999));
208    }
209
210    #[test]
211    fn test_slot_reuse() {
212        let mut map = ConsistentNodeMap::new();
213        map.add();
214        let b = map.add();
215        map.add();
216        assert_eq!(map.slot_count(), 3);
217
218        map.remove(b);
219        let d = map.add();
220        assert_eq!(d, b);
221        assert_eq!(map.slot_count(), 3);
222        assert!(map.is_active(d));
223    }
224
225    #[test]
226    fn test_trailing_pop() {
227        let mut map = ConsistentNodeMap::new();
228        let a = map.add(); // 0
229        let b = map.add(); // 1
230        let c = map.add(); // 2
231        assert_eq!(map.slot_count(), 3);
232
233        // Removing last slot pops it.
234        map.remove(c);
235        assert_eq!(map.slot_count(), 2);
236
237        // Removing last again pops it.
238        map.remove(b);
239        assert_eq!(map.slot_count(), 1);
240
241        // Middle removal is tracked as deleted, not popped.
242        let b2 = map.add(); // appends as 1
243        let c2 = map.add(); // appends as 2
244        assert_eq!(b2, 1);
245        assert_eq!(c2, 2);
246        map.remove(b2); // middle -> deleted set
247        assert_eq!(map.slot_count(), 3);
248        map.remove(c2); // trailing → only pops c2
249        assert_eq!(map.slot_count(), 2); // b2 slot stays as inactive
250        assert_eq!(map.len(), 1);
251        assert!(map.is_active(a));
252    }
253
254    #[test]
255    fn test_consistency_after_add() {
256        let mut map = ConsistentNodeMap::new();
257        for _ in 0..10 {
258            map.add();
259        }
260        let before: Vec<_> = (0..10000)
261            .map(|k| map.get(hasher_for_key(k)).unwrap())
262            .collect();
263        map.add();
264        let after: Vec<_> = (0..10000)
265            .map(|k| map.get(hasher_for_key(k)).unwrap())
266            .collect();
267        let changed = before.iter().zip(&after).filter(|(a, b)| a != b).count();
268        assert!(
269            changed < 2000,
270            "too many keys changed after add: {changed}/10000"
271        );
272    }
273
274    #[test]
275    fn test_remove_10_percent_consistency() {
276        let n = 100;
277        let num_keys = 100_000u64;
278        let to_remove: Vec<usize> = (0..n).step_by(10).collect(); // 10% of nodes
279
280        let mut map = ConsistentNodeMap::new();
281        for _ in 0..n {
282            map.add();
283        }
284
285        let before: Vec<usize> = (0..num_keys)
286            .map(|k| map.get(hasher_for_key(k)).unwrap())
287            .collect();
288
289        for &slot in &to_remove {
290            map.remove(slot);
291        }
292        let remaining = map.len();
293
294        let after: Vec<usize> = (0..num_keys)
295            .map(|k| map.get(hasher_for_key(k)).unwrap())
296            .collect();
297
298        // 1. Keys not on removed nodes must stay on the same node.
299        let mut displaced = 0u64;
300        for (k, (b, a)) in before.iter().zip(&after).enumerate() {
301            if !to_remove.contains(b) {
302                assert_eq!(
303                    b, a,
304                    "key {k}: slot changed from {b} to {a} but was not on a removed slot"
305                );
306            } else {
307                displaced += 1;
308                assert!(
309                    !to_remove.contains(a),
310                    "key {k}: reassigned to removed slot {a}"
311                );
312            }
313        }
314
315        // 2. Displaced fraction should be very close to the theoretical value.
316        let displaced_pct = displaced as f64 / num_keys as f64;
317        let theoretical_pct = to_remove.len() as f64 / n as f64;
318        assert!(
319            (displaced_pct - theoretical_pct).abs() < 0.01,
320            "displaced fraction {displaced_pct:.4} not close to theoretical {theoretical_pct:.4}"
321        );
322
323        // 3. After removal, distribution among remaining nodes should be
324        //    roughly uniform: each node gets ~1/remaining of all keys.
325        let mut counts = vec![0u64; n];
326        for &a in &after {
327            counts[a] += 1;
328        }
329        let expected = num_keys as f64 / remaining as f64;
330        let chi2: f64 = counts
331            .iter()
332            .enumerate()
333            .filter(|(i, _)| !to_remove.contains(i))
334            .map(|(_, &c)| {
335                let diff = c as f64 - expected;
336                diff * diff / expected
337            })
338            .sum();
339        // Chi-squared critical value for 89 df at p=0.001 is ~122.9.
340        assert!(
341            chi2 < 200.0,
342            "distribution not uniform enough: chi2={chi2:.1} (expected < 200)"
343        );
344
345        // 4. Removed slots must have zero keys.
346        for &slot in &to_remove {
347            assert_eq!(counts[slot], 0, "removed slot {slot} still has keys");
348        }
349    }
350}