Existential consistency: Measuring and understanding consistency at Facebook

Haonan Lu, Kaushik Veeraraghavan, Philippe Ajoux, Jim Hunt, Yee Jiun Song, Wendy Tobagus, Sanjeev Kumar, Wyatt Lloyd

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

71 Scopus citations


Replicated storage for large Web services faces a trade-off between stronger forms of consistency and higher performance properties. Stronger consistency prevents anomalies, i.e., unexpected behavior visible to users, and reduces programming complexity. There is much recent work on improving the performance properties of systems with stronger consistency, yet the flip-side of this trade-off remains elusively hard to quantify. To the best of our knowledge, no prior work does so for a large, production Web service. We use measurement and analysis of requests to Face-book's TAO system to quantify how often anomalies happen in practice, i.e., when results returned by eventually consistent TAO differ from what is allowed by stronger consistency models. For instance, our analysis shows that 0.0004% of reads to vertices would return different results in a linearizable system. This in turn gives insight into the benefits of stronger consistency; 0.0004% of reads are potential anomalies that a linearizable system would prevent. We directly study local consistency models-i.e., those we can analyze using requests to a sample of objects-and use the relationships between models to infer bounds on the others. We also describe a practical consistency monitoring system that tracks φ-consistency, a new consistency metric ideally suited for health monitoring. In addition, we give insight into the increased programming complexity of weaker consistency by discussing bugs our monitoring uncovered, and anti-patterns we teach developers to avoid.

Original languageEnglish (US)
Title of host publicationSOSP 2015 - Proceedings of the 25th ACM Symposium on Operating Systems Principles
PublisherAssociation for Computing Machinery, Inc
Number of pages16
ISBN (Electronic)9781450338349
StatePublished - Oct 4 2015
Externally publishedYes
Event25th ACM Symposium on Operating Systems Principles, SOSP 2015 - Monterey, United States
Duration: Oct 5 2015Oct 7 2015

Publication series

NameSOSP 2015 - Proceedings of the 25th ACM Symposium on Operating Systems Principles


Other25th ACM Symposium on Operating Systems Principles, SOSP 2015
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Software
  • Electrical and Electronic Engineering
  • Computer Science Applications


Dive into the research topics of 'Existential consistency: Measuring and understanding consistency at Facebook'. Together they form a unique fingerprint.

Cite this