PACELC Theorem

Background

In a distributed system, we cannot avoid partition. So as per the CAP theorem, the system should choose between consistency or availability.

So ACID databases (such as RDBMSs like MySQL, Oracle) would choose consistency & consequently refuse to respond if they cannot connect with node/peers who are part of the system.

On the other hand, BASE (such as MongoDB, Cassandra) databases choose availability & respond with local data without ensuring it is the latest with its nodes/peers.

But what happens when there is no partition? CAP theorem doesn’t state anything about it.

PACELC builds on the CAP theorem. Both theorems describe how distributed databases have limitations and tradeoffs regarding consistency, availability, and partition tolerance.

PACELC theorem states that:

if Partition then Availability or Consistency Else + Latency or Consistency

In a distributed system where data is replicated -

if there is a partition then the system can trade-off between consistency & availability.

else there is no partition then the system can trade-off between latency & consistency

The first part of theorem i.e. PAC is same as CAP and ELC is extension

Examples

• Dynamo and Cassandra are PA/EL systems: They choose availability over consistency when a partition occurs; otherwise, they choose lower latency.
• BigTable and HBase are PC/EC systems: They will always choose consistency, giving up availability and lower latency.
• MongoDB can be considered PA/EC: MongoDB works in a primary/secondary configuration. In the default configuration, all writes and reads are performed on the primary. As all replication is done asynchronously (from primary to secondaries) when there is a network partition in which primary is lost or becomes isolated on the minority side, there is a chance of losing data that is unreplicated to secondaries, hence there is a loss of consistency during partitions. Therefore it can be concluded that in the case of a network partition, MongoDB chooses availability, but otherwise guarantees consistency. Alternately, when MongoDB is configured to write on majority replicas and read from the primary, it could be categorized as PC/EC.

Keywords & References :

ACID — Atomicity + Consistency +Isolation +Durability

BASE — Basically Available + Soft State +Eventual Consistency

Further reading - https://en.wikipedia.org/wiki/PACELC_theorem