ringlet_hash/lib.rs
1//! Consistent hashing for assigning hashable keys to nodes on a ring.
2//!
3//! Each physical node is represented by `virtual_node_base_count * replica_multiplier`
4//! virtual nodes. Adding or removing a physical node generally changes the owner of
5//! only part of the key space. Use [`ConsistentRing::get_nodes`] when a key needs
6//! several distinct physical nodes. The multiplier is a relative placement
7//! weight, not a data replica count; `get_nodes` only selects owners and can
8//! return fewer than requested. Callers must check capacity, replica policy,
9//! and actual distribution.
10//!
11//! All processes that share a ring must use the same node identifiers, weights,
12//! hash algorithm and seed, and [`Hash`] representation for keys and virtual
13//! node identifiers. Otherwise they may disagree about ownership. Do not use
14//! [`DefaultHasher`](std::collections::hash_map::DefaultHasher) for a shared or
15//! persisted ring: its algorithm and output are not guaranteed across Rust
16//! releases. [`Hash`] output is also not guaranteed across compiler versions or
17//! platforms. Keep those environments aligned, or use a separately specified
18//! encoding and hashing scheme for long-lived, cross-platform placement.
19//!
20//! [`ConsistentRing`] borrows each physical node and stores its identifier and
21//! weight once; virtual positions refer to those entries by index. The caller
22//! must keep node values alive while the ring uses them. [`ClusterManager`]
23//! provides checked membership changes over a ring.
24//!
25//! For background, see [Karger et al.'s original paper](https://people.csail.mit.edu/karger/Papers/web.pdf)
26//! and [Dynamo's discussion of virtual nodes and replica owners](https://www.amazon.science/publications/dynamo-amazons-highly-available-key-value-store).
27//!
28//! # Example
29//!
30//! ```
31//! extern crate ringlet_hash;
32//! use ringlet_hash::{ConsistentRing, RingError, RingConfig};
33//! use xxhash_rust::xxh3::Xxh3Builder;
34//!
35//! let config = RingConfig {
36//! virtual_node_base_count: 50,
37//! build_hasher: Xxh3Builder::new().with_seed(0),
38//! };
39//! let server_a = String::from("server-a");
40//! let server_b = String::from("server-b");
41//! let mut ring = ConsistentRing::try_new(config)?;
42//! ring.add_node(&server_a, "a", 1)?;
43//! ring.add_node(&server_b, "b", 1)?;
44//!
45//! let owner = ring.get_node(&"customer-42").unwrap();
46//! assert!(["server-a", "server-b"].contains(&owner.as_str()));
47//! assert_eq!(ring.get_nodes(&"customer-42", 2).len(), 2);
48//! # Ok::<(), RingError>(())
49//! ```
50
51use std::{
52 collections::HashSet,
53 hash::{BuildHasher, Hash},
54};
55
56mod cluster_manager;
57
58pub use cluster_manager::ClusterManager;
59
60/// A virtual node placed at a hash position on the ring.
61///
62/// Its index refers to one physical node owned by [`ConsistentRing`].
63#[derive(Debug, Clone)]
64pub struct VirtualRingNode {
65 hash: u64,
66 physical_node_index: usize,
67}
68
69/// A borrowed physical node stored once, regardless of its number of virtual positions.
70#[derive(Debug, Clone)]
71pub struct PhysicalRingNode<'a, T> {
72 identifier: String,
73 value: &'a T,
74 weight: usize,
75}
76
77impl<'a, T> PhysicalRingNode<'a, T> {
78 /// Returns the unique identifier used to place this node on the ring.
79 pub fn identifier(&self) -> &str {
80 &self.identifier
81 }
82
83 /// Returns the node value.
84 pub fn value(&self) -> &T {
85 self.value
86 }
87
88 /// Returns the multiplier used to determine its virtual node count.
89 pub fn weight(&self) -> usize {
90 self.weight
91 }
92}
93
94/// A proposed token interval to move when adding or removing a physical node.
95///
96/// Hash positions wrap around at [`u64::MAX`], so `start_hash` can be greater
97/// than `end_hash`.
98#[derive(Debug, Clone)]
99pub struct TokenRangeMigration<T> {
100 /// Hash at the start of the interval.
101 pub start_hash: u64,
102 /// Hash at the end of the interval.
103 pub end_hash: u64,
104 /// Owner of the interval before the membership change.
105 pub from_node: T,
106 /// Owner of the interval after the membership change.
107 pub to_node: T,
108}
109
110/// Settings used to construct a [`ConsistentRing`].
111#[derive(Clone)]
112pub struct RingConfig<BH: BuildHasher> {
113 /// Number of virtual nodes created for a physical node with weight 1.
114 /// Must be greater than zero. `50` is an illustrative starting point;
115 /// measure placement with representative keys and tune for your cluster.
116 pub virtual_node_base_count: usize,
117 /// Hash builder used for both keys and virtual node identifiers.
118 /// Use a named algorithm with a fixed seed for shared or persisted rings;
119 /// `DefaultHasher` has no stable output guarantee across Rust releases.
120 pub build_hasher: BH,
121}
122
123/// A consistent hashing ring of physical nodes of type `T`.
124///
125/// The ring borrows each physical value and stores its identifier and weight
126/// once. Virtual positions refer to it by index. Values must outlive the ring.
127/// [`len`](Self::len) counts virtual nodes, not physical nodes. Ordinary
128/// membership changes and lookups accept values that do not implement [`Clone`];
129/// migration previews require it because they return owned node values.
130#[derive(Clone)]
131pub struct ConsistentRing<'a, T, BH: BuildHasher> {
132 nodes: Vec<VirtualRingNode>,
133 physical_nodes: Vec<PhysicalRingNode<'a, T>>,
134 virtual_node_base_count: usize,
135 build_hasher: BH,
136}
137
138/// Error returned for an invalid ring configuration or node weight.
139#[derive(Debug, Clone)]
140pub enum RingError {
141 /// The configured base virtual node count is zero.
142 EmptyRing(&'static str),
143 /// A node was added or previewed with a zero replica multiplier.
144 ZeroWeight(&'static str),
145 /// A physical node with this identifier is already registered.
146 NodeAlreadyExists(String),
147 /// No physical node has this identifier.
148 NodeNotFound(String),
149}
150
151impl<'a, T, BH: BuildHasher> ConsistentRing<'a, T, BH> {
152 /// Creates an empty ring with the supplied configuration.
153 ///
154 /// Returns [`RingError::EmptyRing`] if `virtual_node_base_count` is zero.
155 pub fn try_new(config: RingConfig<BH>) -> Result<Self, RingError> {
156 if config.virtual_node_base_count == 0 {
157 return Err(RingError::EmptyRing("Virtual nodes count must be > 0"));
158 }
159 Ok(Self {
160 nodes: Vec::new(),
161 physical_nodes: Vec::new(),
162 virtual_node_base_count: config.virtual_node_base_count,
163 build_hasher: config.build_hasher,
164 })
165 }
166
167 fn hash_key<K: Hash>(&self, key: &K) -> u64 {
168 self.build_hasher.hash_one(key)
169 }
170
171 fn format_virtual_node_key(&self, identifier: &str, i: usize) -> String {
172 format!("{identifier}#virtual-node-{i}")
173 }
174
175 /// Adds a physical node and returns its identifier.
176 ///
177 /// The node gets `virtual_node_base_count * replica_multiplier` positions.
178 /// The multiplier is a relative placement weight, not a replica count;
179 /// the caller must decide whether it matches the node's actual capacity.
180 /// The product is not checked for overflow or capped for memory use.
181 /// Returns [`RingError::NodeAlreadyExists`] for a duplicate identifier and
182 /// [`RingError::ZeroWeight`] for a zero multiplier.
183 pub fn add_node(
184 &mut self,
185 node: &'a T,
186 identifier: &str,
187 replica_multiplier: usize,
188 ) -> Result<String, RingError> {
189 if replica_multiplier == 0 {
190 return Err(RingError::ZeroWeight("Replica multiplier must be > 0"));
191 }
192 if self.contains_identifier(identifier) {
193 return Err(RingError::NodeAlreadyExists(identifier.to_owned()));
194 }
195
196 let virtual_nodes_count = self.virtual_node_base_count * replica_multiplier;
197 let physical_node_index = self.physical_nodes.len();
198
199 for i in 0..virtual_nodes_count {
200 let virtual_node_key = self.format_virtual_node_key(identifier, i);
201 let hash = self.hash_key(&virtual_node_key);
202
203 self.nodes.push(VirtualRingNode {
204 hash,
205 physical_node_index,
206 });
207 }
208
209 self.nodes.sort_unstable_by_key(|ring_node| ring_node.hash);
210 self.physical_nodes.push(PhysicalRingNode {
211 identifier: identifier.to_owned(),
212 value: node,
213 weight: replica_multiplier,
214 });
215
216 Ok(identifier.to_string())
217 }
218
219 /// Removes a physical node and all its virtual positions; an unknown identifier has no effect.
220 pub fn remove_node(&mut self, identifier: &str) {
221 if let Some(index) = self.physical_node_index(identifier) {
222 self.nodes.retain(|node| node.physical_node_index != index);
223 for node in &mut self.nodes {
224 if node.physical_node_index > index {
225 node.physical_node_index -= 1;
226 }
227 }
228 self.physical_nodes.remove(index);
229 }
230 }
231
232 fn physical_node_index(&self, identifier: &str) -> Option<usize> {
233 self.physical_nodes
234 .iter()
235 .position(|node| node.identifier == identifier)
236 }
237
238 /// Returns whether a physical node with this identifier is registered.
239 pub fn contains_identifier(&self, identifier: &str) -> bool {
240 self.physical_node_index(identifier).is_some()
241 }
242
243 /// Returns the physical nodes and their weights in insertion order.
244 pub fn physical_nodes(&self) -> &[PhysicalRingNode<'a, T>] {
245 &self.physical_nodes
246 }
247
248 fn get_node_by_hash(&self, hash: u64) -> Option<&'a T> {
249 if self.nodes.is_empty() {
250 return None;
251 }
252
253 let start_index = self.find_start_index(hash);
254
255 Some(self.physical_nodes[self.nodes[start_index].physical_node_index].value)
256 }
257
258 /// Returns the index of the first virtual node at or after `target_hash`.
259 ///
260 /// The search wraps to index 0 beyond the last token. An empty ring also
261 /// returns 0; check [`is_empty`](Self::is_empty) before indexing.
262 pub fn find_start_index(&self, target_hash: u64) -> usize {
263 match self
264 .nodes
265 .binary_search_by(|ring_node| ring_node.hash.cmp(&target_hash))
266 {
267 Ok(exact_match) => exact_match,
268 Err(some_position) => {
269 if some_position == self.nodes.len() {
270 0
271 } else {
272 some_position
273 }
274 }
275 }
276 }
277
278 /// Returns up to `count` distinct physical nodes for a key, in ring order.
279 ///
280 /// The first result is the primary owner returned by [`get_node`](Self::get_node).
281 /// The result is empty for an empty ring or a zero count, and may contain
282 /// fewer than `count` nodes when the ring has fewer distinct identifiers.
283 /// The caller must check the returned length and store any desired copies.
284 pub fn get_nodes<K: Hash>(&self, key: &K, count: usize) -> Vec<&'a T> {
285 if self.is_empty() || count == 0 {
286 return Vec::new();
287 }
288
289 let target_hash = self.hash_key(key);
290
291 let start_index = self.find_start_index(target_hash);
292
293 let mut result = Vec::new();
294 let mut seen_indices = HashSet::new();
295
296 for i in 0..self.len() {
297 let current_index = (start_index + i) % self.len();
298 let ring_node = &self.nodes[current_index];
299
300 if seen_indices.insert(ring_node.physical_node_index) {
301 result.push(self.physical_nodes[ring_node.physical_node_index].value);
302 if result.len() == count {
303 break;
304 }
305 }
306 }
307
308 result
309 }
310
311 /// Previews token ranges associated with adding a node without changing this ring.
312 ///
313 /// Each returned entry identifies an existing owner at a new virtual token
314 /// and the proposed destination. An empty ring has no source to migrate
315 /// from, so it returns an empty list. A zero multiplier returns
316 /// [`RingError::ZeroWeight`].
317 pub fn calculate_migration_on_add(
318 &self,
319 new_node: &'a T,
320 new_identifier: &str,
321 new_replica_multiplier: usize,
322 ) -> Result<Vec<TokenRangeMigration<T>>, RingError>
323 where
324 T: Clone,
325 BH: Clone,
326 {
327 let mut future_ring = self.clone();
328
329 future_ring.add_node(new_node, new_identifier, new_replica_multiplier)?;
330 let new_index = future_ring.physical_nodes.len() - 1;
331
332 let mut migrations = Vec::new();
333 for i in 0..future_ring.len() {
334 let current_virtual_node = &future_ring.nodes[i];
335
336 if current_virtual_node.physical_node_index == new_index {
337 let old_node = self.get_node_by_hash(current_virtual_node.hash);
338
339 if let Some(from_node) = old_node {
340 let previous_virtual_node = if i == 0 { future_ring.len() - 1 } else { i - 1 };
341
342 let start_hash = future_ring.nodes[previous_virtual_node].hash;
343 let end_hash = current_virtual_node.hash;
344
345 migrations.push(TokenRangeMigration {
346 start_hash,
347 end_hash,
348 from_node: from_node.clone(),
349 to_node: new_node.clone(),
350 });
351 }
352 }
353 }
354
355 Ok(migrations)
356 }
357
358 /// Previews token ranges that would leave `identifier` on removal.
359 ///
360 /// Each range is `(start_hash, end_hash]` on the hash ring, wrapping at
361 /// [`u64::MAX`]. The ring is unchanged. Returns an empty list when the
362 /// identifier is absent or when removal would leave no destination node.
363 pub fn calculate_migration_on_remove(&self, identifier: &str) -> Vec<TokenRangeMigration<T>>
364 where
365 T: Clone,
366 BH: Clone,
367 {
368 if self.nodes.is_empty() {
369 return Vec::new();
370 }
371
372 let mut future_ring = self.clone();
373 future_ring.remove_node(identifier);
374 if future_ring.is_empty() {
375 return Vec::new();
376 }
377
378 let Some(removed_index) = self.physical_node_index(identifier) else {
379 return Vec::new();
380 };
381
382 self.nodes
383 .iter()
384 .enumerate()
385 .filter(|(_, node)| node.physical_node_index == removed_index)
386 .map(|(index, node)| {
387 let previous_index = if index == 0 {
388 self.nodes.len() - 1
389 } else {
390 index - 1
391 };
392
393 TokenRangeMigration {
394 start_hash: self.nodes[previous_index].hash,
395 end_hash: node.hash,
396 from_node: self.physical_nodes[removed_index].value.clone(),
397 to_node: future_ring
398 .get_node_by_hash(node.hash)
399 .expect("a destination exists after removal")
400 .clone(),
401 }
402 })
403 .collect()
404 }
405
406 /// Returns the primary owner of `key`, or `None` for an empty ring.
407 pub fn get_node<K: Hash>(&self, key: &K) -> Option<&'a T> {
408 self.get_nodes(key, 1).into_iter().next()
409 }
410
411 /// Returns the number of virtual nodes in the ring.
412 pub fn len(&self) -> usize {
413 self.nodes.len()
414 }
415
416 /// Returns whether the ring has no virtual nodes.
417 pub fn is_empty(&self) -> bool {
418 self.nodes.is_empty()
419 }
420}