Part 4 of 7 · 2 min read
Agreeing on the map
Why everyone must hold the same assignment, and what a coordination service is for.
Think of two receptionists who each keep their own copy of the staff directory. After a staff move, one updates her copy and the other does not. Visitors sent by the second receptionist arrive at an empty desk, and the colleague who now sits there is not expecting them.
The book says this is a challenging problem, because all participants must agree. Otherwise requests are sent to the wrong nodes and not handled correctly. There are protocols for achieving consensus in a distributed system, but they are hard to implement correctly.
Many distributed data systems therefore rely on a separate coordination service such as ZooKeeper to track the cluster's metadata.
Coordination service
A coordination service (such as ZooKeeper or etcd) is a small, highly reliable, strongly consistent store that keeps cluster metadata, such as the map of partitions to nodes, and notifies subscribers when it changes.
Example: each node registers itself in ZooKeeper. ZooKeeper holds the authoritative map. The routing tier subscribes, and is told at once when a partition changes owner.
The book describes the pattern. Each node registers itself with ZooKeeper, and ZooKeeper holds the authoritative mapping. Other parts, like the routing tier or a partition-aware client, subscribe to it. When a partition changes owner or a node is added or removed, ZooKeeper notifies the routing tier so it keeps its routing information current.
Examples named by the book:
- LinkedIn's Espresso uses Helix for cluster management, which relies on ZooKeeper, with a routing tier.
- HBase, SolrCloud and Kafka use ZooKeeper to track partition assignment.
- MongoDB has a similar design with its own config server and mongos routing daemons.
The book "Understanding Distributed Systems" describes the same idea: the mapping between keys and partitions, and other metadata, is usually kept in a strongly consistent configuration store such as etcd or ZooKeeper. A gateway service can route requests to the right place, knowing how keys map to partitions and partitions to nodes.
The coordination service is small and rarely read on the data path: routers and clients cache the map and are told when it changes. It is not asked on every request.
A worked example. A routing tier of 5 routers, 100,000 requests a second in total.
- If every request asked the coordination service for the map: 100,000 reads a second, far too much for a consistency-focused store.
- With cached maps and change notifications: the coordination service sends a few notifications when something changes, say 10 changes per day × 5 routers = 50 messages a day.
- The risk is a stale cache: a router that missed a notification sends requests to the old owner until it learns better. The old owner must reply "not mine" (or forward), so the router refreshes its map.
Check yourself:
- Why do routers cache the map, not ask the coordination service for every request?
- What happens if two routers hold different maps?