6 releases (stable)
1.2.3 | Jan 18, 2024 |
---|---|
1.2.1 | Jul 6, 2023 |
1.2.0 | Jun 22, 2023 |
1.1.0 | Jun 20, 2023 |
0.1.0 | Jun 19, 2023 |
#309 in Algorithms
39KB
535 lines
mpchash
Consistent hashing algorithm implementation based on the Multi-probe consistent hashing paper.
Features
- Multi-probe consistent hashing.
- Balanced distribution of keys, with peak-to-average load ratio of
1 + ε
with just1 + 1/ε
lookups per key. - No virtual nodes, so no extra space required --
O(n)
space complexity. The high space requirement is the main downside of the original Karger's ring. - All conventional consistent hashing methods, like moving through the ring (in both directions), adding and removing nodes, finding the closest node to a key, finding a key range owned by a node etc.
Usage
The implementation supports all the features of the conventional consistent hashing algorithm, so it can be used as a drop-in replacement for any existing implementation.
Defining a node
Anything that implements the following traits can be placed on a ring as a node:
Hash
+ Clone
+ Debug
+ Eq
+ PartialEq
+ Ord
+ PartialOrd
Here is an example of using custom type as a node:
#[derive(Hash, Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct Node {
id: u64,
}
impl Node {
fn new(id: u64) -> Self {
Self { id }
}
}
Creating a ring
To create a ring and populate it with nodes:
fn main() {
use mpchash::HashRing;
let mut ring = HashRing::new();
ring.add(Node::new(1));
ring.add(Node::new(2));
ring.add(Node::new(3));
}
Finding a node that owns a key
Anything that implements Hash
can be used as a key:
fn main() {
// ... ring initialization code
// Anything that implements `Hash` can be used as a key.
let key = "hello world";
// Node that owns the key.
//
// It is the first node when moving in CW direction from the
// position where key is hashed to.
let owning_node = ring.primary_node(&key);
// If we are interested in both ring position and owning node,
// we can get them with `primary_token`.
//
// A token is just a tuple of `(position, node)`.
let token = ring.primary_token(&key);
}
In replicated settings, we want to have several replicas of a key, so need multiple destination/owning nodes.
In order to obtain such a list of replica nodes, we can traverse the ring from a given position:
fn main() {
use mpchash::HashRing;
use mpchash::RingDirection::Clockwise;
let mut ring = HashRing::new();
ring.add(Node::new(1));
ring.add(Node::new(1));
let key = "hello world";
let tokens = ring
.tokens(ring.position(&key), Clockwise)
.collect::<Vec<_>>();
for (pos, node) in ring.tokens(&key, Clockwise) {
println!("node {} is at position {}", node, pos);
}
}
Normally, you would collect/traverse replication factor
number of tokens, so that you have replication factor
of
destination nodes.
Finding a key range owned by a node
Sometimes it is necessary to find a range of keys owned by a node. For example, when some node's data needs to be
rebalanced to another node. In this case, we are moving from the node's position in the ring in CCW direction, until we
find a previous node. As we are operating on a ring we need to account for the wrap-around. All this is handled by
the key_range
method:
fn main() {
use mpchash::RingPosition;
use mpchash::HashRing;
let mut ring = HashRing::new();
// Define nodes.
let node1 = "SomeNode1";
let node2 = "SomeNode2";
// Add nodes to the ring.
ring.add(node1);
ring.add(node2);
// Get the range owned by node1.
let pos = ring.position(&node1);
let range = ring.key_range(pos).unwrap();
// The range starts at the position to the left of node1,
// till (and not including) its own position.
assert_eq!(range.start, ring.position(&node2));
assert_eq!(range.end, ring.position(&node1));
}
License
MIT
Dependencies
~565KB