Consistency Models

Background #

I was reading the documentation for Google's Cloud Spanner recently, and came across the claim that the consistency level guaranteed by the database is External Consistency. The documentation then went on to state that External Consistency is a stronger guarantee than Linearizability.

I found this confusing because I had come across resources that suggested that these terms referred to the same thing. I brought my confusion about these terms to a colleague, who kindly pointed me to one of the earliest sources of these terms to help clarify it.

This post contains my notes from studying section 3.1 of 'Information Storage in a Decentralized Computer System' by David K Gifford.

Note that only a small subset of consistency models for concurrent systems are covered here. For a more detailed treatment of this topic, you'll find this article useful.

Serial Consistency #

Serial Consistency is achieved when a database makes it appear to a transaction that there is no other concurrently executing transaction.

So if we have two transactions:

Sample Transactions T₁ and T₂

The order in which the actions of each transaction is processed is called a schedule.

A serial schedule results when the transactions are executed one at a time to completion. We have 2 serial schedules for the example above:

Sa: {a11, a12, a13, a21, a22, a23}

Sb: {a21, a22, a23, a11, a12, a13}

A database provides serial consistency if it guarantees that the schedule to process a set of transactions is one of the possible serial schedules.

External Consistency and Linearizability #

An external schedule is the unique serial schedule that is defined by the actual time order in which transactions complete. Any system which guarantees that the schedule it will use to process a set of transactions is equivalent to its external schedule, is said to provide external consistency.

Using the example above, if T₁ completes before T₂ starts to commit, then external consistency guarantees that the system will appear as if schedule Sa was used. This means that no clients observing the database will see a state that contains the effects of T₂ but not T₁.

Remember that these consistency models should be thought of in the context of a distributed database, meaning that these transactions can execute on different nodes, and clients can observe the database from different nodes as well.

What makes external consistency stronger than serializability is that in serializability, any of the possible serial schedules can be used, regardless of when each transaction actually committed.

Using the same example of T₁ completing before T₂ commits: in a serializable database, it is possible for a client to read from a database node in a state where it contains the effect of T₂, but not T₁. This can lead to inconsistencies in the data.

With external consistency we're saying that when a transaction has committed, all subsequent transactions will see the effect of that committed transaction in the DB, that's not the same guarantee provided by serializability.

Linearizability, on the other hand, does not say anything about the behaviour of transactions. It is a consistency level that deals more with the behaviour of a single object. It is a recency guarantee for a single object. while it might involve a transaction, its focus is on a recency guarantee for a single object, i.e. when one committed transaction has updated the value of an object, all other reads to that object must see the new value.

In summary, while linearizability is related to external consistency in some way, they're talking about different things.

Further Reading #

Some other useful sources to explore these topics further include:

• Linearizability vs Serializability by Peter Bailis
• Consistency should be more consistent! by Irene Zhang
• Consistency Models - Jepsen blog
• Cloud Spanner: Truetime and External Consistency - Cloud Spanner Documentation

distributed-systems learning-diary

← Home