(the presentation slides are available here)
Geo-distribution is the new norm: today's Internet services span multiple sites scattered around the globe. Distributing data globally enables services to tolerate disasters and minimizes latency by allowing accesses to the closest site.
In a geo-distributed service, data is commonly replicated at the different service locations. Dealing with replicated data is difficult because there exists a tension between (i) data Consistency, i.e., keeping it the same at all replicas, (ii) making data Available at any replica, and (iii) tolerating a Partition of the network. This tension is know as the CAP impossibility result [1].
To partly sidestep the CAP impossibility result, it is possible to make use of conflict-free replicated data type (CRDT). A CRDT [2] is a data structure replicated at multiple sites such that replicas can update it independently and concurrently without coordination between them, and it is always mathematically possible to resolve inconsistencies which might result.
Many CRDTs exist and programmers may use them in lieu of usual data types such as sets, maps or counters. AntidoteDB [3] is a recent effort to make CRDTs available to a wide audience. This storage system allows developers to apply the principle of synchronization-free execution with CRDTs, while reasoning in the familiar relational model, using SQL to access their data.
When invoking a CRDT object at a replica, AntidoteDB does not synchronize with remote replicas before returning to the caller. This mechanism is at the core of the synchronization-free principle and allows the system to tolerate network partitioning.
However, this approach also prevent certain applications to readily migrate their code from a standard SQL system to AntidoteDB. To illustrate this observation, consider a banking application. For simplicity, assume that a bank account is a counter that should never go below zero. Clearly, it is necessary to synchronize replicas in order to avoid exploits with concurrent operations running on different sites.
We posit that an important class of applications (such as the banking one above) require both weakly and strongly-consistent shared objects. To reconcile ease of programming and performance, we propose that the programmer degrade the data consistency of the shared objects. This degradation is controlled at the level of individual object and can be integrated to the language support. The goal of this project is to explore this idea for simple degradable objects (such as the counter above), implementing them atop AntidoteDB.
In a first step, students will add a total order broadcast primitive in AntidoteDB to allow replicas synchronization. Then, they will propose several consistency degradations of the counter object above, from strong to weak, the weakest class being a CRDT. In a last step, the students will implement these data types in AntidoteDB, relying on the total order primitive for synchronization where required.
The students will work with a joint team of researchers from Paris 6 and Télécom SudParis.
[1] CAP Twelve Years Later: How the "Rules" Have Changed, Eric Brewer in Computer, Feb. 2012
[3] AntidoteDB