Review of "Coordination Avoidance in Database Systems"

25 Oct 2015

Review of "Coordination Avoidance in Database Systems"

In order to achieve low latency and high scalability, systems tend to minimize coordination or blocking communication between concurrently executing operations a lot. But uninhibited coordination-free execution can potentially compromise application level consistency. This paper identifies that given knowledge of application transactions and correctness criteria (invariants), it's often possible to avoid coordination while still preserving correctness criteria, but gained much more performance over coordinated executions.

Invariant confluence (I-confluence) is applied in a transactional context, it informally ensures that divergent but I-valid database states can be merged into a valid database state. I-confluence requires that coordination can only be avoided if all local commit decisions are globally valid, alternatively, commit decisions are composable. If two independent decisions to commit can result in invalid converged state, then replicas must coordinate in order to ensure only one of the commits succeeds.

Invariant use is the key to I-confluence. By directly capturing application level correctness criteria via invariants, I-confluence analysis only identifies "true" conflicts. This allows I-confluence analysis to perform a more accurate assessment of concurrency restrictions compared to related conditions such as commutativity. But this also depends on the correctness specified by the user, if the user gets anything wrong in the invariants, the analysis may results in conflict results too.

Will this paper be influential in 10 years? Maybe, it provides a good way to reason about system consistency under concurrency context. In the age of more and more mega scale systems, this certainly has its field of application.