From Causality to Stability: Understanding and Reducing Meta-Data in CRDTs

Onderzoeksoutput: Chapter

1 Citaat (Scopus)

Samenvatting

Modern distributed applications increasingly replicate data to guarantee both high availability of systems and optimal user experience. Conflict-Free Replicated Data Types (CRDTs) are a family of data types specially designed for highly available systems that guarantee some form of eventual consistency. To ensure state convergence between replicas, CRDT implementations need to keep track of additional meta-data. This is not a scalable strategy, as a growing amount of meta-data has to be kept. In this paper, we show that existing solutions for this problem miss optimisation opportunities and may lead to less reactive CRDTs. For this, we analyse the relation between meta-data and the causality of operations in operation-based CRDTs. We explore a new optimisation strategy for pure operation-based CRDTs and show how it reduces memory overhead. Our approach takes advantage of the communication layer providing reliable delivery to determine causal stability, and as a result, meta-data can be removed sooner. We furthermore propose a solution for improving the reactivity of CRDTs built on a reliable causal broadcasting layer. We apply our strategy to pure-operation based CRDTs and validate our approach by measuring its impact on several different setups. The results show how our approach can lead to significant improvements in meta-data cleanup when compared to state-of-the-art techniques.
Originele taal-2English
TitelProceedings of the 17th International Conference on Managed Programming Languages and Runtimes (MPLR ’20)
UitgeverijACM
Pagina's1-12
Aantal pagina's12
ISBN van geprinte versie9781450388535
StatusPublished - okt 2020
Evenement17th International Conference on Managed Programming Languages & Runtimes -
Duur: 4 nov 20205 nov 2020
https://mplr2020.cs.manchester.ac.uk/index.php

Publicatie series

NaamProceedings of the 17th International Conference on Managed Programming Languages and Runtimes (MPLR ’20)

Conference

Conference17th International Conference on Managed Programming Languages & Runtimes
Verkorte titelMPLR '20
Periode4/11/205/11/20
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'From Causality to Stability: Understanding and Reducing Meta-Data in CRDTs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit