Consistency Models

· 3 min read


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 T1 and T2 where T1 has steps a11, a12, a13 and T2 has a21, a22 and a23

Sample Transactions T1 and T2

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 T1 completes before T2 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 T2 but not T1.

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 T1 completing before T2 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 T2, but not T1. 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:

distributed-systems learning-diary

A small favour

Did you find anything I wrote confusing, outdated, or incorrect? Please let me know by writing a few words below.

Follow along

To get notified when I write something new, you can subscribe to the RSS feed or enter your email below.

← Home