Consistency Tradeoffs in Modern Distributed Database System Design
📜 Abstract
The CAP theorem’s impact on modern distributed database system design is more limited than is often perceived. Another tradeoff—between consistency and latency—has had a more direct influence on several well-known DDBSs. A proposed new formulation, PACELC, unifies this tradeoff with CAP.
✨ Summary
Summary
The paper argues that the CAP theorem is frequently misinterpreted as imposing consistency and availability restrictions during normal operation. CAP applies specifically when a network partition occurs; in the absence of a partition, it does not prevent a distributed database from providing strong consistency and high availability simultaneously. The paper identifies a separate and continuously present tradeoff between consistency and latency, arising primarily from data replication. Synchronous replication and quorum-based coordination can improve consistency but increase latency, especially across wide-area networks, while asynchronous replication and geographically local reads can reduce latency at the cost of stale or inconsistent reads.
The paper uses Dynamo, Cassandra, Riak, PNUTS, MongoDB, BigTable, VoltDB/H-Store, and Megastore to illustrate these design choices. It then proposes PACELC: if there is a partition, a system trades off availability and consistency; else, during normal operation, it trades off latency and consistency. The paper classifies several distributed databases using this framework, including Dynamo, Cassandra, and Riak as PA/EL systems, PNUTS as PC/EL, MongoDB as PA/EC, and systems such as Megastore, BigTable, HBase, and VoltDB/H-Store as PC/EC.
Subsequent research adopted PACELC as a framework for analyzing distributed-storage tradeoffs. A 2014 study on consistency-latency tradeoffs cited this paper and developed PCAP systems for Cassandra and Riak, including geo-distributed deployments with consistency and latency service-level objectives. (assured-cloud-computing.illinois.edu) A 2014 PVLDB paper applied PACELC to the design of a telecom data-storage system, explicitly using the framework to reason about consistency, availability, partition tolerance, and latency. (vldb.org) A 2023 review likewise treats CAP and PACELC as foundational frameworks for surveying research on replication, consistency models, quorum protocols, and distributed-database performance. (nti.khai.edu) These references indicate that the paper’s principal influence has been conceptual: PACELC became a commonly used vocabulary for discussing normal-operation consistency/latency choices alongside failure-time consistency/availability choices.