Base Properties - Learning Module

Loading content...

0/273

Eventually Consistent

The Promise That Makes Distributed Systems Work

We've established that distributed systems prioritize availability over strong consistency, and that state in these systems is 'soft'—changing over time even without explicit modification. This raises an uncomfortable question: If data can be inconsistent, how can we reason about correctness at all?

The answer is eventual consistency—the third and final pillar of the BASE model. Eventual consistency provides a crucial guarantee: while data may be temporarily inconsistent across replicas, given sufficient time without new updates, all replicas will converge to the same value.

This guarantee transforms chaos into controlled flexibility. It says: 'Things may be messy right now, but they will eventually be correct.' This seemingly weak guarantee is surprisingly powerful—it enables the world's largest distributed systems while providing a foundation for correctness.

What You Will Learn

By the end of this page, you will understand the formal definition of eventual consistency, where it sits on the consistency model spectrum, the convergence mechanisms that enable it, how to quantify 'eventual' in practice, and design patterns for building applications that work correctly under eventual consistency.

Formal Definition of Eventual Consistency

Eventual Consistency is defined formally as:

If no new updates are made to a given data item, eventually all accesses to that item will return the last updated value.

Let's dissect this definition carefully:

Breaking Down the Definition

•'If no new updates are made' — The system must reach a quiescent state. Continuous writes prevent convergence because there's always a 'newest' value propagating.
•'eventually' — There's no specified time bound. Convergence might take milliseconds or hours. Many practical systems add time-bounded guarantees on top.
•'all accesses' — Any replica, any reader. Not just the writer or a specific replica, but every possible read path.
•'return the last updated value' — After convergence, all replicas agree on the same value—the most recent write according to the system's conflict resolution rules.

What Eventual Consistency Does NOT Guarantee

Eventual consistency makes no promises about: (1) How long convergence takes, (2) What intermediate states are visible during convergence, (3) Reading your own writes, (4) Observing writes in the order they were made, (5) Preventing lost updates during concurrent writes. These require additional guarantees layered on top of eventual consistency.

The Convergence Property:

The mathematical property underlying eventual consistency is convergence. A system converges if, starting from any state where no new writes occur, it eventually reaches a state where all replicas hold identical values.

For convergence to work, the system must have:

A mechanism to propagate updates — Replicas must eventually receive all writes (gossip protocols, anti-entropy, etc.)
A deterministic conflict resolution rule — When replicas receive conflicting updates, they must resolve to the same value (LWW, vector clocks, CRDTs, etc.)
A total ordering on updates (or commutative operations) — Updates must be applicable in any order to reach the same final state

Without these properties, replicas might diverge permanently—a situation called replica divergence or split brain.

The Consistency Model Spectrum

Consistency is not binary. There's a spectrum of consistency models, each with different guarantees, trade-offs, and use cases. Understanding this spectrum helps you choose the right consistency level for each part of your system.

Consistency Model Spectrum (Strongest to Weakest)
Model	Guarantee	Trade-off	Example Use Case
Strict Consistency	Read returns most recent write globally	Impossible in distributed systems	Theoretical only
Linearizability	Operations appear atomic and in real-time order	Coordination required; high latency	Distributed locks, critical transactions
Sequential Consistency	Operations appear in same order to all processes	Less coordination than linearizable	Bank transactions
Causal Consistency	Causally related operations seen in order	Must track causality	Social media feeds, comments
Read-Your-Writes	Writer sees their own writes	Per-client tracking	User profile updates
Monotonic Reads	Once you see a value, you never see older values	Session stickiness	Reading news, progress
Eventual Consistency	All replicas converge eventually	Temporary inconsistency	Likes, view counts, caches

Understanding the Trade-offs:

As you move from stronger to weaker consistency models:

📈 Availability increases — Less coordination means more tolerance for failures 📈 Latency decreases — Less waiting for acknowledgments from other nodes 📈 Scalability improves — Less cross-node communication as you add nodes

📉 Predictability decreases — Harder to reason about what readers will see 📉 Application complexity increases — More edge cases to handle 📉 Debugging difficulty increases — Timing-dependent bugs are hard to reproduce

The art of distributed systems design is choosing the right consistency level for each operation, balancing user expectations against system constraints.

Tunable Consistency

Many modern distributed databases (Cassandra, DynamoDB, CockroachDB) offer tunable consistency—you can choose different consistency levels for different operations. Read product descriptions with eventual consistency for speed. Read inventory counts with strong consistency for correctness. This per-query flexibility is immensely powerful.

Strengthening Eventual Consistency

Pure eventual consistency is often too weak for practical applications. Users expect certain guarantees—like seeing their own updates—that basic eventual consistency doesn't provide. Fortunately, we can add stronger guarantees on top of eventual consistency while preserving most of its availability benefits.

Read-Your-Writes Consistency

•Guarantee: A process always sees its own prior writes
•Implementation: Route reads to the same replica that handled writes (session affinity), or include write timestamp in reads to verify freshness
•Example: After updating your profile picture, you always see the new picture, even if other replicas haven't converged yet
•Cost: Requires tracking per-client state or session stickiness

Monotonic Reads Consistency

•Guarantee: Once you've read a value, you'll never see an older value
•Implementation: Track 'high-water mark' per client; only accept reads from replicas at least that fresh
•Example: Reading a news feed - you never see 'fewer' items than before, even across page refreshes
•Cost: May need to wait for replication or reject stale replicas

Causal Consistency

•Guarantee: Operations that are causally related are seen in causal order by all observers
•Implementation: Vector clocks or causal timestamps to track dependencies
•Example: If you see a reply to a comment, you're guaranteed to see the original comment
•Cost: Must attach causality metadata to all operations

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// Implementing read-your-writes consistency
 
interface WriteReceipt {
  key: string;
  timestamp: number;
  replicaId: string;
}
 
class ReadYourWritesClient {
  private writeReceipts: Map<string, WriteReceipt> = new Map();
  private preferredReplicas: Map<string, string> = new Map();
  
  async write(key: string, value: any): Promise<void> {
    const replica = this.selectPrimaryReplica(key);
    const timestamp = await replica.write(key, value);
    
    // Remember where and when we wrote
    this.writeReceipts.set(key, {
      key,
      timestamp,
      replicaId: replica.id
    });
    
    // Prefer this replica for future reads of this key
    this.preferredReplicas.set(key, replica.id);
  }
  
  async read(key: string): Promise<any> {
    const receipt = this.writeReceipts.get(key);
    
    if (receipt) {
      // We wrote this key - ensure we see our write
      return await this.readWithMinimumFreshness(
        key, 
        receipt.timestamp,
        receipt.replicaId
      );
    } else {
      // We haven't written this key - any replica is fine
      return await this.readFromAnyReplica(key);
    }
  }
  
  private async readWithMinimumFreshness(
    key: string,
    minTimestamp: number,
    preferredReplicaId: string
  ): Promise<any> {
    // Try preferred replica first
    const preferred = this.getReplica(preferredReplicaId);
    const result = await preferred.read(key);
    
    if (result && result.timestamp >= minTimestamp) {
      return result.value; // Got our write!
    }
    
    // Preferred replica is stale - try others or wait
    for (const replica of this.allReplicas()) {
      const result = await replica.read(key);
      if (result && result.timestamp >= minTimestamp) {
        // Update preferred replica
        this.preferredReplicas.set(key, replica.id);
        return result.value;
      }
    }
    
    // No replica has our write yet - wait for replication
    return await this.waitForReplication(key, minTimestamp, 5000);
  }
  
  private async waitForReplication(
    key: string,
    minTimestamp: number,
    timeoutMs: number
  ): Promise<any> {
    const deadline = Date.now() + timeoutMs;
    
    while (Date.now() < deadline) {
      for (const replica of this.allReplicas()) {
        const result = await replica.read(key);
        if (result && result.timestamp >= minTimestamp) {
          return result.value;
        }
      }
      await sleep(100); // Poll every 100ms
    }
    
    throw new Error('Read-your-writes timeout: replication too slow');
  }
}

Convergence Mechanisms

Eventual consistency doesn't happen by magic—it requires specific mechanisms to propagate updates and resolve conflicts. Understanding these mechanisms helps you predict how quickly convergence will occur and troubleshoot when it doesn't.

Update Propagation Mechanisms

•Synchronous Replication — Wait for confirmation from replicas before acknowledging write. Fastest convergence but reduces availability.
•Asynchronous Replication — Acknowledge write immediately; replicate in background. High availability but convergence delay.
•Gossip Protocols — Nodes randomly exchange updates with peers. Eventually percolates to all nodes. Very resilient but non-deterministic timing.
•Anti-Entropy (Merkle Trees) — Periodically compare hash trees between replicas to detect and repair differences. Robust but latency in detection.
•Read Repair — When a read detects inconsistency, trigger immediate repair. Convergence driven by read patterns.
•Hinted Handoff — When target replica is unavailable, store update locally and deliver when it returns. Handles temporary failures.

Deep Dive: Gossip Protocols

Gossip protocols are epidemic protocols—updates spread like disease through a population. Each node periodically selects random peers and exchanges updates. This approach is:

Decentralized: No special coordinator required
Scalable: Works with any number of nodes
Resilient: Tolerates failures of many nodes
Eventually complete: With high probability, all nodes receive all updates

The convergence time for gossip is O(log n) rounds, where n is the number of nodes. In a 1000-node cluster with a 1-second gossip interval, convergence typically occurs within 10 seconds.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// Simplified gossip protocol for eventual consistency
 
interface GossipMessage {
  key: string;
  value: any;
  timestamp: number;
  originNode: string;
}
 
class GossipNode {
  private id: string;
  private data: Map<string, { value: any; timestamp: number }>;
  private peers: GossipNode[];
  private gossipBuffer: GossipMessage[] = [];
  
  constructor(id: string) {
    this.id = id;
    this.data = new Map();
    this.peers = [];
  }
  
  // Start periodic gossip
  startGossip(intervalMs: number = 1000) {
    setInterval(() => this.gossipRound(), intervalMs);
  }
  
  // Local write
  write(key: string, value: any): void {
    const timestamp = Date.now();
    this.data.set(key, { value, timestamp });
    
    // Add to gossip buffer for propagation
    this.gossipBuffer.push({
      key,
      value,
      timestamp,
      originNode: this.id
    });
  }
  
  // One round of gossip
  private async gossipRound(): Promise<void> {
    if (this.peers.length === 0) return;
    
    // Select random subset of peers (fanout)
    const fanout = Math.min(3, this.peers.length);
    const selected = this.selectRandomPeers(fanout);
    
    // Send our buffer to selected peers
    for (const peer of selected) {
      await this.sendGossip(peer, this.gossipBuffer);
    }
    
    // Clear buffer after sending
    this.gossipBuffer = [];
  }
  
  // Receive gossip from peer
  receiveGossip(messages: GossipMessage[]): void {
    for (const msg of messages) {
      const existing = this.data.get(msg.key);
      
      // Apply if newer or new key
      if (!existing || msg.timestamp > existing.timestamp) {
        this.data.set(msg.key, {
          value: msg.value,
          timestamp: msg.timestamp
        });
        
        // Re-gossip to propagate further
        this.gossipBuffer.push(msg);
      }
    }
  }
  
  private selectRandomPeers(count: number): GossipNode[] {
    const shuffled = [...this.peers].sort(() => Math.random() - 0.5);
    return shuffled.slice(0, count);
  }
  
  private async sendGossip(
    peer: GossipNode, 
    messages: GossipMessage[]
  ): Promise<void> {
    try {
      peer.receiveGossip(messages);
    } catch (error) {
      // Peer unavailable - messages will spread via other paths
      console.log(`Gossip to ${peer.id} failed, will retry`);
    }
  }
}
 
// Example: 5-node cluster with gossip
// Updates propagate to all nodes within a few gossip rounds
// Even if some nodes are temporarily unreachable

Anti-Entropy with Merkle Trees

While gossip handles ongoing updates, anti-entropy handles long-term consistency. Merkle trees (hash trees) allow efficient comparison of large datasets—two nodes can identify which keys differ by comparing root hashes and traversing only differing branches. Cassandra, Riak, and DynamoDB all use Merkle trees for anti-entropy.

Quantifying 'Eventually'

The word 'eventually' in eventual consistency is deliberately vague. For practical systems, we need to quantify this. How long will convergence actually take? What factors affect it? How can we measure and monitor it?

Factors Affecting Convergence Time
Factor	Impact on Convergence	Typical Range
Network latency between replicas	Direct delay in propagation	1ms (same DC) to 100ms+ (cross-region)
Replication factor	More replicas = more propagation needed	3-7 replicas typical
Gossip interval	Lower = faster but more overhead	100ms to 5 seconds
Write load	High load delays background processes	Variable impact
Network partitions	Prevents propagation until healed	Seconds to hours
Node failures	Hinted handoff delays	Until node recovers or repair runs
Anti-entropy schedule	How often Merkle trees are compared	Hourly to daily

Practical Convergence Times:

In well-functioning clusters:

Same data center: 10-100 milliseconds typical
Cross-region (same continent): 100-500 milliseconds typical
Global (inter-continental): 200-1000 milliseconds typical

During failures:

Single node failure with hinted handoff: Seconds to minutes (until hints are delivered)
Network partition: Convergence paused until partition heals
Node permanently failed: Until repair runs (minutes to hours)

Measuring Convergence:

To understand your system's actual convergence behavior, measure it:

Write a value with a known timestamp to one replica
Poll all replicas until they return the value
Record the time delta from write to global visibility
Repeat across different conditions (load, time of day, etc.)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Measure actual convergence time in a distributed system
 
interface ConvergenceMetrics {
  writeTime: Date;
  convergenceTime: number;  // ms
  slowestReplica: string;
  allReplicaTimes: Map<string, number>;
}
 
async function measureConvergence(
  cluster: DistributedCluster
): Promise<ConvergenceMetrics> {
  const key = `convergence-test:${Date.now()}`;
  const value = { testId: crypto.randomUUID(), timestamp: Date.now() };
  
  // Write to primary
  const writeTime = new Date();
  await cluster.primary().write(key, value);
  
  const replicaTimes = new Map<string, number>();
  const pendingReplicas = new Set(cluster.allReplicas().map(r => r.id));
  
  const pollStart = Date.now();
  const timeout = 30000; // 30 second timeout
  
  while (pendingReplicas.size > 0 && Date.now() - pollStart < timeout) {
    for (const replicaId of pendingReplicas) {
      const replica = cluster.getReplica(replicaId);
      const result = await replica.read(key);
      
      if (result?.testId === value.testId) {
        replicaTimes.set(replicaId, Date.now() - writeTime.getTime());
        pendingReplicas.delete(replicaId);
      }
    }
    
    if (pendingReplicas.size > 0) {
      await sleep(10); // Poll every 10ms
    }
  }
  
  // Calculate metrics
  const allTimes = Array.from(replicaTimes.values());
  const convergenceTime = Math.max(...allTimes);
  const slowestReplica = Array.from(replicaTimes.entries())
    .sort((a, b) => b[1] - a[1])[0][0];
  
  // Cleanup test key
  await cluster.primary().delete(key);
  
  return {
    writeTime,
    convergenceTime,
    slowestReplica,
    allReplicaTimes: replicaTimes
  };
}
 
// Run continuous convergence monitoring
async function monitorConvergence(
  cluster: DistributedCluster,
  metricsStore: MetricsStore
) {
  while (true) {
    const metrics = await measureConvergence(cluster);
    
    // Record to monitoring system
    metricsStore.recordHistogram(
      'eventual_consistency_convergence_ms',
      metrics.convergenceTime
    );
    
    for (const [replica, time] of metrics.allReplicaTimes) {
      metricsStore.recordGauge(
        'replica_convergence_ms',
        time,
        { replica }
      );
    }
    
    // Alert if convergence is too slow
    if (metrics.convergenceTime > 5000) {
      alerting.warn(
        `Slow convergence: ${metrics.convergenceTime}ms, ` +
                                `slowest replica: ${metrics.slowestReplica}`
      );
    }
    
    await sleep(60000); // Measure every minute
  }
}

Designing for Eventual Consistency

Building applications that work correctly under eventual consistency requires specific design patterns. These patterns embrace temporary inconsistency rather than fighting it, resulting in systems that are both correct and highly available.

Design Patterns for Eventual Consistency

•Idempotent Operations — Design operations that produce the same result whether applied once or multiple times. Essential for safe retries.
•Compensating Transactions — When consistency errors are detected, apply corrective operations rather than rolling back.
•Saga Pattern — Break distributed transactions into local transactions with compensating actions for failures.
•Event Sourcing — Store events, not state. Derive current state by replaying events. Naturally handles eventual consistency.
•CQRS (Command Query Responsibility Segregation) — Separate read and write models. Read models can be eventually consistent while writes are consistent.
•Optimistic UI Updates — Update UI immediately on user action, then reconcile with server response. Covers consistency lag.

Deep Dive: Idempotent Operations

Idempotency is the single most important pattern for eventual consistency. It means:

f(x) = f(f(x))

Applying an operation twice has the same effect as applying it once.

Why It Matters:

In eventually consistent systems, uncertainty is common:

Did my write succeed? (network timeout)
Was this event already processed? (duplicate delivery)
Is this data current? (replication lag)

With idempotent operations, you can safely retry without fear of duplicate effects. If you're unsure whether an operation succeeded, just do it again.

Non-Idempotent (Dangerous)

•incrementCounter()
•addToBalance(amount)
•appendToList(item)
•sendEmail()
•chargeCard(amount)

Idempotent (Safe)

•setCounter(value)
•setBalance(newBalance)
•addToSet(item) (sets ignore duplicates)
•sendEmailIfNotSent(idempotencyKey)
•chargeCardWithKey(amount, key)

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// Making operations idempotent with idempotency keys
 
interface IdempotentOperation {
  idempotencyKey: string;  // Unique ID for this logical operation
  operation: string;
  payload: any;
  timestamp: Date;
}
 
class IdempotentOperationHandler {
  private processedKeys: Map<string, { result: any; expiry: Date }>;
  
  async executeIdempotent<T>(
    key: string,
    operationFn: () => Promise<T>,
    ttlMs: number = 24 * 60 * 60 * 1000  // 24 hours
  ): Promise<T> {
    
    // Check if already processed
    const existing = this.processedKeys.get(key);
    if (existing && existing.expiry > new Date()) {
      console.log(`Idempotency key ${key} already processed, returning cached result`);
      return existing.result as T;
    }
    
    // Execute operation
    const result = await operationFn();
    
    // Store result for future deduplication
    this.processedKeys.set(key, {
      result,
      expiry: new Date(Date.now() + ttlMs)
    });
    
    return result;
  }
}
 
// Usage: Idempotent payment processing
async function processPayment(request: PaymentRequest) {
  const handler = new IdempotentOperationHandler();
  
  // Client provides idempotency key
  // Same key = same payment, safe to retry
  return await handler.executeIdempotent(
    request.idempotencyKey,
    async () => {
      // This will only execute once per key
      const charge = await paymentGateway.charge({
        amount: request.amount,
        customerId: request.customerId,
        idempotencyKey: request.idempotencyKey  // Pass to gateway too
      });
      
      await database.recordPayment({
        chargeId: charge.id,
        amount: request.amount,
        customerId: request.customerId
      });
      
      return { success: true, chargeId: charge.id };
    }
  );
}
 
// Client code - safe to retry on network error
async function makePaymentWithRetry(request: PaymentRequest) {
  const idempotencyKey = `payment:${request.orderId}:${request.amount}`;
  
  for (let attempt = 0; attempt < 3; attempt++) {
    try {
      return await api.processPayment({
        ...request,
        idempotencyKey  // Same key for all retries
      });
    } catch (error) {
      if (error.isRetryable) continue;
      throw error;
    }
  }
}

Summary: The Convergence Guarantee

We've explored the third and final pillar of the BASE consistency model: Eventually Consistent. Let's consolidate the key takeaways:

Key Takeaways

•Eventual consistency guarantees convergence — Given no new writes, all replicas will eventually hold the same value. This is the foundation of distributed system correctness.
•Consistency exists on a spectrum — From strict consistency to eventual consistency, each level trades off availability, latency, and predictability.
•BASE properties can be strengthened — Read-your-writes, monotonic reads, and causal consistency provide stronger guarantees while preserving availability.
•Convergence mechanisms drive consistency — Gossip protocols, anti-entropy, read repair, and hinted handoff work together to propagate updates.
•'Eventually' can be quantified — Measure actual convergence times; typical values range from milliseconds to seconds, longer during failures.
•Design patterns enable correctness — Idempotency, compensating transactions, sagas, and event sourcing make applications work correctly under eventual consistency.

What's Next:

Now that we understand all three pillars of BASE—Basically Available, Soft State, and Eventually Consistent—we're ready to compare BASE with ACID directly. The next page examines ACID vs BASE Trade-offs, helping you understand when to use each consistency model and how to make informed architectural decisions based on your application's specific requirements.

Page Complete

You now understand eventual consistency—the convergence guarantee that gives BASE its foundation of correctness. While data may be temporarily inconsistent, the system will converge to a consistent state. Combined with basic availability and soft state, eventual consistency enables distributed systems that scale to planetary proportions. Next, we'll compare ACID and BASE to understand when each is appropriate.