pub struct ConsistentNodeMap { /* private fields */ }Expand description
A consistent node map that supports dynamic addition and deletion of nodes.
Slots are tracked by storing the total number of slots and a set of deleted slots. To find the slot associated with a key, the consistent choose-k iterator yields positions in a consistent order; the first non-deleted slot is returned.
§Comparison with AnchorHash, MementoHash, and DxHash
This solves the same problem as AnchorHash, MementoHash, and DxHash: consistently mapping keys to a dynamic set of nodes where nodes can be added and removed, with minimal key reassignment. All of these algorithms guarantee that when a node is removed, only keys assigned to that node are redistributed — and they are redistributed uniformly among the remaining nodes.
The key difference is history. AnchorHash, MementoHash, and DxHash keep
redirect/replacement state so that when lookup hits a deleted node, it can
replay enough of the prior removal process to find the correct replacement.
MementoHash, for example, defines its state as <n, R, l>, where R is a
set of replacement tuples and l is the last removed bucket. This
implementation is history-independent: it only needs to know which slots are
currently deleted. Lookup simply iterates the consistent choose-k sequence
until it hits an active slot.
This implementation takes a much simpler approach: it leverages the consistent choose-k algorithm, which already provides both n-consistency and k-consistency by construction. No auxiliary redirect structures are needed beyond the current set of deleted slots.
Let total be the number of slots, active the number of active slots, and
h the number of deleted slots hit during a lookup before the first active
slot is found. For AnchorHash and DxHash, total is the predefined capacity;
for MementoHash and this implementation, it is the current slot count.
MementoHash bounds the expected number of deleted-node hits by harmonic
sums, e.g. 1 + H_total - H_active, which is at most
1 + ln(total / active).
In this implementation, the choose-k iterator never returns the same slot twice, so a deleted slot can be hit at most once during a lookup. Thus the scan has the same deleted-hit behavior as the history-based algorithms, but without storing the deletion history.
The current choose-k iterator costs O(k) to produce the k-th candidate, so a
lookup that skips h deleted slots costs O((h + 1)^2), and the corresponding
expected total lookup cost is O((1 + ln(total / active))^2). This is in the
same practical complexity regime as history-based redirection schemes: the
cost grows roughly quadratically with the number of deleted-node hits, while
the expected number of such hits stays small unless many slots are deleted.
| Algorithm | Total lookup time | State | Predefined capacity? | History-dependent? |
|---|---|---|---|---|
ConsistentNodeMap | O((h + 1)^2), expected O((1 + ln(total / active))^2) | O(deleted) deleted-slot set | No | No |
| AnchorHash | O((h + 1)^2), expected O((1 + ln(total / active))^2) | O(capacity) anchor/removal state | Yes | Yes |
| MementoHash | O((h + 1)^2), expected O((1 + ln(total / active))^2) | O(deleted) replacement tuples | No | Yes |
| DxHash | O((h + 1)^2), expected O((1 + ln(total / active))^2) | O(capacity) redirect/displacement state with smaller constants than AnchorHash | Yes | Yes |
The MementoHash paper explicitly notes that AnchorHash and DxHash keep an internal data structure for all cluster nodes, both working and not working, and require the overall capacity to be fixed during initialization. MementoHash reduces memory by storing only replacement information for removed buckets, but that replacement information still encodes the removal history. This implementation has the same O(deleted) storage shape as that idea, but stores only the deleted set.
§Example
use std::hash::{DefaultHasher, Hash};
use consistent_choose_k::ConsistentNodeMap;
let mut map = ConsistentNodeMap::new();
let a = map.add();
let b = map.add();
let c = map.add();
let mut h = DefaultHasher::default();
42u64.hash(&mut h);
let slot = map.get(h).unwrap();
assert!(slot == a || slot == b || slot == c);Implementations§
Source§impl ConsistentNodeMap
impl ConsistentNodeMap
Sourcepub fn add(&mut self) -> usize
pub fn add(&mut self) -> usize
Add a slot and return its index.
If there is a previously deleted slot, it will be reused.
Sourcepub fn remove(&mut self, index: usize) -> bool
pub fn remove(&mut self, index: usize) -> bool
Remove the slot at the given index. Returns true if it was active.
Sourcepub fn slot_count(&self) -> usize
pub fn slot_count(&self) -> usize
Returns the total number of slots (including deleted ones).
Sourcepub fn is_active(&self, index: usize) -> bool
pub fn is_active(&self, index: usize) -> bool
Returns whether the slot at the given index is active.
Sourcepub fn get<H: ManySeqBuilder>(&self, builder: H) -> Option<usize>
pub fn get<H: ManySeqBuilder>(&self, builder: H) -> Option<usize>
Look up which slot a key maps to using consistent hashing.
The builder should be a hasher seeded with the key. The consistent
choose-k iterator yields positions in a consistent order; the first
active slot is returned.