Consistent hashing

Deep dive

How it works

In: key (bytes), current node set · Out: owning node (or k replica nodes) · State: sorted ring of n·v (point, node) entries · Cost: lookup O(log(n·v)); add/remove moves about 1/n of keys

1. For each node, compute v points h(node_id, i) and insert (point → node) into a sorted array.
2. Lookup: h(key), binary-search for the first point ≥ hash, wrap around to index 0 at the end.
3. Replicas: keep walking clockwise, skipping nodes already chosen (and optionally same-rack nodes), until k distinct.
4. Add node: insert its points; each key whose successor point changed moves to the new node, only from its neighbours' arcs.
5. Weights: vnodes ∝ capacity.

 ring (2^64)       key k ─► h(k) ─► next point clockwise
   A1 ──── B2 ──── A2 ──── C1 ──── B1 ──── C2 ──► (wraps)
          ▲ keys in (A1, B2] go to B

Code

/// splitmix64 finalizer: good avalanche, so nearby inputs land far apart on the ring.
fn mix(mut z: u64) -> u64 {
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
    z ^ (z >> 31)
}

/// FNV-1a over bytes, then mixed. Stable across processes and Rust versions.
pub fn hash_bytes(b: &[u8]) -> u64 {
    let mut h: u64 = 0xcbf29ce484222325;
    for &x in b { h = (h ^ x as u64).wrapping_mul(0x100000001b3); }
    mix(h)
}

pub struct Ring {
    points: Vec<(u64, u32)>, // sorted by hash; (point, node id)
}

impl Ring {
    pub fn new() -> Self { Ring { points: Vec::new() } }

    pub fn add(&mut self, node: u32, vnodes: u32) {
        for i in 0..vnodes {
            let p = mix(hash_bytes(&node.to_le_bytes()) ^ mix(i as u64 + 1));
            self.points.push((p, node));
        }
        self.points.sort_unstable();      // rebuild on membership change; lookups dominate
    }

    pub fn remove(&mut self, node: u32) { self.points.retain(|&(_, n)| n != node); }

    fn first_at_or_after(&self, h: u64) -> usize {
        let i = self.points.partition_point(|&(p, _)| p < h);
        if i == self.points.len() { 0 } else { i } // wrap around
    }

    pub fn lookup(&self, key: &[u8]) -> Option<u32> {
        if self.points.is_empty() { return None; }
        Some(self.points[self.first_at_or_after(hash_bytes(key))].1)
    }

    /// First `k` distinct nodes clockwise from the key: its replica set.
    pub fn replicas(&self, key: &[u8], k: usize) -> Vec<u32> {
        let mut out: Vec<u32> = Vec::with_capacity(k);
        if self.points.is_empty() { return out; }
        let start = self.first_at_or_after(hash_bytes(key));
        for j in 0..self.points.len() {
            let n = self.points[(start + j) % self.points.len()].1;
            if !out.contains(&n) { out.push(n); if out.len() == k { break; } }
        }
        out
    }
}

/// Bounded-load lookup: skip nodes already at capacity = ceil((1+eps) * total / nodes).
pub fn lookup_bounded(ring: &Ring, key: &[u8], load: &[u64], eps: f64) -> Option<u32> {
    let nodes = load.len() as f64;
    let total: u64 = load.iter().sum::<u64>() + 1;
    let cap = ((1.0 + eps) * total as f64 / nodes).ceil() as u64;
    let start = ring.first_at_or_after(hash_bytes(key));
    (0..ring.points.len())
        .map(|j| ring.points[(start + j) % ring.points.len()].1)
        .find(|&n| load[n as usize] < cap)
}

load is indexed by node id, so ids are assumed dense (0..nodes).

Complexity and constants

• Memory: 12-16 bytes per point; 1,000 nodes × 100 vnodes = 10⁵ points ≈ 1.6 MB, which exceeds L2 on many cores, so a lookup costs a few cache misses: order of 100-200 ns. An Eytzinger layout (eytzinger-binary-search) makes it cheaper.
• Keys moved on add/remove: ≈ 1/(n+1) of all keys, from about v neighbours each.
• Imbalance: relative std. dev. of per-node load ≈ 1/√v; the most loaded of n nodes sits a few standard deviations above average.
• Bounded loads with ε = 0.25: no node above 1.25 × average; the paper bounds the expected moves per change by O(1/ε²), so very small ε gets expensive.

Efficiency

• Cost: one lookup is a binary search over 12-16 byte points; at 10⁵ points (about 1.6 MB, past L2) order of 100-200 ns, bound by cache misses. A membership change moves about 1/(n+1) of the keys, and the transfer is network and disk bound, not CPU.
• Levers:
  • Eytzinger layout of the sorted points — fewer cache misses per lookup (see eytzinger-binary-search) — rings past L2 size
  • fewer vnodes with a token allocator — balance without every node sharing ranges (Cassandra 4.0 cut num_tokens 256 → 16) — replicated stores
  • bounded loads, ε = 0.25 — no node above 1.25 × average (Mirrokni et al., SODA 2018) — hot-spot sensitive caches and brokers
  • rebuild the ring and swap it atomically — lock-free lookups — read-heavy paths
  • fixed partitions then explicit assignment — rebalance without rehashing keys — large stateful clusters
• Naive → standard → state of the art:
  • hash(key) % n · moves almost every key on a change
  • ring with v ≈ 100 vnodes · about 1/n moved, load spread about 1/√v
  • ring with bounded loads or fixed partitions · hard load cap, planned rebalance

Implementation notes

• Use a stable, well-mixed hash (fast hash functions): std's DefaultHasher output is not guaranteed stable across Rust releases, and plain FNV of consecutive ids clusters points.
• Store the ring as a sorted Vec, rebuilt on membership change and swapped atomically (Arc swap); never lock on the lookup path.
• Replica placement: skip nodes in the same rack/zone when walking clockwise.
• Precompute token ownership ranges for streaming data on rebalance: each new point's range is (predecessor, point].
• Hash the node's stable identity (name/UUID), not its IP, or a restart with a new address reshuffles.

Pitfalls

• Too few vnodes: one node gets 2-3× the average; hot shards.
• Too many vnodes with replication: every node shares ranges with every other, so any two concurrent failures lose some range's quorum and repair streams touch all nodes (why Cassandra cut 256 → 16).
• Different clients computing different rings (stale membership): keys bounce between nodes; version the ring.
• Hot keys are not fixed by any hash: replicate or split them.

Variants and alternatives

In production

Amazon Dynamo, Apache Cassandra and ScyllaDB token rings, Riak (fixed-partition ring), Akka consistent-hashing routers, memcached clients (ketama), Envoy RING_HASH load balancer, HAProxy hash-type consistent with hash-balance-factor (bounded loads), Google Cloud Pub/Sub (bounded loads).

Implementations

Sources

• David Karger et al., Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web, STOC 1997. paper
• Vahab Mirrokni, Mikkel Thorup, Morteza Zadimoghaddam, Consistent Hashing with Bounded Loads, SODA 2018. paper
• Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. paper · PDF
• Envoy documentation, Supported load balancers (ring hash). docs