Expand description
Consistent hashing for assigning hashable keys to nodes on a ring.
Each physical node is represented by virtual_node_base_count * replica_multiplier
virtual nodes. Adding or removing a physical node generally changes the owner of
only part of the key space. Use ConsistentRing::get_nodes when a key needs
several distinct physical nodes. The multiplier is a relative placement
weight, not a data replica count; get_nodes only selects owners and can
return fewer than requested. Callers must check capacity, replica policy,
and actual distribution.
All processes that share a ring must use the same node identifiers, weights,
hash algorithm and seed, and Hash representation for keys and virtual
node identifiers. Otherwise they may disagree about ownership. Do not use
DefaultHasher for a shared or
persisted ring: its algorithm and output are not guaranteed across Rust
releases. Hash output is also not guaranteed across compiler versions or
platforms. Keep those environments aligned, or use a separately specified
encoding and hashing scheme for long-lived, cross-platform placement.
ConsistentRing borrows each physical node and stores its identifier and
weight once; virtual positions refer to those entries by index. The caller
must keep node values alive while the ring uses them. ClusterManager
provides checked membership changes over a ring.
For background, see Karger et al.’s original paper and Dynamo’s discussion of virtual nodes and replica owners.
§Example
extern crate ringlet_hash;
use ringlet_hash::{ConsistentRing, RingError, RingConfig};
use xxhash_rust::xxh3::Xxh3Builder;
let config = RingConfig {
virtual_node_base_count: 50,
build_hasher: Xxh3Builder::new().with_seed(0),
};
let server_a = String::from("server-a");
let server_b = String::from("server-b");
let mut ring = ConsistentRing::try_new(config)?;
ring.add_node(&server_a, "a", 1)?;
ring.add_node(&server_b, "b", 1)?;
let owner = ring.get_node(&"customer-42").unwrap();
assert!(["server-a", "server-b"].contains(&owner.as_str()));
assert_eq!(ring.get_nodes(&"customer-42", 2).len(), 2);Structs§
- Cluster
Manager - Manages physical node membership through a
ConsistentRing. - Consistent
Ring - A consistent hashing ring of physical nodes of type
T. - Physical
Ring Node - A borrowed physical node stored once, regardless of its number of virtual positions.
- Ring
Config - Settings used to construct a
ConsistentRing. - Token
Range Migration - A proposed token interval to move when adding or removing a physical node.
- Virtual
Ring Node - A virtual node placed at a hash position on the ring.
Enums§
- Ring
Error - Error returned for an invalid ring configuration or node weight.