Building Tunable CRDTs

Abstract

Nowadays multiple large-scale services are hosted on the Internet, many of them with millions of daily users. These systems need to scale efficiently, providing fast access and being always available, despite failures of the servers or of the network and high amounts of users accessing the service. As such, these services typically trade strong consistency for high availability and low latency. However, not having strong consistency implies that conflicts arising from concurrent updates will occur, which need to be solved. Conflict-Free Replicated Data Types (CRDTs) provide low latency and solve conflicts automatically, ensuring eventual state convergence. However, one shortcoming of CRDTs is the way they deal with concurrency conflicts – usually they solve them automatically by applying a specific policy. For example, in a set, e priority to the add. These policies are limited and not adequate for all applications, especially since CRDTs don’t allow for policies dependent on the application context, such as, give priority to add if it’s element e, but give priority to remove if it’s element f. As such, in this thesis we propose a new type of CRDTs, called tunable CRDT (t- CRDT), which allows the programmer to specify for each operation what is the desired conflict solving policy, by supplying a simple boolean function. The programmer can either supply his own policy or use one of the many we provide in our t-CRDT library. T-CRDTs solve conflicts automatically by applying the policies in each operation. This new type of CRDTs adapt more easily to each application specific needs, as it gives more control to the programmer while still having the main properties of CRDTs, i.e., eventual convergence of state and low latency. With this, it is expected that more applications can start using CRDTs as their data solution and benefit from their properties.