ECROs: building global scale systems from sequential code

Research output: Chapter in Book/Report/Conference proceedingConference paper

Abstract

To ease the development of geo-distributed applications, replicated data types (RDTs) offer a familiar programming interface while ensuring state convergence, low latency, and high availability. However, RDTs are still designed exclusively by experts using ad-hoc solutions that are error-prone and result in brittle systems. Recent works statically detect conflicting operations on existing data types and coordinate those at runtime to guarantee convergence and preserve application invariants. However, these approaches are too conservative, imposing coordination on a large number of operations. In this work, we propose a principled approach to design and implement efficient RDTs taking into account application invariants. Developers extend sequential data types with a distributed specification, which together form an RDT. We statically analyze the specification to detect conflicts and unravel their cause. This information is then used at runtime to serialize concurrent operations safely and efficiently. Our approach derives a correct RDT from any sequential data type without changes to the data type's implementation and with minimal coordination. We implement our approach in Scala and develop an extensive portfolio of RDTs. The evaluation shows that our approach provides performance similar to conflict-free replicated data types for commutative operations, and considerably improves the performance of non-commutative operations, compared to existing solutions.

Original languageEnglish
Title of host publicationProceedings of the ACM on Programming Languages
PublisherACM
Pages1-30
Number of pages30
Volume5
DOIs
Publication statusPublished - 15 Oct 2021
EventOOPSLA 2021 - Swissotel, Chicago, United States
Duration: 17 Oct 202122 Oct 2021
https://2021.splashcon.org/track/splash-2021-oopsla

Publication series

NameProceedings of the ACM on Programming Languages
PublisherAssociation for Computing Machinery
ISSN (Print)2475-1421

Conference

ConferenceOOPSLA 2021
CountryUnited States
CityChicago
Period17/10/2122/10/21
Internet address

Keywords

  • replication
  • data structures
  • eventual consistency

Fingerprint

Dive into the research topics of 'ECROs: building global scale systems from sequential code'. Together they form a unique fingerprint.

Cite this