Replication means keeping a copy of the same data on multiple machines that are connected via a network. If the data that you are replicating does not change over time, then replication is easy - just copy the data to every node. All of the difficulty in replication lies in handling changes to replicated data. Replication has three popular algorithms :
- Single-leader replication
- Multi-leader replication
- Leaderless replication
We will review in details them later
Motivation
- Latency - keep data geographically close to your users (and thus reduce latency)
- Availability - allow the system to continue working even if some nodes have failed
- Throughput - Scale out the number of machines that can serve read queries
Leaders and Followers
Every write to database need to be processed by each replica. Otherwise replicas will not contain the same data. The most common solution for this is called leader-based replication ( also known as master-slave replication )
All writes or other operations that change data are send to the replica appointed as the leader. After performing the changes locally the leader notifies the followers about the changes in data. The followers, in response, update their own local copy of the data to keep up with the leader. You can read from any replica, but only the leader will accept writes.
Synchronous vs Asynchronous replication
Synchronous
In this replication method, once the master gets a write request from the application. first, writes data into the database then sends these changes to all replicas. Then the master waits till all replicas write the changes into their database and acknowledge and finally master responds success message to the application write request.
Asynchronous
In the Asynchronous replication method, the master sends the confirmation to the application as soon as it has received the message and written successfully into the database then it sends the replicate request to all replicas.
Replication algorithms
Single leader replication
In this setup, the clients always send writes (in the case of databases, INSERT, UPDATE and DELETE queries) to the leader, and never to a follower. These followers can, however, answer read queries.
The main benefit of having a single leader is that we avoid conflicts caused by concurrent writes. All the clients are writing to the same server, so the coordination is easier.
The main problem is that we need to make sure that just one node is able to handle all the writes. Although we can split the read work across the entire cluster, all the writes are going to a single server, and if your application is very write-intensive that might be a problem. Keep in mind though, that most applications read a lot more data than they write, so you need to analyze if that’s really a problem for you.
Multi leader replication
The main reason to consider a multi leader approach is that is solves some of the problems that we face when we have just one leader node. Namely, we have more than one node handling writes, and these writes can be performed by databases that are closer to the clients. If your application needs to handle a very high number of writes, it might make sense to split that work across multiple leaders. Also, if the latency price to write in a database that is very far is too high, you could have one leader in each location (for example, one in North America, one in Europe and another in Asia).
Another good use case is when you need to support offline clients, that might be writing to their own (leader) database, and these writes need to be synchronized with the rest of the databases once this client gets online again.
The main problem you will face with multiple leaders accepting writes is that you need some way to solve conflicts. For example, let’s say you have a database constraint to ensure that your users’ emails are unique. If two clients write to two different leaders that are not yet in sync, both writes will succeed in their respective leaders, but we will have problems when we try to replicate that data.
Leaderless replication
The basic idea is that clients will send writes not only to one replica, but to several (or, in some cases, to all of them). Advantage here that we have is that we can tolerate node failures more easily. Think about what would happen in a scenario where we had to send a write to a single leader and for some reason that leader didn’t respond. The write would fail and we would need to start a failover process to elect a new leader that could start receiving writes again.
What happens if, say, your write succeeds in 2 replicas, but fails in 1? You now have 2 replicas with the new value and 1 with the old value. Remember, these replicas are not talking to each other, there’s no leader handling any kind of synchronization.
We still have a problem, though. One of the replicas still has the old value, and we need to somehow synchronize it with the rest of the replicas (after all, replication is the process of keeping the same data in several places).
There are usually two ways to do that: We can make the client responsible for this update, or we can have another process that is responsible just for finding differences in the data and fixing them.
Making the client fix it is conceptually simple, when the client reads data from several nodes and detects that one of them is stale, it sends a write request with the correct value. This is usually called read repair.
