Joshua Lockerman, Jose M. Faleiro, Juno Kim, Soham Sankaram, Daniel J. Abadi, James Aspnes, Siddhartha Sen, and Mahesh Balakrishnan. The FuzzyLog: A partially ordered shared log. 13th USENIX Symposium on Operating Systems Design and Implementation, October 2018, pp. 357–372.
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 FuzzyLog for linear scalability, flexible consistency guarantees (e.g., causal+ consistency), and network partition tolerance. On a 6-node Dapple deployment, our FuzzyLogbased ZooKeeper supports 3M/sec single-key writes, and 150K/sec atomic cross-shard renames.
@inproceedings{Lockerman+2018,
author = {Lockerman, Joshua and Faleiro, Jose M. and Kim, Juno and Sankaram, Soham and Abadi, Daniel J. and Aspnes, James and Siddhartha, Sen and Balakrishnan, Mahesh},
title = {The {FuzzyLog}: A Partially Ordered Shared Log},
month = oct,
year = 2018,
booktitle={13th USENIX Symposium on Operating Systems Design and Implementation},
pages={357--372}
}