Log-Structured Conflict-Free Replicated Data Types

Report ID: 
2021-01
Authors: 
Nazmus Saquib, Chandra Krintz, and Rich Wolski
Date: 
2021-01-01 00:00:00

Abstract

Conflict-Free Replicated Data Types (CRDTs) are highly available data types conforming to strong eventual consistency.  CRDTs do not need synchronization for concurrent updates and can resolve conflicts locally without extra coordination.  In this paper, we introduce Log-Structured Conflict-Free Replicated Data Types (LSCRDTs) that leverage the advantages of both CRDTs and append-only logs.  We show that a log-based approach addresses several well-known challenges to using CRDTs.  First, it facilitates a uniform approach to reversing operations.  Second, it removes constraints such as exactly-once delivery and idempotence of operations which are commonly associated with operation-based CRDTs.  Third, it provides robustness via efficient access to earlier versions of the data types.  We select three commonly used CRDTs for our study: register, counter, and set. We show how each is implemented using LSCRDT, demonstrate the benefits achieved, and present an empirical evaluation of their performance.

Document

PDF icon paper.pdf