Trade-offs of Distributed Data Stores : Theories and Theorems
Tags: captheorem, pacelc, distributedsystems, nosql
Published: 2022-08-13 05:30:00

**Distributed Data Store** refers to either a distributed database storing on a number of nodes (often in a replicated fashion)
_OR_ 
a computer network storing information on a number of peer network nodes.

Certain theorems describes potential limitations and trade-offs (say, in consistency) for distributed databases, CAP Theorem is one of them.
The **CAP Theorem** states that any distributed data store can provide only two of the following three guarantees :
Consistency-Availability-Tolerance towards Network Partition
This theorem is also named as Brewer's theorem after computer scientist Eric Brewer who gave it's hypothesis and the theorem was proved by Gilbert and Lynch.

Considering a distributed system with more than one node, 
In a <u>_Consistent_</u> system, once a client writes a value to any of the nodes and gets a response, it expects to get the latest value next time it read back from any of the nodes.
Being <u>_Available_</u> means all non-failing nodes continue to serve requests if the system is partitioned.
System should function correctly despite arbitrary <u>_Network Partitions_</u>.

It is important to note that Consistency in **_CAP Theorem [Consistent-Available-Partition-tolerant]_** isn't the same as in **_ACID [Atomic-Consistent-Isolated-Durable]_** database transactional properties.
CAP comes from the distributed systems theory, while ACID belongs to database systems one.
**_“C”_** in the CAP Theorem refers to <u>_each node in the system having the same data_</u>, the **_“C”_** in ACID refers to a <u>_single node enforcing the same rules on every potential commit_</u>, such as the type of a field or a field not being null.

![CAP Theorem with Databases that chooses CA, CP and AP](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l6kbgxbj8p87hnx38bsc.png)

![Summary Table with characteristics of the selected NoSQL databases](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q4w0kssdoddsuli2356f.png)

Database systems designed with traditional ACID guarantees in mind such as <u>_RDBMS_</u> choose consistency over availability, 
whereas systems designed around the BASE philosophy, common in the <u>_NoSQL_</u> movement for example, choose availability over consistency.
**Eventual consistency** is a consistency model used in distributed computing to achieve high availability, if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value. Eventually-consistent services are often classified as providing **_BASE semantics (Basically-available, Soft-state, Eventual consistency)_**.

<u>_Basically available_</u>: reading and writing operations are available as much as possible (using all nodes of a database cluster), but might not be consistent (the write might not persist after conflicts are reconciled, and the read might not get the latest write)
<u>_Soft-state_</u>: without consistency guarantees, after some amount of time, we only have some probability of knowing the state, since it might not yet have converged
<u>_Eventually consistent_</u>: If we execute some writes and then the system functions long enough, we can know the state of the data; any further reads of that data item will return the same value

**Consistency Model** specifies a contract between the programmer and a system, wherein the system guarantees that if the programmer follows the rules for operations on memory, memory will be consistent and the results of reading, writing, or updating memory will be predictable. Consistency models are used in distributed systems like distributed shared memory systems or distributed data stores (such as filesystems, databases, optimistic replication systems or web caching).

**PACELC Theorem** is an extension to the CAP theorem. It states that an additional trade-off exists: between latency and consistency, even in absence of partitions, thus providing a more complete portrayal of the potential consistency trade-offs for distributed systems. 

PACELC Theorem states that in case of network partitioning (P) in a distributed computer system, one has to choose between availability (A) and consistency (C), but else (E), even when the system is running normally in the absence of partitions, one has to choose between latency (L) and consistency (C). PACELC reorders CAP into PAC and adds a statement about what happens when the network is present. That is, you may choose between increased latency and consistency (Else Latency or Consistency).

**Database PACELC ratings :**
The default versions of <u>_DynamoDB_</u>, <u>_Cassandra_</u>, <u>_Riak_</u> and <u>_Cosmos DB_</u> 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.
Fully ACID systems such as <u>_VoltDB/H-Store_</u>, <u>_Megastore_</u>, <u>_MySQL Cluster_</u> and <u>_PostgreSQL_</u> are PC/EC: they refuse to give up consistency, and will pay the availability and latency costs to achieve it. <u>_BigTable_</u> and related systems such as <u>_HBase_</u> are also PC/EC.
<u>_Cosmos DB_</u> supports five tunable consistency levels that allow for tradeoffs between C/A during P, and L/C during E. Cosmos DB never violates the specified consistency level, so it's formally CP.
Cosmos DB offers five well-defined levels. From strongest to weakest, the levels are:
**_Strong, Bounded staleness, Session, Consistent prefix, Eventual_**
<u>_MongoDB_</u> can be classified as a PA/EC system. In the baseline case, the system guarantees reads and writes to be consistent.

A high availability requirement implies that the system must replicate data. As soon as a distributed system replicates data, a trade-off between consistency and latency arises.
Thus, the choice of the system characteristics depends on the application and requirements. 

References :
[Wikipedia - Distributed Data Stores](https://en.wikipedia.org/wiki/Distributed_data_store)
[Wikipedia - Consistency Model](https://en.wikipedia.org/wiki/Consistency_model)
[Wikipedia - PACELC](https://en.wikipedia.org/wiki/PACELC_theorem#cite_ref-csmsclvl_9-0)
[mwhittaker.github.io](https://mwhittaker.github.io/blog/an_illustrated_proof_of_the_cap_theorem/)
[edisciplinas.usp.br](https://edisciplinas.usp.br/pluginfile.php/2541318/mod_resource/content/1/TeoremaDeBrewer.pdf)
[medium.com/@skeller88](https://medium.com/@skeller88/cap-and-acid-8bbf9b45941)
[blog.thislongrun.com](http://blog.thislongrun.com/2015/03/the-confusing-cap-and-acid-wording.html)
[Eventual_consistency](https://en.wikipedia.org/wiki/Eventual_consistency)
[ardalis.com](https://ardalis.com/cap-pacelc-and-microservices/)
[Azure CosmosDB](https://docs.microsoft.com/en-us/azure/cosmos-db/consistency-levels)

Image Resources :
[CAP-theorem-with-databases-that-choose-CA-CP-and-AP](https://www.researchgate.net/profile/Joao-Lourenco-8/publication/282519669/figure/fig1/AS:281002732736529@1444007680733/CAP-theorem-with-databases-that-choose-CA-CP-and-AP.png)
[Summary Table](https://www.researchgate.net/figure/Summary-table-with-characteristics-of-the-selected-NoSQL-databases_tbl1_282519669)