How consistent hashing works

Distribute keys across a changing set of servers while moving as few keys as possible.

The problem it fixes

• Naive hash(key) % N remaps almost every key when N changes (a server added or removed), so caches cold-start and databases reshuffle.
• Consistent hashing changes only about k/N keys when the server pool changes, preserving the rest.

The ring

            · S1 ·
       k8 ·         · k1
     S3                 S2
       k6 ·         · k3
            · k4 ·
  key → first server clockwise; add/remove a node ⇒ only ~k/N keys move

• Hash both servers and keys onto one circular keyspace (the ring). A key belongs to the first server found walking clockwise from the key’s position.
• Add or remove a server and only the keys between it and its predecessor move; every other key stays put.

Virtual nodes (balance)

• With one point per server, load is lumpy and a removed server dumps its whole range on one neighbor.
• Give each physical server many virtual nodes (points) on the ring; load evens out, and a failure spreads across many neighbors instead of one.

Replication

• To replicate, walk clockwise past the first server and place copies on the next R − 1 distinct physical servers (its preference list), skipping virtual nodes of the same machine.

Trade-offs and when to use it

• Buys minimal reshuffling and smooth scaling; costs a hash ring to maintain and slightly harder range queries.
• Use it for caches (Memcached/CDN), sharded stores, and any pool that grows, shrinks, or loses nodes often.