When Does Consistency Require Coordination? (original) (raw)

12 Nov 2014

My coauthors and I recently published a paper (that will appear at VLDB 2015) answering one of my longest standing research questions: when does consistency require coordination? It’s well known that many “strong” properties like “ACID” serializability and linearizability are not achievable without coordination, or synchronous communication between concurrent operations. But why is it that we can still implement reliable distributed counters and shopping carts that don’t lose writes, build indexes that are “consistent” with base data, and ensure useful properties like read-your-writes—all without coordination? Why do some operations require coordination while others don’t, and what’s the fundamental difference at play?

In the paper, we present a property, called invariant confluence (I-confluence), that precisely answers this question. I-confluence is necessary and sufficient for safe, coordination-free, available, and convergent execution (think CAP “AP”, without breaking your app). That is, if I-confluence holds, there exists a coordination-free execution strategy that preserves these properties. If it does not hold, no such strategy exists, so don’t waste your time looking for a coordination-free algorithm or concurrency control mechanism that’ll work in all cases.

The intuition behind I-confluence is pretty simple. We capture “consistency” (or safety) using invariants, or declarative correctness criteria about database states (e.g., no user has a negative account balance). Then, given a user’s transactions and a merge procedure used to reconcile divergent states (e.g., last-write-wins, set union, or a convergent datatype), we can check for I-confluence. Simply put, under I-confluence: all local commit decisions must be globally invariant-preserving. If I commit an operation on my local copy of database state, I must make sure that no other concurrent operation would invalidate my commit decision upon merge. If no such state exists, I don’t have to coordinate to commit. That’s it.

“That’s it? That sounds too simple to be true!” you protest.

It’s true, formalizing this property requires some care,1 but the basic idea is pretty simple.2 The key is to specify correctness in terms of invariants rather than reads and writes.3 Without knowledge of what “correctness” means to your app (e.g., the invariants used in I-confluence), the best you can do to preserve correctness under a read/write model is serializability.4 (Hopefully your database offers it.)

“So what?” you ask.

We applied I-confluence to a range of integrity constraints found in database systems, including foreign key, uniqueness, and row-level check constraints as well as some invariants over abstract datatypes.5 The results show that, while coordination can’t always be avoided, in many cases, it can (even when serializability would indicate otherwise). By applying these results to the industry standard TPC-C Benchmark, we achieve a 25-fold improvement over the prior best result (12.7M New-Order transactions per second on 200 servers—I’ll write about the details in another blog post, but, for now, the paper has details). We’ve also been looking at open source applications and applying I-confluence analysis (the subject of another paper and post) and have seen similar wins. Our experience indicates I-confluence works.

Consistency doesn’t always require coordination. In fact, in practice, it seldom does. I’m excited to finally have a piece of work that exactly characterizes this trade-off, backed by some serious experimental data that shows why it matters.

Notes

You can follow me on Twitter here.

Read More