Data Replication Design Spectrum

Failure Masking vs Failure Detection

When designing a distributed database, one needs to choose a replication algorithm to replicate data across machines. Consistent data replication algorithms fall across two categories: those designed to quietly tolerate failing replicas (failure masking), and those necessitating explicit reconfiguration around identified failures (failure detection). This post mounts the argument that these are just two opposite points on a spectrum of design possibilities in between. We’ll be taking a look at three points^[1] in particular: quorum-based leaderless replication for failure masking algorithms, reconfiguration-based replication for failure detection algorithms, and leaderful consensus as the most well-known set of replication algorithms that blend the two. [1]: Don’t forget about the idea that there are more valid points along the spectrum than just these three!

There isn’t one universally optimal replication algorithm to use. Compiling together data on what replication algorithm is used by OSS, Proprietary, and internal-only Proprietary databases, we see a distribution of: ^[2][2]: The chart is weighted by the number of database systems, whereas a more realistic metric would be something that accounts for popularity such as the number of deployed machines or size of managed data. With cloud vendors preferring leaderful replication by a large extent, a popularity-weighted chart would likely be even more heavily skewed towards leaderful replication. However, there’s no way I can get that information to present such a graph.

So leader-based consensus, such as Raft, is indeed popular, but by no means the only valid choice. But why the differences? Why isn’t there one correct choice? What factors drove different databases to choose different solutions to their replication needs? Does Raft’s popularity correspond to its general superiority?

Different replication algorithms have different characteristics. This post breaks down each replication algorithm into its resource efficiency, availability, and latency. For resource efficiency, we’ll be looking at the question: post-replication, how much of the storage capacity and read/write throughput remains? As the counterpoints to resource efficiency, we’ll also be looking at availability (given the loss of a random machine, what’s the chance that a user will observe a transient service disruption), and latency (how many RTTs for a read or a write to complete).

With such an analysis, one would expect HN/Twitter/etc. to have replies of the form "But your analysis is invalid because you didn’t account for this replication algorithm optimization!". And so to preempt any such replies, each section produces the analysis for both the most classic, unoptimized form of the replication algorithm, and also walks through improved designs or potential optimizations that can be applied and how they affect the replication algorithm’s resource efficiency, availability, and latency. Correspondingly, this post is a sizable read. There is an excessive list of references at the bottom of this post which all link to the Google Scholar search result for each paper.

There’s also a significant scope restriction to keep this post focused and manageable. Only consistent data replication algorithms will be examined, and "consistent" always means [Linearizability] here. There are a significant number of meaningful consistency levels weaker than linearizable, however, any divergence from linearizability immediately disqualifies the algorithm or optimization from examination below. Replication algorithms with a greater focus on availability are valid and important, and an area of significant research, but have an entirely different set of trade-offs and use cases.

Lastly, this post lives purely in the land of theory. A real-life system implementing a "less efficient" replication algorithm can have higher observed resource efficiency than an implementation of a "more efficient" replication algorithm. Implementation-level choices matter tremendously. In the "write bandwidth efficiency" above, we’re only concerning ourselves with the network bandwidth. Storage efficiency partly captures the disk write bandwidth efficiency, as storing 3 copies of data requires writing 3 copies of data. However, this largely discounts the impact of storage engine write amplification, and it’s tremendously more likely that the bottleneck for writes will be the disk and not the network.^[3] However, we’re discussing the theoretical write throughput trade-offs only, because write network bandwidth throughput illustrates how replication topology matters for efficiency. [3]: Storage engine write amplification tends to be anywhere from 10x-100x depending on the workload and data structure being used. Disk throughput has steadily improved over time, but disk throughput isn’t 10x-100x faster than network throughput, and thus it’s very likely the bottleneck for writes.

Failure Masking: Quorums

Replication algorithms that rely on failure masking for all of their replicas use quorums, so that a majority of replicas may make progress despite a minority of failed replicas of working replicas. The [Paxos] family of consensus protocols are well-known quorum-based replication algorithms. However, achieving consensus is not required to replicate data consistently, and simple majority quorum-based algorithms such as [ABD] are in this category. Quorum-based replication is used in industry by systems like [Megastore], [PaxosStore], and [Cassandra].

While leaderless [Paxos] and [ABD] differ in terms of consistency guarantees^[4], they’re very similar in terms of resource efficiency. All replicas store a full copy of all the data. Reads and writes are broadcast to all replicas and can make forward progress with only a majority of responses. The need for a majority largely characterizes failure masking replication algorithms, as they require \(2f+1\) replicas to tolerate \(f\) failures.^[5] [4]: See Murat Demirbas’s Is this consensus? for a refresher on consensus versus not. [5]: One might expect a mention of [Flexible Paxos] here, but it doesn’t change the optimal number of replicas for a given \(f\) failure tolerance. Flexible Paxos notes that \(|Q1| + |Q2| > N\) and so a minimal \(Q1\) is \(|Q1| = N - |Q2| - 1\). We require \(|Q2| = f+1\), and so for \(f=2\), that’s still \(|Q1| = 3\) and \(|Q2| = 3\).

Quorums

Our analysis is consistently targeting \(f=2\), and thus for quorums, this means we’ll be looking at the efficiencies of a replication group of \(2f+1 = 5\) replicas.

For storage efficiency, all replicas store a full copy of the data by default, and thus 1/5th of the total storage capacity is available post-replication. There are a wide set of storage optimizations, and all have seen little adoption in industry. [Witness Replicas] permit removing the full copy of the data from a minority (2/5ths) of the replication group, with that minority instead only storing the version number for each replicated value. However, this comes at the cost that a read cannot always successfully be completed if the most up-to-date value is "known" only by witnesses. This is effectively unavailability for even some types of network partitions and thus removes it from consideration for this analysis.

Erasure coding^[6] is instead an attractive possibility for reducing storage costs, as it would encode the data such that any three copies could reform the original data, and the total storage used across all 5 replicas would be the equivalent of 1.67 full copies of the data. Its usual cost of having to read encoded values from three replicas to decode into the full, correct result is essentially free, as those reads are required by the quorum logic anyway. [RS-Paxos] examined applying erasure coding to Paxos log entries, and concluded that space savings can only be obtained if fault tolerance is sacrificed. However, I believe the ideas presented in [Erasure Coded Raft] should apply equally to leaderless consensus as well, so we’ll assume erasure coding is feasible.^[7] HRaft adaptively changes the erasure code based on the number of available replicas, which brings the storage efficiency to 33% (a \(1+2\) code) when 3 replicas are available, to 60% storage efficiency (a \(3+2\) code) when all 5 replicas are available. Pessimistically, one must likely provision for 33% storage efficiency, but if failures can be repaired quickly, closer to the 60% storage effiency is likely. [6]: And see the Erasure Coding in Distributed Systems post on this blog. [7]: There are a number of issues being handwaved away here. It’s unclear how to apply operations from the log when any one replica only has the erasure coded values stored. [Erasure Coded Raft] falls back to full data replication when a single node stops responding, and this was improved in [Erasure Coded HRaft]. Erasure coding in consensus has not received a significant amount of academic attention, and so I’m hopeful that other deficiencies can likely be similarly explored and improved. This is mostly to show the theoretical maximum in an ideal world and less a claim that it’s what should be implemented.

Majority quorums^[8] do a simple broadcast for both reads and writes, which earns a uniform 20% read bandwidth efficiency and 20% write bandwidth efficiency. Applying the erasure coding ideas above to the Paxos log entries could bring the write efficiency from 20% to 33%, and reading erasure coded data also brings the read efficiency from 20% to 33%. It is not required for majority quorums nor Paxos to always immediately send read requests to all replicas, however, and optimistically choosing to only read from a minority can allow for a read throughput of 33% when all replicas are available, at the cost of increased tail latency and degradation of latency and throughput if a replica fails. Combining this minimal majority reads with erasure coding allows for 55% read throughput efficiency. [8]: There are many ways of arranging quorums that aren’t a simple majority, and all the variations affect the read and write throughput calculations. It used to be more popular to allow for tuning the read quorum and write quorum sizes, but many of those systems have since died out, such as Riak. More esoteric quorum setups exist, but they aren’t commonly used and thus out of scope for this post. [Quoracle] is a fun read on alternative schemes though.

A major advantage of leaderless, quorum-based algorithms is the lack of dependence on a leader. All failures can be masked, with no need to detect or reconfigure around the failure. All leaderless replication algorithms earn a perfect 0% chance of unavailability on random node failure.

Though majority quorums has been repetitively stated to be a simple 1RTT broadcast for both reads and writes, that’s a bit of an oversimplification. For majority quorums to be linearizable, this post’s threshold for "consistent", [Read Repair] must be used to write back the most recent value if replicas diverged, thus earning a worst-case 2RTT for reads. Majority quorums are thus the inverse of Paxos, which always has two rounds of broadcasts for writes, and reads are a one-round broadcast. [FastPaxos] permits performing writes in one-round if a supermajority of replicas accept.

An implementation of majority quorums typically uses some form of a Last Writer Wins timestamping scheme, so that if a read returns three distinct values, it’s possible to choose the "most recent" value as the correct read result. [ABD] uses a logical clock, and what’s referred to as just "majority quorums"^[9] here uses a physical clock. ABD ensures that its writes have a higher logical clock than all existing values by first reading the existing values, thus earning it 2RTT for writes, and does a similar read repair step after reads to earn it 2RTT for reads also. Majority quorums with physical timestamping can use its local time to skip the first phase of ABD’s write protocol, so its writes are just 1RTT. [9]: If it were not for the immense popularity of physically timestamped majority quorums, due to its use in systems like Cassandra, I would have greatly preferred to present ABD as the "default" majority quorum algorithm. For learning purposes, at least I’d suggest starting with it instead.

This table presents that the difference between majority quorums/ABD and Paxos is one of read and write latency, but again, don’t forget that there’s a very significant difference in data consistency between the two replication algorithms. It’s also not strictly a one-or-the-other. [Gryff] is an example of a design uses [ABD] for reads and writes, and [EPaxos] for read-modify-writes. Although Erasure Coded Paxos outwardly appears optimal across several metrics, it isn’t an algorithm that actually exists neither in academia nor in industry.

One of the largest concerns around deploying [Paxos] to production is its vulnerability to livelock under contention. Contending proposals can force both to retry the writes, mutually preventing forward progress, and so contention on a single replicated item is to be avoided if possible. [Megastore] is very contention prone as every proposal is trying to target the next slot in the replicated log, and thus they tried to include a weak leadership optimization. [PaxosStore] deployed only to geographically close replicas to minimize the latency from proposing to accepting, thus minimizing the window for proposals to conflict. [EPaxos] focuses on allowing concurrent updates to distinct entities, and only ordering conflicting proposals. [CASPaxos] avoids a log entirely, and thus trivially allows concurrent updates on distinct items. [Tempo] and [Accord] assign client-generated timestamps to all requests so that all replicas process requests in a deterministic order, but at the cost of a fixed increase in latency to wait out clock skew bounds before processing any request. If a use case requires handling potentially many concurrent update attempts to the same item, then it’s possible that leaderless consensus is not a good choice of replication algorithm.

Failure Detection: Reconfiguration

Failure detection-based replication algorithms have a chosen set of replicas in a replication group which must be live for the algorithm to make progress. On detected replica failure, these algorithms reconfigure the replication group to exclude the failed replica and include a new, live replica. Rather than allow replicas to be failed, a failed replica is evicted from the replication group. All replicas are either working, or will be removed.

All reconfiguration-based replication protocols share certain attributes. All writes are always sent to all replicas, and a single replica will always have a full and consistent snapshot of the replicated data. This means reads may be served by a single replica. Additionally, only \(f+1\) replicas are needed to tolerate \(f\) failures, as the one remaining replica will be sufficient to re-replicate the data. However, due to only having \(f+1\) replicas, there is a consistent theme in that all algorithms examined are not consensus. This also means that they cannot solve consensus problems, such as deciding which replicas are responsible for a shard of data, or which node is the primary. They all rely on an external consensus service to help with those issues. Think of this as a control plane / data plane split: there’s one instance of a consensus service in the control plane orchestrating the small amount of metadata deciding which replicas are in which replication groups responsible for which shards of data, and the horizontally scalable data plane replicates each shard of data within its assigned group.

There are two shapes of algorithms in this class of failure detection-based replication protocols: those in which inter-replica communication is done as a broadcast, and those in which it is done as a linear chain. Broadcast-based replication is well known as [Primary-Backup]^[10] replication, which we’ll be examining through the lens of [PacificA] which has more of an emphasis on the reconfiguration support, and [Hermes] as a more recent improvement on broadcast-based replication. For chain-based replication, we’ll be examining the original [Chain Replication], and [CRAQ] as its more recent improvement. [10]: Some implementations of primary-backup do asynchronous replication to all replicas, and those are excluded from consideration in this entire post because it’s not consistent replication. Some implementations of primary-backup allow waiting for a subset, but not all, of the backups to acknowledge a write from the primary, and this is excluded from consideration in this section because that’s failure masking for backups! Specifically, that’s a Hybrid replication algorithm, which is examined in the section below. Only fully synchronous primary-backup replication is in scope for this section.

In academia, many of the ideas in reconfiguration-based replication are rooted in [Virtual Synchrony]. Evolving Paxos into a reconfigurable primary-backup replication was examined in [Vertical Paxos II]. In industry, [Kafka] and [FoundationDB] use different variants of broadcast-based replication, and Apache Pegasus uses [PacificA]. Nearly all of the chain replication databases in industry seem to have died out, as hibari was one of the last but appears abandoned now, and [HyperDex] almost become a startup. Reconfiguration-based replication algorithms are frequently found in block and blob storage products^[11] where the decreased number of replicas means significant cost savings. [Ceph] implements both broadcast and chain-based replication. [GFS] implements broadcast-based replication, and [HDFS] similarly follows suit. [11]: That’s not to say that all such storage products do, as for example [Alibaba EFS] and [PolarFS] use leaderful consensus, but just that reconfiguration-based replication is comparatively a much more frequently chosen solution for replication in the different domain. It’s databases specifically that are more aligned itself around leaderful consensus.

Our analysis is consistently targeting \(f=2\), and thus for quorums, this means we’ll be looking at the efficiencies of a replication group of \(f+1 = 3\) replicas.

In reconfiguration-based replication algorithms, all three replicas store a full copy of the data, yielding a 33% storage efficiency for all four algorithms. Unlike the quorum systems, there’s no inherent opportunity for erasure coding. When the number of replicas is \(f+1\), we expect that a single alive replica can serve reads for all of its data. Applying erasure coding requires increasing the set of replicas (while the erasure coding maintains the same aggregate storage efficiency), and then choosing the number of parity blocks to equal the number of failures one wishes to be able to recover from. This effectively applies quorums for failure masking, though at the level of erasure coding rather than at the level of the replication algorithm. Such a design is common in blob storage systems, but not in distributed databases, except for YDB.

With [Chain Replication], only the tail of the chain is allowed to answer read requests, which it does with 1RTT means a read bandwidth efficiency of 33%. [CRAQ] permits any node to answer reads, and thus it gets 100% read bandwidth efficiency, but if there’s an ongoing write to the same key, the replica has to wait to hear back from the tail replica that the write was completed before it may respond to the read.^[12] Both [PacificA] and [Hermes] are capable of serving reads from all replicas, so they gain a 100% read bandwidth efficiency. [PacificA]'s primary can serve reads in 1RTT and the secondaries in 2RTT (as they must check with the primary). [Hermes] allows serving reads in 1RTT (but possibly requires waiting for up to 1RTT while a write finishes). If we wished to strictly ensure 1RTT reads, one could use [PacificA] and decline to read from the secondaries. [12]: This means CRAQ is optimal for 100% read or 100% write workloads, and degrades read latency in between, which is a trade off I haven’t seen in any other replication algorithm. It’d be ideal for large data loads (100% writes), followed by an online serving workload (100% reads), and could serve reads with degraded latency as a data load is ongoing.

Both [Chain Replication] and [CRAQ] have 33% write bandwidth efficiency, as one replica accepts writes and each replica sends to only one more replica so there’s no further bottleneck on outgoing bandwidth. The chain means that writes in both take 2.5RTT to complete. [PacificA] only allows the primary to accept writes, and it must broadcast to two replicas, yielding a 16% write bandwidth efficiency. [Hermes] allows any replica to accept writes, and receives the replication broadcast from the other two replicas. This balances the incoming and outgoing bandwidth requirements to allow 33% write bandwidth efficiency. Both broadcast-based replication algorithms take 2RTT for writes.

Unavailability is the weak point of reconfiguration-based systems. In all examined systems, any failure requires detection (generally through a heartbeat timeout), and then a membership view change to a new set of non-failed replicas. Any replica failure has a 100% chance of causing a client-visible spike in latency due to no requests being processed while the heartbeat times out and the view change protocol runs.

The end result shows that [CRAQ] is a better version of [Chain Replication], and [Hermes] is a better version of [PacificA]. To optimize for latency, choose [Hermes]. To optimize for throughput, choose [CRAQ].

It’s important to note that the surface-level simplicity of replication algorithms rooted in [Virtual Synchrony] instead hold their complexity in two nontrivial topics: group membership and failure detection.

The focus on how to change a replication group’s members is not unique to reconfiguration-based protocols. [Reconfiguring Replicated Storage Tutorial] uses [ABD] as its example protocol to describe safe reconfiguration. [Viewstamped Replication] models leader election as a reconfiguration. However, reconfiguration-based replication algorithms are unique in that they use reconfiguration as their only way to handle replica failures. An external service being the authority on what replicas are or are not part of a given replication group adds an additional layer of complexity that isn’t present in consensus systems. [PacificA] has a great discussion of this topic.

Failure detectors have their own rich history that warrants a separate post sometime. The simplest failure detector is a periodic heartbeat with a timeout. An ideal failure detector is both accurate in detecting when a component has failed, and reactive in minimizing the time between the failure and the detector identifying it. [Localizing Partial Failures] pitches specializing failure detection to each individual component/behavior/RPC endpoint of a system. [Falcon] presents a compelling argument that involving of multiple layers of a system can provide a faster reaction to failures than heartbeats alone. The best failure detection is likely to be tightly integrated with both the service being monitored and the environment the service runs in.

Furthermore, failure detection is not just for crash-stop failures. One needs a very precise definition of what "functioning correctly" means. If the disk is failing and its throughput drops by 90% or if there’s a bad switch causing packet loss and thus TCP throughput drops significantly^[13], that’s not a "correctly functioning" machine, and one would wish to reconfigure around the failure. [Gray Failure Achilles Heel] discusses gray failure issues in more detail. [Limping Hardware Tolerant Clouds] offers more concrete examples. Dan Luu has written about this as well. Detecting "slow" is significantly more difficult than detecting "failed", with an approach to doing so illustrated in [Perseus]. [13]: The most frequent singular cause of times I’ve been paged awake by a service in the middle of the night has been some networking equipment deciding to drop 1% of packets, and TCP thus slowing down to approximately dial-up speeds. Heartbeats could still be sent, so the service wasn’t "unavailable", but it sure wasn’t working well.

Hybrid: Leaders

Leaderful consensus is what is generally brought to mind when one mentions "consensus". It is best known as [Raft], [MultiPaxos]^[14] or [ZAB], and exemplified by distributed databases such as [CockroachDB], [TiDB] and [Spanner], or configuration management systems such as [Paxos Made Live] and [Zookeeper]. (Among many other high-quality, production systems.) [14]: Though for learning about Multi-Paxos, I’d significantly recommend reading [Paxos Made Moderately Complex] and [MultiPaxos Made Complete] instead.

In the simplest Raft implementation, one replica is nominated as a leader. All operations are sent to the leader, and the leader broadcasts the replication stream to its followers. Raft tolerates \(f\) failures using \(2f+1\) replicas. Thus, at most two of five replicas are permitted to be unavailable. Throughout this section, I will be using "Raft" and "Multi-Paxos" interchangeably. The differences between the two algorithms (discussed in detail in [Paxos vs Raft]) do not affect resource efficiency, throughput or latency.

Our analysis is consistently targeting \(f=2\), and thus for quorums, this means we’ll be looking at the efficiencies of a replication group of \(2f+1 = 5\) replicas.

All replicas store a full copy of the data, and thus 1/5th of the total storage capacity is available post-replication. The storage optimizations available are similar to what was discussed for leaderless replication. [Witness Replicas] permit removing the full copy of the data from a minority (2/5ths) of the replication group, and the leaderful consensus variant of witness replicas is always able to serve reads from the leader even with a simple majority of replicas alive. Note though, that removing storage means that witness replicas can’t serve reads. I’m only aware of EnterpriseDB Postgres Distributed and (Cloud) Spanner implementing support for witness replicas as part of Raft and Multi-Paxos, respectively. The other possible direction for storage efficiency improvement is [Erasure Coded Raft] which again allows between a 33% and 60% storage efficiency depending on replica availability. As 99% of the Raft implementations one might ever encounter have a storage efficiency of 1/5th, that is the value that will be used for storage efficiency for the rest of the analysis.

Naive Raft has the leader serve all reads, yielding 1/5th read throughput at 1RTT^[15]. [Linearizable Quorum Reads] pitches the idea that one can also perform linearizable reads by reading from a majority quorum of the non-leader replicas, and implementing this brings Raft to 2/5ths read throughput (1/5th from the leader + 1/5th aggregate across the followers). [Paxos Quorum Leases]^[16] pitches the idea of electing a leader and two more replicas to which the leader must replicate all commits, thus enabling those required followers to serve reads to clients with no further coordination, which brings Raft to 3/5ths read throughput (1/5th for each leader and lease holder) at the cost of some tail latency on writes and increased risk of unavailability on failure. [Consistent Follower Reads]^[17][18] allows any follower to serve read requests by first checking with the leader for the most recently applied position in the replication log, allowing for 5/5ths read throughput at the cost of read latency increasing to 2RTTs. Each has their own set of trade-offs, but we’ll use 5/5ths as Raft’s optimal read throughput, which is realistic given that follower reads have been implemented in production systems such as Spanner and TiKV. [15]: Leaders may not trivially serve read requests, otherwise, no-longer leaders risk serving stale results. Leaders must either wait for the next quorum reply to confirm leadership, or use time-based leader leases to exclude potential concurrent leaders. We assume the latter, as it is commonly implemented. [16]: [Paxos Quorum Leases] is an example of a replication algorithm that’s a hybrid of failure masking and failure detection, but strikes a trade-off more towards failure detection than where Raft sits. [17]: "Follower reads" can be colloquially used to mean any form of reading from followers. Cockroach in particular uses a number of tricks around timestamps to allow replicas to locally serve data. What they call follower reads allows replicas to serve reads for older versions. Global tables support local, consistent reads by writing in the future. My focus is specifically on linearizable reads which don’t overly compromise writes, and that specific cockroach feature isn’t yet implemented. But I highlight all of this to show that there’s ways to deliver increased read throughput when bending other constraints or leaning on the semantics of other components (e.g. hybrid clocks). [18]: There’s frustratingly no good citation for follower reads that contact the leader to keep their replies consistent and linearizable. [Consistent Follower Reads] links to the Raft thesis, which mentions it in passing, but I can’t find a paper which details the optimization well. PingCAP’s blog post on implementing it is a more detailed overview.

In classic Raft, all proposals go to the leader, and then the leader broadcasts the proposals to all followers. This means Raft is first constraining to utilizing only \(1/(2f+1)\) or 1/5th of the available incoming bandwidth. Then the bottleneck becomes the leader’s outgoing bandwidth, further reduction of \(1/2f\), so 1/4th. This means a write bandwidth efficiency of \(1/(4f^2 + 2f)\) or 1/20th. There have been ways discussed to scale the write bandwidth. [Pull-Based Consensus] presents an argument that a fixed topology is not needed, replicas can fetch from other replicas, and thus even a linear chain of replicas could work. [Scaling Replication] shows another view that the work of broadcasting to all replicas can be delegated to other replicas. [Commutative Raft] presents a different approach, in which clients are allowed to directly send to all replicas (avoiding the leader bottleneck), and the leader only arbitrates ordering when there are conflicts (and saving 1RTT when there aren’t). Of these, only [Pull-Based Consensus] is implemented in industry, but I’m not aware that even MongoDB itself runs in a linear chain configuration. (It’s mostly about saving WAN costs.) [Erasure Coded Raft] applies to the Raft log as well, providing a 5/3rds increase in bandwidth. However, 1/20th is still the write bandwidth efficiency that almost any real Raft implementation will exhibit.

Many optimizations strike different points along the Pareto curve of latency versus throughput, so I’ve outlined them all below. Combinations of them form the optimal trade-offs for latency or throughput, so I’ll also note a "Latency Optimized Raft" as [Linearizable Quorum Reads] + [Commutative Raft], and a "Throughput Optimized Raft" implementation as the effect of combining [Consistent Follower Reads], [Pull-Based Consensus] in a linear chain of replicas, and [Erasure Coded Raft].

Databases built around Multi-Paxos generally aren’t picking just one optimization to implement. The exact tradeoff of reads versus writes and throughput versus latency is specific to each individual use case. Thus, databases tend to implement multiple optimizations and allow users to configure specific database deployments or tables within the database for how they wish for reads and writes to be done. The optimizations covered above are also just those that affect resource efficiency. There’s a tremendously larger set of published optimizations focusing on performance when geographically distributed, enhancing failure recovery, managing replicated log truncation, etc.

In the failure detection section, we discussed the complexity of failure detection-based replication algorithms is often centered around group membership changes and (gray) failure detectors. Safe group membership changes is a topic occasionally discussed in consensus papers. Heidi Howard’s distributed consensus reading list has a whole section on it. Comparatively, the need for a comprehensive failure detector for the Raft leader is often overlooked. Notably, however, [MultiPaxos Made Complete] gives the topic a proper treatment.

One of the major points of this post is that a five replica Raft group is 1/5th failure detection + 4/5ths failure masking. However you feel about reconfiguration and failure detection-based distributed system design is exactly how you should feel about the leader in Raft/Multi-Paxos. Some folk really don’t like systems that rely on failure detectors and have a reconfiguration step during which the partition is unavailable, and that’s okay. But any failure pattern you might have thought of and felt concerned about while reading the failure detection section applies precisely the same to the leader in Raft. If it seems unacceptable that chain replication has unavailability during reconfiguration when any replica fails, the exact same unavailability during reconfiguration happening to Raft when the leader fails should also feel unacceptable.

Comparison

There isn’t a single way to do a direct, fair, apples-to-apples comparison of different systems and optimizations across the different replication algorithms. We’ll first look at the most popular/common choice for each category, and then take a look at the latency-optimal, throughput-optimal, and storage-optimal choices.

For the popularity-based rankings, we’ll use "Paxos" from the Quorums section, "PacificA" from the Reconfiguration section, and "Consistent Follower Reads" from the Hybrid section:

Using Paxos requires compromising read throughput. PacificA delivers superior write bandwidth and similar latencies to Raft, with the trade-off being a higher chance of unavailability versus more replicas required, respectively.

For our latency-optimized comparison, "Fast Paxos" is the quorum-based replication algorithm which offers the possibility for 1RTT reads and writes. "PacificA (Primary-only)" is the latency optimal reconfiguration-based algorithm. Linearizable Quorum Reads is our hybrid selection. (And note again that all primary/leader-based replication algorithms depend on leader leases and clock synchronization to be able to serve 1RTT reads from the primary/leader.)

Reveals an interesting effect that Reconfiguration-based algorithms have lower read throughput on the lowest latency variant than either quorum-based or hybrid replication schemes.^[19] [19]: I don’t think a similar optimization which reads only from the backups would be safe unless commits were made durable on the primary first before replication, which would likely cost more than an extra write RTT. Would be happy to find out I’m wrong!

For our throughput-optimized and storage-optimized variant analysis, our choices are actually the same! It’s the erasure coded variant of each replication algorithm. (Except for storage-optimized reconfiguration-based replication algorithm, we could arbitrarily choose any, as they’re all the same, but CRAQ is the correct choice for throughput-optimized.)

We see that erasure coding just brings each quorum-based algorithm to the resource efficacy of the reconfiguration-based algorithm in its worst case, but still requires 66% more replicas than a reconfiguration-based algorithm. A 5-replica erasure coded variant of CRAQ permits always being able to obtain the 60% storage efficiency. This leaves reconfiguration-based replication algorithms and Throughput Optimized Raft as the most cost-effective to deploy for use cases bottlenecked on storage or throughput. Throughput Optimized Raft gives a lower chance of unavailability on failure, whereas reconfiguration-based replication is significantly less complex to implement and has a lower minimum number of replicas.

There are a number of other resources to consider in a real environment other than what was presented in this post. CPU, memory, disk IOPS, etc., are all finite resources, which were not discussed, but if those become the limiting factor for performance, then that is the bottleneck and efficiency metric to be mindful of. As one example, [Scalable But Wasteful] notes that constrained CPU usage can lead [MultiPaxos] (and probably [PacificA]) to have 2x more throughput than [EPaxos]. If throughput is what determines the amount of hardware you need to buy/rent for your database deployment, and the hardware is CPU constrained, then this is a more impactful efficiency to keep in mind than anything discussed above.

There are also other deployment environment considerations. The analysis above considers all round-trip times equal, which is not the case in geographically distributed deployments. Cross-datacenter network links are notoriously prone to random packet delays or loss, making any form of quorums more attractive for minimizing tail latency. All RTT calculations above have considered a request as starting from a client, but if a client is always co-located with the primary or leader in a datacenter, that RTT is comparatively free, and only the round trips across datacenters or regions are worth optimizing. One should tailor the choice of replication algorithm to also best suit the deployment environment.

But after all this analysis, does Raft’s hybrid approach to failure handling deliver some superior advantage that justifies its popularity? Not really. Quorums deliver superior availability, but at the cost of read throughput efficiency (and livelock for Paxos, or inconsistency for ABD). Reconfiguration delivers superior resource efficiency, but at the cost of availability. Raft has unwaveringly moderate results in each comparison. Instead, its main strength is that its hybrid nature avoids the major pitfalls on both sides: it won’t livelock under contention, and it can mask some failures. If those are what the use case needs, then it’s a great fit. Otherwise, consider implementing a different approach.

References

References as BibTeX

See discussion of this page on Reddit, HN, and lobsters.