Consistent Hashing

Consistent hashing minimizes key movement when nodes join/leave.

Concepts

Keys and nodes are mapped onto a ring via a hash function.
Requests go to the first node clockwise from the key’s position.
Virtual nodes (many points per physical node) smooth distribution.

Uses

Distributed caches (Memcached), database sharding, sticky load balancing.

Details

Virtual nodes improve balance and reduce hotspots.
Replicate to k successors for fault tolerance.

Code: simple ring (TypeScript)

// language-typescript
import { createHash } from 'crypto'

type Node = { id: string }
const ring: { hash: number; node: Node }[] = []

function h(s: string) {
  return parseInt(createHash('sha1').update(s).digest('hex').slice(0, 8), 16)
}

export function addNode(node: Node, replicas = 100) {
  for (let i = 0; i < replicas; i++) ring.push({ hash: h(node.id + ':' + i), node })
  ring.sort((a, b) => a.hash - b.hash)
}

export function getNode(key: string): Node {
  const x = h(key)
  const i = ring.findIndex((p) => p.hash >= x)
  return (ring[i] || ring[0]).node
}

Rebalancing

When adding/removing a node, only a fraction of keys move to new owners; far less than modulo‑based hashing.

Analogy

Imagine a circular bookshelf with labels (hashes). Adding a new librarian inserts new labels; only nearby books move to the new section.

FAQ

Do I still need replication? Yes—consistent hashing doesn’t duplicate data by itself.
How many virtual nodes? Start with 100–200 per physical node; tune based on variance.

*Consistent Hashing