%0 Conference Paper
%B 36th IEEE International Symposium on Reliable Distributed Systems
%D 2017
%T DottedDB: Anti-Entropy without Merkle Trees, Deletes without Tombstones
%A Ricardo Gonçalves
%A Paulo Sérgio Almeida
%A Carlos Baquero Moreno
%A Vitor Fonte
%C Hong Kong, China
%I IEEE
%S SRDS 2017
%X <p>To achieve high availability in the face of network partitions, many distributed databases adopt eventual consistency, allow temporary conflicts due to concurrent writes, and use some form of per-key logical clock to detect and resolve such conflicts. Furthermore, nodes synchronize periodically to ensure replica convergence in a process called anti-entropy, normally using Merkle Trees. We present the design of DottedDB, a Dynamo-like key-value store, which uses a novel node-wide logical clock framework, overcoming three fundamental limitations of the state of the art: (1) minimize the metadata per key necessary to track causality, avoiding its growth even in the face of node churn; (2) correctly and durably delete keys, with no need for tombstones; (3) offer a lightweight anti-entropy mechanism to converge replicated data, avoiding the need for Merkle Trees. We evaluate DottedDB against MerkleDB, an otherwise identical database, but using per-key logical clocks and Merkle Trees for anti-entropy, to precisely measure the impact of the novel approach. Results show that: causality metadata per object always converges rapidly to only one id-counter pair; distributed deletes are correctly achieved without global coordination and with constant metadata; divergent nodes are synchronized faster, with less memory-footprint and with less communication overhead than using Merkle Trees.</p>
%8 28 September
%> https://haslab.uminho.pt/sites/default/files/tome/files/dotteddb_srds.pdf