@inproceedings{lockerman2018the,
author = {Lockerman, Joshua and Faleiro, Jose and Kim, Juno and Sankaran, Soham and Abadi, Daniel J. and Aspnes, James and Sen, Siddhartha and Balakrishnan, Mahesh},
title = {The FuzzyLog: A Partially Ordered Shared Log},
booktitle = {13th USENIX Symposium on Operating Systems Design and Implementation (OSDI)},
year = {2018},
month = {October},
abstract = {The FuzzyLog is a partially ordered shared log abstraction. Distributed applications can concurrently append to the partial order and play it back. FuzzyLog applications obtain the benefits of an underlying shared log -- extracting strong consistency, durability, and failure atomicity in simple ways -- without suffering from its drawbacks. By exposing a partial order, the FuzzyLog enables three key capabilities for applications: linear scaling for throughput and capacity (without sacrificing atomicity), weaker consistency guarantees, and tolerance to network partitions. We present Dapple, a distributed implementation of the FuzzyLog abstraction that stores the partial order compactly and supports efficient appends/playback via a new ordering protocol. We implement several data structures and applications over the FuzzyLog, including several map variants as well as a ZooKeeper implementation. Our evaluation shows that these applications are compact, fast, and flexible: they retain the simplicity (100s of lines of code) and strong semantics (durability and failure atomicity) of a shared log design while exploiting the partial order of the Fuzzy-
Log for linear scalability, flexible consistency guarantees (e.g., causal+ consistency), and network partition tolerance. On a 6-node Dapple deployment, our FuzzyLog-based ZooKeeper supports 3M/sec single-key writes, and 150K/sec atomic cross-shard renames.},
url = {http://approjects.co.za/?big=en-us/research/publication/the-fuzzylog-a-partially-ordered-shared-log/},
}