What is consistent hashing?

Question

Accepted Answer

**Consistent hashing** is a technique for distributing data across nodes (servers) that **minimizes redistribution when nodes are added or removed** — unlike simple hashing, which remaps most keys when the node count changes. It's important for distributed caches, databases, and load distribution.

## The problem with simple hashing

```text
Simple approach: node = hash(key) % N  (N = number of nodes)
  ✗ when N CHANGES (add/remove a node), N changes → MOST keys remap to different nodes →
    massive data movement / cache invalidation (almost everything moves!)
→ adding/removing a server causes huge disruption → bad for dynamic distributed systems.
```

## How consistent hashing works

```text
Map both NODES and KEYS onto a HASH RING (a circle of hash values):
  → a key belongs to the FIRST node clockwise from it on the ring
  → adding/removing a node only affects keys in ONE segment of the ring (its neighbors) →
    only a SMALL fraction of keys move (≈ K/N, not most of them)
→ minimal redistribution when nodes change → much better for dynamic systems.
```

## Virtual nodes and uses

```text
✓ VIRTUAL NODES → each physical node maps to MANY points on the ring → EVEN distribution
  (avoids uneven load from few nodes/uneven placement) → handles heterogeneous capacity
USES:
  → distributed CACHES (e.g. memcached clusters) — add/remove cache nodes without mass
    invalidation
  → distributed DATABASES (Cassandra, DynamoDB) — partition data across nodes
  → load balancers; any system distributing data/load across a changing set of nodes
```

## Why it matters

Understanding consistent hashing is valuable senior-level knowledge because it's a **fundamental technique for distributing data in dynamic distributed systems**, used in many real systems, so it's important for distributed system design.

The problem it solves is real and important: **simple hashing** (`hash(key) % N`) causes **most keys to remap when the node count changes** (adding or removing a server moves almost all data — causing massive data movement or cache invalidation), making it terrible for dynamic distributed systems where nodes are added and removed. **Consistent hashing** solves this by mapping both nodes and keys onto a **hash ring** (with a key belonging to the first node clockwise), so that **adding or removing a node only moves a small fraction of keys** (those in one ring segment, ≈ K/N) rather than most — minimizing redistribution and disruption when the node set changes.

Understanding this — how the ring works and why it minimizes key movement — is the key insight.

Understanding **virtual nodes** (mapping each physical node to many ring points for even distribution, avoiding the uneven load that few or poorly-placed nodes cause, and handling heterogeneous capacity) reflects how consistent hashing works well in practice.

Understanding the **uses** — distributed caches (adding/removing cache nodes without mass invalidation), distributed databases (Cassandra, DynamoDB partitioning data), and load balancers — clarifies its importance, since it's used in many real, widely-used systems.

Consistent hashing is a classic, important distributed-systems technique frequently appearing in system design discussions.

Since distributing data across a dynamic set of nodes (with minimal disruption when nodes change) is a common need in distributed systems and consistent hashing solves it (where simple hashing fails badly), and since it's used in real systems (distributed caches and databases) and understanding it reflects distributed-systems knowledge, understanding consistent hashing is valuable senior-level knowledge — a fundamental technique for data distribution in dynamic distributed systems, used in many real caches and databases, solving the key-redistribution problem of simple hashing, and a classic distributed-systems concept reflecting the depth expected for senior roles designing distributed systems.