PACELC Theorem

PACELC Theorem

In this tutorial, we are going to explore about the PACELC Theorem and its usage. The PACELC theorem is an extension of the CAP theorem in distributed systems. It describes the trade-offs between consistency, availability, latency, and partition tolerance in the presence or absence of network partitions.

Background

We cannot avoid partition in a distributed system, therefore, according to the CAP theorem, a distributed system should choose between consistency or availability. ACID (Atomicity, Consistency, Isolation, Durability) databases, such as RDBMSs like MySQL, Oracle, and Microsoft SQL Server, chose consistency (refuse response if it cannot check with peers), while BASE (Basically Available, Soft-state, Eventually consistent) databases, such as NoSQL databases like MongoDB, Cassandra, and Redis, chose availability (respond with local data without ensuring it is the latest with its peers).

One place where the CAP theorem is silent is what happens when there is no network partition? What choices does a distributed system have when there is no partition?

Solution

The PACELC theorem states that in a system that replicates data:

  • if there is a partition (‘P’), a distributed system can tradeoff between availability and consistency (i.e., ‘A’ and ‘C’);
  • else (‘E’), when the system is running normally in the absence of partitions, the system can tradeoff between latency (‘L’) and consistency (‘C’).
PACELC Theorem

The first part of the theorem (PAC) is the same as the CAP theorem, and the ELC is the extension. The whole thesis is assuming we maintain high availability by replication. So, when there is a failure, CAP theorem prevails. But if not, we still have to consider the tradeoff between consistency and latency of a replicated system.

Breakdown of PACELC Theorem
  1. PAC:
    • Stems from the CAP theorem, which states that in a distributed system, you can only guarantee two of the following three during a partition:
      • P: Partition tolerance
      • A: Availability
      • C: Consistency
    Thus, when a network partition occurs, systems must choose between C (Consistency) and A (Availability).
  2. ELC:
    • Extends CAP to describe the behavior of distributed systems when there is no partition.
    • Highlights a trade-off between:
      • E: Latency
      • C: Consistency
Interpretation of PACELC Theorem
  • During a partition (P), the system must choose between A (Availability) and C (Consistency).
  • Else (no partition), the system must choose between E (minimizing latency) and C (maximizing consistency).
Implications

PACELC theorem shows that even in the absence of failures, distributed systems face trade-offs that are not addressed by CAP alone. A system designer must consider:

  • How the system behaves during partitions (CAP trade-off).
  • How the system optimizes latency versus consistency when there are no partitions (ELC trade-off).
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 (default configuration): MongoDB works in a primary/secondaries 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.

In summary, PACELC theorem expands on CAP by incorporating latency as a critical factor, making it more comprehensive for evaluating distributed systems in practical scenarios.

That’s all about the PACELC Theorem. If you have any queries or feedback, please write us at contact@waytoeasylearn.com. Enjoy learning, Enjoy system design interview series..!!

PACELC Theorem
Scroll to top