Primary-Backup Replication Algorithm

Techniques for propagating updates

There are two ways to propagate the updates: synchronously and asynchronously.

Synchronous replication

In synchronous replication, the node replies to the client to indicate the update is complete—only after receiving acknowledgments from the other replicas that they’ve also performed the update on their local storage. This guarantees that the client is able to view the update in a subsequent read after acknowledging it, no matter which replica the client reads from.

Furthermore, synchronous replication provides increased durability. This is because the update is not lost even if the leader crashes right after it acknowledges the update.

However, this technique can make writing requests slower. This is because the leader has to wait until it receives responses from all the replicas.

Asynchronous replication

In asynchronous replication, the node replies to the client as soon as it performs the update in its local storage, without waiting for responses from the other replicas.

This technique increases performance significantly for write requests. This is because the client no longer pays the penalty of the network requests to the other replicas.

However, this comes at the cost of reduced consistency and decreased durability. After a client receives a response for an update request, the client might read older (stale) values in a subsequent read. This is only possible if the operation happens in one of the replicas that have not yet performed the update. Moreover, if the leader node crashes right after it acknowledges an update, and the propagation requests to the other replicas are lost, any acknowledged update is eventually lost.

Most widely used databases, such as PostgreSQL or MySQL, use a primary-backup replication technique that supports both asynchronous and synchronous replication.

Advantages of primary-backup replication

• It is simple to understand and implement
• Concurrent operations serialized in the leader node remove the need for more complicated, distributed concurrency protocols. In general, this property also makes it easier to support transactional operations
• It is scalable for read-heavy workloads because the capacity for reading requests can be increased by adding more read replicas

Disadvantages of primary-backup replication

• It is not very scalable for write-heavy workloads because a single node’s capacity (the leader’s capacity) determines the capacity for writes
• It imposes an obvious trade-off between performance, durability, and consistency
• Scaling the read capacity by adding more follower nodes can create a bottleneck in the network bandwidth of the leader node, if there’s a large number of followers listening for updates
• The process of failing over to a follower node when the leader node crashes is not instant. This may create some downtime and also introduce the risk of errors

Failover

Failover is when the leader node crashes and a follower node takes over.

When the leader node crashes, we need to choose another leader node. Following are the approaches to perform failover.

Managing failover

In general, there are two approaches to perform a failover: manual and automated.

Manual approach

In the manual approach, the operator selects the new leader node and instructs all the nodes accordingly. This is the safest approach, but it incurs significant downtime.

Automated approach

An alternative is an automated approach, where follower nodes detect that the leader node has crashed (e.g., via periodic heartbeatsPeriodic messages sent by a node that indicate that it is working failure-free), and attempt to elect a new leader node. This is faster but is quite risky. This is because there are many different ways in which the nodes can get confused and arrive at an incorrect state.

The chapter about consensus will cover this topic, called leader election, in more detail.