Part 4 of 8 · 2 min read
Multi-leader topologies
The paths that writes follow between leaders, and the order problem.
Think of passing a message along a chain of people. If one person leaves, the chain breaks. If everyone talks to everyone, the message arrives by several routes, but a quick message from a nearby person may overtake an earlier one from a distant person.
A replication topology describes the paths along which writes pass from node to node. The book shows three:
- Circular. Each node receives writes from one node and passes them, with its own, to one other. MySQL supports only this by default.
- Star. One root node sends writes to all others. A star can grow into a tree.
- All-to-all. Every leader sends its writes to every other. It is the most general.
In circular and star shapes, a write passes through several nodes. To stop infinite loops, each node has an id, and every write is tagged with the ids of the nodes it has passed. A node that receives a change tagged with its own id ignores it.
A fault in a circular or star topology is serious: one failed node interrupts the flow between others until someone reconfigures it, usually by hand. All-to-all has better fault tolerance, since messages can take different paths.
But all-to-all has its own flaw. Some links are faster, so messages overtake each other. The book's example: client A inserts a row on leader 1. Client B updates that row on leader 3. Leader 2 may receive the update first, an update to a row that does not exist yet, and the insert later. The update depends on the insert, so this is a problem of causality. A timestamp alone does not fix it, since clocks may not be in step. A technique named version vectors orders the events correctly (covered below). The book warns that many multi-leader systems do poorly here: PostgreSQL BDR did not give causal ordering, and Tungsten Replicator for MySQL did not try to detect conflicts. The advice is to read the documentation and test the database to see whether it really gives the guarantees you believe it does.
| Topology | Strength | Weakness |
|---|---|---|
| Circular | Simple, few links | One failure breaks the ring |
| Star / tree | Simple, central control | The root is a single point of failure |
| All-to-all | Several paths, survives failures | Messages may overtake each other |
A worked example of the link count. With 5 leaders: circular needs 5 links, a star needs 4, all-to-all needs 5 × 4 ÷ 2 = 10 links (20 one-way channels). With 10 leaders: all-to-all needs 45 links.
Check yourself:
- How does a node avoid copying a change round a circle for ever?
- What problem arises when a message overtakes another in an all-to-all set-up?