Unit 5.4 · about 3 h
269 / 324Partitioning, hot keys, rebalancing and stale writers
Moving bytes does not transfer exclusive ownership by itself. Partition placement, request routing and stale-writer rejection must agree before a rebalanced shard can safely accept effects.
- explain
You can now
- Explain how range and hash partition keys trade scan locality against load distribution.
- Derive key movement and request skew for an explicit partition change.
- Trace a stale-owner write and explain what resource-enforced epochs do and do not prevent.
Covers
- Partition keys, hashing, ranges, hot keys and skew
- Rebalancing, ownership epochs and stale writers
Study, in this order
2 steps
- DDIA, 2nd edition: partition placement and routingDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 7, Sharding by Key Range through Operations: Automatic Versus Manual Rebalancing, pp. 256 to 265; Request Routing, pp. 265 to 267
- DDIA, 2nd edition: enforcing ownership at the resourceDesigning Data-Intensive Applications, 2nd edition - distributed data path
Chapter 9, Distributed Locks and Leases, including Fencing off zombies and delayed requests and Fencing with multiple replicas, pp. 373 to 376
Focus on
- A partition key determines colocation. Range partitioning supports nearby-key scans but can concentrate timestamp writes; hashing spreads distinct keys, not repeated requests for one key.
- Separate keys-to-shards from shards-to-nodes. Fixed virtual shards avoid remapping every key when the node count changes.
- Routing metadata can be stale during transfer. Record an ownership epoch and decide when the new owner and receiving resource have installed it.
- A resource that remembers the greatest accepted fencing token rejects lower tokens only after learning the newer one. Persist that fence with the protected mutation; equal-token retries still need operation deduplication.
Reproduce closed-book
By hand or in Python 3.14, use integer keys 0 through 11 and the toy hash \(h(k)=k\). Changing node assignment from \(k \% 3\) to \(k \% 4\) moves nine keys. Instead keep 12 fixed shards, initially owned by \(\text{shard} \% 3\), and move only shards 3,7,11 to new node 3: three keys move and each node owns three keys. For a separate workload of 90 requests for key 0 and one for each key 1 through 11, \(k \% 3\) gives request counts
[93,4,4]. Then trace writes at one shared resource with initial maximum token 7: A writes \((\text{token } 7, x=\text{old})\) and receives OK; B installs token 8 and writes \(x=\text{new}\); delayed A writes \((7, x=\text{old})\) and is rejected. Remove the token check and A overwrites new. Also test A arriving before the resource sees token 8: a greatest-seen-token check still accepts 7. Check these counts and orders directly, not as a benchmark; issuance of token 8 elsewhere is not instantaneous revocation at this resource.Traps
- Using Python's process-randomized string hash as a persistent partition function.
- Assuming balanced key counts imply balanced request load or that hashing can split a single hot key.
- Checking a lease only at the sender. Pauses and delayed requests can outlive that check; fencing is resource enforcement, not a clock trick or an exactly-once mechanism.
Practice
The section mini-project covers this: partition movement and hot-key counts, ownership transfer, persistent resource-side fencing, and delayed stale writes before and after the new epoch is installed.
Self-test
-
Why does adding nodes not fix one overloaded partition key?
If all requests for that key remain on one shard, its load stays concentrated. Splitting the logical key requires application aggregation or another workload-specific design. -
What is stable when a fixed shard is moved to a new node?
The key-to-shard mapping. Shard-to-node placement and routing metadata change. -
Has issuing token 8 revoked token 7 at every resource?
No. A greatest-seen-token resource must first install or observe 8, and all protected resources must enforce the fence. -
Can token 8 be used for two duplicate increments?
Yes, if equal tokens are accepted. Fencing blocks stale owners, not duplicate operations from the current owner. Deduplication needs an operation identity and atomic effect boundary.
Completion criterion
Stop when
You reproduce both movement counts and the skew, then explain why the stale write is rejected only after the receiving resource installs the new fence.
Mark passed, then open 5.5 Only mark this when you can do it without notes.Leads to
- 5.5 Durable logs, delivery guarantees and idempotent consumers Apply ownership epochs to consumers that resume a partition after failover.
Resources for this unit
- Designing Data-Intensive Applications, 2nd edition - distributed data path Read the selected chapters on replication, partitioning, distributed-system trouble, consistency and consensus, batch processing and stream processing. For each guarantee, write its assumptions, a confirming history and one counterexample outside the boundary.
Also in this section
- Gossip Glomers - Echo, Unique ID and Broadcast Complete Challenge 1 Echo, Challenge 2 Unique ID Generation and Challenge 3a Single-Node Broadcast. Add 3b Multi-Node Broadcast only after writing the delivery, duplicate and partition assumptions. Preserve protocol histories rather than relying on a success banner.
- MIT 6.5840 - MapReduce, RPC and consistency bridge Use the introductory MapReduce, RPC, GFS and consistency lectures after the local RPC and store gates. The MapReduce lab is optional. Do not begin Raft or sharded KV as foundation work.
- Apache Kafka documentation - design Read Persistence, The Consumer (Consumer Position), Message Delivery Semantics, Using Transactions, Replication and Log Compaction for a concrete log: offsets, consumer positions, the at-most-once, at-least-once and exactly-once boundaries, in-sync replicas and compaction guarantees. Map each guarantee onto your own log before trusting it.
- Building Distributed Systems from Scratch - one challenge path Choose one messaging, durable-log or partitioning challenge that matches a failed checkpoint. State the model, failures and evidence independently because interactive grading behavior has not been verified.
- AlgoMaster System Design - distributed fundamentals slice Use Database Replication, Consistency Models, Logical Clocks, Vector Clocks, Network Partitions, Split Brain Problem, Leader Election, Database Partitioning, Consistent Hashing, Delivery Semantics, Dead Letter Queues, Idempotency, Two-Phase Commit (2PC), Outbox Pattern and Streaming Engines as bounded review after DDIA. Attempt only the exercise that matches your implemented history, then challenge its assumptions with a node-loss, delay or duplicate case.