Consistent Hashing (Rust)
Topics: consistent hashing, virtual nodes, hash ring
Problem
Distribute keys across a changing set of nodes (cache shards, storage replicas) so that adding or
removing a node moves only ~1/N of the keys, not the whole keyspace. The trick is a hash ring
with virtual nodes.
pub struct Ring { /* … */ }
impl Ring {
pub fn new(replicas: usize) -> Self;
pub fn add(&mut self, node: &str);
pub fn remove(&mut self, node: &str);
pub fn get(&self, key: &str) -> Option<String>;
}
add places replicas virtual points for the node around the ring (hash(node#i)). Idempotent.get hashes the key and returns the node of the first virtual node clockwise (wrapping past
the end); None if the ring is empty.remove drops a node and all its virtual points.
Key concepts
- The ring: keep
ring: Vec<(u64, String)> sorted by hash; get is a partition_point for the
first hash ≥ the key's, wrapping to index 0 with % len.
- Virtual nodes: each real node gets many points so its share of the ring is even — more
replicas → smoother distribution.
- Minimal disruption: because a key only depends on the next point clockwise, adding a node
steals keys only from the arcs it lands on; everything else is untouched.
The struct, new, and the hash helper are provided; you implement add, remove, and get.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.