Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
PACELC design principle
open-in-new
<h2 id="overview">Overview</h2> <p>The <a href="/facts/CAP_theorem/qnxvcbLp">CAP theorem</a> can be phrased as "PAC", the <a href="/facts/Proof_of_impossibility/rAQEghH8">impossibility theorem</a> that no <a href="/facts/Distributed_data_store/Raz2puRl">distributed data store</a> can be both consistent and available in executions that contains partitions. This can be proved by examining latency: if a system ensures consistency, then operation latencies grow with message delays, and hence operations cannot terminate eventually if the network is partitioned, i.e. the system cannot ensure availability.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p><p>In the absence of partitions, both consistency and availability can be satisfied.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> PACELC therefore goes further and examines how the system replicates data. Specifically, in the absence of partitions, an additional <a href="/facts/Trade-off/xY3nXnJN">trade-off</a> (ELC) exists between latency and consistency.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> If the store is atomically consistent, then the sum of the read and write delay is at least the message delay. In practice, most systems rely on explicit acknowledgments rather than timed delays to ensure delivery, requiring a full network round trip and therefore message delay on both reads and writes to ensure consistency.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> In low latency systems, in contrast, consistency is relaxed in order to reduce latency.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p><p>There are four configurations or tradeoffs in the PACELC space: </p> <ul><li>PA/EL - prioritize availability and latency over consistency</li> <li>PA/EC - when there is a partition, choose availability; else, choose consistency</li> <li>PC/EL - when there is a partition, choose consistency; else, choose latency</li> <li>PC/EC - choose consistency at all times</li></ul> <p>PC/EC and PA/EL provide natural cognitive models for an application developer. A PC/EC system provides a firm guarantee of atomic consistency, as in ACID, while PA/EL provides high availability and low latency with a more complex consistency model. In contrast, PA/EC and PC/EL systems only make conditional guarantees of consistency. The developer still has to write code to handle the cases where the guarantee is not upheld. PA/EC systems are rare outside of the in-memory data grid industry, where systems are localized to geographic regions and the latency vs. consistency tradeoff is not significant.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> PC/EL is even more tricky to understand. PC does not indicate that the system is fully consistent; rather it indicates that the system does not reduce consistency beyond the baseline consistency level when a network partition occurs—instead, it reduces availability.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>Some experts like Marc Brooker argue that the <a href="/facts/CAP_theorem/qnxvcbLp">CAP theorem</a> is particularly relevant in intermittently connected environments, such as those related to the <a href="/facts/Internet_of_things/rwwGAxn3">Internet of Things</a> (IoT) and <a href="/facts/Mobile_app/r7vp6meo">mobile applications</a>. In these contexts, devices may become partitioned due to challenging physical conditions, such as <a href="/facts/Power_outage/CBp7xY9w">power outages</a> or when entering confined spaces like elevators. For <a href="/facts/Distributed_computing/o5nyhqTF">distributed systems</a>, such as <a href="/facts/Cloud_computing/guhg0FGV">cloud applications</a>, it is more appropriate to use the PACELC theorem, which is more comprehensive and considers trade-offs such as <a href="/facts/Latency_(engineering)/6Bjhn30H">latency</a> and <a href="/facts/Consistency_(database_systems)/GmTWXGKA">consistency</a> even in the absence of network partitions.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p> <h2 id="history">History</h2> <p>The PACELC theorem was first described by <a href="/facts/Daniel_Abadi/vhs9IzKL">Daniel Abadi</a> from <a href="/facts/Yale_University/KUdS6jt1">Yale University</a> in 2010 in a blog post,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> which he later clarified in a paper in 2012.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> The purpose of PACELC is to address his thesis that "Ignoring the consistency/latency trade-off of replicated systems is a major oversight [in CAP], as it is present at all times during system operation, whereas CAP is only relevant in the arguably rare case of a network partition." The PACELC theorem was proved formally in 2018 in a SIGACT News article.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p> <h2 id="database-pacelc-ratings">Database PACELC ratings</h2> <p><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> Original database PACELC ratings are from.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> Subsequent updates contributed by wikipedia community. </p> <ul><li>The default versions of <a href="https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf">Amazon's early (internal) Dynamo</a>, <a href="/facts/Apache_Cassandra/WCJyV4rA">Cassandra</a>, <a href="/facts/Riak/zhRLQHh8">Riak</a>, and <a href="/facts/Cosmos_DB/rCAusDul">Cosmos DB</a> are PA/EL systems: if a partition occurs, they give up consistency for availability, and under normal operation they give up consistency for lower latency.</li> <li>Fully ACID systems such as <a href="/facts/VoltDB/JRz68XXT">VoltDB</a>/H-Store, Megastore, <a href="/facts/MySQL_Cluster/BwXDHev6">MySQL Cluster</a>, and <a href="/facts/PostgreSQL/LHdXuHfl">PostgreSQL</a> are PC/EC: they refuse to give up consistency, and will pay the availability and latency costs to achieve it. <a href="/facts/Bigtable/xlXLKV0t">Bigtable</a> and related systems such as <a href="/facts/Apache_HBase/D4XU1dqK">HBase</a> are also PC/EC.</li> <li>Amazon DynamoDB (launched January 2012) is quite different from the <a href="https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf">early (Amazon internal) Dynamo</a> which was considered for the PACELC paper.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> DynamoDB follows a strong leader model, where every write is strictly serialized (and conditional writes carry no penalty) and supports read-after-write consistency. This guarantee does not apply to "Global Tables<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a>" across regions. The DynamoDB SDKs use eventually consistent reads by default (improved availability and throughput), but when a consistent read is requested the service will return either a current view to the item or an error.</li> <li>Couchbase provides a range of consistency and availability options during a partition, and equally a range of latency and consistency options with no partition. Unlike most other databases, Couchbase doesn't have a single API set nor does it scale/replicate all data services homogeneously. For writes, Couchbase favors Consistency over Availability making it formally CP, but on read there is more user-controlled variability depending on index replication, desired consistency level and type of access (single document lookup vs range scan vs full-text search, etc.). On top of that, there is then further variability depending on cross-datacenter-replication (XDCR) which takes multiple CP clusters and connects them with asynchronous replication and Couchbase Lite which is an embedded database and creates a fully multi-master (with revision tracking) distributed topology.</li> <li><a href="/facts/Cosmos_DB/rCAusDul">Cosmos DB</a> supports five tunable consistency levels that allow for tradeoffs between C/A during P, and L/C during E. <a href="/facts/Cosmos_DB/rCAusDul">Cosmos DB</a> never violates the specified consistency level, so it's formally CP.</li> <li><a href="/facts/MongoDB/9myQKGoY">MongoDB</a> can be classified as a PA/EC system. In the baseline case, the system guarantees reads and writes to be consistent.</li> <li>PNUTS is a PC/EL system.</li> <li>Hazelcast IMDG and indeed most in-memory data grids are an implementation of a PA/EC system; Hazelcast can be configured to be EL rather than EC.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> Concurrency primitives (Lock, AtomicReference, CountDownLatch, etc.) can be either PC/EC or PA/EC.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a></li> <li>FaunaDB implements Calvin, a transaction protocol created by Dr. Daniel Abadi, the author<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> of the PACELC theorem, and offers users adjustable controls for LC tradeoff. It is PC/EC for strictly serializable transactions, and EL for serializable reads.</li></ul> <table><tbody><tr><th>DDBS</th><th>P+A</th><th>P+C</th><th>E+L</th><th>E+C</th></tr><tr><td>Aerospike<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a></td><td></td><td>paid only</td><td>optional</td><td></td></tr><tr><td>Bigtable/HBase</td><td></td><td></td><td></td><td></td></tr><tr><td>Cassandra</td><td></td><td></td><td><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a></td><td><a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a></td></tr><tr><td>Cosmos DB</td><td></td><td></td><td> <a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a></td><td></td></tr><tr><td>Couchbase</td><td></td><td></td><td></td><td></td></tr><tr><td>Dynamo</td><td></td><td></td><td><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a></td><td></td></tr><tr><td>DynamoDB</td><td></td><td></td><td></td><td></td></tr><tr><td>FaunaDB<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a></td><td></td><td></td><td></td><td></td></tr><tr><td>Hazelcast IMDG<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a><a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a></td><td></td><td></td><td></td><td></td></tr><tr><td>Megastore</td><td></td><td></td><td></td><td></td></tr><tr><td>MongoDB</td><td></td><td></td><td></td><td></td></tr><tr><td>MySQL Cluster</td><td></td><td></td><td></td><td></td></tr><tr><td>PNUTS</td><td></td><td></td><td></td><td></td></tr><tr><td>PostgreSQL</td><td></td><td></td><td></td><td></td></tr><tr><td>Riak</td><td></td><td></td><td><a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a></td><td></td></tr><tr><td>SpiceDB<a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a></td><td></td><td></td><td></td><td></td></tr><tr><td>VoltDB/H-Store</td><td></td><td></td><td></td><td></td></tr></tbody></table> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/CAP_theorem/qnxvcbLp">CAP theorem</a></li> <li><a href="/facts/Consistency_model/a8Xphrs7">Consistency model</a></li> <li><a href="/facts/Fallacies_of_distributed_computing/8cWyyu3X">Fallacies of distributed computing</a></li> <li><a href="/facts/Lambda_architecture/gSC3JA38">Lambda architecture</a> (solution)</li> <li><a href="/facts/Paxos_(computer_science)/S7KYPNb6">Paxos (computer science)</a></li> <li><a href="/facts/Project_management_triangle/NylkbaBg">Project management triangle</a></li> <li><a href="/facts/Raft_(algorithm)/ppsFb4Xq">Raft (algorithm)</a></li> <li><a href="/facts/Trilemma/SQ82oo6z">Trilemma</a></li></ul> <h2 id="notes">Notes</h2> <h2 id="external-links">External links</h2> <ul><li><a href="https://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf">"Consistency Tradeoffs in Modern Distributed Database System Design", by Daniel J. Abadi, Yale University</a> Original paper that formalized PACELC</li> <li><a href="https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html">"Problems with CAP, and Yahoo's little known NoSQL system", by Daniel J. Abadi, Yale University</a>. Original blog post that first described PACELC</li> <li><a href="https://uwaterloo.ca/distributed-algorithms-systems-lab/sites/default/files/uploads/files/proving_pacelc.pdf">"Proving PACELC", by Wojciech Golab, University of Waterloo</a> Formal proof of the PACELC theorem</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Golab, Wojciech (2018). "Proving PACELC". ACM SIGACT News. 49 (1): 73–81. doi:10.1145/3197406.3197420. S2CID 3989621. <a href="https://dl.acm.org/doi/10.1145/3197406.3197420" target="_blank">https://dl.acm.org/doi/10.1145/3197406.3197420</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Abadi, Daniel J. (2010-04-23). "DBMS Musings: Problems with CAP, and Yahoo's little known NoSQL system". Retrieved 2016-09-11. <a href="https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html" target="_blank">https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Abadi, Daniel J. "Consistency Tradeoffs in Modern Distributed Database System Design" (PDF). Yale University. <a href="http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf" target="_blank">http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Golab, Wojciech (2018). "Proving PACELC". ACM SIGACT News. 49 (1): 73–81. doi:10.1145/3197406.3197420. S2CID 3989621. <a href="https://dl.acm.org/doi/10.1145/3197406.3197420" target="_blank">https://dl.acm.org/doi/10.1145/3197406.3197420</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Abadi, Daniel J. (2010-04-23). "DBMS Musings: Problems with CAP, and Yahoo's little known NoSQL system". Retrieved 2016-09-11. <a href="https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html" target="_blank">https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Abadi, Daniel (15 July 2019). "The dangers of conditional consistency guarantees". DBMS Musings. Retrieved 29 August 2024. <a href="https://dbmsmusings.blogspot.com/2019/07/the-dangers-of-conditional-consistency.html" target="_blank">https://dbmsmusings.blogspot.com/2019/07/the-dangers-of-conditional-consistency.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Abadi, Daniel J. "Consistency Tradeoffs in Modern Distributed Database System Design" (PDF). Yale University. <a href="http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf" target="_blank">http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly Media. ISBN 978-1449373320. <a href="978-1449373320" target="_blank">978-1449373320</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Abadi, Daniel J. (2010-04-23). "DBMS Musings: Problems with CAP, and Yahoo's little known NoSQL system". Retrieved 2016-09-11. <a href="https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html" target="_blank">https://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Abadi, Daniel J. "Consistency Tradeoffs in Modern Distributed Database System Design" (PDF). Yale University. <a href="http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf" target="_blank">http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Golab, Wojciech (2018). "Proving PACELC". ACM SIGACT News. 49 (1): 73–81. doi:10.1145/3197406.3197420. S2CID 3989621. <a href="https://dl.acm.org/doi/10.1145/3197406.3197420" target="_blank">https://dl.acm.org/doi/10.1145/3197406.3197420</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Abadi, Daniel J. "Consistency Tradeoffs in Modern Distributed Database System Design" (PDF). Yale University. <a href="http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf" target="_blank">http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Abadi, Daniel J.; Murdopo, Arinto (2012-04-17). "Consistency Tradeoffs in Modern Distributed Database System Design". Retrieved 2022-07-18. <a href="https://www.slideshare.net/arinto/consistency-tradeoffinmoderndb" target="_blank">https://www.slideshare.net/arinto/consistency-tradeoffinmoderndb</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Abadi, Daniel J.; Murdopo, Arinto (2012-04-17). "Consistency Tradeoffs in Modern Distributed Database System Design". Retrieved 2022-07-18. <a href="https://www.slideshare.net/arinto/consistency-tradeoffinmoderndb" target="_blank">https://www.slideshare.net/arinto/consistency-tradeoffinmoderndb</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>"Global tables - multi-Region replication for DynamoDB". AWS Documentation. Retrieved 4 January 2023. <a href="https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/GlobalTables.html" target="_blank">https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/GlobalTables.html</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Abadi, Daniel (2017-10-08). "DBMS Musings: Hazelcast and the Mythical PA/EC System". DBMS Musings. Retrieved 2017-10-20. <a href="https://dbmsmusings.blogspot.com/2017/10/hazelcast-and-mythical-paec-system.html" target="_blank">https://dbmsmusings.blogspot.com/2017/10/hazelcast-and-mythical-paec-system.html</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>"Hazelcast IMDG Reference Manual". docs.hazelcast.org. Retrieved 2020-09-17. <a href="https://docs.hazelcast.org/docs/4.0.2/manual/html-single/index.html#cp-subsystem" target="_blank">https://docs.hazelcast.org/docs/4.0.2/manual/html-single/index.html#cp-subsystem</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Abadi, Daniel J. "Consistency Tradeoffs in Modern Distributed Database System Design" (PDF). Yale University. <a href="http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf" target="_blank">http://www.cs.umd.edu/~abadi/papers/abadi-pacelc.pdf</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Porter, Kevin (29 March 2023). "Where does aerospike fall in PACELC?". Aerospike Community Forum. Retrieved 30 March 2023. <a href="https://discuss.aerospike.com/t/where-does-aerospike-fall-in-pacelc/10111/2" target="_blank">https://discuss.aerospike.com/t/where-does-aerospike-fall-in-pacelc/10111/2</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Dynamo, Cassandra, and Riak have user-adjustable settings to control the LC tradeoff.[6] <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Dynamo, Cassandra, and Riak have user-adjustable settings to control the LC tradeoff.[6] <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Cosmos DB has five selectable consistency levels to control the LC tradeoff.[11] <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Dynamo, Cassandra, and Riak have user-adjustable settings to control the LC tradeoff.[6] <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Abadi, Daniel (2018-09-21). "DBMS Musings: NewSQL database systems are failing to guarantee consistency, and I blame Spanner". DBMS Musings. Retrieved 2019-02-23. <a href="https://dbmsmusings.blogspot.com/2018/09/newsql-database-systems-are-failing-to.html" target="_blank">https://dbmsmusings.blogspot.com/2018/09/newsql-database-systems-are-failing-to.html</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Abadi, Daniel (2017-10-08). "DBMS Musings: Hazelcast and the Mythical PA/EC System". DBMS Musings. Retrieved 2017-10-20. <a href="https://dbmsmusings.blogspot.com/2017/10/hazelcast-and-mythical-paec-system.html" target="_blank">https://dbmsmusings.blogspot.com/2017/10/hazelcast-and-mythical-paec-system.html</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>"Hazelcast IMDG Reference Manual". docs.hazelcast.org. Retrieved 2020-09-17. <a href="https://docs.hazelcast.org/docs/4.0.2/manual/html-single/index.html#cp-subsystem" target="_blank">https://docs.hazelcast.org/docs/4.0.2/manual/html-single/index.html#cp-subsystem</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>Dynamo, Cassandra, and Riak have user-adjustable settings to control the LC tradeoff.[6] <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> <li id="fn:28"><p>Zelinskie, Jimmy (2024-04-23). "SpiceDB Concepts: Consistency". SpiceDB documentation. Retrieved 2024-05-02. <a href="https://authzed.com/docs/spicedb/concepts/consistency" target="_blank">https://authzed.com/docs/spicedb/concepts/consistency</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li> </ol>