Don't Get Stuck in the "Con" Game

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

Like many others, I’ve succumbed 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?

When they say “consistency”, database people loosely mean ACID transactional consistency (approximately the same as serializability).  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!

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, Convergence, and Eventual Convergence

Linearizability is not the same as convergence.   

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).

In plain English, under linearizability, writes should appear to be instantaneous. Imprecisely, once a write completes, all later reads (where “later” is defined by wall-clock time) should return the value of that write or the value of a later write. Once a read returns a particular value, all later reads should return that value or the value of a later write.

In fact, there are subtleties in this, too.  Is wall-clock time as seen by the client?  Is wall-clock time as seen by some server or servers implementing the linearizable single-object?  In my opinion, each client sees a “happened-before” relationship (as defined by Lamport in 1978 in Time, Clocks, and the Ordering of Events in a Distributed System).

Linearizability guarantees that the union of the partial orders as seen by the set of clients provides a total order.  That total order looks like a global variable with reads and writes happening one at a time.

Linearizability speaks to the behavior seen by individual operations as they work on linearizable objects.  

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 and convergence are very similar in that they both refer to single objects (whatever that means).

Replication: The Ultimate Serial Killer

In Bailis’s blog post cited above, he defines the following:

Linearizability is a guarantee about single operations on single objects.

Serializability is a guarantee about transactions, or groups of one or more operations over one or more objects.

It guarantees that the execution of a set of transactions (usually containing read and write operations) over multiple items is equivalent to some serial execution (total ordering) of the transactions.

Both linearizability and serializability provide guarantees to an application accessing their data using reads and writes.  Writes are non-reorderable.

In both linearizable data and serializable data, the application expectation of reads and writes undermines any form of eventual linearizability or eventual serializability.  These don’t exist because of the ordering constraints of the application’s read/write semantics.  

• For linearizability, the CAP theorem proves “there ain’t no eventual linearizability”.  See Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services.

• Serializable databases have even more complex guarantees provided to their applications.  So, we can also say “there ain’t no eventual serializability” !  

This is due to the semantics of read and write against linearizable objects or serializable databases. 

• For replicated data, WRITE is wrong.  

Replication is the ultimate serial killer!

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 Confluent Streams

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.

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 of 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.  Eventual consistency means nothing both now AND later.  It does, however, confuse the heck out of a lot of people.

So, 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)?

• 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 linearizability?

• 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?