This crate implements a concurrent, lock-free consistent hashing ring data structure.
This section documents the features of the data structure implementation.
Information about the supported crate features can be found throughout this documentation
page.
The crate includes support for a configurable number of virtual nodes per ring node (i.e., each node can be mapped and placed multiple times on the ring, and the number of these times is configurable) to allow for improved efficiency in load balancing scenarios.
The number of virtual nodes per ring node is configurable only at the time of the creation of the data structure.
Moreover, the crate includes support for keeping track of key replication. This means that, provided with a replication factor of the caller's choice, looking up keys in the consistent hashing ring data structure reports all the distinct ring nodes on which replicas of the key at hand are assigned. Note that consecutive virtual nodes on a consistent hashing may belong to the same distinct ring node; this crate makes sure that keys are assigned to a number of distinct ring nodes equal to the (configurable) replication factor (as long as they are available), by skipping some virtual nodes if required.
The replication factor is configurable only at the time of the creation of the data structure.
The primary purpose of this crate has been to be work correctly in multi-threaded contexts, i.e., in cases where multiple threads have access to the consistent hashing ring data structure and operate on it at the same time. More specifically, it has been designed and implemented mainly for use cases where a large number of reader threads may need to access it, whereas write operations are sparse (if you are unsure whether you know what read and write operations may refer to, do not worry, please read on). Nevertheless, the data structure can be used in single-threaded environments equally well.
The ring data structure is represented by the exported [HashRing<N, H>] type, which is
generic over the [Node] and the [Hasher].
Virtual nodes are represented by the exported [VirtualNode<N>] type.
Any type can be used as a node of the consistent hashing ring, as long as it implements the
[Node] trait.
The implementation of this trait requires a method ([Node::hashring_node_id]) which allows to
uniquely represent the type as a byte slice.
Implementing the [Node] trait can be as trivial as:
struct ExampleNode {
various: u64,
fields: Vec<i32>,
// . . .
unique_name: String,
}
impl Node for ExampleNode {
fn hashring_node_id(&self) -> Cow<'_, [u8]> {
Cow::Borrowed(&self.unique_name.as_bytes())
}
}or:
struct StrNode(str);
impl Node for StrNode {
fn hashring_node_id(&self) -> Cow<'_, [u8]> {
Cow::Borrowed(self.0.as_bytes())
}
}Note that [Node] can be unsized and that the crate already provides implementations for the
following types:
StringstrVec<u8>&[u8][u8]
For a Node to be inserted in (or removed from) the consistent hashing ring, it needs to be
hashed one or more times (depending on the configured number of virtual nodes per Node).
The produced virtual nodes are then appropriately "placed" on the ring based on their hash
digests.
Multiple hash algorithms can be used.
The crate includes an implementation of [HashRing<N, H>] that employs standard library's
DefaultHasher (constructed via [HashRing::new] or
[HashRing::with_nodes]).
However, you may also bring your own hash algorithm implementation by implementing the
[Hasher] trait.
This trait defines the [Hasher::digest] method which, provided an input byte slice, produces
a hash digest as an owned Vec<u8>, to be used for placing the Nodes on the consistent
hashing ring in the correct order.
Not relying on standard library's machinery for hashing is a design choice that allows using
[HashRing<N, H>] with hash functions that produce digests longer than u64.
By enabling the blake3-hash crate feature, a [Hasher] that employs the BLAKE3
cryptographic hash function as implemented in the blake3 crate is made available.
For more information, refer to the documentation of the [Blake3Hasher] type.
A [Hasher] implementation based on the BLAKE2b cryptographic hash function and the
blake2b_simd crate is available by enabling the blake2b-hash crate feature.
For more information, refer to the documentation of the [Blake2bHasher] type.
All supported operations on the ring fall into two main categories: "read-like" and "write-like".
- Read operations require access to the information stored in the ring, but they do not
mutate the ring itself.
The most common example of such an operation is looking up where a key should be assigned to
according to the consistent hashing algorithm (e.g., see [
HashRing::nodes_for_key]). Another example is to loop through all the virtual nodes that are contained in the consistent hashing ring via an iterator (e.g., see [HashRing::iter] and [Iter]). - Write operations are considered those that effectively mutate the ring itself.
Common examples are the [
HashRing::insert] and [HashRing::remove] methods, which insert new nodes to the consistent hashing ring, or remove existing ones, respectively.
What follows is a basic, single-threaded example to showcase its use:
use std::sync::Arc;
use hex_literal::hex;
use lfchring::{HashRing, Node, VirtualNode, Vnid};
const VIRTUAL_NODES_PER_NODE: Vnid = 2;
const REPLICATION_FACTOR: u8 = 3;
// Create an empty ring (see the docs for further options on constructing a ring).
let ring = HashRing::new(VIRTUAL_NODES_PER_NODE, REPLICATION_FACTOR).unwrap();
// Insert three new Nodes.
let nodes: Vec<Arc<str>> = vec![Arc::from("Node1"), Arc::from("Node2"), Arc::from("Node3")];
ring.insert(&nodes).expect("hash collision when inserting 3 new Nodes");
assert_eq!(ring.len_nodes(), 3);
assert_eq!(ring.len_virtual_nodes(), 3 * VIRTUAL_NODES_PER_NODE as usize);
// Look up a key in the ring.
let key = hex!("232a8a941ee901c1");
let virtual_node_clone = ring.virtual_node_for_key(&key).unwrap();
// The Nodes that should own a replica for the particular key can also be found via:
let replica_owning_nodes = ring.nodes_for_key(&key).unwrap();
assert_eq!(replica_owning_nodes, virtual_node_clone.replica_owners());
// In this example, since the ring is populated with 3 Nodes and the replication factor is also
// equal to 3, all Nodes should be assigned with a replica of the key.
// However, the following assertion would fail, because of the order in which the replica
// owning Nodes are reported: they are reported according to the order in which their virtual
// nodes have been placed on the ring, rather than the order of the Nodes were inserted.
assert_ne!(nodes, replica_owning_nodes); // `ne` due to the order in which Nodes are reported!Mind that in multi-threaded contexts, users of [HashRing<N, H>] should explicitly wrap it in
an Arc to share it among the threads.
Single-threaded contexts may opt out of this to avoid the overhead of atomic reference
counting; however, Arcs are being used internally all over the crate anyway.
The soundness of the implementation of the crate is undergirded by a
Read-Copy-Update-like technique for synchronizing concurrent accesses to the consistent
hashing ring data structure by multiple threads.
This means that the implementation of the data structure does not rely on locks, but on
atomically reading a pointer internal to [HashRing<N, H>], copying the data, updating the
local copy and then atomically storing the new address to the pointer.
The primitives upon which the implementation is based belong to the crossbeam_epoch crate.
An alternative to this would be to use a Mutex or a RwLock, but this is
not how this crate has been implemented.
Concurrent read and write operations on a [HashRing<N, H>] using a RCU-like technique
introduce a major issue:
when a mutation occurs, the underlying data structure pointed to internally by the
[HashRing<N, H>] is no longer needed, and is therefore dropped and immediately freed.
However, a number of concurrent reader threads may still require access to it.
Garbage-collected languages, like Java and Go, trivially solve this issue by relying on their
runtime's garbage collector to clean it up only when no threads can access it.
Rust's lightweight runtime does not include a garbage collector; it rather relies on its unique
RAII-based system.
To address this issue, this crate is based on the crossbeam_epoch crate, which enables
epoch-based memory reclamation.
This is also where the [Guard] type and the [pin] function are re-exported from, for ease
of use.
It is highly recommended for anyone that considers using this crate to go through the
documentation of the crossbeam_epoch crate as well.
The crate has not been properly benchmarked and evaluated yet.
Informally, it certainly looks and feels fast, especially in the aforementioned cases of multiple concurrent reader threads and rare write operations.
$ RUST_LOG=debug cargo t --all-features -- --nocapture$ cargo doc --all-features --no-depsDistributed under the terms of the Apache License, Version 2.0.
For further details consult the included LICENSE file or http://www.apache.org/licenses/LICENSE-2.0.