Meeting with Marc Shapiro about his European project SyncFree
© Inria / Photo J.-M. Ramès
"WORK MATHEMATICS: THE COMPROMISE BETWEEN AVAILABILITY AND CONSISTENCY OF DATA"
> Could you briefly describe your team and the Regal project?
Regal (RépartitionEtGestion desApplications àLarge échelle, meaning "Distribution and Management of Large-Scale Applications") is a project team comprising close to two dozen members, including eight permanent staff (two Inria researchers, lecturers, and two professors), Ph.D. candidates, and post-docs. The team leader is Pierre Sens. We are interested in distributed systems such as data clouds, the Internet, peer-to-peer (P2P) systems, cooperative systems, online games, and even robot swarms. In other words, everything related to communication, interaction, and cooperation among a large number of computers, multicores and processes. As a system-oriented team, we develop algorithms, check their correctness, and perform practical testing of their efficiency and usefulness.
> And what is your specialty?
Specifically, data clouds and sharing on the web. For example, imagine an online game. The game space constitutes a database shared by all users. For everyone to see the same game status, one could imagine centralizing all the data in a single server. Unfortunately, beyond a few hundred users, the load is too high and the more remote users are at a disadvantage because of the network delay. We therefore recommend distributing replicas, or copy servers, near the users. This creates another problem: the problem of consistency between these servers. That is the topic I work on: guaranteeing the availability of data and the response speed while maintaining consistency of the data between these servers.
> How can this difficultly be solved?
There are generally two classes of solution, called CP and AP. CP (consistent partitioned) solutions synchronize updates to be strongly consistent. These are convenient for programmers, but also costly because of the large number of synchronizations (and more difficult to upscale), and they constitute a poor use of the hardware (which is kept waiting for a long time). In case of a network failure (partition), a CP system hangs completely. AP (available partitioned) solutions accept parallel updates without synchronizing, and are therefore always available, respond quickly, and can be brought closer to users. But copies can diverge, and it is fundamentally the responsibility of the application programmer to prevent this divergence from corrupting the data.
There is an inherent divide between CP and AP, but our research aims to reduce the gap between them. One technology we have been developing with our partners since 2009 is called CRDT (Conflict-Free Replicated Data Types). Thanks to its mathematical properties, it guarantees that an AP system will converge towards an acceptable value (because the concurrent operations of a CRDT are commutative, they do not need to be sequenced) without any effort by the application programmer. Our specifications have been used by several industrial users (including Facebook, TomTom and the Riak database, industrialized by Basho). CRDTs constitute the starting point of the European SyncFree project, in response to interest from industrial users.
> What is gained in latency and data rate? How does this translate into return on investment for those companies?
We have implemented several protocols in a single system. Experimentally, our measurements show that broadly speaking for the same application, the weakest protocol responds four times more quickly and each server serves four times more clients than with the strongest protocol. Another example is bet365, a UK online sports betting website, which has switched from an Oracle database (CP) to Riak with CRDT. At the end of a match, they used to need almost half an hour to calculate the odds and winnings. Now this can be done in a few minutes, without a change of hardware.
CRDTs solve part of the problem, the convergence aspect, but for many applications that is not enough. To go further, the SyncFree project has developed Antidote.
> What are the advantages of Antidote?
Antidote is an enhanced AP cloud database. It is available and scalable like its AP competitors, but stands out thanks to its much stronger guarantees. It already allows operations to be grouped into atomic transactions and applies strong consistency inside a computation center. Between computing centers, it offers causal consistency, which avoids abnormal sequencing whilst remaining AP. Finally, we are developing a new technology called "Just-Right Consistency", which fine-tunes the database to the consistency needs of a particular application: static analysis determines which are the critical operations that require stronger synchronization. Finally, we have paid careful attention to the engineering aspect: layer structure, good development practice, much feedback on the code, test suites. I think Antidote is ready to be tested by industrial users who might need its benefits.