PACELC Theorem: Beyond CAP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

CQRS Architecture with PACELC:
 
┌─────────────────────────────────────────────────────────────┐
│                        Clients                               │
└─────────────┬────────────────────────────┬──────────────────┘
              │ Commands (writes)           │ Queries (reads)
              ▼                             ▼
┌─────────────────────────┐    ┌──────────────────────────────┐
│    Command Service      │    │       Query Service          │
│    (PC/EC behavior)     │    │       (PA/EL behavior)       │
│                         │    │                              │
│  - Strong consistency   │    │  - Eventual consistency      │
│  - Higher latency OK    │    │  - Low latency critical      │
│  - Write to primary     │    │  - Read from replicas        │
└───────────┬─────────────┘    └──────────────┬───────────────┘
            │                                  │
            ▼                                  ▼
┌─────────────────────────┐    ┌──────────────────────────────┐
│   Write Database        │───▶│     Read Database(s)         │
│   (e.g., PostgreSQL)    │    │   (e.g., Elasticsearch,      │
│                         │    │    Redis, Read Replicas)     │
│  Optimized for:         │    │  Optimized for:              │
│  - ACID compliance      │    │  - Query performance         │
│  - Consistency          │    │  - Low latency               │
│  - Durability           │    │  - Read scaling              │
└─────────────────────────┘    └──────────────────────────────┘
            │                                  ▲
            └──────────── Async Sync ──────────┘
                      (Event sourcing/CDC)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Multi-Region Deployment Strategies:
 
1. Single-Leader (PC/EC globally):
   ┌─────────────┐
   │  Region A   │◀── All writes
   │  (Primary)  │
   └──────┬──────┘
          │ Sync replication (100-200ms latency penalty)
   ┌──────┼──────┐
   ▼      ▼      ▼
┌──────┐┌──────┐┌──────┐
│Reg B ││Reg C ││Reg D │  (Read-only replicas)
└──────┘└──────┘└──────┘
 
   + Strong consistency globally
   - High write latency from non-primary regions
   - Single point of failure for writes
 
2. Multi-Leader + Conflict Resolution (PA/EL globally):
   ┌──────────┐    ┌──────────┐    ┌──────────┐
   │ Region A │◀──▶│ Region B │◀──▶│ Region C │
   │ (Leader) │    │ (Leader) │    │ (Leader) │
   └──────────┘    └──────────┘    └──────────┘
        ▲               ▲               ▲
        │               │               │
     Writes          Writes          Writes
   (local)          (local)         (local)
   
   + Low latency writes everywhere
   + High availability (any region can accept writes)
   - Conflicts possible; need resolution strategy (LWW, CRDT, etc.)
   - Eventual consistency; temporary divergence
 
3. Hybrid: Strong within region, eventual across (PC locally, PA globally):
   Each region runs PC/EC internally
   Cross-region replication is async (EL)
   Users routed to nearest region
   Cross-region reads may be stale

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Saga Pattern (PA/EL with application-level consistency):
 
Traditional 2PC (PC/EC):
  - All participants must be available
  - Locks held during coordination
  - High latency, poor availability during partitions
 
Saga (PA/EL with eventual correctness):
  Step 1: Book flight (local commit, fast)
  Step 2: Book hotel (local commit, fast)
  Step 3: Charge payment (local commit, fast)
  
  If Step 3 fails:
    Compensate Step 2: Cancel hotel
    Compensate Step 1: Cancel flight
    
  PACELC Implications:
    - Each step is fast (EL) - no distributed locking
    - Temporary inconsistencies exist (flight booked, hotel not yet)
    - Eventually consistent via compensating actions
    - Available during partitions (PA) - steps queued
    
  Trade-off:
    - Simpler consistency reasoning with 2PC
    - Better latency and availability with Sagas
    - More complex error handling (compensating logic)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

-- Cassandra Consistency Levels
 
-- EL Behavior (default): Fast but eventually consistent
CONSISTENCY ONE
INSERT INTO orders (id, status) VALUES (uuid(), 'pending');
-- Latency: ~2-5ms
-- Writes to any single replica; async replication to others
-- Risk: Data loss if replica fails before replication
 
-- Balanced: Majority agreement
CONSISTENCY QUORUM
SELECT * FROM orders WHERE id = ?;
-- Latency: ~10-30ms (depends on RF and topology)
-- Requires majority (RF/2 + 1) for reads and writes
-- Strong consistency when using QUORUM for both R and W
 
-- EC Behavior: Maximum consistency
CONSISTENCY ALL
INSERT INTO accounts (id, balance) VALUES (?, ?);
-- Latency: ~50-200ms (slowest replica)
-- All replicas must acknowledge
-- Maximum durability and consistency
 
-- LOCAL variants for multi-DC:
CONSISTENCY LOCAL_QUORUM
-- Quorum within local datacenter only
-- Faster than QUORUM for geographically distributed clusters
-- Cross-DC consistency is eventually consistent

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// DynamoDB Consistency Options
 
// EL Behavior: Eventually consistent read (default)
const eventualRead = await docClient.get({
    TableName: 'Orders',
    Key: { orderId: '12345' }
    // ConsistentRead defaults to false
}).promise();
// Latency: ~5-10ms
// Cost: 0.5 RCU per 4KB
// May return stale data (typically <1 second old)
 
// EC Behavior: Strongly consistent read
const strongRead = await docClient.get({
    TableName: 'Orders',
    Key: { orderId: '12345' },
    ConsistentRead: true  // Force strong consistency
}).promise();
// Latency: ~10-20ms (roughly 2x)
// Cost: 1.0 RCU per 4KB (2x cost)
// Always returns latest committed write
 
// Writes are always strongly consistent within a region
// Global Tables: Async replication, eventually consistent across regions
 
// TransactWriteItems for ACID across items (EC behavior)
const txResult = await docClient.transactWrite({
    TransactItems: [
        { Put: { TableName: 'Orders', Item: order } },
        { Update: { TableName: 'Inventory', Key: {...}, ... } }
    ]
}).promise();
// Latency: ~25-50ms (coordination overhead)
// Both operations succeed or both fail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// MongoDB Consistency Configuration
 
// EL-leaning: Acknowledge primary only
db.orders.insertOne(
    { orderId: "12345", status: "pending" },
    { writeConcern: { w: 1 } }  // Primary acknowledgment only
);
// Latency: ~2-5ms
// Risk: Data loss if primary fails before replication
 
// EC-leaning: Majority acknowledgment
db.orders.insertOne(
    { orderId: "12345", status: "pending" },
    { writeConcern: { w: "majority", j: true } }  // Majority + journal
);
// Latency: ~10-50ms (depends on replica locations)
// Durability: Survives primary failure
 
// Read Concern for EC behavior
db.orders.find({ orderId: "12345" })
    .readConcern("majority");  // Only majority-committed data
// Prevents reading data that might be rolled back
 
// Linearizable reads (strongest EC)
db.orders.find({ orderId: "12345" })
    .readConcern("linearizable");
// Latency: Highest (~50-100ms+)
// Guarantees real-time consistency
// Use sparingly for critical reads
 
// Read Preference for EL behavior
db.orders.find({ status: "pending" })
    .readPreference("nearest");  // Lowest latency replica
// May return stale data from secondary
// Ideal for analytics, dashboards

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Example: E-Commerce Platform
 
PC/EC Operations (correctness critical):
  - Inventory decrement on purchase → PostgreSQL (serializable)
  - Order creation → PostgreSQL with ACID transactions
  - Payment processing → External payment service with idempotency
  
  Data Store: PostgreSQL with synchronous standby
  Configuration: synchronous_commit = on
  Expected Latency: 20-50ms
 
PA/EL Operations (speed critical, staleness acceptable):
  - Product catalog browsing → Elasticsearch
  - User session data → Redis Cluster
  - Shopping cart → DynamoDB (eventually consistent)
  - Product recommendations → Precomputed, served from CDN
  
  Data Stores: Various, optimized for read latency
  Configuration: Async replication, local reads
  Expected Latency: 5-15ms
 
Hybrid Operations (context-dependent):
  - Inventory display (browsing): Eventually consistent (stale OK)
  - Inventory check (checkout): Strongly consistent (must be accurate)
  
  Same data, different consistency per operation context

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Partition Behavior Design:
 
1. Identify partition-sensitive operations:
   - Cross-region database writes
   - Distributed transactions
   - Consensus-dependent coordination
   
2. Define partition detection:
   - Timeout thresholds (e.g., 5 second timeout = assume partition)
   - Health check endpoints
   - Quorum loss detection
   
3. Design PA behavior (if choosing availability):
   - Accept writes locally, queue for reconciliation
   - Use CRDTs or LWW for conflict resolution
   - Communicate staleness to clients ("data may be outdated")
   - Reconcile when partition heals
   
4. Design PC behavior (if choosing consistency):
   - Return errors for operations requiring consensus
   - Allow read-only mode if read quorum available
   - Queue writes for execution after partition heals
   - Communicate degraded state to clients
   
5. Document failure mode in runbooks:
   - Expected behavior during partition
   - Monitoring alerts for partition detection
   - Manual intervention procedures if needed
   - Testing procedures (chaos engineering)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

The Mistake:
  "Our median latency is 10ms, so we're fine."
  
  Reality with quorum systems:
    - p50: 10ms (half of operations)
    - p99: 100ms (1% of operations, but that's 10,000/day at 1M ops)
    - p99.9: 500ms (rare but destroys user experience)
    
  With fan-out (reading from multiple services):
    - Each service p99: 100ms
    - If request hits 10 services: 1-(0.99)^10 = 9.6% chance of >100ms
    - Aggregate p99 is much worse than component p99
 
The Correction:
  - Measure and alert on p99 and p99.9, not just p50
  - Use speculation: send to more replicas, use fastest response
  - Set timeouts and fallbacks for slow operations
  - Consider hedged requests for latency-sensitive operations
  - Accept that strong consistency increases tail latency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

DynamoDB Global Tables PACELC Analysis:
 
Architecture:
  - Multi-region, multi-active
  - Each region is a full read/write replica
  - Async replication between regions via DynamoDB Streams
  
PACELC Classification: PA/EL globally, PA/EC regionally
 
Within a region (E clause):
  - Writes: Synchronously replicated within region (EC)
  - Reads: Eventually consistent default, strongly consistent opt-in
  - Typical latency: 5-20ms
  
Across regions (E clause):
  - Replication lag: typically 100-500ms
  - Conflicts resolved by Last Writer Wins (LWW) based on timestamp
  - No global strong consistency available
  
During partition (P clause):
  - Each region continues operating (PA)
  - Writes accepted locally, queued for replication
  - Conflicts resolved when partition heals
  
Practical Implication:
  - Users see local low-latency writes
  - Cross-region users may see delayed/stale data
  - Application must handle LWW conflict semantics
  - Ideal for: user profiles, shopping carts, session data
  - Not ideal for: globally consistent inventory, financial ledgers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Google Spanner PACELC Analysis:
 
Architecture:
  - Globally distributed, synchronized
  - TrueTime API using atomic clocks + GPS
  - Paxos consensus for each partition
  
PACELC Classification: PC/EC (achieves global strong consistency)
 
Within a region (E clause):
  - Writes: Synchronous via Paxos, ~5-10ms
  - Reads: Snapshot reads at TrueTime timestamp
  - Latency: competitive with single-region databases
  
Across regions (E clause):
  - TrueTime enables external consistency without 2PC
  - Commit wait: ~7ms to account for clock uncertainty
  - Cross-region transaction: ~50-200ms (physics limit)
  
During partition (P clause):
  - Requires majority (PC behavior)
  - Minority partitions cannot process transactions
  - Availability sacrificed for consistency
  
How they achieve PC/EC globally:
  - Specialized hardware (atomic clocks, GPS)
  - TrueTime bounds clock uncertainty to ~7ms
  - Commit wait ensures serialization
  - Accept latency cost for global consistency
  
Practical Implication:
  - True ACID transactions at global scale
  - Higher latency than eventually consistent alternatives
  - Significant infrastructure investment
  - Ideal for: financial systems, inventory, anything requiring correctness

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Netflix Cassandra PACELC Usage:
 
Context:
  - Global streaming service, 200M+ subscribers
  - Viewing history, user preferences, session data
  - Billions of operations per day across 3 regions
  
PACELC Classification: PA/EL (tuned for availability and speed)
 
Configuration:
  - Replication Factor: 3 per datacenter (9 total globally)
  - Default: LOCAL_QUORUM for most operations
  - Strong consistency (QUORUM all DCs) for critical metadata only
  
E clause behavior:
  - LOCAL_QUORUM: ~5-15ms reads/writes within region
  - Cross-region reads: routed regionally, <20ms
  - Global consistency: eventual, 100-500ms propagation
  
P clause behavior:
  - Regions degrade independently
  - Local operations continue (PA)
  - Cross-region operations may return stale data
  
Key Design Decisions:
  - Accept eventual consistency for viewing history (stale is OK)
  - Use LOCAL_QUORUM (not ALL) for availability during node failures
  - Cross-region: async replication, accept staleness
  - User context provides consistency: your own history is consistent
  
Result:
  - Sub-20ms latency globally
  - 99.99%+ availability
  - Occasional stale reads accepted (user won't notice)
  - Not suitable for billing/payment (use different system)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Business-Friendly Framing:
 
Question: "Why can't we have both fast AND always-correct?"
 
Answer using analogy:
  Think of a chain of stores updating prices.
  
  Option A (Fast, Eventually Correct):
    - Each store updates immediately when they receive the memo
    - Customers get instant service
    - Different stores might briefly show different prices
    - Eventually, all stores sync up (minutes)
    
  Option B (Slow, Always Correct):
    - Central coordinator calls each store before change
    - No customer sees different prices at same time
    - Every price update takes longer (calls to all stores)
    - If one store is unreachable, updates halt
    
  Our system faces the same choice:
    - Fast responses OR perfect real-time consistency
    - We've chosen [X] because [business reason]
    - Here's the trade-off impact: [specific scenario]
 
Business Questions to Ask:
  1. What's the cost of a user seeing stale data for 1 second?
  2. What's the cost of a 200ms slower response?
  3. Which matters more for this feature?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Engineering Team Documentation Template:
 
## PACELC Trade-off Decision: [Feature/System]
 
### Context
- Feature: [What we're building]
- Data: [What data is involved]
- Scale: [Expected throughput, geographic distribution]
 
### Requirements Analysis
| Operation | Consistency Need | Latency Target | PACELC |
|-----------|-----------------|----------------|--------|
| Read X    | Eventual OK     | <50ms          | EL     |
| Write Y   | Strong          | <200ms OK      | EC     |
 
### Decision
- Database: [Selection] with PACELC: [Classification]
- Normal operation (E): [EL or EC behavior]
- Partition (P): [PA or PC behavior]
 
### Configuration
```
Consistency level: [Specific setting]
Replication: [Sync/async]
Read preference: [Setting]
```
 
### Implications
- Expected latency: [range]
- Consistency guarantee: [specific]
- Failure mode: [what happens during partition]
 
### Alternatives Considered
- [Option A]: Rejected because [reason]
- [Option B]: Rejected because [reason]