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

System Parameters:
  N = Number of replicas
  W = Write quorum (replicas that must acknowledge a write)
  R = Read quorum (replicas that must respond to a read)
  
Latency Variables:
  RTT_i = Round-trip time to replica i
  D_i = Disk write latency at replica i
  P_i = Processing latency at replica i
  
Total Operation Latency:
  L_write = max(RTT_i + D_i + P_i) for i in fastest W replicas
  L_read = max(RTT_i + P_i) for i in fastest R replicas
  
Latency to Replica i:
  λ_i = RTT_i + D_i + P_i  (for writes)
  λ_i = RTT_i + P_i        (for reads)
  
Sorted Latencies:
  λ₁ ≤ λ₂ ≤ λ₃ ≤ ... ≤ λ_N
  
Quorum Latency:
  L_write = λ_W  (Wth fastest replica)
  L_read = λ_R   (Rth fastest replica)

1
2
3
4
5
6
7
8
9
10
11
12
13

Strong Consistency Condition:
  R + W > N
  
This guarantees that any read quorum overlaps with any write quorum.
At least one replica participates in both operations.
This replica has the latest value, ensuring the read sees the latest write.
 
Examples with N=5:
  R=3, W=3: 3+3=6 > 5 ✓ (Strong)
  R=2, W=4: 2+4=6 > 5 ✓ (Strong)
  R=1, W=5: 1+5=6 > 5 ✓ (Strong, slow writes)
  R=5, W=1: 5+1=6 > 5 ✓ (Strong, slow reads)
  R=2, W=2: 2+2=4 < 5 ✗ (Eventual consistency)

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

Trade-off Optimization Problem:
 
  Minimize: α·L_write + β·L_read
  Subject to: R + W > N
  
Where α and β are weights based on read/write ratio:
  - Read-heavy workload: α=1, β=10 → Minimize read latency
  - Write-heavy workload: α=10, β=1 → Minimize write latency
  - Balanced workload: α=1, β=1 → Minimize total latency
 
Solution Approach:
  L_write = λ_W (latency to Wth fastest replica)
  L_read = λ_R (latency to Rth fastest replica)
  
  Since λ is sorted ascending:
    Increasing W increases L_write
    Increasing R increases L_read
    
  The constraint R + W > N means:
    Decreasing W requires increasing R (and vice versa)
    You can trade write latency for read latency
    
  Optimal configuration depends on:
    - Replica latency distribution
    - Read/write ratio of workload
    - Latency sensitivity of operations

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

Order Statistic Effect on Latency:
 
Assume each replica has latency distribution:
  p50 = 10ms, p99 = 50ms, p99.9 = 100ms
 
For W=1 (any single replica):
  System p50 ≈ 10ms (best of N samples, actually lower)
  System p99 ≈ 50ms
  
For W=3 (majority of 5):
  System p50 ≈ 10ms (third-fastest of 5, roughly median)
  System p99 ≈ 50ms (but probability compounds)
  
For W=5 (all replicas):
  System p50 ≈ 10ms (worst of 5 medians)
  System p99 ≈ probability that any one exceeds p99
           ≈ 1 - (0.99)^5 = 4.9% of requests exceed 50ms!
           So actual p99 is much higher, perhaps 100ms+
 
Key insight: Higher quorums amplify tail latency!
  - With W=5, a slow replica makes EVERY request slow
  - With W=1, a slow replica is never waited for

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

Bounded Staleness Implementation:
 
1. Each data item has a version timestamp: v.ts
2. Reader specifies staleness bound: Δ
3. Read returns local replica if:
   current_time - v.ts ≤ Δ
4. Otherwise, fetch from primary/quorum
 
Trade-off curve:
  Δ = 0:       Always fresh → Always pay coordination latency
  Δ = 100ms:   100ms staleness → Local reads if within bound
  Δ = 1s:      1 second staleness → Almost always local reads
  Δ = ∞:       Eventual consistency → Always local, unknown staleness
 
Example (replication lag = 50ms average):
  Δ = 100ms: ~80% of reads served locally (~5ms)
             ~20% require coordination (~100ms)
             Expected latency: 0.8*5 + 0.2*100 = 24ms
             
  Δ = 500ms: ~98% of reads served locally
             Expected latency: ~7ms
             
Bounded staleness is ideal when:
  - Some staleness is acceptable
  - Latency is critical
  - You want a tunable knob between EL and EC

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

Flat Replication (5 replicas globally):
 
  Client → Primary → [R1, R2, R3, R4, R5] (parallel)
  
  Latency: max(RTT_R1, RTT_R2, RTT_R3, RTT_R4, RTT_R5) for W=5
         = max(5ms, 60ms, 90ms, 120ms, 180ms) = 180ms
 
Hierarchical Replication (2-level):
 
  Client → Primary (US-East) 
           ├── Local replicas (synchronous, 5ms)
           └── Region leaders (async, parallel):
               ├── US-West leader → local replicas (5ms sync)
               ├── Europe leader → local replicas (5ms sync)
               └── Asia leader → local replicas (5ms sync)
 
  Local strong consistency: 5ms (within region)
  Cross-region: eventual consistency, async propagation
  
  Result: Strong consistency at 5ms for reads within same region
          Eventual consistency for cross-region reads
          Best of both worlds for region-local workloads

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

Read-Your-Writes Implementation:
 
1. Each write returns a version token to the client
   write_response = {success: true, version: "v42"}
 
2. Client includes version token in subsequent reads
   read_request = {key: "user_123", min_version: "v42"}
 
3. Server routes to replica that has min_version
   - If local replica has it: serve locally (fast)
   - If not: route to primary or wait for propagation
 
4. Optimization: predict propagation time
   - If write was >propagation_lag ago, local is safe
   - estimate: propagation_lag ≈ p99 of replication delay
 
Latency Profile:
  Immediate read after write: route to primary (~100ms)
  Read after propagation (>500ms): local replica (~5ms)
  
User Experience:
  - User always sees their own changes immediately
  - Other users may see eventual consistency
  - Satisfies most user expectations without full EC cost

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

Speculative Execution for Reads:
 
1. Send read request to all R replicas simultaneously
2. Return first response that meets consistency requirement
3. Cancel outstanding requests
 
Benefit: Latency = min(replica latencies in R), not max
 
Example (R=3 of 5):
  Without speculation:
    Send to replicas 1, 2, 3 in sequence or parallel
    Wait for slowest of the 3: λ₃ = 93ms
    
  With speculation:
    Send to ALL 5 replicas simultaneously
    Return after 3rd response: λ₃ = 93ms (same worst case)
    But often faster because you pick fastest 3:
    Expected: ~λ₂ to λ₃ depending on latency variance
    
Trade-off: Higher network/compute cost (more requests)
Best for: Read-heavy workloads with latency SLAs

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

Adaptive Consistency Strategy:
 
1. Monitor replication lag continuously
   current_lag = time_since_last_sync_with_primary
   
2. Define consistency tiers based on lag:
   if current_lag < 10ms:  serve_local()      // Effectively consistent
   if current_lag < 100ms: serve_local()      // Bounded staleness OK
   if current_lag < 1s:    check_freshness()  // May need coordination
   if current_lag > 1s:    route_to_primary() // Stale, force fresh
   
3. Expose freshness to application:
   response.data_age_ms = current_lag
   
   Application can decide:
   if (critical_operation && response.data_age_ms > threshold) {
     retry_with_strong_consistency();
   }
   
4. Advantages:
   - Low latency when replication is healthy
   - Automatic fallback to strong consistency when degraded
   - Application can make informed decisions

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

Cost Components:
 
1. Direct Latency Cost (User Experience)
   latency_cost = (L_ec - L_el) * requests_per_second
   
   Example:
     L_ec = 100ms, L_el = 5ms, RPS = 10,000
     Additional latency per second: 95ms * 10,000 = 950 seconds
     Aggregate user wait time: 950 seconds per second of operation!
     
2. Infrastructure Cost (Provisioning)
   - Higher latency = lower throughput per node
   - If response time doubles, you need 2x servers for same RPS
   - Cloud cost multiplier: L_ec / L_el
   
   Example:
     L_ec/L_el = 100ms/5ms = 20x
     EC choice may require 20x infrastructure (simplified)
     
3. Opportunity Cost (User Behavior)
   - Study: 100ms latency = 1% revenue drop (Amazon)
   - Study: 500ms latency = 20% traffic drop (Google)
   - Strong consistency latency premium directly impacts business
   
4. Consistency Cost (Correctness)
   - EL choice risks: stale reads, lost updates, conflicts
   - Cost of customer service, refunds, reputation
   - Sometimes infinite (incorrect financial transactions)

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

Total Cost Function:
 
  Cost(EC) = latency_cost + infrastructure_cost + opportunity_cost
  Cost(EL) = consistency_violation_cost * probability_of_harm
  
Choose EC when:
  Cost(EC) < Cost(EL)
  
Examples:
 
1. Financial Transaction (banking transfer):
   - Cost of incorrect balance: reputation, legal, regulatory
   - Probability of harm if EL: high (concurrent transactions common)
   - Cost(EL) = very high
   - Decision: EC despite latency cost
   
2. Social Media Feed:
   - Cost of stale post: user sees slightly delayed content
   - Probability of user noticing: low
   - Cost(EC) = 10x latency, poor UX, lower engagement
   - Decision: EL, prioritize responsiveness
   
3. Inventory Count:
   - Cost of incorrect count: overselling, refunds, reputation
   - Probability of harm: medium (depends on velocity)
   - Latency tolerance: users expect some delay for inventory
   - Decision: EC for writes, EL with bounded staleness for reads
   
4. Session Data:
   - Cost of stale session: minor UX issues
   - Probability of harm: low (single user affected)
   - Latency tolerance: users expect instant response
   - Decision: EL with read-your-writes guarantee