DISTRIBUTED DATABASE REPLICATION
Multi Master Replication
Understanding Multi Master Replication in Distributed Database Systems
As we saw in the previous article, Single Master Replication is a simple and easy-to-operate replication method that abstracts the distributed nature of the system while supporting transactions and other important database features. This method is designed to prioritize simplicity and consistency over availability and scalability.
However, Single Master Replication has limitations in terms of performance, scalability, and availability, which are crucial in many applications that cannot afford to sacrifice these features.
Multi-Master Replication
Multi-Master Replication is an alternative replication technique that prioritizes high availability and performance over data consistency.
With this replication method, all nodes are equal and can accept both read and write requests. There is no single leader that receives writes; instead, all nodes can concurrently handle writes. However, this also means that nodes might disagree on the order of events, resulting in conflicts.
Not sure how this can create conflicts?
Distributed Conflict
Let’s assume a system with three nodes and a client.
- The client wants to write
x=10, and the request reaches Node A, which commits it. - Node A initiates a broadcast to other nodes, indicating that it received
x=10and that they should also commit this to their storage. - Node C successfully receives the broadcast and commits
x=10to its own storage. - However, before Node B receives
x=10, the client initiates another request,x=14, which reaches Node B. Node B commitsx=14to its storage. - Node B initiates a broadcast indicating that it received
x=14and that other nodes should commit this to their storage. - Both Node A and Node C commit
x=14to their storage. - The initial broadcast from Node A finally reaches Node B, asking it to commit
x=10, which Node B then commits. - Now, Node A and Node C have the value
14, while Node B has10. - When the client asks for
x, they will receive different results depending on which node the request reaches.
This is called a conflict. How will we resolve this?
Conflict Resolution
There are different types of conflict resolution based on the guarantees your system needs to support.
Expose Conflict Resolution to Clients
When the next read request is sent, why don’t we send both values to the client and ask it to resolve the conflict for us? Since the client knows the context of what needs to happen, it can resolve conflicts better than the database.
This type of conflict resolution is popular in Git, where you get a merge conflict and you, as a client, will have to manually resolve the conflict and tell git which version you want.
Last Write Wins Resolution
What if we attach a timestamp to each write request, and the system considers the write with the latest timestamp to be the most recent write, discarding any earlier writes?
It’s certainly possible, but we’ll have to be mindful of Clock Skew. If we use Physical Time, there’s a possibility that an earlier generated message has a later time than a message generated later because of NTP.
We can use Logical Time here to detect the order of events and execute them, but there’s still a possibility that two writes are concurrent. Logical Time won’t help in that case. However, since it can detect it, we can offload just those to the clients.
Causality Tracking Algorithms
The system uses an algorithm that keeps track of Causality and Causal Relationships between different requests.
If you don’t know what Causal Relationship is, I have an article which explains this in detail. You can read it here
Essentially, this means that if there’s a conflict between two writes (A, B), and we somehow figure out that A caused B to occur directly, then B takes precedence over A.
We can figure this out using Vector Clocks.
However, there’s also a possibility that the two events are not causally related, i.e., the requests are concurrent. In such systems, we cannot make a decision.
