Crate lfchring[−][src]
This crate implements a concurrent, lock-free consistent hashing ring data structure.
Features
Virtual Nodes
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.
Replication
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.
Original Purpose
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.
Node
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:
Hasher
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 Node
s 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
.
The Two Main Kinds of Operations
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., seeHashRing::iter
andIter
). - Write operations are considered those that effectively mutate the ring itself.
Common examples are the
HashRing::insert
andHashRing::remove
methods, which insert new nodes to the consistent hashing ring, or remove existing ones, respectively.
Implementation Notes
Arc
s
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, Arc
s are being used internally all over the crate anyway.
RCU-like Synchronization
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.
Garbage Collection
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.
Performance
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.
Structs
Guard | A guard that keeps the current thread pinned. |
HashRing | The consistent hashing ring data structure. |
Iter | An iterator over the |
VirtualNode | A type to represent a single virtual node of a distinct |
Enums
HashRingError | An error type returned by calls to the API exposed by this crate. |
Traits
Hasher | A trait to be implemented by any type that needs to act as a hash algorithm implementation. |
Node | A trait to be implemented by any type that needs to act as a distinct node in the consistent hashing ring. |
Functions
pin | Pins the current thread. |
Type Definitions
Result | A custom |
Vnid | A type for the internal ID of each virtual node of every distinct consistent hashing ring node. |