CAP Theorem

Consistency means that every read operation receives the most recent write or an error. In a consistent system, all nodes see the same data at the same time. This is often referred to as linearizability or atomic consistency.

• Mechanism: Achieved through coordination protocols like two-phase commit (2PC) or consensus algorithms like Raft and Paxos.
• Trade-off: Guaranteeing consistency often requires nodes to block or delay responses until data is synchronized, potentially impacting availability.
• Example: A financial database ensuring that a balance transfer is immediately reflected across all replicas before confirming the transaction to the user.

Availability means that every request (read or write) receives a (non-error) response, without guarantee that it contains the most recent write. The system remains operational for both reads and writes even during failures.

• Mechanism: Achieved by allowing nodes to operate independently, often serving potentially stale data from local replicas.
• Trade-off: High availability can lead to eventual consistency, where different nodes may return different data for a short period.
• Example: A social media timeline that always loads quickly, even if it occasionally shows a slightly outdated post count or like tally during a network issue.

Partition tolerance means the system continues to operate despite an arbitrary number of network messages being dropped (or delayed) between nodes. A network partition is a break in communication, splitting the network into isolated subgroups.

• Fundamental Constraint: In a distributed system, network partitions are a guaranteed eventual failure mode. Therefore, partition tolerance (P) is non-negotiable for any practical wide-area network system.
• Implication: The true choice in system design is between Consistency and Availability when a partition occurs (CP vs. AP).
• Example: A globally distributed database that can handle an undersea cable break, allowing regional data centers to continue serving requests independently, even if they cannot communicate with each other.

CP systems prioritize consistency over availability during a network partition. If nodes cannot communicate to guarantee consistency, the system will return an error or become unavailable for writes/reads on the affected data.

• Typical Use Cases: Financial systems (e.g., stock trades, bank account balances), distributed locking services, and metadata coordination where correctness is paramount.
• Examples: Google Spanner, etcd, ZooKeeper, and traditional relational databases with synchronous replication.
• Behavior on Partition: A node may refuse a write request if it cannot achieve a quorum to replicate the data consistently, preserving the atomicity of operations.

AP systems prioritize availability over strict consistency during a network partition. All nodes remain responsive, but they may serve stale or divergent data. The system provides eventual consistency.

• Typical Use Cases: Social media platforms, e-commerce product catalogs, DNS, and real-time collaborative applications where uninterrupted service is more critical than immediate uniformity.
• Examples: Amazon DynamoDB, Apache Cassandra, Riak, and CouchDB.
• Behavior on Partition: Nodes in each partition continue to accept reads and writes locally. When the partition heals, a conflict resolution mechanism (like last-write-wins or application-defined logic) merges the divergent data states.

A CA system provides both Consistency and Availability, but only in the absence of network partitions. This is effectively a single-node or tightly-coupled cluster system where partition tolerance is not a design consideration.

• Reality Check: In a true distributed system across multiple failure domains (e.g., different data centers), network partitions are inevitable. Therefore, a CA distributed system is a practical impossibility.
• Localized Examples: A single PostgreSQL database server, or a Redis cluster running within a single rack with a perfect network. The moment the system is stretched across a wide-area network, it must choose CP or AP behavior for partition scenarios.
• Misconception: The CAP theorem is often misinterpreted as "choose 2 out of 3 at all times." In reality, it's about the trade-off enforced during a partition.

A consistency model where, given sufficient time without new writes, all replicas of a data item in a distributed system will converge to the same value. This is a common choice for AP (Availability, Partition Tolerance) systems that prioritize responsiveness over immediate uniformity.

• Key Mechanism: Uses asynchronous replication and conflict resolution protocols.
• Example: DNS (Domain Name System) updates propagate globally over hours.
• Trade-off: Provides high availability and partition tolerance at the cost of temporary staleness (read-your-writes consistency is not guaranteed during a partition).

A protocol used by distributed processes to agree on a single data value or sequence of actions, which is fundamental for implementing CP (Consistency, Partition Tolerance) systems. These algorithms ensure all non-faulty nodes share a consistent view even during network failures.

• Primary Purpose: Achieves fault-tolerant agreement in the presence of node failures or network partitions.
• Examples: Paxos, Raft, and Byzantine Fault Tolerance (BFT) variants.
• CAP Implication: During a network partition, a consensus cluster may become unavailable (sacrificing A) to preserve strict consistency (C) across the minority partition.

A fault isolation design pattern inspired by ship compartments. It partitions system resources (e.g., thread pools, connections, service instances) to prevent a failure in one component from cascading and exhausting all resources, causing a total system failure.

• Core Benefit: Limits the blast radius of a failure, preserving partial system availability.
• Implementation: Uses separate connection pools, microservices, or compute resources for critical vs. non-critical functions.
• Relation to CAP: Enhances availability (A) within a partitioned system by isolating failures, making graceful degradation possible.

A stability design pattern that detects failures and prevents an application from repeatedly attempting an operation that is likely to fail. It acts as a proxy for operations, which can trip open to stop calls, allowing the failing service time to recover.

• Three States: Closed (normal operation), Open (fast fail, no calls made), Half-Open (trial requests to test recovery).
• Purpose: Prevents resource exhaustion and cascading failures, enabling system resilience.
• CAP Context: Protects availability (A) of the calling service during the partial unavailability (a form of partition) of a downstream dependency.

An extension of the CAP theorem that provides a more complete framework for distributed database trade-offs. It states that if a Partition occurs (P), the trade-off is between Availability and Consistency (A vs. C); Else (E), when the network is functioning normally, the trade-off is between Latency and Consistency (L vs. C).

• Refinement: Acknowledges that consistency vs. latency is a critical design decision even in the absence of partitions.
• Practical Impact: Guides database selection (e.g., DynamoDB is PA/EL, Cassandra is PA/EL, MongoDB is PC/EC).
• Significance: Moves beyond the binary CAP trade-off to include performance considerations.

A data structure designed for highly available (AP) distributed systems. CRDTs can be updated independently and concurrently on different replicas, and can always be merged automatically into a consistent state without conflict, guaranteeing strong eventual consistency.

• Key Property: Operations are commutative, associative, and idempotent, enabling deterministic merging.
• Use Cases: Collaborative editing (e.g., Google Docs), counter increments, shopping carts.
• CAP Alignment: Embodies the AP choice, ensuring availability and partition tolerance by deferring complex coordination and relying on mathematically sound merge operations.