Replication Lag and Consistency Guarantees#

TL;DR#

Asynchronous replication enables high write availability but introduces replication lag, which leads to temporary inconsistencies across database replicas. This lesson explores three critical single-user consistency guarantees: read-your-writes consistency, monotonic reads, and consistent prefix reads. These models protect users from experiencing confusing anomalies while the cluster converges toward eventual consistency.

The idea#

When building a distributed database, we must decide how updates are sent to follower replicas. As we saw in 07-replication-single-leader.md, synchronous replication forces the leader to wait for all followers to confirm a write before responding to the client. This ensures absolute consistency but introduces high write latency and makes the entire system vulnerable to a single replica failing.

To keep write latencies low and ensure high availability, most distributed databases use asynchronous replication. In this model, the leader processes writes immediately and propagates updates to followers in the background. The major trade-off of asynchronous replication is replication lag: the delay between a write landing on the leader and being applied to a follower replica.

In a well-designed cluster under normal operations, replication lag is negligible, usually a fraction of a second. However, if the system faces a sudden traffic spike, network congestion, or hardware slowness, this lag can easily spike to seconds, minutes, or even hours.

When a database replica lags, it holds a stale snapshot of the data. If a user reads from this lagging replica right after making a write, they see their changes vanish. This inconsistency causes extreme frustration, making the system feel broken and buggy.

Eventual consistency is a weak guarantee that promises replicas will converge if no new writes occur. However, it makes no promises about when they will converge, nor does it protect users from seeing inconsistent states in the meantime. To solve this without sacrificing read performance, we implement targeted consistency guarantees. These guarantees are weaker than strict, immediate consensus, but they ensure a coherent user experience despite underlying replication delays.

How it works#

To understand replication lag in practice, we must explore how it breaks user expectations and how we can prevent specific anomalies. While eventual consistency allows the system to converge in the background, a user can navigate the application in ways that expose this replication lag. Let's examine the three core consistency guarantees designed to mitigate lag and prevent confusing anomalies.

Comparison of Consistency Guarantees#

Before looking at the mechanics of each guarantee, here is a high-level summary of the anomalies they target and how databases prevent them:

Consistency Guarantee	Target Anomaly	Root Cause of Anomaly	Primary Prevention Technique
Read-Your-Writes	A user submits an update but sees their old data after refreshing.	Read is routed to a follower that has not yet pulled the write from the leader.	Route owned reads to the leader, or block reads on followers using write LSNs.
Monotonic Reads	A user refreshes a page and sees data regress from a newer state to an older state.	Subsequent reads are routed to different followers with varying lag times.	Pin each user session to a specific replica (e.g., via user ID hash routing).
Consistent Prefix Reads	Causal sequences appear out of order (e.g., seeing an answer before the question).	Data is partitioned, and partitions replicate to followers at different speeds.	Route causally related data to the same partition, or track causal dependency logs.

1. Read-Your-Writes Consistency (Read-After-Write)#

This guarantee ensures that if a user updates some data, they will always see their own update when they reload the page. It makes no promises about what other users see.

The Anomaly#

Imagine a user updating their profile bio on a social media site.

Leader Node (Leader)       Replica A (Lagging)
     |                             |
     |<---- 1. Write (t=10)        |
     |      "Update Bio"           |
     |----                         |
     |    | 2. Sync Lag            |
     |<----                        |
     |                             |
     |                             |
     | (Replication Lagging...)    |
     |                             |
     |                             |<---- 3. Read (t=12)
     |                             |      "Read Bio"
     |                             |----> 4. Returns STALE (Old bio)
     |                             |      [Anomaly!]

Worked Example 1 (Logical Timestamps and LSNs)#

Let's look at a concrete sequence of events with numbers: - At physical time 10:00:00.100, User 456 sends an update request to change their profile bio to "Distributed systems enthusiast." - The leader processes this write, assigning it a logical log sequence number (LSN) of 45210. The leader returns success to the client, along with this LSN in the response metadata: json { "status": "success", "updated_fields": { "bio": "Distributed systems enthusiast" }, "lsn": 45210 } - The client application stores this LSN 45210 in local session storage or a browser cookie. - At 10:00:00.150, User 456 refreshes their profile page. The load balancer directs this read request to Replica A. - Replica A is currently lagging behind the leader. Its current LSN is only 45180. - Because Replica A has not processed log sequence number 45210, it returns the old bio: "Software engineer." - User 456 is confused, thinking their update was lost, and submits the write again.

The Techniques to Fix It#

We can enforce read-your-writes consistency through several practical strategies: - Leader routing for owned data: We can route reads for data that the user might have modified to the leader instead of a follower. For example, a user's own profile page is always read from the leader, while other users' profiles can be safely read from follower replicas. - Time-based routing: The application can track the timestamp of the user's last write. For a specific window of time (such as one minute) after a write, we route all reads from that user to the leader. Alternatively, we can block reads on a follower until that replica has caught up to the write's timestamp. - Logical position tracking: The client tracks the LSN of its last successful write in a local session cookie. When sending a read query to a follower, the client includes this LSN. The follower replica only answers the query if its own LSN is greater than or equal to the client's LSN. If the follower is lagging, the query waits for the replication log to catch up, or it gets redirected to a replica that is sufficiently updated.

Cross-Device Complications#

A major challenge arises when a user switches devices. If they update their bio on a smartphone and then open a laptop, local tracking (like a browser cookie) won't work. The laptop doesn't know about the LSN from the smartphone.

Solving this requires storing the user's last write logical timestamp in a centralized user session database. This metadata must be fetched on login and tracked globally across all active sessions.

Client-Side Caching (The UI Layer Fix)#

To prevent network hops altogether, many applications use optimistic UI updates. When a user submits a write, the frontend immediately updates the local UI state before the server even responds. If the user then reloads or navigates within the application, the frontend serves the updated data from its local cache (such as Redux or Apollo Client cache) instead of querying the backend database. This creates a flawless illusion of read-your-writes consistency, though developers must be careful to handle write failures by rolling back the UI state if the server eventually rejects the write.

2. Monotonic Reads#

This guarantee ensures that once a user has seen a certain piece of data, they won't see older versions of that same data on subsequent queries. It prevents physical time from appearing to run backwards.

The Anomaly#

Imagine a customer checking the status of a package delivery.

User             Replica A (Caught up)      Replica B (Lagging)
 |                     |                             |
 |---- 1. Read ------->|                             |
 |<--- 2. "Delivered" -|                             |
 |                     |                             |
 |---- 3. Refresh ---------------------------------->|
 |<--- 4. "In Transit" <-----------------------------|
                                                    [Anomaly: Time went backwards!]

Worked Example 2 (Consistent Replica Routing)#

Let's trace this with numbers: - At 10:05:00.000, the package status is updated to "Delivered" on the leader. - Replica A receives the update and applies it immediately. Replica B faces network congestion and remains lagging. - At 10:05:01.000, the customer queries the system. The load balancer routes the read to Replica A. The customer sees "Delivered." - At 10:05:05.000, the customer refreshes the tracking page. The load balancer routes this second query to Replica B. - Replica B is still lagging and returns "In Transit." - The customer is highly confused, believing the package status was rolled back or that the system is broken.

The Techniques to Fix It#

We can achieve monotonic reads by pinning each user to a specific replica: - Replica pinning: We route a user's requests to the same database node using a hash of their user ID rather than choosing nodes randomly. For instance, hash(user_789) % number_of_replicas determines which replica serves all reads for User 789. - Failover handling: If the pinned replica fails, the system must route the user to a new replica. To avoid breaking monotonic reads during this transition, the new replica must be caught up at least to the logical timestamp of the user's last read. The system can reject the connection or route to the leader if the fallback follower is too stale.

3. Consistent Prefix Reads#

This guarantee ensures that if a sequence of writes happens in a specific causal order, anyone reading those writes will see them appear in that exact same order.

The Anomaly#

This anomaly typically occurs in partitioned (sharded) databases. Imagine a conversation between two friends where the answer is displayed before the question.

Partition 1 (Alice)             Partition 2 (Bob)
     |                                 |
  [Alice: "Are you free?"]             |
     |                                 |
     |-- Replicated (Slow) -->         |
     |                               [Bob: "Yes, I am!"] (Causally dependent)
     |                                 |
     |                                 |-- Replicated (Fast) -->
     |                                 v
     |                          Observer Node reads Partition 2, then Partition 1
     |                          Observer sees: "Yes, I am!" before "Are you free?"

Worked Example 3 (Causal Disruption)#

Let's see this in a partitioned setup: - Alice posts a message: "Are you free for lunch tomorrow?" This write is routed to Partition 1 because Alice's user ID hashes to that partition. - Bob sees Alice's message on Partition 1 and replies: "Yes, I am!" This reply is routed to Partition 2 because Bob's user ID hashes to Partition 2. - There is a causal relationship here: Bob's reply makes no sense without Alice's question. - An observer, Charlie, queries a lagging follower replica of the database. - The replication stream for Partition 2 is fast, so Bob's reply arrives on Charlie's follower immediately. The replication stream for Partition 1 is lagging due to network issues, so Alice's question is delayed. - Charlie reads the conversation and sees Bob's reply first: "Yes, I am!" Alice's question is nowhere to be seen. This destroys the causal order.

Why Partitions Break It#

In a database with only a single partition, a single leader enforces a total order of all writes. The replication log applies them in the same sequence on all followers, preventing this anomaly.

When data is partitioned, different partitions operate independently. There is no global leader to sequence writes across partitions, which allows causal order to break during replication.

This issue is particularly common in multi-region deployments. Network latencies between different data centers can vary widely, causing some partitions to replicate significantly faster than others.

The Techniques to Fix It#

We can preserve consistent prefix reads with these methods: - Single partition routing: We can route causally related data to the same partition. For instance, we can ensure that all messages in a specific chat room or thread share the same partition key, forcing them through a single ordering log. - Causal dependency tracking: The database can track causal relationships using logical clocks or vector clocks. When Charlie reads the messages, the client application uses this metadata to delay showing Bob's reply until Alice's question has also been loaded and displayed.

Relation to Stronger Consistency and Transactions#

These three guarantees are weaker than strict consistency models like linearizability, which we will explore in 13-consistency-and-consensus.md. Linearizability guarantees that all reads see the absolute latest write globally, as if there was only one copy of the data. This requires global real-time synchronization, which severely limits performance and write availability.

In contrast, read-your-writes, monotonic reads, and consistent prefix reads are single-user guarantees. They ensure that an individual user's view of the database remains logical and coherent, without making promises about how quickly other users see their updates.

How Transactions and Isolation Levels Help#

When application requirements demand multi-user consistency, weak guarantees are not enough. For example, if two users try to book the same flight seat, we cannot allow both to succeed. This is where database transactions and isolation levels help: - ACID Isolation: Transactions isolate concurrent operations from each other. Serializable isolation guarantees that transactions execute as if they ran in a strict, sequential order, preventing any concurrent race conditions. - Snapshot Isolation: This isolation level allows transactions to read from a consistent snapshot of the database. This prevents many read anomalies, but in a distributed system, the database must still coordinate to ensure that the snapshots themselves are synchronized across all replicas. - Distributed Transactions: When data spans multiple partitions or replicas, we must use protocols like Two-Phase Commit or distributed consensus to ensure that all nodes either commit or abort a transaction together. This provides a stronger consistency ceiling but comes with substantial coordination latency. We will cover this in detail in future lessons on consistency and consensus.

Pros#

Consistent user experience: Users are spared from confusing anomalies like disappearing edits, retrograding timestamps, or out-of-order conversations.
High read availability: The system can continue serving reads from any replica without sacrificing write performance or blocking writes on leader confirmation.
Reduced network latency: Replicas can answer queries locally without requiring slow, synchronous coordination rounds across the entire cluster.
Simpler client code: Handling consistency at the database and routing layers keeps application developers from writing custom, error-prone client-side retry rules.

Cons#

Complex routing architectures: Databases or application proxies must track user IDs, logical timestamps, and causal metadata to route requests to the correct replica.
Reduced load-balancing efficiency: Pinning users to specific replicas can cause uneven load distribution, creating "hot replicas" and reducing the benefits of read scaling.
Metadata storage overhead: Replicas and clients must carry and store extra causal logs or sequence numbers, which increases network payload size.
No multi-user write conflict protection: These guarantees only protect an individual user's view of their own data, doing nothing to prevent concurrent write conflicts from different users.

Alternatives#

Linearizability (Strong Consistency): This model guarantees that all operations appear to execute atomically at a specific point in time. It is perfect for financial balances but requires slow, expensive coordinator steps and reduces availability during network partitions.
Synchronous Replication: You configure the leader to block write responses until all follower replicas have successfully written the log. This approach eliminates replication lag entirely but makes writes slow and vulnerable to any single replica failing.
Staleness-Bounded Consistency: The system guarantees that replicas will never lag behind the leader by more than a specific, configured physical time window (such as five seconds) or a fixed number of logical operations. If a replica lags beyond this bound, it stops answering reads until it catches up. This is useful when you want to place a firm limit on how stale a read can be, without paying the heavy performance cost of immediate, synchronous consensus.
Single-Node Databases: Avoiding replication entirely bypasses all replication lag issues. This is great for small workloads but limits your system's storage capacity, read throughput, and fault tolerance.

When to use it#

These consistency guarantees are ideal for the following real-world scenarios: - Social media networks: Activities like posting comments, updating profile bios, liking posts, and refreshing feeds require low-latency reads. Users expect their own actions to remain consistent (such as seeing their comment appear immediately), but they can tolerate minor delays in seeing other users' updates. - Personal productivity apps: Email clients, task managers, and note-taking applications often serve individual users. Providing read-your-writes and monotonic reads prevents the user from experiencing confusing data regressions across refreshes. - Collaborative message threads: Standard group chats require that messages maintain logical and causal sequence, making consistent prefix reads highly suited for preserving the flow of conversation.

When NOT to use it#

Avoid relying on these weak consistency models in the following scenarios: - Financial and banking ledgers: Account balances must be strictly consistent globally at all times. A user cannot be allowed to withdraw funds from a lagging follower that does not yet reflect a recent transfer. - E-commerce inventory counters: If stock count is stale, two users might concurrently purchase the last available item, creating an inventory conflict. - Critical security and permission systems: Revoking a user's access tokens or changing role policies must propagate immediately across the entire cluster. Lagging replicas could allow unauthorized actions, representing a major security risk. For these use cases, reach for linearizable reads, strict serializable transactions, or strong consensus mechanisms.

Key takeaways / mental model#

Think of eventual consistency like a group of friends sharing gossip. Alice tells Bob a secret, who then tells Charlie, meaning it takes time for the news to spread. Querying Dave too early will result in him knowing nothing.

This model can be summarized using the following analogies:

Read-your-writes is like keeping a diary of what you said so you never contradict yourself.
Monotonic reads is like only talking to friends who are at least as caught up on the gossip as the last person you spoke to.
Consistent prefix reads ensures you never hear the punchline of a joke before the setup.

Self-check questions#

A user updates their status on a phone, then immediately opens their laptop and sees the old status. What consistency guarantee was broken here, and how would you fix it?
Why is pinning a user to a specific replica to achieve monotonic reads vulnerable to node failures, and how can the system handle failover safely?
How do consistent prefix read anomalies occur in partitioned databases but rarely in single-partition, single-leader systems?
Explain the difference between read-your-writes consistency and linearizability. Which one would you choose for a collaborative document editing tool, and why?
Imagine a system where reads are routed to followers but a user's own writes must be read from the leader. What happens to the system's write and read capacity if every user constantly edits their own data?
When routing client reads to replicas based on logical timestamps, what trade-off do we make regarding system latency and resource utilization?
In a chat system with millions of active rooms, how would you design the partitioning key and routing strategy to guarantee consistent prefix reads without causing extreme skew?
What are logical clocks (such as vector clocks), and how can a client application use them to reconstruct the correct causal sequence of events when a partitioned database fails to maintain consistent prefix reads?

References#

Designing Data-Intensive Applications (Martin Kleppmann), Chapter 5
13-consistency-and-consensus.md