Conflict-free Replicated DataTypes in Practice

1/11/2017

By Georges Younes and Vitor Enes, HASLab, INESC TEC & University of Minho.

Abstract. Replication is a currently a de facto approach for highly scalable and available systems. In particular, full replication requires all system replicas to be equal, and thus consistent, even under network-partition failures (where some replicas may be unreachable by others). Since such failures often occur in most large-scale systems, a strong consistency model (which requires full synchronization among replicas on each request) would negatively impact availability. However, as giving up availability is nowadays not an option for large-scale service providers such as Google, Microsoft, Facebook, Amazon, Basho, they tend to adopt weaker consistency models such as eventual consistency (EC) — that allows a replica to be accessed without prompt sync with others. In EC systems, replicas are allowed to temporarily diverge, provided that this divergence can, later on, be reconciled into a common consistent state. Practical systems used to resolve conflicts in ad-hoc ways that can lead to anomalies, as the shopping cart in Amazon’s Dynamo DB. Recently, Conflict-free Replicated Data Types (CRDTs) were introduced to avoid these issues in a systematic way without the burden of data-type-specific crafting of conflict resolution. This talk will focus on introducing the different flavours of CRDTs, and briefly showing how we implemented them in practical and real systems like Redis, Antidote DB, Lasp language, and a benchmarking platform.

Keywords. Distributed Systems, Conflict-free Replicated Data Types, Eventual Consistency.

About the speakers.

Georges Younes is currently a 2nd year MAP-I PhD student, under the supervision of Prof. Carlos Baquero, and hosted by HASLab, INESC TEC and University of Minho. He was awarded a grant from Google within the Google Summer of Code program in 2016 for his work on implementing pure-op-based CRDTs in Lasp programming language – which will partially be covered in the talk. He was also granted an internship from NOVA university of Lisbon for his work within the EU FP7 SyncFree project. Georges received his MSc in Informatics and Telecommunication from the University of Toulouse, France, and was hosted by HASLab to accomplish his MSc thesis work that was partially published at the ECOOP PMLDC’16 workshop in Italy.

Vitor Enes is a MSc student at the Department of Informatics of the University of Minho, supervised by Prof. Carlos Baquero, and hosted by HASLab, INESC TEC. He has been granted two internships from HASLab and from NOVA University of Lisbon to pursue his research, mainly within his MSc program and the EU FP7 SyncFree project, which was partially published at ECOOP PMLDC’16 workshop in Italy. Vitor holds a Bachelor degree in Computer Science from University of Minho as well. He is working on Distributed Systems (Eventual Consistency), but he also enjoys Formal Methods (although he knows very little about them). He hopes that, one day, he can work on both of them to make Distributed Systems work better.