Categorizing How Distributed Databases Utilize Consensus Algorithms
Categorizing How Distributed Databases Utilize Consensus Algorithms
Distributed databases generally fall into two camps when it comes to architectures for maintaining high availability (HA) [1]. Both architectures are used by many successful production systems, but each has very different trade-offs. I couldn’t find anyone who had studied these trade-offs, which is what motivated this article. I don’t know of standard/well-known names for the two HA approaches, so I’m going to refer to them as “Consensus for Metadata” (CfM) and “Consensus for Data” (CfD). As their names suggest, both designs use a consensus algorithm (Raft, Paxos, etc.) to handle failures and store data, but they differ in the type of data that is managed by consensus. To start, I’ll give an overview of the two architectures ignoring most implementation details since those differ in each database and don’t impact the architecture’s trade-offs for the most part. I’ll assume only that we are dealing with data that is sharded and has several copies of each shard spread across hosts in a distributed database.Full disclosure, I’ve spent many years working on a CfM database (MemSQL/SingleStore), so I’m more familiar with this design. I’ve studied open source CfD databases along with their publicly available papers and documentation, but have much less personal experience with them. This may skew my opinion on this topic a bit.Consensus for Metadata (CfM)Figure 1 one shows the CfM architecture. This design is used by systems such as Apache Kafka, FoundationDB and SingleStoreDB/MemSQL among others. CfM stores high level metadata about the state of the cluster (i.e., which hosts are online vs offline, which shards are stored on which hosts, etc.) in a centralized set of coordinator nodes (in green on the diagram). The coordinator nodes themselves don’t typically store any of the user’s data (i.e., they don’t store shards), just metadata. The coordinators use a consensus algorithm to replicate metadata changes and keep metadata available to the cluster if coordinators node fail. The user data itself in CfM is replicated using primary — secondary replication algorithms specific to each database system (synchronous replication of a transaction log typically). These replication algorithms only worry about transmitting data, and not about what how to elect a new primary if a primary fails (the blue replication arrows in figure 1). When a data node becomes unhealthy the centralized coordinator is responsible for electing a new primary for this nodes shards from its replica’s(triggering a failover) and updating its cluster metadata appropriately. CfM separates replication of data from the algorithms used for election/failover. This involves a protocol between the data nodes and the coordinators so the coodinators know which replica’s are safe to failover to (have all committed data).Figure 1: Consensus For MetadataConsensus for Data (CfD)Figure 2 shows the high level architecture of CfD. It uses consensus replication to store user data and keep it available. The consensus algorithm running on the data nodes is responsible for electing a new primary for each shard if a data node dies. Google Spanner and modern MongoDB are the most popular examples of this design. CfD databases may or may not have a centralized coordinator nodes for other reasons (ie., running DDL operations like adding/removing nodes), but this coordinator won’t be responsible for acting on data node failures.Figure 2: Consensus for DataBelow is a non-exhaustive list of examples of each type of system (to the best of my knowledge).Consensus for Data examples:SpannerMongoDBDynamoDBCosmosDBCockroachDBTiDBYugabyteRedpandaConsensus for Metadata examples:Apache KafkaFoundationDB (and thus Snowflake which uses FoundationDB for metadata)MemSQL/SingleStoreClickhouseElasticSearchRedshiftPlanetScaleCitusDBAWS AuroraAzure SQL HyperscaleNeon (for WAL writes) (*)HDFSAs is common in software engineering, these designs come with different trade-offs. I haven’t seen the trade-offs written down in detail anywhere, so I’ll take a stab at writing them down here. Note that some of these are my opinion as someone who has spent >10 years building distributed databases and close to 20 years building databases in general. I try to back my opinions up with examples as much as possible, but others may disagree with some of my claims none the less.(*) Neon uses Paxos to replicate WAL, but Jeremy Schnedier pointed out on twitter that it doesn’t use Paxos for leader elections. I originally had them as CfD but moved them to CfM based on this observation from Jeremy. There is more of design spectrum here as Alex Miller recently wrote about in depth, but for the purposes of this blog the centralized coordinator Neon uses (Kubernetes) to spin up a new leader makes it more CfM then CfD in my opinion.Advantages of Consensus For MetadataCfM needs to store fewer copies of user data to achieve a given level of durability compared to CfD. Consensus algorithms (typically) need a majority to elect a new leader (or to commit new data), which means to survive f failures, you need 2f+1 copies of the data (i.e., to survive 2 node failures, consensus algorithms need 5 copies of the data). With CfM to survive f failures you only need f + 1 copies of the data (see next bullet point. CfM allows a lot of flexibility on the commit quorum used — some systems may use different quorums). This means CfM has almost 50% lower storage and network costs compared to CfD — it needs to store far fewer data copies. Said another way, this means CfM designs can tolerate more node failures while maintaining HA with a given number of copies of the data.CfM is a more flexible design. This is a handwavy claim, so I’ll try to provide some high-level intuition about why CfM is more flexible as well as give a few examples from real CfM systems. Most of the extra flexibility with CfM comes from using “simpler” replication algorithms for primary data that can be customized more easily compared to modifying a consensus algorithm. Consensus algorithms are notoriously complex which makes it harder to safely add new features to them. Because CfD uses consensus to replicate data, it’s harder (or sometimes impossible) to build particular features into the replication protocol used for user data. On the other hand, CfM replication algorithms are only concerned with replicating data (not electing leaders/doing failovers) so are simpler. This may seem like a “fuzzy” claim, so here are a few example features from real CfM systems harder to do in CfD systems:Kafka (a CfM system) only replicates data to other hosts in memory. It doesn’t wait for data to be durable on disk to consider it replicated / committed (it doesn’t wait for an fsync()). This is a difficult feature to build into a consensus algorithm (i.e., its not possible with vanilla Raft or Paxos to the best of my knowledge). The CfM design is flexible enough to allow Kafka to build this feature that would be hard (or maybe impossible) in a CfD design.CfM allows user data replication to use different quorum models. For example, PlanetScale uses MySQLs semi-sync replication. AWS Aurora uses a (4/6 write, 3/6 read) quorum. SingleStoreDB allows customers to choose either sync or async replication models (sync is the default). This breadth of quorum models is likely not possible with CfD (potentially some of them are).CfM designs have more control over who is elected a leader after a failure event. i.e., if there are 2 replica’s, the CfM coordinator can choose which specific one to elect as leader potentially based on network topology (i.e., to keep the data in the same AZ as other shards/partitions). The same goes for adding a node back into the cluster when it recovers from failure. This “placement policy” is harder to build into a consensus algorithm directly. Most CfD systems allow consensus to elect a new leader then move the leader to a higher priority location there after as a 2nd phase.Once a failed host has been detected, its likely the CfM design can failover and get the cluster back online faster then CfD though I have no hard data to back this up. This is because CfM can failover all shards on a dead node in batch, whereas CfD needs a series of consensus elections to happen (one for each shard typically).CfM replication designs more easily support replicating data out of order to avoid head-of-line blocking. That is, a large transaction that is taking a while to commit blocking a quick/small transaction from committing at the same time because the small transaction was ordered after the large transaction in the log. Note the data still needs to be replayed in order on the replica’s, but it can be sent out of order over the wire. This is more difficult to do in consensus algorithms (again, it is not allowed in vanilla Raft).Advantages of Consensus For DataCfD is much better at dealing with slow networks or otherwise replica’s that are sometimes slow to acknowledge newly replicated data for other reasons. CfD only needs to wait for a majority of replica’s to ack a transaction to commit, so slower nodes will naturally not be part of the majority. On the other hand, CfM designs typically wait for all replicas to ack a transaction. Because of this, CfD is better for replication between regions (or between hosts that are far apart) or any place there is latency variation between hosts.CfD is also better at dealing with replica failures (when the primary is still online). CfM typically needs the coordinator to mark a dead replica as offline before data can be committed, whereas CfD will have that dead replica outside of its majority and be allowed to commit (so may not even notice a dead replica directly). The precise trade-off depends on the quorum algorithm used by the CfM database. This can show up as higher p99 latency on writes in CfM designs when replica’s are failing. This is more so the case for “gray failures” where a node is not completely offline, but very badly degrade. These failures are hard for the CfM coordinator to detect quickly. CfD will happily drop the “gray failed” nodes from its majority automatically — its not a special case.CfD databases don’t need a special coordinator tier that is responsible for metadata storage and triggering failovers. All nodes in the cluster can be homogenous which makes clusters easier to deploy and operate. This potentially doesn’t matter as much in managed service environments, though it will still cost the managed service operator more money to run the coordinator nodes. That said, distributed databases often have coordinator nodes for other reasons anyways, so some CfD systems may not have this advantage (i.e, Yugabyte a CfD system has YB-Master coordinator).Assuming you have a correct consensus algorithm, CfD is a simpler design. How the coordinator triggers failovers for CfM and how the data nodes run the failovers in the face of network partitions and other nodes failing or rejoining the cluster is not easy to develop/test. CfD hides this complexity inside the consensus algorithm which I suspect is easier to test and easier to prove correct as an independent module (with TLA+ or P).Concluding CommentsOne thing of note is that many newer distributed OLTP databases (say developed in the mid 2010’s onwards) have tended to use CfD (i.e, TiDB, Yugabyte, CockroachDB, Redpanda) while older systems used CfM (FoundationDB, Kafka, SingleStoreDB). Why is this? I suspect the popularity of the Google Spanner design amongst database builders is one possible reason (published 2012). Several of the newer CfD systems are heavily inspired by Spanner, by their own admission. This is interesting because Spanner was explicitly designed for geo-distributed cross-data center deployments (see Figure 3 below) which is a common problem for Google, but not as common for OLTP applications in general. CfD is the best design if this an important use case.Figure 3: Snippet of the introduction of the paper on Google Spanner (“Spanner: Google’s Globally-Distributed Database”)Neither CfD nor CfM is clearly superior to the other. In my opinion CfM is better for most OLTP applications because it doesn’t require storing as many copies of data and because most apps aren’t geo-distributed across regions where CfD is a better design. CfM designs typically support asynchronous cross region replication only. CfD is the best choice if unreliable networks are a key design constraint and is an overall cleaner architecture in my opinion (at the cost of extra data copies). Given a robust consensus implementation already, CfM is probably harder to build and make robust.[1] ignoring multi-master designs where all nodes can do writes. These design don’t really need an explicit “failover” mechanism in many cases (clients can just try a different node if they fail running a query