Consistent Hashing

Consistent hashing remaps only 1/n of the keys when nodes are added or removed, minimizing redistribution; it is used in distributed caching and sharding.

Purpose

To minimize data movement when nodes join or leave, a core technique for distributed storage and caching.

Mechanism

Map both nodes and keys onto a 0-2^32 hash ring; each key belongs to the first node clockwise from it. Adding or removing a node affects only the keys in the adjacent arc. Virtual nodes (multiple hash points per node) improve balance. Load spreads roughly evenly.

Use cases

Distributed caching (Memcached)
CDN node sharding
Database sharding (Cassandra)
Load balancing

Examples

Input

Node C joins

Output

Only keys in C's adjacent arc migrate

Minimal migration

Common errors

Too few virtual nodes causes uneven load: Use 150+ virtual nodes per node

Related terms

A hash table maps keys to a bucket array via a hash function, providing average O(1) lookup/insert/delete; it is among the most used data structures.

A Bloom filter approximates set membership with k hash functions and a bit array, offering space efficiency at the cost of a false-positive rate.

A Merkle tree has data hashes at its leaves and hashes of children at internal nodes, enabling efficient integrity verification of large data; it is used in Git and blockchains.

References