Skip to main content

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}