Partitioning, Designing Data-Intensive Applications Notes

6.1Chapter Thesis

Once a dataset is too large or too hot for one machine, it has to be split. Partitioning is the decision of which key goes on which machine - a purely algorithmic problem (hashing) that becomes an operational one the moment machines are added, removed, or fail, because every partitioning scheme has to answer how much data moves when the set of machines changes.

6.2First Principles

Hash partitioning distributes load, destroys range queries

Hashing a key to choose its partition spreads keys near-uniformly across machines, avoiding hotspots from sequential access patterns. The cost is that keys which were adjacent in sort order are now scattered across arbitrary partitions - a range query ("all events between time A and B") can no longer be answered by reading one contiguous region.

Modulo hashing couples partition count to key placement

The naive scheme - hash(key) % N - assigns keys based on the current node count N. The moment N changes, almost every key's assigned partition changes too, because the modulo of nearly every hash value shifts. This forces a near-total data reshuffle for what should be a routine capacity change.

Consistent hashing decouples the two

Placing both nodes and keys on the same hash ring, and assigning each key to the next node clockwise from its hash position, means adding or removing one node only affects the keys between it and its neighbor on the ring - not the entire keyspace. This is the constraint modulo hashing violates and consistent hashing is specifically designed to satisfy.

6.3Mechanism

Each physical node is hashed to several points on the ring ("virtual nodes"), which smooths out the uneven distribution that a single hash position per node would produce. A key's owner is found by hashing the key and walking clockwise to the nearest virtual node - an O(log V) operation over a sorted array of virtual node positions.

6.4Build It Yourself

consistent-hash-ring.ts

hash(s: string): number {
  let h = 0;
  for (let i = 0; i < s.length; i++) h = (h * 31 + s.charCodeAt(i)) >>> 0;
  return h;
}

class HashRing {
  private ring: [number, string][] = [];

  constructor(private virtualNodesPerNode = 100) {}

  addNode(node: string): void {
    for (let i = 0; i < this.virtualNodesPerNode; i++) {
      this.ring.push([hash(`${node}#${i}`), node]);
    }
    this.ring.sort((a, b) => a[0] - b[0]);
  }

  // removing a node only affects the ring arc it owned -
  // every other key's owner is unchanged.
  removeNode(node: string): void {
    this.ring = this.ring.filter(([, n]) => n !== node);
  }

  ownerOf(key: string): string {
    const h = hash(key);
    const owner = this.ring.find(([pos]) => pos >= h) ?? this.ring[0];
    return owner[1];
  }
}

6.5Failure Modes

Condition	Resulting state
A single key receives disproportionate traffic (a celebrity account, a viral post)	Every request lands on one partition regardless of how well-distributed the rest of the keyspace is - hash partitioning distributes keys, not per-key load.
Too few virtual nodes per physical node	The ring assigns visibly uneven arc lengths to different nodes by chance, so some machines carry meaningfully more keys than others even though the hash function itself is uniform.
A rebalance is triggered while writes are in flight	A write addressed to a key mid-transfer between owners can be accepted by the old owner and never forwarded, or accepted by both, unless the rebalance protocol explicitly tracks in-flight ownership handoff.

6.6Tradeoffs

Scheme	Benefit	Cost	When it makes sense
Range partitioning	Efficient range queries and ordered scans	Sequential key patterns create hotspots on the newest range	Time-series or naturally ordered access patterns
Modulo hash partitioning	Simple, uniform key distribution	Node count changes reshuffle nearly the entire keyspace	Fixed, rarely-changing cluster size
Consistent hashing	Minimal data movement when nodes join or leave	More complex to implement and reason about than modulo hashing	Elastic clusters expected to scale up/down regularly

6.7Production Perspective

Production systems add a request-routing layer that caches partition ownership and refreshes it on rebalance events, plus replication (see Replication) layered on top of each partition so a single node's failure doesn't remove a shard of the keyspace entirely - partitioning and replication are near-always deployed together, not as alternatives.

Partitioning