Video coming soon. Start with the reading below.
Data replication is a fundamental building block of distributed systems. One reason for replicating data is to increase availability. If some data is stored exclusively on a single process, and that process goes down, the data won’t be accessible anymore. However, if the data is replicated, clients can seamlessly switch to a copy. Another reason for replication is to increase scalability and performance; the more replicas there are, the more clients can access the data concurrently.
Implementing replication is challenging because it requires keeping replicas consistent with one another even in the face of failures. In this lesson, we will explore Raft’s replication algorithm[1], a replication protocol that provides the strongest consistency guarantee possible — the guarantee that to the clients, the data appears to be stored on a single process, even if it’s actually replicated. Arguably, the most popular protocol that offers this guarantee is Paxos[2], but we will discuss Raft as it’s more understandable.
Raft is based on a mechanism known as state machine replication. The main idea is that a single process, the leader, broadcasts operations that change its state to other processes, the followers (or replicas). If the followers execute the same sequence of operations as the leader, then each follower will end up in the same state as the leader. Unfortunately, the leader can’t simply broadcast operations to the followers and call it a day, as any process can fail at any time, and the network can lose messages. This is why a large part of the algorithm is dedicated to fault tolerance.
The reason why this mechanism is called stated machine replication is that each process is modeled as a state machine[3] that transitions from one state to another in response to some input (an operation). If the state machines are deterministic and get exactly the same input in the same order, their states are consistent. That way, if one of them fails, a redundant copy is available from any of the other state machines. State machine replication is a very powerful tool to make a service fault-tolerant as long it can be modeled as a state machine.
For example, consider the problem of implementing a fault-tolerant key-value store. In this case, each state machine represents a storage node that accepts put(k, v) and get(k) operations. The actual state is represented with a dictionary. When a put operation is executed, the key-value pair is added to the dictionary. When a get operation is executed, the value corresponding to the requested key is returned. You can see how if every node executes the same sequence of puts, all nodes will end up having the same state.
In the next section, we will take a deeper look at Raft’s replication protocol. It’s a challenging read that requires to pause and think, but I can assure you it’s well worth the effort, especially if you haven’t seen a replication protocol before.
State machine replication
When the system starts up, a leader is elected using Raft’s leader election algorithm discussed in Leader election (lesson 03.05), which doesn’t require any external dependencies. The leader is the only process that can change the replicated state. It does so by storing the sequence of operations that alter the state into a local log, which it replicates to the followers. Replicating the log is what allows the state to be kept in sync across processes.
As shown in Figure 10.1, a log is an ordered list of entries where each entry includes:
- the operation to be applied to the state, like the assignment of 3 to x. The operation needs to be deterministic so that all followers end up in the same state, but it can be arbitrarily complex as long as that requirement is respected (e.g., compareand-swap or a transaction with multiple operations);
- the index of the entry’s position in the log;
- and the leader’s election term (the number in each box).

Figure 10.1: The leader’s log is replicated to its followers.
When the leader wants to apply an operation to its local state, it first appends a new entry for the operation to its log. At this point, the operation hasn’t been applied to the local state just yet; it has only been logged.
The leader then sends an AppendEntries request to each follower with the new entry to be added. This message is also sent out periodically, even in the absence of new entries, as it acts as a heartbeat for the leader.
When a follower receives an AppendEntries request, it appends the entry it received to its own log (without actually executing the operation yet) and sends back a response to the leader to acknowledge that the request was successful. When the leader hears back successfully from a majority of followers, it considers the entry to be committed and executes the operation on its local state. The leader keeps track of the highest committed index in the log, which is sent in all future AppendEntries requests. A follower only applies a log entry to its local state when it finds out that the leader has committed the entry.
Because the leader needs to wait for only a majority (quorum) of followers, it can make progress even if some are down, i.e., if there are 2f+ 1 followers, the system can tolerate up to ffailures. The algorithm guarantees that an entry that is committed is durable and will eventually be executed by all the processes in the system, not just those that were part of the original majority.
So far, we have assumed there are no failures, and the network is reliable. Let’s relax those assumptions. If the leader fails, a follower is elected as the new leader. But, there is a caveat: because the replication algorithm only needs a majority of processes to make progress, it’s possible that some processes are not up to date when a leader fails. To avoid an out-of-date process becoming the leader, a process can’t vote for one with a less up-to-date log. In other words, a process can’t win an election if it doesn’t contain all committed entries.
To determine which of two processes’ logs is more up-to-date, the election term and index of their last entries are compared. If the logs end with different terms, the log with the higher term is more up to date. If the logs end with the same term, whichever log is longer is more up to date. Since the election requires a majority vote, and a candidate’s log must be at least as up to date as any other process in that majority to win the election, the elected process will contain all committed entries.
If an AppendEntries request can’t be delivered to one or more followers, the leader will retry sending it indefinitely until a majority of the followers have successfully appended it to their logs. Retries are harmless as AppendEntries requests are idempotent, and followers ignore log entries that have already been appended to their logs.
If a follower that was temporarily unavailable comes back online, it will eventually receive an AppendEntries message with a log entry from the leader. The AppendEntries message includes the index and term number of the entry in the log that immediately precedes the one to be appended. If the follower can’t find a log entry with that index and term number, it rejects the message to prevent creating a gap in its log.
When the AppendEntries request is rejected, the leader retries the request, this time including the last two log entries — this is why we referred to the request as AppendEntries and not as AppendEntry. If that fails, the leader retries sending the last three log entries and so forth.[4] The goal is for the leader to find the latest log entry where the two logs agree, delete any entries in the follower’s log after that point, and append to the follower’s log all of the leader’s entries after it.
Consensus
By solving state machine replication, we actually found a solution to consensus[5] — a fundamental problem studied in distributed systems research in which a group of processes has to decide a value so that:
- every non-faulty process eventually agrees on a value;
- the final decision of every non-faulty process is the same everywhere;
- and the value that has been agreed on has been proposed by a process.
This may sound a little bit abstract. Another way to think about consensus is as the API of a write-once register[6] (WOR): a thread-safe and linearizable[7] register that can only be written once but can be read many times.
There are plenty of practical applications of consensus. For example, agreeing on which process in a group can acquire a lease requires consensus. And, as mentioned earlier, state machine replication also requires it. If you squint a little, you should be able to see how the replicated log in Raft is a sequence of WORs, and so Raft really is just a sequence of consensus instances.
While it’s important to understand what consensus is and how it can be solved, you will likely never need to implement it from scratch8. Instead, you can use one of the many off-the-shelf solutions available.
For example, one of the most common uses of consensus is for coordination purposes, like the election of a leader. As discussed in 9.2, leader election can be implemented by acquiring a lease. The lease ensures that at most one process can be the leader at any time and if the process dies, another one can take its place. However, this mechanism requires the lease manager, or coordination service, to be fault-tolerant. Etcd[9] and ZooKeeper[10] are two widely used coordination services that replicate their state for fault-tolerance using consensus. A coordination service exposes a hierarchical, keyvalue store through its API, and also allows clients to watch for changes to keys. So, for example, acquiring a lease can be implemented by having a client attempt to create a key with a specific TTL. If the key already exists, the operation fails guaranteeing that only one client can acquire the lease.
Consistency models
We discussed state machine replication with the goal of implementing a data store that can withstand failures and scale out to serve a larger number of requests. Now that we know how to build a replicated data store in principle, let’s take a closer look at what happens when a client sends a request to it. In an ideal world, the request executes instantaneously, as shown in Figure 10.2.

Figure 10.2: A write request executing instantaneously
But in reality, things are quite different — the request needs to reach the leader, which has to process it and send back a response to the client. As shown in Figure 10.3, these actions take time and are not instantaneous.
The best guarantee the system can provide is that the request executes somewhere between its invocation and completion time. You might think that this doesn’t look like a big deal; after all, it’s

Figure 10.3: A write request can’t execute instantaneously because it takes time to reach the leader and be executed.
what you are used to when writing single-threaded applications. For example, if you assign 42 to x and read its value immediately afterward, you expect to find 42 in there, assuming there is no other thread writing to the same variable. But when you deal with replicated systems, all bets are off. Let’s see why that’s the case.
In State machine replication in Replication, we looked at how Raft replicates the leader’s state to its followers. Since only the leader can make changes to the state, any operation that modifies it needs to necessarily go through the leader. But what about reads? They don’t necessarily have to go through the leader as they don’t affect the system’s state. Reads can be served by the leader, a follower, or a combination of leader and followers. If all reads have to go through the leader, the read throughput would be limited to that of a single process. But, if any follower can serve reads instead, then two clients, or observers, can have a different view of the system’s state since followers can lag behind the leader.
Intuitively, there is a tradeoff between how consistent the observers’ views of the system are and the system’s performance and availability. To understand this relationship, we need to define precisely what we mean by consistency. We will do so with the help of consistency models[11], which formally define the possible views the observers can have of the system’s state.
Strong consistency
If clients send writes and reads exclusively to the leader, then every request appears to take place atomically at a very specific point in time as if there were a single copy of the data. No matter how many replicas there are or how far behind they are lagging, as long as the clients always query the leader directly, there is a single copy of the data from their point of view.
Because a request is not served instantaneously, and there is a single process that can serve it, the request executes somewhere between its invocation and completion time. By the time it completes, its side-effects are visible to all observers, as shown in Figure 10.4.

Figure 10.4: The side-effects of a strongly consistent operation are visible to all observers once it completes.
Since a request becomes visible to all other participants between its invocation and completion time, a real-time guarantee must be enforced; this guarantee is formalized by a consistency model called linearizability[12], or strong consistency. Linearizability is the strongest consistency guarantee a system can provide for single-object requests.[13]
Unfortunately, the leader can’t serve reads directly from its local state because by the time it receives a request from a client, it might no longer be the leader; so, if it were to serve the request, the system wouldn’t be strongly consistent. The presumed leader first needs to contact a majority of replicas to confirm whether it still is the leader. Only then is it allowed to execute the request and send back a response to the client. Otherwise, it transitions to the follower state and fails the request. This confirmation step considerably increases the time required to serve a read.
Sequential consistency
So far, we have discussed serializing all reads through the leader. But doing so creates a single chokepoint, limiting the system’s throughput. On top of that, the leader needs to contact a majority of followers to handle a read, which increases the time it takes to process a request. To increase the read performance, we could also allow the followers to handle requests.
Even though a follower can lag behind the leader, it will always receive new updates in the same order as the leader. For example, suppose one client only ever queries follower 1, and another only ever queries follower 2. In that case, the two clients will see the state evolving at different times, as followers are not perfectly in sync (see Figure 10.5).
The consistency model that ensures operations occur in the same order for all observers, but doesn’t provide any real-time guarantee about when an operation’s side-effect becomes visible to them, is called sequential consistency[14]. The lack of real-time guarantees is

Figure 10.5: Although followers have a different view of the system’s state, they process updates in the same order.
what differentiates sequential consistency from linearizability.
A producer/consumer system synchronized with a queue is an example of this model; a producer writes items to the queue, which a consumer reads. The producer and the consumer see the items in the same order, but the consumer lags behind the producer.
Eventual consistency
Although we managed to increase the read throughput, we had to pin clients to followers — if a follower becomes unavailable, the client loses access to the store. We could increase the availability by allowing the client to query any follower. But this comes at a steep price in terms of consistency. For example, say there are two followers, 1 and 2, where follower 2 lags behind follower 1. If a client queries follower 1 and then follower 2, it will see an earlier state, which can be very confusing. The only guarantee the client has is that eventually all followers will converge to the final state if writes to the system stop. This consistency model is called eventual consistency.
It’s challenging to build applications on top of an eventually consistent data store because the behavior is different from what we are used to when writing single-threaded applications. As a result, subtle bugs can creep up that are hard to debug and reproduce. Yet, in eventual consistency’s defense, not all applications require linearizability. For example, an eventually consistent store is perfectly fine if we want to keep track of the number of users visiting a website, since it doesn’t really matter if a read returns a number that is slightly out of date.
The CAP theorem
When a network partition happens, parts of the system become disconnected from each other. For example, some clients might no longer be able to reach the leader. The system has two choices when this happens; it can either:
- remain available by allowing clients to query followers that are reachable, sacrificing strong consistency;
- or guarantee strong consistency by failing reads that can’t reach the leader.
This concept is expressed by the CAP theorem[15], which can be summarized as: “strong consistency, availability and partition tolerance: pick two out of three.” In reality, the choice really is only between strong consistency and availability, as network faults are a given and can’t be avoided.
Confusingly enough, the CAP theorem’s definition of availability requires that every request eventually receives a response. But in real systems, achieving perfect availability is impossible. Moreover, a very slow response is just as bad as one that never occurs. So, in other words, many highly-available systems can’t be considered available as defined by the CAP theorem. Similarly, the theorem’s definition of consistency and partition tolerance is very precise, limiting its practical applications.[16] A more useful way to think about the relationship between availability and consistency is as a spectrum. And so, for example, a strongly consistent and partition-tolerant system as defined by the CAP theorem occupies just one point in that spectrum.[17]
Also, even though network partitions can happen, they are usually rare within a data center. But, even in the absence of a network partition, there is a tradeoff between consistency and latency (or performance). The stronger the consistency guarantee is, the higher the latency of individual operations must be. This relationship is expressed by the PACELC theorem[18], an extension to the CAP theorem. It states that in case of network partitioning (P), one has to choose between availability (A) and consistency (C), but else (E), even when the system is running normally in the absence of partitions, one has to choose between latency (L) and consistency (C). In practice, the choice between latency and consistency is not binary but rather a spectrum.
This is why some off-the-shelf distributed data stores come with counter-intuitive consistency guarantees in order to provide high availability and performance. Others have knobs that allow you to choose whether you want better performance or stronger consistency guarantees, like Azure’s Cosmos DB[19] and Cassandra[20].
Another way to interpret the PACELC theorem is that there is a tradeoff between the amount of coordination required and performance. One way to design around this fundamental limitation is to move coordination away from the critical path. For example, earlier we discussed that for a read to be strongly consistent, the leader has to contact a majority of followers. That coordination tax is paid for each read! In the next section, we will explore a different replication protocol that moves this cost away from the critical path.
Chain replication
Chain replication[21] is a widely used replication protocol that uses a very different topology from leader-based replication protocols like Raft. In chain replication, processes are arranged in a chain. The leftmost process is referred to as the chain’s head, while the rightmost one is the chain’s tail.
Clients send writes exclusively to the head, which updates its local state and forwards the update to the next process in the chain. Similarly, that process updates its state and forwards the change to its successor until it eventually reaches the tail.
When the tail receives an update, it applies it locally and sends an acknowledgment to its predecessor to signal that the change has been committed. The acknowledgment flows back to the head, which can then reply to the client that the write succeeded[22].
Client reads are served exclusively by the tail, as shown in Fig 10.6. In the absence of failures, the protocol is strongly consistent as all writes and reads are processed one at a time by the tail. But what happens if a process in the chain fails?
Fault tolerance is delegated to a dedicated component, the configuration manager or control plane. At a high level, the control plane monitors the chain’s health, and when it detects a faulty process, it removes it from the chain. The control plane ensures that there is a

Figure 10.6: Writes propagate through all processes in the chain, while reads are served exclusively by the tail.
single view of the chain’s topology that every process agrees with. For this to work, the control plane needs to be fault-tolerant, which requires state machine replication (e.g., Raft). So while the chain can tolerate up to N −1 processes failing, where N is the chain’s length, the control plane can only tolerate C
2 failures, where C is the number of replicas that make up the control plane.
There are three failure modes in chain replication: the head can fail, the tail can fail, or an intermediate process can fail. If the head fails, the control plane removes it by reconfiguring its successor to be the new head and notifying clients of the change. If the head committed a write to its local state but crashed before forwarding it downstream, no harm is done. Since the write didn’t reach the tail, the client that issued it hasn’t received an acknowledgment for it yet. From the client’s perspective, it’s just a request that timed out and needs to be retried. Similarly, no other client will have seen the write’s side effects since it never reached the tail.
If the tail fails, the control plane removes it and makes its predecessor the chain’s new tail. Because all updates that the tail has received must necessarily have been received by the predecessor as well, everything works as expected.
If an intermediate process X fails, the control plane has to link X’s predecessor with X’s successor. This case is a bit trickier to handle since X might have applied some updates locally but failed before forwarding them to its successor. Therefore, X’s successor needs to communicate to the control plane the sequence number of the last committed update it has seen, which is then passed to X’s pre-decessor to send the missing updates downstream.
Chain replication can tolerate up to N −1 failures. So, as more processes in the chain fail, it can tolerate fewer failures. This is why it’s important to replace a failing process with a new one. This can be accomplished by making the new process the tail of the chain after syncing it with its predecessor.
The beauty of chain replication is that there are only a handful of simple failure modes to consider. That’s because for a write to commit, it needs to reach the tail, and consequently, it must have been processed by every process in the chain. This is very different from a quorum-based replication protocol like Raft, where only a subset of replicas may have seen a committed write.
Chain replication is simpler to understand and more performant than leader-based replication since the leader’s job of serving client requests is split among the head and the tail. The head sequences writes by updating its local state and forwarding updates to its successor. Reads, however, are served by the tail, and are interleaved with updates received from its predecessor. Unlike in Raft, a read request from a client can be served immediately from the tail’s local state without contacting the other replicas first, which allows for higher throughputs and lower response times.
However, there is a price to pay in terms of write latency. Since an update needs to go through all the processes in the chain before it can be considered committed, a single slow replica can slow down all writes. In contrast, in Raft, the leader only has to wait for a majority of processes to reply and therefore is more resilient to transient degradations. Additionally, if a process isn’t available, chain replication can’t commit writes until the control plane detects the problem and takes the failing process out of the chain. In Raft instead, a single process failing doesn’t stop writes from being committed since only a quorum of processes is needed to make progress.
That said, chain replication allows write requests to be pipelined, which can significantly improve throughput. Moreover, read throughput can be further increased by distributing reads across replicas while still guaranteeing linearizability. The idea is for replicas to store multiple versions of an object, each including a version number and a dirty flag. Replicas mark an update as dirty as it propagates from the head to the tail. Once the tail receives it, it’s considered committed, and the tail sends an acknowledgment back along the chain. When a replica receives an acknowledgment, it marks the corresponding version as clean. Now, when a replica receives a read request for an object, it will immediately serve it if the latest version is clean. If not, it first contacts the tail to request the latest committed version (see Fig 10.7).

Figure 10.7: A dirty read can be served by any replica with an ad-ditional request to the tail to guarantee strong consistency.
As discussed in Leader election (lesson 03.05), a leader introduces a scalability bottleneck. But in chain replication, the data plane (i.e., the part of the system that handles individual client requests on the critical path) doesn’t need a leader to do its job since it’s not concerned with failures — its sole focus is throughput and efficiency. On the contrary, the control plane needs a leader to implement state machine replication, but that’s required exclusively to handle the occasional failure and doesn’t affect client requests on the critical path. Another way to think about this is that chain replication reduces the amount of coordination needed for each client request. In turn, this increases the data plane’s capacity to handle load. For this reason, splitting the data plane from the control plane (i.e., the configuration management part) is a common pattern in distributed systems. We will talk in more detail about this in Control planes and data planes (lesson 04.10).
You might be wondering at this point whether it’s possible to replicate data without needing consensus[23] at all to improve performance further. In Coordination avoidance (lesson 03.07), we will try to do just that.
References
- “In Search of an Understandable Consensus Algorithm,” https://raft.github.io/raft.pdf
- “Paxos Made Simple,” https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
- “Finite-state machine,” https://en.wikipedia.org/wiki/Finite-state_machine
- In practice, there are ways to reduce the number of messages required for this step.
- “Consensus,” https://en.wikipedia.org/wiki/Consensus_(computer_science)
- “Paxos made Abstract,” https://maheshba.bitbucket.io/blog/2021/11/15/Paxos.html
- We will define what linearizability means in the next section. 8nor want to, since it’s very challenging to get right; see “Paxos Made Live - An Engineering Perspective,” https://static.googleusercontent.com/media/research.google.com/en//archive/paxos_made_live.pdf
- “etcd: A distributed, reliable key-value store for the most critical data of a distributed system,” https://etcd.io/
- “Apache ZooKeeper: An open-source server which enables highly reliable distributed coordination,” https://zookeeper.apache.org/
- “Consistency Models,” https://jepsen.io/consistency
- “Linearizability,” https://jepsen.io/consistency/models/linearizable
- For example, this is the guarantee you would expect from a coordination service that manages leases.
- “Sequential Consistency,” https://jepsen.io/consistency/models/sequential
- “Perspectives on the CAP Theorem,” https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf
- “A Critique of the CAP Theorem,” https://www.cl.cam.ac.uk/research/dtg/www/files/publications/public/mk428/cap-critique.pdf
- “CAP Theorem: You don’t need CP, you don’t want AP, and you can’t have CA,” https://www.youtube.com/watch?v=hUd_9FENShA
- “Consistency Tradeoffs in Modern Distributed Database System Design,” https://en.wikipedia.org/wiki/PACELC_theorem
- “Consistency levels in Azure Cosmos DB,” https://docs.microsoft.com/en-us/azure/cosmos-db/consistency-levels
- “Apache Cassandra: How is the consistency level configured?,” https://docs.datastax.com/en/cassandra-oss/3.0/cassandra/dml/dmlConfigConsistency.html
- “Chain Replication for Supporting High Throughput and Availability,” https://www.cs.cornell.edu/home/rvr/papers/OSDI04.pdf
- This is slightly different from the original chain replication paper since it’s based on CRAQ, an extension of the original protocol; see “Object Storage on CRAQ,” https://www.usenix.org/legacy/event/usenix09/tech/full_papers/terrace/terrace.pdf .
- required for state machine replication