Part 6 of 7 · 4 min read
Walk-through: a request, a failure, a move
One request at three moments: normal, after a failure, and during a partition move.
Walk-through: a request, a failure, a move
Think of following one parcel in a delivery network on an ordinary day, on the day a depot burns down, and on the day the depots swap routes.
The set-up. A sharded key-value store has a config store (ZooKeeper-like), 3 routers, 8 data nodes and 64 partitions with 8 on each node. Routers subscribe to the config store and keep a copy of the map.
An ordinary request. A client sends GET user:812 to a router (found by DNS or a load balancer).
- The router hashes
user:812to partition 41 (key to partition). - Its map says partition 41 is led by node 5 (partition to node).
- It forwards the read to node 5. Node 5 answers. The router returns the answer. Time: about 3 ms.
A node fails. Node 5 crashes.
- The failure is detected by timeouts (module 1), say after 10 seconds.
- The followers of the partitions led by node 5 elect new leaders. For partition 41, node 2 becomes the leader.
- The config store is updated and notifies the 3 routers. In the meantime some requests fail.
- Writes to partition 41 sent to node 5 during those 10 seconds fail or time out. At 50 writes a second to that partition, about 500 writes are affected.
- The routers learn the new map and send partition 41 to node 2. The client sees the problem end. The client library should retry once.
A partition moves. A new node 9 joins and takes partition 41 from node 2 (rebalancing, module 5).
- Node 9 copies the data of partition 41 from node 2 and catches up with the log (module 1).
- During the copy, the old assignment serves requests.
- At the switch, the config store changes the owner to node 9 and notifies the routers.
- A router that has not yet heard still sends a request to node 2. Node 2 replies "not the owner, try node 9" (or forwards it). The router updates its map and retries.
- After a short time all routers use node 9.
A worked example of the cost of staleness. A router misses the notification and uses the old map for 5 seconds at 200 requests a second to partition 41: 1,000 requests, each takes an extra hop of 1 ms from the forward. Total extra time: 1 second of added latency over 5 seconds. With no forwarding or retry, 1,000 requests would fail.
Interview angle
Answer in your head first, then open it.
How does a client find the shard for a key?
Hash the key to a partition, then look up the partition in a routing table kept by a config store and cached by the router or client. Name the three designs.
Where do you keep the partition map?
In a small strongly consistent store like ZooKeeper or etcd, with change notifications, or spread by gossip. Say the map is cached, not read on every request.
What happens during a rebalance or failover?
Some requests reach the old owner. It rejects or forwards them, the caller refreshes its map and retries. The old assignment serves until the transfer is done.
Router, smart client or any node?
A router keeps clients simple and adds a hop. A smart client is fastest but needs update logic in every client. Any-node needs no extra tier and costs forwards.
What if the config store is down?
Routers keep working with their cached map. Changes (failovers, moves) pause until it returns, so make it highly available.
Check yourself:
- What happens if the config store is down but the routers hold their cached map?
- What must an old owner do when it receives a request for a partition it has given away?
Words you will meet
| Word | Plain meaning |
|---|---|
| Request routing | Sending a request to the node that holds its key's partition |
| Routing table (partition map) | The record of which node holds which partition |
| Routing tier | A set of machines that only direct requests to data nodes |
| Partition-aware client | A client that knows the partition map and connects directly |
| Service discovery | Finding the address of a service that moves or has many copies |
| Coordination service | A small consistent store for cluster metadata with notifications |
| ZooKeeper, etcd | Examples of coordination services |
| Gossip protocol | Nodes spread cluster news by telling random peers |
| Stale map | A copy of the map that is out of date |
| Not-the-owner reply | The answer of a node that no longer holds the partition |