Part 3 of 7 · 3 min read
Three designs
Letting any node forward, using a routing tier, or making the client smart.
Think of three ways to reach the right office in a large company. You can phone the main desk and ask to be transferred, you can go through a receptionist whose only job is to direct visitors, or you can carry the staff directory yourself and go straight to the right desk.
The book gives three approaches.
- Any node. Clients contact any node, for example through a round-robin load balancer. If that node happens to own the partition, it handles the request. If not, it forwards the request to the right node, receives the reply, and passes it back to the client.
- A routing tier. All requests go first to a routing tier, which determines the node for each request and forwards it. The tier handles no requests itself. It only acts as a partition-aware load balancer.
- A partition-aware client. The client knows the partitioning and the assignment of partitions to nodes, so it connects directly to the right node with no intermediary.
Partition-aware routing
Partition-aware routing means that whoever makes the routing decision (a node, a routing tier or the client) knows which node holds the partition for a key.
Example: a client library keeps a copy of the routing table and sends a write for partition 41 straight to node 7.
In every case the key problem is the same: how does the component that decides (a node, the routing tier or the client) learn about changes in the assignment?
A worked example comparing the extra hops for a request, with made-up times: 0.5 ms per network hop inside the data centre, 1 ms of processing at the data node.
| Design | Path | Hops (one way) | Time if the first node is right | Time if wrong |
|---|---|---|---|---|
| Any node | client → node → (forward) → owner node | 1 or 2 | 2 × 0.5 + 1 = 2 ms | 4 × 0.5 + 1 = 3 ms |
| Routing tier | client → router → owner node | 2 | 4 × 0.5 + 1 = 3 ms | same |
| Partition-aware client | client → owner node | 1 | 2 × 0.5 + 1 = 2 ms | 2 ms (3 ms plus a retry if the map is stale) |
With a hit rate of 1 ÷ 16 for a random node (the chance it owns the key), 15 out of 16 requests take the long path: the average for "any node" is about 2.94 ms.
| Any node | Routing tier | Smart client | |
|---|---|---|---|
| Extra hop | Often | Always | None |
| Client complexity | Low | Low | High (needs the map and updates) |
| Where the map lives | In every node | In the router | In every client |
| Failure point | Any node | The router (make it redundant) | None extra |
| Updating the map | Nodes tell each other | Router subscribes to changes | Clients must subscribe |
Cassandra and Riak use the first approach. MongoDB and LinkedIn's Espresso use a routing tier. Many client libraries use the third.
Check yourself:
- In which design does the request never pass through an extra machine?
- With 10 nodes and any-node routing, what share of requests need a forward?