System Design: Database Replication Cont’d. (part 2)

6 min readApr 3, 2020

This is my second blog in the system design series which I am currently working on. So this blog is in continuation of my previous blog on Database Replication. If you haven’t read my previous blog on this topic then I will highly recommend reading it here.

So in this blog, we are going to discuss the in-depth details of another replication algorithm know as Multi-Leader Replication in Database.

Again, I am assuming that you are aware of basic system design terminologies. And if not, then I will highly recommend reading about them from here or let me know in comments and I’ll try to cover some in my future blogs.

In this blog, we are going to discuss below-mentioned topics in-depth

Issues in Leader based Replication? Why do we need to look for another algorithm?
What is Multi-Leader Replication with advantages?
Real-Time scenarios where Multi-Leader Replication is used in our daily lives?
What are the Issues in Multi-Leader Replication with its possible solutions?
How to handle issues in Multi-Leader Replication?

Issues in Leader based Replication

Let’s take a real-time scenario to understand the issue in Leader based Replication.
Again I will extend my previous blog example here. So as the CEO of an e-commerce startup based in the USA, I wanted to cater to orders from people living in Antarctica :P
No issues, as a solution what I can do is to place some of my database servers (Followers) in Antarctica itself to reduce the Read Latency of my application (As customers are equivalent to God :P) but there is a limitation here. Take some time and think about it.
Yes, you guessed it correct what about Write Latency.

So as we know in leader based replication all writes must go through the leader itself and there is only a single leader in it.
Now I have two options, whether to place my leader in the data center of Antarctica or to place my leader in the data center of the USA (near the headquarters).
So, in either case, customers coming to place orders (Write operation for DB) from the different geographic areas are going to suffer Write Latency. Which in turn can impact the performance of my system again.
Also what if the data center having the leader (containing latest changed) fails and those changes were not replicated to all the followers in other data centers?

So are you able to see the flaws in our current implementation? Yes, I am trying to create a basic requirement to have a better solution. Indeed that’s Multi-Leader Replication.

What is Multi-Leader Replication?

Multi-leader replication across multiple datacenters

So in Multi-Leader replication, we are going to have one leader in each of my data centers and each data center’s leader replicates its changes to the leaders in other data centers asynchronously.

Advantages of Multi-Leader Replication

Better Performance as compared to Single leader replication as we have now reduced both Read & Write Latency of our application
High Fault Tolerance as each data center can continue operating independently of others if any data center goes down. This is possible because each data center has its leader. Also, replication catches up when the failed datacenter comes back online (Might be by promoting a follower as a leader and asking for the latest changes from the leaders of other data centers).

Moreover, if one data center goes down in one particular geographic area then temporarily we can route the requests from that geographic area to some other healthy data center in another geographic area till that unhealthy data center becomes healthy. Yes, there is a trade-off between Performance and High Availability here.

Multi-Leader Replication used in our daily lives?

So can you think of any mobile applications we use in daily life that use the concept of Multi-Leader Replication?
Yes, you guessed it correct we have many like Google Calendar, Outlook Calendar, etc.

Let’s understand it better how these apps work internally. So when you make any change while you are offline in the calendar app like you booking a slot for the meeting.
Now those changes need to be synced (replicated) with the server (including other devices on which app is installed) when our device gets online back. So every device database can act as a dynamic leader and performs Async Multi-leader replication

Another similar example I can give you is a feature called Collaborative Editing used in applications on cloud storage like Google sheets, Google docs, Microsoft Excel, etc. This feature allows several people to edit a document simultaneously in real-time.
So apart from replication, other concepts like Operational Transformation and certain Locking mechanisms (Can slow down editing) are also used to handle conflict issues.
Going further in-depth for Collaborative Editing is overkill and above the scope of this blog. You can read more about Operational Transformation here.

Issues in Multi-Leader Replication with its possible solutions?

Write conflict caused by two leaders concurrently updating the same record

So by going through the above realtime implementation of Multi-Leader Replication, you people might be wondering that what if there is a conflict between the changes?

Again let’s have a better example. Now when you are booking a meeting slot from 3 P.M. to 4 P.M. with a meeting name “Appraisal discussions” :P on your device those changes need to be synced (replicated) with other devices. Correct?
But what if on the other devices someone has already booked another meeting slot with a different name but with the same time slot (3 P.M. to 4 P.M.)? Yes, you are correct this is a conflict.

Also even as a developer if you have previously worked with GIT as a Version Control System then you can also connect this scenario similar to merge conflicts that generally come when two developer changes code in the same line of the same source code file. You can read more about VCS here.

Possible Solutions for above-mentioned problems

Conflict Detection
Conflict Avoidance

Conflict Detection

In the Multi-Leader replication scheme, when two leaders in different data centers have conflicts then those write conflicts can be detected asynchronously at some later point in time without blocking any user.

But at that time, it may be too late to ask the user to resolve the conflict. So this approach isn’t widely accepted.

Conflict Avoidance (Recommended approach)

The simplest strategy for dealing with conflicts is to avoid them. So according to this technique if the application can ensure that all writes for a particular record go through the same leader (data center), then conflicts cannot occur.

Probably that datacenter is in his geographical location or is the nearest datacenter to his geographical location.

Yes, you people might be wondering what if a user has moved to a different location and is now closer to a different datacenter. Yes, you got it right, in this situation, the conflict avoidance technique will break.

Conclusion

So as we always know There is no such thing as a perfect system, but yes there are good and bad systems.

But we know Prevention is always better than cure. So here Prevention corresponds to Avoidance and Cure corresponds to a situation when conflict has already occurred and we need to eliminate it by Detecting it.

Hence we can conclude that Conflict Avoidance is better than Conflict Detection.