A Study Guide to Confusingly Named Consistency Guarantees

There are a huge number of terms used when describing consistency guarantees in distributed systems. What’s the difference between serializable and linearizable? What’s a ‘dirty read’? How do these concepts map between SQL and NoSQL databases? What, in other words, is Kyle Kingsbury actually talking about? I personally find the concepts very confusing. For one thing, everyone uses slightly different terminology for similar or adjacent concepts. Martin Kleppmann helpfully points out that it’s not just me. The study of consistency guarantees started from an analysis of early databases. The terms reflect their naming conventions, however odd, and isolation levels, however desirable or practical.

Right now I work mostly with messaging middleware. It’s surprising how many conversations I’ve had with people who implicitly assume their messaging solutions offer transactional guarantees. Professionally, I feel like it’s important to get these concepts straight in my own head to be clear when helping others. So here is a quick and dirty study guide of confusingly named consistency models.

ACID transactions

Transactions are the units of work of relational database management systems (RDBMS): sets of read and write operations ending in a commit which saves any changes. Transactions are said to be Atomic, Cconsistent, Isolated, and Durable.

Strict Serializability

Serializability relates to the effect of “groups of one or more operations over one or more objects”. In a distributed system there can be different levels of serializability. For instance, consider a database which commits transactions T1 and T2 serially (in that order). The database is backed up asynchronously to a read replica. There are no checks in the replica on order of receipt, T2 arrives before T1, and the transactions are committed in reverse order. Both the database and its replica have committed their transactions in a locally consistent serial ordering, but the replica’s ordering is obviously wrong. “One copy serializability” refers to all replicas of a system acting as if there was one data item (i.e. serial order for any operation is the same regardless of which replica is contacted).

One copy serializable systems can still present anomalies due to clock skew. For instance, a (commited) write with timestamp t=2 to a data object is ignored because an earlier (committed) write’s timestamp is t=3, regardless of the way the user think’s time is supposed to work. It’s also possible for all writes to be overidden by an immortal write, where the system decides one commit is serially after any other future transaction. A system is said to be linearlizable if such time-travel anomalies are not possible:

“Linearizability is a guarantee about single operations on single objects. It provides a real-time (i.e. wall clock) guarantee on the behaviour of a set of single operations (often reads and writes) on a single object (e.g., distributed register or data item). […] Linearizability […] is synonimous with atomic consistency [ (the C in CAP) ]. […] We say linearizability is composable (or “local”) because, if operations on each object in a system are linearizable, then all operations in the system are linearizable.” - Peter Baillis

Strict (or Strong) Serializability refers to systems which are both (one-copy) serializable and linearizable.

There are two main ways of ensuring strict serializability:

Less-than-strict serializability

Serializability and linearizability require coordination. As a result, a strict serializable system cannot guarantee availabilty in an asynchronous network (CAP Theorem et al.). In order to achieve better availability guarantees, various systems have been designed with more relaxed subsets of conditions than both serializability and linearizability. Jepsen has an incredibly helpful map of these various consistency models.

Relaxing Serializability

I’ll cover serializability models starting with the least strict.

Relaxing Linearizability

Causality is important for building meaningful applications. However, there are different levels of causal guarantees available:

Linearizability is sequential consistency with a real-time guarantee.

Reaching consensus in distributed systems

These consistency models were developed primarily for single monolithic databases. They’ve been extended in different ways to apply to microservices.

One convention for microservices is to say that there is a transaction boundary around each service (assuming they each have a local database). This approach treats each microservice as its own monolith and doesn’t attempt to make achieve any higher level transactional guarantees.

On the other hand, implementing transactions across a multi-node database requires consensus. The two most common consensus protocols are Raft and Paxos. Sarah Christoff has a great summary of the differences between the two so I won’t try.

Implementing a consensus protocol can be very difficult in practice because they are quite sensitive to latency. For instance, Raft relies on a heartbeat from other nodes to know when to trigger an election. It is generally suggested not to span AZs (or potentially even datacenters) when deploying CP systems which rely on consensus (e.g. Zookeeper) because the latency hit can severly impact their ability to maintain a stable quorum.

Prioritizing Availability

The cost in downtime and coordination effort of guaranteeing consistency is too much for certain types of applications. Firms who’s globe spanning operations require higher availability than consensus-based approaches can provide favour AP systems. Werner Vogels describes these eventuallly consistent models as a means of “building reliable distributed systems at a worldwide scale”. With no subsequent updates, eventually all reads will converge on the same value.

“If no failures occur, the maximum size of the inconsistency window can be determined based on factors such as communication delays, the load on the system, and the number of replicas involved in the replication scheme.” - Werner Vogels

If eventual consistency is a good enough guarantee for an application there are many options for how to reconcile state. However, all options require a more relaxed interpretation of what constitutes the lifetime of a transaction (and, informally, how long it might take to roll back):

Server-side Consistency

These consistency models treat the database as a black box. In practice, the number of nodes of a distributed database required to process reads or writes has a meaningful impact on the guarantees it can offer.

N = number of replicas for given data (which will all be eventually updated)
W = number of replicas that need to ack a write in order for a write to be committed
R = number of replicas that need to ack a (consistent) read in order for a read to be committed
(obviously W <= N, R <= N)

Round up

Clearly, there are levels to this. Pay attention to the guarantees provided by your database. Be careful when making promises to your customers about what your system guarantees. And be clear about what you can offer. Bear in mind that the way we think about databases and stateful systems in general is as much about their history as the logic that underpins them.