Expand description
Consistent hashing algorithm implementation based on the Multi-probe consistent hashing paper.
Overview
Multi-probe consistent hashing is a variant of consistent hashing that doesn’t require virtual nodes to achieve the same load balancing properties.
Nodes are assigned randomly to positions on the ring, however the key is not assigned to the next clockwise node, but instead multiple probes (using double-hashing) are made, and attempt/position with the closest distance to some node wins – that node is considered owning the key space for the key.
This means that nodes that happen to control wide range of the key space still do not get an increased chance of being selected, as most probes for such nodes will happen to possess not the smallest distance to a key.
Main structures
HashRing
is the main structure that holds the ring state. For cases
where ring of the u64
size is not big enough, you will need to define your
own Partitioner
.
Usage
use {
mpchash::{HashRing, RingDirection::Clockwise},
rand::Rng,
};
// Define a node type.
#[derive(Hash, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
struct Node {
id: u64,
}
impl Node {
fn random() -> Self {
Self {
id: rand::thread_rng().gen(),
}
}
}
// Create a new ring.
let mut ring = HashRing::new();
// Populate the ring with some nodes.
let node1 = Node::random();
let node2 = Node::random();
ring.add(node1.clone());
ring.add(node2);
// Get the primary key space owning node for a key.
// This will return the first node when moving clockwise from the key's position.
let node = ring.primary_node(&42).unwrap();
// Remove a node from the ring.
ring.remove(&node1);
// Iterate over the ring.
for (position, node) in ring.tokens(0, Clockwise) {
println!("{}: {:?}", position, node);
}
Structs
- Consistent hash ring.
- A (half-open) range bounded inclusively below and exclusively above i.e.
[start..end)
. - A partitioner that uses a XXH3 hash function to partition data.
Enums
- Defines the direction in which the ring is traversed.
Constants
- Number of probing attempts before selecting key’s position on the ring.
- Sample seed for double hashing.
- The second seed for double hashing.
Traits
- A keyspace partitioning strategy.
- Node that can be assigned a position on the ring.
Type Aliases
- Default partitioner.
- Position on the ring.
- An ownership over a position on the ring (by the object of type
T
, normally,RingNode
).