Skip to main content

ConsistentNodeMap

Struct ConsistentNodeMap 

Source
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.

AlgorithmTotal lookup timeStatePredefined capacity?History-dependent?
ConsistentNodeMapO((h + 1)^2), expected O((1 + ln(total / active))^2)O(deleted) deleted-slot setNoNo
AnchorHashO((h + 1)^2), expected O((1 + ln(total / active))^2)O(capacity) anchor/removal stateYesYes
MementoHashO((h + 1)^2), expected O((1 + ln(total / active))^2)O(deleted) replacement tuplesNoYes
DxHashO((h + 1)^2), expected O((1 + ln(total / active))^2)O(capacity) redirect/displacement state with smaller constants than AnchorHashYesYes

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

Source

pub fn new() -> Self

Create an empty node map.

Source

pub fn add(&mut self) -> usize

Add a slot and return its index.

If there is a previously deleted slot, it will be reused.

Source

pub fn remove(&mut self, index: usize) -> bool

Remove the slot at the given index. Returns true if it was active.

Source

pub fn len(&self) -> usize

Returns the number of active slots.

Source

pub fn is_empty(&self) -> bool

Returns true if there are no active slots.

Source

pub fn slot_count(&self) -> usize

Returns the total number of slots (including deleted ones).

Source

pub fn is_active(&self, index: usize) -> bool

Returns whether the slot at the given index is active.

Source

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.

Trait Implementations§

Source§

impl Default for ConsistentNodeMap

Source§

fn default() -> Self

Returns the “default value” for a type. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.