EuroSys 2015: Putting Consistency Back into Eventual Consistency

Paper accepted for publication at EuroSys 2015

Valter Balegas, Mahsa Najafzadeh, Sérgio Duarte, Carla Ferreira, Marc Shapiro, Rodrigo Rodrigues, Nuno Preguiça

Geo-replicated storage systems are at the core of current Internet services. The designers of the replication protocols for these systems have to choose between either support- ing low latency, eventually consistent operations, or supporting strong consistency for ensuring application correctness. We propose an alternative consistency model, explicit consistency, that strengthens eventual consistency with a guarantee to preserve specific invariants defined by the applications. Given these application-specific invariants, a system that supports explicit consistency must identify which operations are unsafe under concurrent execution, and help pro- grammers to select either violation-avoidance or invariant-repair techniques. We show how to achieve the former while allowing most of operations to complete locally, by relying on a reservation system that moves replica coordination off the critical path of operation execution. The latter, in turn, allow operations to execute without restriction, and restore in- variants by applying a repair operation to the database state. We present the design and evaluation of Indigo, a middle- ware that provides Explicit Consistency on top of a causally- consistent data store. Indigo guarantees strong application invariants while providing latency similar to an eventually consistent system.