Scalable Human Blog

What is a replication topology?

This outlines the communication paths, where writes are propagated to one node or the other.

You only have two leaders?

There is only one suitable topology…

• Leader one must send all writes to leader two and vice versa

With more that two leaders various topologies are possible

The most general topology is all to all, every leader sends its writes to every other leader.

Although, there are more restricted topologies that can also be used. For instance:

• MySQL by default only supports a circular topology.
  • Each node receives writes from one node and forwards those writes, plus any writes of its own to one other node, forming a circle.
• Another popular topology is the star topology
  • One designated root node forwards the writes to all other nodes
  • Star topology can be generalised to a tree

In circular and star topologies:

• Any write may need to pass through several nodes to reach all replicas
• This means, node need to forward data changes they receive from other nodes
• To prevent infinite replication loops..
  • Each node is given a unique identifier
  • In replication log each write is tagged with the identifiers the node has passed through
  • When a node receives data change, tagged with its own identifier that data change is ignored because the node already knows that it already been processed

⚠️ Problem with circular and star topologies:

• If just one node fails it can interrupt the flow of replication messages between other nodes
  • This can cause them not being able to communicate until the node is fixed
• The topology could be reconfigured to work around the failed node
  • But in most deployments such reconfiguration would have to be done manually
• The fault tolerance of a more densely connected all to all topology is better
  • Because it allows the messages to travel along different paths, avoiding a single point of failure
• ⚠️ To note, all to all topologies can have issue
  • Some network links maybe faster than others, which maybe due to network congestion
    • With the result of some replication messages may overtaking others
    • To describe this situation:
      • Client 1 inserts a row on leader 1
      • Client 2 updates that newly inserted row on leader 3
      • However leader 2 receives these writes in a different order, it may first receive client 2 update, which in its point of view updates a row that does not exist in the database
      • Only later this will receive the corresponding insert which should of proceeded the update
    • This is a problem of causality
      • The update depends on the prior insert
      • So we need to ensure that all the nodes process the insert first and then the update
      • Simply attaching a timestamp to every write is not sufficient
      • This is because the clocks cannot be trusted to be sufficiently in sync to correctly order the as mentioned events at leader 2
    • The solution to ordering these events correctly, is done by a technique called version vectors.

However conflict detection techniques are poorly implemented in many multi leader replication systems

• For example, PostgreSQL BDR has been noted not to provide a causal ordering of writes
• And Tungsten replicator by MySQL does not even try to detect these conflicts!

If your using a system with multi leader replication, it is well worth knowing these issues.

Tips for choosing the best database technology

• Carefully read the documeneation
• Thoroughly test the database to make sure it provides the guarantees you believe its offering

📚 Further Reading & Related Topics

If you’re exploring multi-leader replication topologies in distributed systems, these related articles will provide deeper insights:

• Understanding Partitioning: Proportional to Nodes – Learn how partitioning works alongside multi-leader replication to optimize data distribution and performance across distributed systems.

• Replication vs. Sharding: Key Differences in Distributed Databases – Dive into the differences between various data distribution strategies like replication and sharding, and how they influence scalability, availability, and performance in large systems.