Part 2 of 7 · 2 min read
The routing question
How a client knows which node to call for a key.
Think of a large library whose books move between buildings as it grows. A reader who wants a book needs a current map. If the map is a day old, the reader walks to the wrong building and finds an empty shelf.
The book "Designing Data-Intensive Applications" poses the question: the data set has been split over several nodes on several machines. When a client makes a request, how does it know which node to connect to? As partitions are rebalanced, the assignment of partitions to nodes changes. Someone must stay on top of the changes to answer: if I want to read or write the key "foo", which IP address and port do I connect to?
Request routing
Request routing is the job of sending each request to the node that holds the partition for its key, using a map of partitions to nodes that changes over time.
Example: a request for user 8,812 hashes to partition 41. The map says partition 41 lives on node 7 at 10.0.3.17:9042. The request goes there.
The book notes that this is an instance of a more general problem, service discovery, which is not limited to databases. Any software reached over a network has it, especially if it runs in a redundant configuration on several machines for high availability (Level 1, module 6 covered service discovery for stateless services). Many companies wrote their own tools, and many were released as open source.
The map has two layers:
- Key to partition. A fixed rule (range boundaries, a hash, a ring). This part changes rarely, or never, if the number of partitions is fixed.
- Partition to node. An assignment that changes whenever a node is added, removed, fails, or a partition moves.
The second layer is the difficult one, since it changes during normal operation.
A worked example. A store has 256 partitions on 16 nodes. The routing table has 256 rows:
| Partition | Leader node | Follower nodes |
|---|---|---|
| 0 | node 3 | node 8, node 11 |
| 1 | node 9 | node 2, node 14 |
| ... | ... | ... |
| 255 | node 5 | node 1, node 12 |
It is tiny: 256 rows of about 50 bytes is 12.8 KB. Size is not the problem. Freshness is. If node 3 fails and partition 0's leader moves to node 8, clients that still send writes to node 3 get errors.
Check yourself:
- What are the two layers of the map, and which one changes more often?
- Why is routing a form of service discovery?