Eventual Consistency

Version vectors & stale reads

Simple Fundamental Explanation

Imagine you have three friends keeping track of a shared bank account balance on three separate ledgers. You live in different cities and only communicate by writing letters.

When you deposit $100, you write it in your ledger and mail a letter to your two friends. For the next few days, your friends’ ledgers are out of date. If someone asks them for the balance, they will give the wrong answer.

However, you guarantee that once the mail system delivers all the letters, and all your friends read them and update their ledgers, everyone will eventually agree on the exact same balance.

This is Eventual Consistency. It is a consistency model used in distributed computing that guarantees that, if no new updates are made to a given data item, eventually all accesses to that item will return the last updated value. It trades immediate, perfect accuracy for extreme availability and low latency. It is inherently probabilistic: when you read data, there is a probability it is stale, but that probability approaches zero over time.

---

Deep Dive: How It Works Under the Hood

In distributed databases (like Amazon DynamoDB or Apache Cassandra), data is replicated across multiple nodes to ensure fault tolerance.

Strong Consistency (The Alternative)

In strong consistency, when you write to Node A, Node A locks the data and refuses to return a success message to the user until it has successfully coordinated with Node B and Node C to update their copies too.

• Pros: Perfect accuracy.
• Cons: Slow. If Node C is down, the whole system freezes. (See: CAP Theorem).

Eventual Consistency (The Tradeoff)

In eventual consistency, when you write to Node A, it writes the data to its local disk and immediately tells the user “Success!” In the background, asynchronously, it gossips or replicates the update to Nodes B and C.

If a user reads from Node B exactly 5 milliseconds after the write to Node A, Node B might not have the update yet. Node B serves a “stale read.”

Visual Diagram

Timeline of a Write and Read in an Eventually Consistent System:

Client       Node A (Primary)    Node B (Replica)     Node C (Replica)
  |                 |                   |                    |
  |--- Write(X=5)-->|                   |                    |
  |                 | (Writes to disk)  |                    |
  |<--- Success ----|                   |                    |
  |                 |                   |                    |
  |                 |---- Async Repl -->|                    |
  |                 |                   |---- Async Repl --->| (Network delay!)
  |                 |                   |                    |
  |                 |                   |                    |
  |---------------------- Read(X) -------------------------->|
  |                 |                   |                    |
  |<---------------------- Returns X=0 (Stale!) -------------|
  |                 |                   |                    |
  |                 |                   |                    | (Message arrives)
  |                 |                   |                    | (Writes X=5)
  |                 |                   |                    |
  |---------------------- Read(X) -------------------------->|
  |<---------------------- Returns X=5 ----------------------|

---

Practical Example: The Amazon Shopping Cart

Amazon’s foundational Dynamo paper popularized eventual consistency. They applied it to the shopping cart.

If Amazon’s database goes down, they lose millions of dollars a minute. Therefore, the shopping cart must always accept “Add to Cart” clicks, even if the database nodes are experiencing severe network partitions.

If a server goes down while you add “Socks” to your cart, the system accepts the write locally and says “Added!” If you quickly refresh the page, your request might hit a different server that hasn’t received the update yet. Your cart might look empty. This is a stale read.

However, within milliseconds or seconds, the servers reconcile their data using vector clocks or last-write-wins algorithms. Eventually, the “Socks” reappear in your cart. Amazon decided that a slightly confusing user experience for 0.01% of requests is vastly superior to the website crashing for everyone.

---

The Mathematics: Probabilistic Bounds

Eventual consistency is not random; the “staleness” can be modeled probabilistically.

Let $N$ be the number of replicas. Let $W$ be the number of nodes that must acknowledge a write for it to be considered successful. Let $R$ be the number of nodes that must respond to a read.

In a perfectly strongly consistent system (Quorum), $W+R>N$.

In an eventually consistent system, usually $W=1$ and $R=1$.

The probability $P(stale)$ of reading stale data depends on the time interval $\Delta t$ between the write and the read, and the message propagation delay distribution $f(x)$.

If the propagation delay between nodes follows an exponential distribution with rate parameter $\lambda$, the cumulative distribution function for a message arriving before time $t$ is: $F(t)=1-e^{-\lambda t}$

If you write to 1 node and read from 1 random node out of $N$, the probability you hit the updated node is $1/N$. The probability you hit a stale node is $(N-1)/N$.

If you hit a stale node, the probability that the replication message has not arrived yet at time $\Delta t$ is $1-F(\Delta t)=e^{-\lambda \Delta t}$.

Therefore, the probability of a stale read after $\Delta t$ is:

$$P(\text{stale}\mid \Delta t)=\left(\frac{N-1}{N}\right)e^{-\lambda \Delta t}$$

As $\Delta t\to \infty$, $P(\text{stale})\to 0$. The decay is exponential, meaning the “window of inconsistency” is usually incredibly narrow (a few milliseconds), making it practically invisible to humans.

Lab

Eventual consistency (W=1, R=1): writes return immediately; replicas converge via async replication and version-vector max-merge. Step the timeline for stale reads, then convergence — same tradeoff as the README Amazon cart diagram.

Amazon cartConcurrent writesSlow replication

Timeline stepstep 0: Initial

Δt since write (model)50.0 ms

λ (replication rate)8.0/s

Step timelineReset

Initial — all replicas agree on balance 0

Replica A

0

{}

Replica B

0

{}

Replica C

0

{}

At step 0, before the next read: will the client see a stale value? (P(stale) model ≈ 44.7% at Δt = 50.0 ms.)

Yes — read is likely staleNo — read is fresh or no read occurred

Step 0/5: Replication in progress. Use presets or step to trigger stale reads.