Don’t Get Stuck in the “Con” Game (V2)

Consistency, convergence, and confluence are NOT the same! Eventual consistency and eventual convergence aren’t the same as confluence, either.

This is a major rewrite of yesterday’s post Don’t Get Stick in the “Con” Game. I’ve added a bunch more stuff (including on Linearizability and the CAP theorem).

---

Like many others, I’ve fallen victim to using the term eventual consistency.  As I’ve reflected on this, it’s clear that the meaning of this is fuzzy.  Different communities within computer science use the word “consistency” in varying ways.  Even within our different communities, we are inconsistent in our use of consistency.  That fuzziness has gotten many of us, myself included, tangled up in misunderstanding.

It turns out that there are other terms, convergence and confluence, that have crisper definitions and are more easily understood than consistency.

What Is Meant by Consistency?  What about Eventual Consistency?

Database people loosely mean ACID transactional consistency (approximately the same as serializability) when they say “consistency”.  My dear friend, Andreas Reuter, coined the term ACID in 1983 the paper Principles of Transaction-Oriented Database Recovery.  Recently, I asked him what the C meant, he said “The App can control when the database tries to commit.”  In other words, don’t commit a proper subset of the updates for the transaction.  Don’t commit early.  That, combined with Isolation, means the application can control their very own “consistency” of the data.  That’s not QUITE the same as how most database people interpret consistency.  See  ACID: My Personal “C” Change.  Database people (including me) are even confused about THEIR meaning of consistency. 

Distributed systems people sometimes use the word consistency in a different fashion.  When talking to them about what “consistency” means, the answer has historically been “Each of the replicated values for Object-X have the same value.”  There is no notion of work ACROSS the objects, just the individual objects and their values.  Today, this is more commonly called convergence.  A while ago, I chatted with my friend, Doug Terry and asked him about consistency and eventual consistency.  Since Doug coined the phrase eventual consistency in the Bayou paper in 1995, I was interested in his perspective.  When he defined eventual consistency, it meant that for each object in a collection of objects, all the replicas of each object will eventually have the same value.   Then, he said: “Yeah, I should have called it eventual convergence.”  So, the distributed systems people are also confused about their own interpretation of consistency, too!

Looking at the proof of the CAP Theorem in Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Gilbert and Lynch (2002) shows yet another meaning of the word consistency!  Of course, the proof has a different definition for consistency than the other descriptions of CAP that I located.

Distributed systems people and database people get wrapped around the axle when discussing what is meant by “eventual consistency” WITHIN their own community.  It’s even uglier when they talk to folks in the OTHER community! 

Convergence and Eventual Convergence

Next, let’s consider the definition of convergence.

My friend, Peter Alvaro addresses convergence in his 2015 PhD thesis  Data-centric Programming for Distributed Systems on page 76.  He defines convergence as: 

“A system is convergent or “eventually consistent” if, when all messages have been delivered, all replicas agree on the set of stored values.”

This is essentially the same as seen within the original 2011 CRDT paper by Marc Shapiro et al: Conflict-free Replicated Data Types although Alvaro focuses on a system with a set of eventually convergent values and Shapiro et al focus on a single object.  Shapiro et al say:

“Strong Convergence:Correct replicas that have delivered the same updates have equivalent state.”

Note that this is also how Doug Terry used convergence and “eventual convergence” in our chat a few years ago.

Convergence is a property of individual objects and their merge function.

Eventual convergence is a phrase with “too much extra redundancy”.  Convergence means convergent, eventually or not.  Still, “eventual convergence” sounds cool so I’ll go with it.

Linearizability

Linearizability is not the same as convergence.   

Every distributed system’s geek should study Linearizability: a Correctness Condition for Concurrent Objectsby Herlihy and Wing (1990).  I did not STUDY it prior to yesterday when I wrote the first version of this blog post.  I did today and I am updating this blog post.  It is an amazingly clear and crisp definition of a correctness criteria for some objects within distributed systems. After reading this paper, I can easily and clearly explain linearizability.

Quoting Peter Bailis from his famous blog post Linearizability versus Serializability we see linearizability defined as:

Linearizability is a guarantee about single operations on single objects. It provides a real-time (i.e., wall-clock) guarantee on the behavior of a set of single operations (often reads and writes) on a single object (e.g., distributed register or data item).

As I learned from the Herlihy and Wing paper: 

Under linearizability, operations should appear to be instantaneous from the perspective of the object. Operations happen one at a time (as seen by the object) and each operation acts on the state of the object as derived from its local history.

Clients see invocations of an operation on a linearizable object followed later by responses to these operations.  From the perspective of the client, the operation occurs at the object sometime between the invocation and the response.

Linearizability defines a relationship between the partial order (or history) of the object and the partial order (or history) of each client.

While “wall-clock” time provides a dandy intuitive description, the true relationship between the histories of the object and its clients is a “happened-before” relationship (as defined by Lamport in 1978 in Time, Clocks, and the Ordering of Events in a Distributed System).

Linearizability does NOT imply read/write operations, although those are possible.  A linearizable object may provide ANY operations and these operations appear to occur one at a time in the history of the object.  These operations appear to occur at each client sometime between the client’s invocation and the client’s receipt of the response.

Many times, the word “consistency” is used to describe linearizable read/write operations over a set of objects.  READ is defined to return the latest value seen in a WRITE to the object. If Client-A does a WRITE followed by a READ to a linearizable object, the value returned to the READ invocation must be either the one previously WRITTEN by Client-A OR the value of a WRITE from another Client-B processed by the object after Client-A’s WRITE and before Client-A’s subsequent READ.  It is the interaction of the READ operation with the history of the object (at the time of the READ) that poses challenges under partitioning.

Again, Linearizability defines a relationship between the partial order (or history) of the object and the partial order (or history) of each client.  It supports any operation that can be invoked in a single request to one object.

Convergence versus Linearizability

Convergence speaks to what happens when you stop tormenting multiple disjoint replicas of the same object and bring the replicas together.  Specifically, if you have many replicas of an object and each receive different subsets of all of the updates, a convergent object will merge with its replicas and yield the same object.  This is independent of the order the updates were applied to the various replicas.

Linearizability is a property of the history of a single object and that history’s relation to the histories of the clients sending operations to that single object.  The linearizable object’s crisp history must look like it lives in one location doing one operation at a time.

Linearizability and convergence are very similar in that they both refer to single objects (whatever that means).  They are existentially different in that convergence assumes multiple replicas but linearizability must appear to be one replica with a linear history.

A Few More Meanings of Consistency: the “C” in the CAP Theorem

When rethinking this post to make a second version, I remembered the “C” in CAP.  What about the CAP theorem?  Is this a consistent “Consistent”?

CAP was famously posed as a conjecture in a keynote at PODC 2000 called Towards Robust Distributed Systems.  It was later proved to become the CAP Theorem in Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Gilbert and Lynch (2002).   The conjecture and theorem get their name CAP from “Consistency, Availability, Partition-tolerance:  Pick two.”

According to Brewer in CAP Twelve Years Later: How the Rules Have Changed (2012), consistency is defined as “Consistency (C) equivalent to having a single up-to-date copy of the data”.  He further states:

Consistency (C). In ACID, the C means that a transaction preserves all the database rules, such as unique keys. In contrast, the C in CAP refers only to single-copy consistency, a strict subset of ACID consistency. ACID consistency also cannot be maintained across partition.  Partition-recovery will need to restore ACID consistency. More generally, maintaining invariants during partitions might be impossible, thus the need for careful thought about which operations to disallow and how to restore invariants during recovery.

Then, we see: 

“Aspects of the CAP theorem are often misunderstood, particularly the scope of availability and consistency, which can lead to undesirable results.” 

Followed by:

“Scope of consistency reflects the idea that, within some boundary, state is consistent, but outside that boundary all bets are off. For example, within a primary partition, it is possible to ensure complete consistency and availability, while outside the partition, service is not available.”

Being confused, I dug deeper.  In the 2012 article, Brewer indicated that the CAP conjecture was first discussed in 1999 in Harvest, Yield, and Scalable Tolerant Systems by Fox and Brewer.  How is consistency defined there?  Here we see:

“In this discussion, strong consistency means single-copy ACID consistency; by assumption a strongly-consistent system provides the ability to perform updates, otherwise discussing consistency is irrelevant.” 

What about in the keynote at PODC 2000 called Towards Robust Distributed Systems?  Here we only see the definition of “C” as “Strong Consistency” under the category of “ACID” transactions versus “Weak Consistency” under the category of “BASE” (Basically Available Soft-state Eventually-consistent). 

Finally, I figured I’d check out the proof of the theorem in Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services by Gilbert and Lynch (2002).

Here, I found a concise definition for consistency, even if it was different than any others I found in this spelunking of CAP:

“The most natural way of formalizing the idea of a consistent service is as an atomic data object. Atomic, or linearizable, consistency is the condition expected by most web services today.  Under this consistency guarantee, there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time. This is the consistency guarantee that generally provides the easiest model for users to understand, and is most convenient for those attempting to design a client application that uses the distributed service.”

OK!  Cool!  This is linearizability for operations against a single object as so crisply described by Herlihy and Wing.  Nice!   Reading further, I found the theorem they proved:

Theorem 1: It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: 

•      Availability 

•      Atomic consistency

in all fair executions (including those in which messages are lost). 

To my surprise, the theorem stipulated a read/write object.  This stipulation was NOT in the paper’s definition of consistency!  Their proof counts on read/write operations but that’s not part of the defined consistency model.

Studying this paper, I do believe they proved the theorem they enumerated.  I’m struggling to correlate it to the C for consistency as quoted in the CAP conjecture.  Still, it’s cool and I think it’s a very useful result.

Let’s say consistency sometimes means: “Read/Write Operations Against a Linearizable Object”

Gilbert and Lynch’s proof hinges on the fact that the READ operation is only defined in the context of the entire history of the linearizable object:  

• As we stated above, READ is defined to return the latest value seen in a WRITE to the object. If Client-A does a WRITE followed by a READ to a linearizable object, the value returned to the READ invocation must be either the one previously WRITTEN by Client-A OR the value of a WRITE from another Client-B processed by the object after Client-A’s WRITE and before Client-A’s subsequent READ. 

• When clients are separated from the linearizable object by a partition, that doesn’t work.

Confluence:  Dealing with Component Input and Output

Finally, let’s look at confluence.  This is the approach I believe allows the best behavior for composing our replicated applications and their encapsulated data.   

Peter Alvaro’ thesis defines confluence as follows:

We call a dataflow component confluent if it produces the same set of outputs for all orderings of its inputs. At any time, the output of a confluent component (and any redundant copies of that component) is a subset of the unique, “final” output.

Alvaro continues to contrast convergence and confluence:

Convergence is a local guarantee about component state; by contrast, confluence provides guarantees about component outputs, which (because they can become the inputs to downstream components) compose into global guarantees about dataflows. 

In summary: 

• Convergence is a definition based on eventual state.  

• Confluence is a definition based on behavior and program outputs.

So, given a set of inputs to a component, we get a set of outputs from the component.  No matter what legal subset of the inputs we see, we will never retract any output we have emitted.

Confluence is written about in both Alvaro’s thesis and in a new paper by Joe Hellerstein and Peter Alvaro:  Keeping CALM: When Distributed Consistency Is Easy.  In that paper, they say:

Unlike traditional memory consistency properties such as linearizability, confluence makes no requirements or promises regarding notions of recency (for example, a read is not guaranteed to return the result of the latest write request issued) or ordering of operations (for example, writes are not guaranteed to be applied in the same order at all replicas). 

Nevertheless, if an application is confluent, we know that any such anomalies at the memory or storage level do not affect the application outcomes.

In other words, confluence is NOT about memory reads and writes. 

Confluence, Monotonicity, and Sealing

So, confluence is a property of inputs to and outputs from a function.  It means that, for a given set of inputs, you will only create outputs that are never retracted when you get new inputs.  Basically, you never change your mind about an output.

Monotonicity means you only move forward, never backward.  In other words, you never need to retract an output once you’ve said it.

CALM stands for Consistency as Logical Monotonicity.   The logical part of this means that you can squint at the inputs and the outputs in such a way that you HAVE MONOTONICITY.  Can you leave off enough details that you don’t need to back away from any output messages?

In their CACM CALM paper, Hellerstein and Alvaro point out that confluent functions can answer questions about “does this exist?” but have a really hard time answering questions like “does this NOT exist?”.  This is because the confluent function may still get later knowledge and that new knowledge may add the thing that so far does not exist.  Hence, you’d better not SAY it doesn’t exist until you know you aren’t getting new facts as new inputs.

There is a concept called sealing of a confluent stream.  Sealing is a way to say “no more confluent operations” will arrive.   When you seal a confluent stream, you CAN get an output that says: “I can attest that this does NOT exist”.  See Alvaro’s thesis.

Sealing a Confluent Stream

Sealing of a confluent stream is funky.  By definition, the seal operation is ordered and, hence, not a part of the confluent set of inputs (because the order of the seal matters).  

I don’t have too much to say here about sealing a confluent stream except I think it is woefully under researched.  My instinct tells me that there are many creative ways to apply seal with new semantic interpretations.  

I will undoubtably think hard about this when my wife is not looking.  When she’s looking, I am NOT going to think about sealing because she finds it VERY annoying when I’m off in my own world thinking hard about such things in her presence.

I am pretty sure I will pop up with new stories to tell about sealing.

Inconsistent and Consistent “Consistency”

There seem to be at least three popular uses for the word “consistency”:

• Database consistency:   This is a conflation of “Complete” transactions with some unstated enforcement of unstated rules.  Because the set of updates within a transaction must be bounded by the application in cahoots with the upper part of the database, the application and upper-database can enforce some rules that the transaction system doesn’t understand.  I think of this as “Complete” from the transaction’s perspective.

• Eventual consistency of replicated objects (Convergent): When all the replicas of an object are merged, they will all have the same value.

• Consistency as linearizable read/write operations:  Updates to EACH object in a distributed system must appear as if they occurred within a single history as seen by the object AND the invocations and responses from the client must form a well-defined “happened-before” history at each client.

None of these popular uses make any sense to me.  Now, there ARE usages of consistency (with an adjective in front of them) that I crisply understand:

• Strict consistency:  This is exactly the same as linearizable read/write operations as defined by Gilbert and Lynch in the proof of the CAP conjecture, even though they didn't refer to the operations with this name.  

• Sequential consistency:  Defined by Lamport in How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs (1979), sequential consistency is weaker than strict consistency.  Each client’s writes to a variable appear in order from the perspective of the writer. Reads by a client do not guarantee visibility to other client’s concurrent writes.  I understand this definition.

• Causal consistency:  One of my favorite forms of consistency.  A weakened form of sequential consistency which categorizes writes based on their causal dependence.  In other words, I track what an updating Client-A had visible within the object at the time of its local update at the client.  When Client-B reads an update by Client-A, all of the changes seen by Client-A when it did the update will be visible to Client-B as Client-B reads the update.   This is incredibly useful in occasionally connected systems. 

Conclusion

This short blog post is about nomenclature and HOW to talk about stuff.  I am going to work hard to make my usage of words crisper and more concise in the future:

• Convergence is a property of an object.  It means you have a merge algorithm that allows you to smash divergent replicas together and get the identical result.  
  
  A convergent object’s merge algorithm must be associative, commutative, and idempotent.  If you merge any two replicas in any order, as long as you’ve captured the same set of changes on any replica in any order, you will get the same result.  This makes it easy to distribute the work across space and time.  Then, you can have ACID 2.0 (Associative, Commutative, Idempotent, and Distributed) changes to the object.

• Eventual convergence is the same as plain-old convergence but it sounds cooler and may help you be successful when meeting new people in a bar.

• Confluent is a property of a dataflow component.  Alvaro says: 

  “We call a dataflow component confluent if it produces the same set of outputs for all orderings of its inputs. At any time, the output of a confluent component (and any redundant copies o f that component) is a subset of the unique, “final” output.”

  Confluent dataflow components compose.  In my opinion, confluence is the new and exciting space for distributed systems research.

The word consistent is not consistent.  I pretty much think it means nothing useful unless preceded by strong, sequential, or causal.  

Eventual consistency means nothing both now AND later.  It does, however, confuse the heck out of a lot of people.   

So, except for strict consistency, sequential consistently, or causal consistency, I’m am going to consistently avoid using the word “consistent” in the future.  Most of the time.

Open Questions

• When should a designer choose an operation-centric approach to replication (e.g., confluence) and when is an object-centric approach to replication (e.g., convergence)?

• When, where, and how is causal consistency an amazing gift to any system’s designer?

• Consensus is a mechanism to allow an agreed new value for an object.  Is that simply a distributed write operation?  Why do we focus consensus as a form of writing a new value?  Is that the same as strong consistency?

• How should you react on a first date when you meet someone and they talk about “eventual consistency”?  It that a more difficult discussion than talking about politics?