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}