Concise Server-Wide Causality Management for Eventually Consistent Data Stores - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

Concise Server-Wide Causality Management for Eventually Consistent Data Stores

(1, 2, 3) , (1, 3, 2) , (1, 3, 2) , (1, 3, 2)
1
2
3

Abstract

Large scale distributed data stores rely on optimistic replication to scale and remain highly available in the face of network partitions. Managing data without coordination results in eventually consistent data stores that allow for concurrent data updates. These systems often use anti-entropy mechanisms (like Merkle Trees) to detect and repair divergent data versions across nodes. However, in practice hash-based data structures are too expensive for large amounts of data and create too many false conflicts.Another aspect of eventual consistency is detecting write conflicts. Logical clocks are often used to track data causality, necessary to detect causally concurrent writes on the same key. However, there is a non-negligible metadata overhead per key, which also keeps growing with time, proportional with the node churn rate. Another challenge is deleting keys while respecting causality: while the values can be deleted, per-key metadata cannot be permanently removed without coordination.We introduce a new causality management framework for eventually consistent data stores, that leverages node logical clocks (Bitmapped Version Vectors) and a new key logical clock (Dotted Causal Container) to provides advantages on multiple fronts: 1) a new efficient and lightweight anti-entropy mechanism; 2) greatly reduced per-key causality metadata size; 3) accurate key deletes without permanent metadata.
Fichier principal
Vignette du fichier
978-3-319-19129-4_6_Chapter.pdf (492.64 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01775033 , version 1 (24-04-2018)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Ricardo Gonçalves, Paulo Sérgio Almeida, Carlos Baquero, Victor Fonte. Concise Server-Wide Causality Management for Eventually Consistent Data Stores. 15th IFIP International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2015, Grenoble, France. pp.66-79, ⟨10.1007/978-3-319-19129-4_6⟩. ⟨hal-01775033⟩
31 View
93 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More