License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2017.23
URN: urn:nbn:de:0030-drops-86456
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8645/
Go to the corresponding LIPIcs Volume Portal

Jungnickel, Tim ; Oldenburg, Lennart ; Loibl, Matthias

Designing a Planetary-Scale IMAP Service with Conflict-free Replicated Data Types

pdf-format:
LIPIcs-OPODIS-2017-23.pdf (0.6 MB)

Abstract

Modern geo-replicated software serving millions of users across the globe faces the consequences of the CAP dilemma, i.e., the inevitable conflicts that arise when multiple nodes accept writes on shared state. The underlying problem is commonly known as fault-tolerant multi-leader replica- tion; actively researched in the distributed systems and database communities. As a more recent theoretical framework, Conflict-free Replicated Data Types (CRDTs) propose a solution to this problem by offering a set of always converging primitives. However, modeling non-trivial system state with CRDT primitives is a challenging and error-prone task. In this work, we propose a solution for a geo-replicated online service with fault-tolerant multi-leader replication based on CRDTs. We chose IMAP as use case due to its prevalence and simplicity. Therefore, we modeled an IMAP-CRDT and verified its correctness with the interactive theorem prover Isabelle/HOL. In order to bridge the gap between theory and practice, we implemented an open-source proto- type pluto and an IMAP benchmark for write-intensive workloads. We evaluated our prototype against the standard IMAP server Dovecot on a multi-continent public cloud. The results ex- pose the limitations of Dovecot with respect to response time performance and replication lag. Our prototype was able to leverage its conceptual advantages and outperformed Dovecot. We find that our approach is promising when facing the multitude of potential concurrency bugs in development of systems at planetary scale.

BibTeX - Entry

@InProceedings{jungnickel_et_al:LIPIcs:2018:8645,
  author =	{Tim Jungnickel and Lennart Oldenburg and Matthias Loibl},
  title =	{{Designing a Planetary-Scale IMAP Service with Conflict-free Replicated Data Types}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8645},
  URN =		{urn:nbn:de:0030-drops-86456},
  doi =		{10.4230/LIPIcs.OPODIS.2017.23},
  annote =	{Keywords: Geo-Replication, CRDT, Distributed Systems, IMAP, Isabelle/HOL}
}

Keywords: Geo-Replication, CRDT, Distributed Systems, IMAP, Isabelle/HOL
Collection: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Issue Date: 2018
Date of publication: 28.03.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI