The FuzzyLog: A Partially Ordered Shared Log

Authors: 

Joshua Lockerman, Yale University; Jose M. Faleiro, UC Berkeley; Juno Kim, UC San Diego; Soham Sankaran, Cornell University; Daniel J. Abadi, University of Maryland, College Park; James Aspnes, Yale University; Siddhartha Sen, Microsoft Research; Mahesh Balakrishnan, Yale University / Facebook

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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

Presentation Audio

BibTeX
@inproceedings {222573,
author = {Joshua Lockerman and Jose M. Faleiro and Juno Kim and Soham Sankaran and Daniel J. Abadi and James Aspnes and Siddhartha Sen and Mahesh Balakrishnan},
title = {The FuzzyLog: A Partially Ordered Shared Log},
booktitle = {13th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 18)},
year = {2018},
isbn = {978-1-931971-47-8},
address = {Carlsbad, CA},
pages = {357--372},
url = {https://www.usenix.org/conference/osdi18/presentation/lockerman},
publisher = {{USENIX} Association},
}