Consistent Hashing

#Context

const keys = Array.from({length: 100_000}, (_, i) => 'key' + i)
const where = (n) => keys.map(k => hash(k) % n)

const before = where(4), after = where(5)   // scale from 4 to 5 servers
const moved = before.filter((s, i) => s !== after[i]).length
console.log(moved / keys.length)             // ≈ 0.80  — 80% of keys moved
// consistent hashing: ≈ 0.20  — only the keys the new server takes over

Hash space / ring

The range of the hash function (say 0 to 2^32 − 1) treated as a circle, so the largest value wraps to zero.

Token

A point on the ring owned by a server. A server with one token owns the arc from the previous token up to its own.

Virtual node (vnode)

One of many tokens for the same physical server, so its ownership is many small arcs instead of one big one.

Replication factor

How many distinct servers hold each key: the owner plus the next R − 1 physical servers clockwise.

Rebalancing

Moving the keys whose owner changed after a server joins or leaves. Consistent hashing minimises how many.

Hot spot

A server that receives far more traffic than its share, from an uneven ring or from a single hot key.

#Why it matters

#The problem with mod N

#The ring

1. 1
   Hash each server identifier (host:port, or host:port:vnode-index) with the same function as the keys, and keep the resulting tokens in a sorted array.
2. 2
   To look up a key, hash it and binary-search the array for the first token ≥ the hash. If none, wrap to the first token. That token's server owns the key: O(log N).
3. 3
   To add a server, insert its tokens; the keys between each new token and the previous token move from their old owner to the new one. Nothing else changes.
4. 4
   To remove a server, delete its tokens; each of its arcs merges into the next token's owner.

import {createHash} from 'node:crypto'

const h32 = (s: string) =>
  createHash('md5').update(s).digest().readUInt32BE(0)   // any uniform 32-bit hash

export class Ring {
  private tokens: number[] = []
  private owner = new Map<number, string>()

  constructor(nodes: string[], private vnodes = 150) {
    nodes.forEach(n => this.add(n))
  }
  add(node: string) {
    for (let i = 0; i < this.vnodes; i++) {
      const t = h32(`${node}#${i}`)
      this.owner.set(t, node)
      this.tokens.push(t)
    }
    this.tokens.sort((a, b) => a - b)
  }
  remove(node: string) {
    this.tokens = this.tokens.filter(t => this.owner.get(t) !== node)
    for (const [t, n] of this.owner) if (n === node) this.owner.delete(t)
  }
  get(key: string): string {
    const x = h32(key)
    let lo = 0, hi = this.tokens.length              // first token >= x
    while (lo < hi) {
      const mid = (lo + hi) >>> 1
      if (this.tokens[mid] < x) lo = mid + 1; else hi = mid
    }
    return this.owner.get(this.tokens[lo % this.tokens.length])!
  }
}

#Virtual nodes, replication and what the ring does not fix

Replication along the ring

#Alternatives and where each is used

#Pitfalls

• mod N for a cache cluster

  Works in staging with a fixed node count, then the first autoscale event or node replacement remaps most keys, the hit ratio drops to near zero, and the database behind the cache absorbs the storm. Use a client library that implements a ring (or rendezvous) from day one; switching later requires the same storm once.

• Too few virtual nodes

  One or a handful of tokens per server produces arcs that differ by multiples, so one server is the bottleneck and a departure doubles a neighbour's load. Use on the order of 100-200 tokens per server, fewer only if you have many servers or use a scheme (like Cassandra 4's allocation) that places tokens deliberately rather than randomly.

• Replicas on the same physical node

  Walking clockwise over tokens without checking which physical server each belongs to puts two or three copies of a key on the same machine, or in the same rack. The replica walk must skip already-chosen servers and honour rack/zone awareness, or the redundancy is fictional.

• Expecting it to solve hot keys

  Even distribution of keys says nothing about distribution of requests. A celebrity's profile, a global config key or a flash-sale product still lands on one server. Layer a local cache, split the key, or use bounded-load hashing.

• Clients disagreeing about the ring

  If each client builds the ring from its own view of the node list, two clients with different views write the same key to different servers. Distribute the membership list from one source (config service, gossip with versioning, or the cluster itself), and version it so stale clients can be detected.

• A weak or non-uniform hash

  Java's String.hashCode or a CRC over short similar keys clusters tokens and keys together, defeating the randomness the scheme relies on. Use MurmurHash3, xxHash or MD5 over the full identifier; speed is rarely the constraint at this layer.

#Interview questions