Coordination-Avoiding Database Systems.

Concurrent access to shared state results in a fundamental trade-off between coordination—surfacing in the form of reduced availabil-ity, decreased scalability, and increased latency—and application-level consistency, or semantic guarantees for end users. Traditional mechanisms such as serializable transactions are sufficient to en-sure application-level consistency but require synchronous coor-dination, while weaker mechanisms may sacrifice consistency for less coordination and greater scalability. In this paper, we identify a necessary and sufficient condition for achieving coordination-free execution without violating application-level consistency: invari-ant confluence. By explicitly considering application-level invari-ants, invariant confluence analysis allows databases to coordinate between operations only when anomalies that might violate invari-ants are possible. This provides a formal basis for coordination-avoiding database systems, which coordinate only when it is nec-essary to do so. We demonstrate the utility of invariant confluence analysis on a subset of SQL and via a coordination-avoiding proof-of-concept database prototype that scales linearly to over a million TPC-C New-Order transactions per second on 100 servers. 1.