books / ddia / ch-06SHEET 6 / 11 · REV ASIGN IN
MODULE 6 · DESIGNING DATA-INTENSIVE APPLICATIONS CH 6

Shard It

Cut the keyspace four ways, then move a slice to a new node without dropping a single request.

The idea

Replication gave every node a copy of everything. That helps with failures and reads, but not with size or write load, because each node still does all the work. The next move is to cut: split the keyspace into partitions and give each node only some of them. Ten nodes can then hold ten times the data and take ten times the writes.

There are two ways to cut. Range partitioning keeps keys sorted, so a scan over last Tuesday hits one node, but everyone writing today's timestamps hammers the same partition. Hash partitioning scatters neighbours evenly, which fixes hot spots but destroys range scans. Neither is correct in the abstract; the workload decides, and you can see which bet you lost by reading per-node counters.

Hashing does not save you from a celebrity key. A hash sends one key to one place, so if a single key takes 40 percent of the writes, one node takes 40 percent of the writes. The fix lives in the application: split the hot key into sixteen sub-keys, spread writes across them, and pay for it by reading all sixteen back. Write relief bought with read fan-out.

Growth is the other hard part. If you compute the node as hash of key modulo the node count, adding one machine reshuffles most of your data. The standard fix is unclever and effective: create many more partitions than nodes up front and move whole partitions when the cluster changes. Then a router that owns the partition map can flip an entry atomically while traffic keeps flowing, which is the whole game.

The bench — 4 exercises

EX 01

Sixteen Slots, Four Nodes

Split the keyspace into 16 fixed logical partitions across 4 local node processes and build the router that owns the map. This is the skeleton every sharded system shares.

  1. Run four node processes on localhost, each owning four of sixteen partitions, wrapping your existing key-value store
  2. Build a router process that holds a partition-to-node map and computes the partition as a stable hash of the key modulo 16
  3. Forward every get and put through the router to the owning node and relay the reply
  4. Make nodes refuse keys for partitions they do not own with an explicit error instead of silently accepting
hint

Use a stable hash like fnv1a or murmur, not your language's per-process randomized hash, because later exercises depend on it never changing

hint

The router should feel insultingly simple; all the intelligence lives in the map, not the forwarding

DONE WHEN

· Write 10,000 keys through the router and read every one back correctly

· Ask each node to list its keys and confirm every key sits on the node the map assigns

· Each node reports exactly four partitions

· A key sent directly to the wrong node is refused with an error

EX 02

The Hot Partition

Add range partitioning alongside hash, then run two workloads that each break one scheme, watch the imbalance in your own counters, and fix it with key design.

  1. Add a range mode to the router: sixteen contiguous key ranges read from a boundaries file, sharing the same map machinery
  2. Drive a Zipfian workload where one celebrity key takes roughly 40 percent of writes, and a sequential-timestamp workload, through both modes while recording per-node request counts
  3. Salt the celebrity key into sixteen sub-keys in the router, spreading writes and scatter-reading and merging on get
  4. Compound the timestamp key with a sensor ID prefix so writes fan out, and note what it costs your range scans
hint

The router must know which keys are salted; a hardcoded list of one is honest, because salting everything makes every read a scatter

hint

If the fixed Zipfian run is still hot, check that reads scatter too — a salted key always read from sub-key zero is renamed, not spread

DONE WHEN

· Before fixing, the hottest node handles at least three times the mean load in each broken pairing

· After fixing, max over mean node load is under 1.5x on both workloads

· Reads of the salted key return the correct merged value

· A range scan in range mode touches only the nodes holding the spanned partitions

EX 03

Move It Live

First prove why hash-modulo-N rebalancing is a disaster, then add a fifth node under continuous load and migrate partitions to it without dropping a request.

  1. Implement hash-modulo-N assignment as a throwaway router mode and count how many of 10,000 keys change homes going from four to five nodes, versus fixed-partition reassignment
  2. Start a continuous load driver against the router that records every request outcome
  3. Bring up node five and migrate three partitions: snapshot each partition, ship it, then stream the writes that landed during the snapshot using your replication log code
  4. Once caught up, flip the map atomically in the router while the old owner drains, forwarding or retry-rejecting stragglers
hint

Catch-up must complete before the flip; snapshot then flip then catch up is the data-loss ordering

hint

The old owner should enter a draining state before the map flips, so there is a moment where both nodes know their role

hint

Reuse the replication stream you already wrote rather than building a new transfer path

DONE WHEN

· Modulo-N moves roughly 80 percent of keys while fixed partitions move roughly 20 percent

· Zero failed requests across the whole migration, and every acknowledged write is readable afterwards

· Every migrated key is present on node five and absent from its old owner

· Sentinel keys written to a migrating partition right through the cutover read back correctly

EX 04

Find It By Value

Values become small JSON documents and the query becomes 'color equals red'. Build both a local and a global secondary index and count where each one pays.

  1. Store small JSON documents and add a router query that filters on an indexed field
  2. Build local mode: each node indexes only its own rows, and the router scatters the query to all nodes and merges results
  3. Build global mode: partition index entries by term, so each term key lives on one partition listing matching primary keys
  4. On every write in global mode, have the owning node send an asynchronous index update through the router, then measure request counts in both modes
hint

In global mode the index update is just another write; route it through the router since a term is just a key

hint

If dual-writing from the node feels fragile, that is exactly why real systems feed global indexes from a change log

DONE WHEN

· Both modes return the same correct results, with a settle window allowed for global mode

· Local mode touches every node per query; global mode touches at most two

· A write that changes an indexed value touches one partition locally and two globally

· A write-then-immediately-query probe visibly catches the global index trailing at least once

Go deeper (after the bench)

Read DDIA chapter 6 (Partitioning) after exercise 02 — skew and rebalancing land differently once you have watched your own node counters spike, and the Request Routing section names the three options your router chose between. Then, as a victory lap after exercise 03, read the free Redis Cluster specification at redis.io: fixed hash slots, key hash tags, and live slot migration with ASK redirection are a production answer sheet for exactly what you built.