Strong Consistency

In 2012, Amazon revealed that every 100 milliseconds of latency cost them 1% in sales. In high-frequency trading, firms spend billions on infrastructure to shave microseconds off transaction times. For Google, a 500ms delay in search results causes a 20% drop in traffic.

These aren't abstract numbers—they represent the profound impact of latency on user behavior and business outcomes. When we choose linearizability, we're accepting latency penalties that can range from 10x to 100x compared to eventually consistent alternatives. Understanding these performance implications and how to mitigate them is essential for building systems that are both correct and usable.

Human perception is remarkably sensitive to latency. Understanding these thresholds helps us evaluate whether linearizability's latency penalty is acceptable for a given use case.

Human Perception Thresholds

The perception hierarchy:

• < 100ms: Feels instantaneous. Users perceive the system as responding directly to their actions.
• 100-300ms: Noticeable but acceptable. Users perceive a slight delay but stay engaged.
• 300ms-1s: Obvious delay. Users begin to feel the system is slow.
• 1-10s: Disruptive. Users may abandon tasks, lose context, or multitask.
• > 10s: Broken. Users assume the system has failed.

Linearizability's Latency Reality

Let's map common linearizable operations to these thresholds:

The Compounding Problem

Web applications rarely make a single database call. A typical page load involves:

User Request
  → Authentication check (linearizable)     : 50ms
  → User profile fetch (linearizable)       : 50ms  
  → Permission check (linearizable)         : 50ms
  → Business data query (linearizable)      : 50ms
  → Audit log write (linearizable)          : 50ms
                                     Total  : 250ms (just DB calls)
  + Application processing                  : 50ms
  + Network round-trip to user              : 20ms
                                     Grand Total: 320ms

With 5 linearizable operations, latency compounds rapidly. The same application with eventual consistency might complete in 80ms total—4x faster.

Interactive vs Batch Workloads

The impact varies dramatically by workload type:

Average latency tells an incomplete story. In distributed systems, tail latency (P99, P99.9) often matters more—and linearizability dramatically amplifies tail latency.

Why Tail Latency Matters

Consider a web request that queries 10 services in parallel:

If each service has P99 = 100ms:
P(at least one > 100ms) = 1 - (0.99)^10 = 9.6%

Almost 10% of user requests experience the worst-case latency!

With linearizability, tail latency gets worse because:

1. Quorum dependency: Must wait for the slowest member of the fastest quorum
2. Consensus timeouts: Occasional leader elections spike latency
3. Disk sync variability: SSDs have occasional long pauses
4. Network jitter: Cross-region links are more variable

Tail Latency in Linearizable Systems

The Quorum Slowdown Effect

With linearizable reads requiring consensus, tail latency is bounded by the slowest quorum member:

# Simplified model of quorum read latency
def quorum_latency(node_latencies, quorum_size):
    # Sort latencies and take the quorum_size-th smallest
    sorted_latencies = sorted(node_latencies)
    return sorted_latencies[quorum_size - 1]

# Example: 5 nodes, need 3 for quorum
node_latencies = [5, 8, 12, 150, 180]  # ms
quorum_latency = 12  # We wait for 3rd-fastest

# But what if node 3 is having a bad day?
node_latencies_bad = [5, 8, 200, 150, 180]  # ms
quorum_latency = 150  # Now we must wait for 4th-fastest!

One slow node can't be avoided—the system must include it in the quorum.

Latency Amplification During Instability

During system instability, tail latency explodes:

Linearizable systems exhibit non-linear throughput degradation as load increases. Understanding this behavior is critical for capacity planning.

The Saturation Curve

Eventually consistent systems often show linear throughput scaling until hardware limits:

[Eventually Consistent]
                          ┌────────── HW Limit
 Throughput      ●───●───●───●───●
                /
               /
              /
             ●
            /
           ●
          /
         ●
        ────────────────────────────────►
                      Load

Linearizable systems hit saturation earlier due to coordination:

[Linearizable]
                    ┌────────── Consensus Limit
 Throughput   ●────●
             /     ╲──────────
            /        ╲──────── Degradation
           /
          ●
         /
        ●
       ────────────────────────────────►
                     Load

Why Throughput Degrades

Quantifying the Degradation

Let's model throughput for a Raft cluster handling key-value writes:

Baseline capacity (5-node, single region):

• Leader CPU: 8 cores
• Consensus round time: 5ms
• Network bandwidth: 10 Gbps
• Theoretical max: ~1,600 ops/second/core × 8 = ~12,800 ops/s

Observed behavior:

Notice the non-linear degradation: at 90% load, latency spikes 8x from baseline. At overload (120%), throughput actually decreases as the system spends more time handling retries and timeouts than processing new requests.

Load Shedding and Backpressure

To prevent catastrophic degradation, linearizable systems need aggressive load management:

Strategies for load management:

1. Client-side rate limiting
   - Reject requests before they hit the database
   - Token bucket per client/tenant

2. Queue depth limits
   - Fast-reject when pending operations exceed threshold
   - Return 'overloaded' error rather than timeout

3. Adaptive concurrency control
   - Reduce in-flight requests when latency increases
   - AIMD (Additive Increase, Multiplicative Decrease)

4. Priority queues
   - Critical operations (leader election, health checks) get priority
   - User operations shed first under pressure

While linearizability has inherent costs, several strategies can minimize the performance impact.

Strategy 1: Minimize Linearizable Surface Area

The most effective optimization is to limit where linearizability is applied:

Hybrid Architecture:

┌─────────────────────────────────────────────────────────┐
│                    Application Layer                    │
└─────────────────┬───────────────────────┬───────────────┘
                  │                       │
         ┌────────▼────────┐    ┌─────────▼─────────┐
         │  Linearizable   │    │     Eventually    │
         │     Store       │    │    Consistent     │
         │  (Coordination) │    │     Store         │
         │  - Locks        │    │  - User sessions  │
         │  - Counters     │    │  - Caches         │
         │  - Config       │    │  - Analytics      │
         └────────────────-┘    └───────────────────┘

Examples:

• Use Redis (eventual) for session storage, etcd (linearizable) for leader election
• Use Cassandra (eventual) for time-series data, CockroachDB (linearizable) for financial transactions
• Cache hot data in eventually consistent layer; only touch linearizable store for mutations

Strategy 2: Batching and Pipelining

Amortize consensus cost across multiple operations:

Batching at the client:

# Instead of:
for item in items:
    db.write(item)  # Each incurs consensus

# Batch writes:
db.write_batch(items)  # Single consensus round

Server-side batching:

Leader collects operations for a short window (1-5ms)
Single consensus round for entire batch
Latency increases slightly, throughput increases dramatically

Pipelining:

Start consensus(batch1)
Start consensus(batch2)  -- don't wait for batch1
Start consensus(batch3)
...
Receive batch1 acknowledgment
Receive batch2 acknowledgment

Strategy 3: Lease-Based Reads

Avoid consensus for reads by using leader leases:

Leader heartbeat:
  1. Leader sends heartbeat to followers
  2. Followers acknowledge with bounded timestamp
  3. Leader knows it's still leader for lease_duration

Read serving:
  - While lease is valid, leader serves reads locally
  - No consensus required for reads
  - Latency drops from consensus_rtt (~100ms) to local_read (~1ms)

Risk:
  - Clock skew can violate linearizability
  - Requires bounded clock drift (NTP or better)

Trade-off: Lease-based reads reduce latency 10-100x but introduce clock skew risks. Systems like etcd and ZooKeeper use this with careful clock management.

Strategy 4: Speculative Execution

Optimistically process while consensus is in-flight:

Client perspective:
  1. Send write to leader
  2. Leader acknowledges speculatively (before consensus)
  3. Client continues with next operation
  4. Leader confirms or rolls back after consensus

Benefit: Reduced perceived latency
Risk: Must handle rollback gracefully in application

Beyond point optimizations, architectural patterns can fundamentally improve linearizable system performance.

Pattern 1: Local Shard Affinity

Route operations to replicas in the same region:

┌─────────────────────────────────────────────────────────┐
│                    Global Routing Layer                 │
└───────────┬────────────────────────────┬────────────────┘
            │                            │
    ┌───────▼───────┐            ┌───────▼───────┐
    │   US Clients  │            │   EU Clients  │
    └───────┬───────┘            └───────┬───────┘
            │                            │
    ┌───────▼───────┐            ┌───────▼───────┐
    │   US Leader   │◄──────────►│   EU Leader   │
    │   Raft Group  │  (async    │   Raft Group  │
    │   (shards     │   cross-   │   (shards     │
    │    1-100)     │   region)  │    101-200)   │
    └───────────────┘            └───────────────┘

By partitioning data geographically, most operations stay local:

• US user data lives on US shards → US clients get local consensus
• EU user data lives on EU shards → EU clients get local consensus
• Only cross-region operations pay the global consensus cost

Pattern 2: Witness Replicas

Reduce replication cost with lightweight witnesses:

Traditional 5-node:
  - 5 full replicas (all data, all compute)
  - Cost: 5x storage, 5x CPU

Witness pattern:
  - 3 full replicas + 2 witness replicas
  - Witnesses: store only log metadata, not full data
  - Participate in voting but not in read serving
  - Cost: 3x storage, 3.5x CPU

Benefit: Same fault tolerance, 40% cost reduction

Pattern 3: Follower Reads for Bounded Staleness

If bounded staleness is acceptable, read from followers:

Follower read protocol:
  1. Client requests read with max_staleness = 100ms
  2. Follower checks: applied_index >= (leader_index - staleness_window)
  3. If yes: serve read locally
  4. If no: either wait for replication or forward to leader

Benefit: Reads from any replica, distributed load
Trade-off: Reads may be up to max_staleness behind

Pattern 4: Consensus Groups by Access Pattern

Align consensus groups with access patterns to minimize cross-group operations:

Optimizing performance requires measuring it correctly. Linearizable systems have unique benchmarking and monitoring requirements.

Key Metrics to Track

Latency metrics (per operation type):

• P50, P90, P99, P99.9 — The full distribution matters
• Client-observed vs server-observed — Includes network latency
• By operation type — Reads vs writes vs CAS
• By shard/partition — Identify hot spots

Throughput metrics:

• Operations per second (by type)
• Batches per second (if batching)
• Cross-partition operations per second
• Failed/retried operations per second

Consensus health metrics:

• Replication lag (per follower)
• Leader election frequency
• Quorum health (nodes available)
• Log append latency
• Snapshot frequency and duration

Benchmarking Best Practices

1. Measure under realistic conditions

• Include network latency simulation for cross-region
• Use production-like data sizes
• Simulate concurrent clients (not just sequential)

2. Test failure scenarios

• Measure latency during leader election
• Measure behavior during node failure and recovery
• Test with clock skew injection

3. Report the full picture

• Never just report averages
• Include P99 and P99.9
• Report throughput vs latency curves
• Note environmental conditions

4. Compare fairly

• Same hardware and network conditions
• Same data size and access patterns
• Same durability guarantees (fsync vs buffered)

We've explored the performance implications of linearizability in depth. The costs are real, but understanding them enables informed optimization and architectural decisions.

What's Next:

Now that we understand the performance implications, the next page explores when strong consistency is required—identifying use cases where linearizability isn't optional, and the consequences of choosing weaker guarantees.