CSE Roadmap

Common tier · about 3 hours · 7 parts

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:

  1. 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.
  2. 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?