The SNOW Theorem and Latency-Optimal Read-Only Transactions

Authors: 

Haonan Lu, University of Southern California; Christopher Hodsdon, University of Southern California; Khiem Ngo, University of Southern California; Shuai Mu, New York University; Wyatt Lloyd, University of Southern California

Abstract: 

Scalable storage systems where data is sharded across many machines are now the norm for Web services as their data has grown beyond what a single machine can handle. Consistently reading data across different shards requires transactional isolation for the reads. Yet a Web service may read from its data store hundreds or thousands of times for a single page load and must minimize read latency to keep response times low. Examining the read-only transaction algorithms for many recent academic and industrial scalable storage systems suggests there is a tradeoff between their power—expressed as the consistency they provide and their compatibility with other types of transactions—and their latency.

We show that this tradeoff is fundamental by proving the SNOW Theorem, an impossibility result that states that no read-only transaction algorithm can provide both the lowest latency and the highest power. We then use the tight boundary from the theorem to guide the design of new read-only transaction algorithms for two scalable storage systems, COPS and Rococo. We implement our new algorithms and then evaluate them to demonstrate they provide lower latency for read-only transactions and to understand their impact on overall throughput.

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 {199396,
author = {Haonan Lu and Christopher Hodsdon and Khiem Ngo and Shuai Mu and Wyatt Lloyd},
title = {The {SNOW} Theorem and Latency-Optimal Read-Only Transactions},
booktitle = {12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16)},
year = {2016},
isbn = {978-1-931971-33-1},
address = {Savannah, GA},
pages = {135--150},
url = {https://www.usenix.org/conference/osdi16/technical-sessions/presentation/lu},
publisher = {{USENIX} Association},
}