The SNOW theorem and latency-optimal read-only transactions

Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, Wyatt Lloyd

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016
PublisherUSENIX Association
Pages135-150
Number of pages16
ISBN (Electronic)9781931971331
StatePublished - Jan 1 2016
Event12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016 - Savannah, United States
Duration: Nov 2 2016Nov 4 2016

Publication series

NameProceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016

Conference

Conference12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016
CountryUnited States
CitySavannah
Period11/2/1611/4/16

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'The SNOW theorem and latency-optimal read-only transactions'. Together they form a unique fingerprint.

Cite this