The many faces of consistency

~ Adrian Colyer

The many faces of consistency Aguilera & Terry, IEEE TC on Data Engineering Bulletin, 2016

Update: Mark Vukolic posted a comment to point me to an ACM Survey paper he published together with Paolo Viotti last year that looks at 50 different consistency models for distributed non-transactional storage systems and puts them into a comprehensive framework. Looks like another great resource for those of you interested in this topic – check out Figure 1 on page A:7!

We continue to work through The Morning Paper gaps from Murat Demirbas’ Distributed Systems Seminar reading list this week…

If you struggle to remember all of the various consistency models and their nuances, you’re not alone! Mix in some isolation levels, and the terminology differences between the database systems and distributed systems communities and it’s definitely a recipe for confusion. I’m sure many people have reached the point of carefully constructing the castle in their heads, drawing out the anomaly diagrams and having that moment of clarity when it all seems to fit together… and then two weeks later the details are fuzzy again (and in this space, the details really matter). You need good notes to go back to!

Here are some of the resources we’ve looked at in previous editions of The Morning Paper that have helped me:

(And let’s not even get started on consensus!)

I also wrote a short rant/position statement on the state of consistency in practice as the first part of my 2015 ‘Out of the Fire Swamp‘ mini-series (see also part 2 and part 3). One of my favourite ways of thinking about consistency models is through the lens of ‘what can go wrong?’ (i.e. what anomalies can occur).

In ‘The many faces of consistency’ Aguilera and Terry share their model for thinking about consistency in its various guises, together with providing a good map of the territory. For extra bonus points, they also attempt to resolve terminology across not just distributed systems and database systems, but also computer architecture. (“We find that the use of consistency varies significantly across these disciplines”).

Consistency is an important consideration in computer systems that share and replicate data… data sharing and replication raise a fundamental question: what should happen if a client modifies some data items and simultaneously, or within a short time, another client reads or modifies the same items, possibly at a different replica?

The new angle that Aguilera and Terry bring is to look at this problem through the lens of two different kinds of consistency: state consistency and operation consistency. State consistency is the easiest to understand – it’s simply the set of properties (or invariants) that we want to hold across the (possibly distributed) state of the system. We say the system is consistent when all of those properties hold. (Another way of saying this is that state consistency constrains the set of states a system can be in).

Operation consistency is the set of properties that we want to hold for the results of client operations, including constraints on sequences of operations. A question I had early on in reading the paper, is why state consistency doesn’t subsume operation consistency – i.e., doesn’t the state dictate the result of an operation. The clarification comes in section 3.3:

Operation consistency is an end-to-end property, because it deals with results that clients can observe directly. This is in contrast to state consistency, which deals with system state that clients observe indirectly by executing operations. In other words, operation consistency is at a higher level of abstraction than state consistency. As a result, a system might have significant state inconsistencies, but hide these inconsistencies externally to provide a strong form of operation consistency.

The aha moment for me was an example of three replicated servers where writes go to any majority (two) of servers. The state is now inconsistent across the three replicas (until the third catches up), but a read operation can still return a strongly consistent result by reading from any two replicas and if the values disagree, accepting the one with the later clock value.

Let’s look at how the three disciplines interpret consistency in the context of state vs operational models. You can judge for yourself whether this helps to clear things up or not!

In distributed systems, consistency refers to either state or operation consistency…

Mutual consistency (e.g. primary-backup) and eventual consistency are forms of state consistency. Linearizability and the various read-write consistency models are forms of operation consistency.

In database systems, consistency refers to state consistency. For example, consider the ACID acronym that describes the guarantees of transactions. The “C” stands for consistency, which in this case means that the database is always in a state that developers consider valid.

So database systems don’t have operation consistency then? Oh yes they do! The ‘A’ and ‘I’ in ACID stand for atomicity and isolation which are forms of operation consistency.

Although the database systems community separates transaction isolation from consistency and atomicity, in the distributed systems community, transaction isolation is seen as a form of consistency, while in the computer architecture community, a concept analogous to isolation is called atomicity.

Is it getting clearer yet?! It’s a wonder anyone can make head or tail of those papers on distributed in-memory datastores with NVMM! 😉

In computer architecture, consistency refers to operation consistency. A similar concept called coherence is also a form of operation consistency. Consistency and coherence have a subtle difference. Consistency concerns the entire memory system; it constrains the behaviour of reads and writes – called loads and stores – across all the memory locations; an example is the sequential consistency property. Coherence concerns the cache subsystem; it can be seen as consistency of the operation of the various caches responsible for a given memory location.

Some examples of state consistency

  • Uniqueness and referential integrity constraints in database systems
  • Mutual consistency – the notion that replicas have the same state when there are no outstanding updates
  • Eventual consistency

Some examples of operation consistency

  • Linearizability
  • Sequential consistency – a total ordering of operations respecting the order in which clients issued them
  • Serializability
  • Strong session serializability – which respects the order of transactions within a session
  • Order-preserving or strict serializability which respects the real-time ordering of transactions
  • Read-your-writes
  • Bounded staleness
  • Operational eventual consistency – EC defined in terms of what values are returned by read operations
  • Cache coherence in computer architectures