1. 7

Minimizing coordination, or blocking communication between con- currently executing operations, is key to maximizing scalability, availability, and high performance in database systems. However, uninhibited coordination-free execution can compromise applica- tion correctness, or consistency. When is coordination necessary for correctness? The classic use of serializable transactions is sufficient to maintain correctness but is not necessary for all applications, sacrificing potential scalability. In this paper, we develop a formal framework, invariant confluence, that determines whether an appli- cation requires coordination for correct execution. By operating on application-level invariants over database states (e.g., integrity constraints), invariant confluence analysis provides a necessary and sufficient condition for safe, coordination-free execution. When programmers specify their application invariants, this analysis al- lows databases to coordinate only when anomalies that might violate invariants are possible. We analyze the invariant confluence of com- mon invariants and operations from real-world database systems (i.e., integrity constraints) and applications and show that many are invariant confluent and therefore achievable without coordination. We apply these results to a proof-of-concept coordination-avoiding database prototype and demonstrate sizable performance gains com- pared to serializable execution, notably a 25-fold improvement over prior TPC-C New-Order performance on a 200 server cluster.

  1.  

  2. 4

    Murat, whose blog I’ve grown to appreciate and wish I had more time to read, reviewed this paper and listed a couple of related works.