Handling write conflicts under multi-master replication (4) - multi-master replication topology

The topology of replication describes the communication path through which write requests are propagated from one node to another.With two masters, as in Figure-7, there is only one reasonable topology: M1 must synchronize all his writes to M2, and vice versa.When there are more than two M, a variety of different topologies are possible.Figure-8 illustrates some examples.

The most common topology is all-to-all, i.e. Figure-8, where each M synchronizes its writes to all other Ms.

But more restricted topologies are also used: for example, MySQL only supports circular topologies, where each node receives writes from the previous node and writes those writes (plus its own writes)In) forwarded to the subsequent node.

Another popular structure is the star shape ^v.A designated root node forwards writes to all other nodes.The star topology can be generalized to trees.

Ring, star topology

Write requests need to go through multiple nodes to reach all replicas, i.e. intermediate nodes need to forward data changes received from other nodes.To avoid infinite loops, each node needs to be assigned a unique identifier, and each write request in the replication log is marked with the identifiers of all nodes that have passed.When a node receives a data change marked with its own identifier, the data change will be ignored, avoiding repeated forwarding.

Questions

If a node fails, it may disrupt the flow of replicated messages between other nodes, rendering them unable to communicate until the node is repaired.Topologies can be reconfigured to work on failed nodes, but in most deployments this reconfiguration must be done manually.A more densely connected topology (such as all-to-all) is more fault-tolerant because it allows messages to travel along different paths, avoiding a single point of failure.

All-to-all topologies can also be problematic.Especially when some network links may be faster than others (network congestion), as a result some replicated messages may "overtake" others, as shown in Figure-9.

Client A sends L1A row is inserted into the table, and B updates the row in L3.However, L2 can receive writes in a different order: updates (from its perspective, updates to rows that don't exist in the database) can be received first, and then L1's insert log (which should arrive before the update log).

This is a causality problem, similar to "consistent prefix reads": updates depend on previously completed inserts, so make sure all nodes receive inserts before processing updates.Adding a timestamp to each log write is not enough, mainly because there is no way to ensure that the clocks are fully synchronized and thus the received logs cannot be ordered correctly on L2.

To properly order log messages, a version vector can be used.Conflict detection technology is not fully implemented in many primary replication systems.As PostgreSQL BDR does not provide causal ordering of writes, Tungsten Replicator for MySQL does not even attempt to detect conflicts.