Design Consistent Hashing

Consistent hashing distributes requests/data efficiently across servers for horizontal scaling, minimizing redistribution when servers are added/removed.

1 of 5: The rehashing problem #

Traditional approach: serverIndex = hash(key) % N where N = server count.

When N changes (server added/removed), most keys get different server indexes: not just the keys from the affected server. This causes a storm of cache misses.

Example: Server 1 goes offline (N=4 → N=3).

Most keys are redistributed to different servers even if they weren't stored on server 1.

2 of 5: Consistent hashing basics #

Only k/n keys need remapping on average (k = keys, n = slots), vs nearly all keys with traditional hashing.

Hash space and hash ring #

Using SHA-1 (hash space 0 to 2^160 − 1):

Connect both ends → hash ring:

Hash servers and keys #

Map servers onto the ring by hashing IP or name:

Hash cache keys onto the same ring (no modular operation):

Server lookup #

To find which server stores a key: go clockwise from the key's position until a server is found.

3 of 5: Add and remove servers #

Add a server: only keys between the new server and its predecessor (anticlockwise) need redistribution.

After adding server 4: only key0 redistributed (moves from server 0 to server 4). k1, k2, k3 stay.

Remove a server:

When server 1 removed: only key1 remapped (to server 2). Others unaffected.

4 of 5. Two issues and the fix: virtual nodes #

Issue 1: uneven partition sizes: partitions between adjacent servers can vary greatly. If s1 removed, s2's partition becomes twice the size of s0 and s3.

Issue 2: non-uniform key distribution: keys may cluster on specific servers, leaving others empty.

Virtual nodes #

Each physical server is represented by multiple virtual nodes on the ring.

1. Server 0 → s0_0, s0_1, s0_2; Server 1 → s1_0, s1_1, s1_2
2. Each server responsible for multiple partitions
3. Lookup: go clockwise from key to first virtual node → maps to physical server

Tradeoff: more virtual nodes = more balanced distribution, smaller standard deviation: but more memory to store virtual node data.

• 100–200 virtual nodes → standard deviation 5–10% of mean
• More virtual nodes → smaller standard deviation

5 of 5: Find affected keys and wrap up #

Adding server 4: affected range starts from s4, goes anticlockwise to next server (s3). Keys between s3 and s4 redistributed to s4.

Removing server 1: affected range starts from s1, goes anticlockwise to next server (s0). Keys between s0 and s1 redistributed to s2.

Benefits #

1. Minimized keys redistributed when servers added/removed
2. Easy horizontal scaling with even data distribution
3. Mitigates hotspot key problem (e.g. celebrity shard overload)

Real-world usage #

1. Partitioning in Amazon's Dynamo database
2. Data partitioning in Apache Cassandra
3. Discord chat application
4. Akamai CDN
5. Maglev network load balancer