Consistent hashing in HLD - System Design Guide

Problem Statement

When a distributed system adds or removes servers, a naive hashing method causes most keys to remap to different servers. This leads to massive cache misses or data reshuffling, causing high latency and instability.

Solution

Consistent hashing arranges servers and keys on a circular hash ring. Each key is assigned to the next server clockwise on the ring. When servers join or leave, only a small portion of keys need to move, minimizing disruption and maintaining balance.

Architecture

┌─────────────┐
│   Hash Ring  │
│             │
│  ● Server A │
│       ↑     │
│  ● Server B │
│       ↑     │
│  ● Server C │
│             │
│  ● Key 1 → Server B
│  ● Key 2 → Server C
│  ● Key 3 → Server A
└─────────────┘

This diagram shows servers and keys placed on a circular hash ring. Each key maps to the next server clockwise, illustrating how consistent hashing distributes keys.

Trade-offs

✓ Pros

→

Minimizes key remapping when servers change, reducing cache misses and data movement.

→

Balances load evenly across servers by spreading keys uniformly on the ring.

→

Scales smoothly as servers are added or removed without full system rehashing.

✗ Cons

→

Requires careful implementation of virtual nodes to avoid uneven load distribution.

→

Adds complexity compared to simple modulo hashing.

→

Does not handle heterogeneous server capacities without extra logic.

Use when you have a distributed cache or storage system with frequent server changes and need to minimize data reshuffling, typically at scales above hundreds of servers.

Avoid when the system has very few servers (less than 10) or when server membership rarely changes, as the added complexity is unnecessary.

Real World Examples

Amazon

Amazon DynamoDB uses consistent hashing to distribute data partitions across nodes, enabling smooth scaling and fault tolerance.

Netflix

Netflix uses consistent hashing in its caching layer to ensure user sessions consistently route to the same cache server, reducing re-authentication overhead.

LinkedIn

LinkedIn applies consistent hashing in its distributed key-value stores to handle node failures and additions with minimal data movement.

Alternatives

Modulo Hashing

Assigns keys by key hash modulo number of servers, causing massive remapping when server count changes.

Use when: Choose when server count is fixed and rarely changes, and simplicity is preferred over flexibility.

Rendezvous (Highest Random Weight) Hashing

Assigns keys to the server with the highest hash weight per key, avoiding a ring structure.

Use when: Choose when you want minimal remapping and simpler load balancing without virtual nodes.

Summary

Consistent hashing reduces data reshuffling when servers join or leave a distributed system.

It maps keys and servers on a hash ring, assigning keys to the next server clockwise.

This approach improves scalability and fault tolerance in large distributed caches and storage.