How Distributed Systems Keep Data in Sync at Scale

The systems behind the software we use every day operate across thousands of servers in datacenters all over the world. At this scale, failures are continuous: server racks lose power, cooling systems overheat, and natural disasters or even drone strikes can bring entire datacenters offline. In spite of this, our data remains accessible and the systems we use remain operational (most of the time). That’s because data is never stored in one place; systems constantly replicate data across datacenters and regions, often storing several copies to guarantee that data remains readily accessible in the event of failures. This also serves to improve performance at scale, allowing data to be accessed from multiple replicas closer to users instead of every request hitting the same central server. However, data replication introduces complexity and tradeoffs that must be carefully considered when designing a system, since keeping copies synchronized around the world is a fundamentally difficult problem.

CAP Theorem

One of the most foundational tradeoffs in distributed databases is defined by CAP theorem, which states that a distributed database can only provide 2 of the following 3 guarantees:

• Consistency: Every read always sees the most recent write or an error.
• Availability: Every request receives a non-error response.
• Partition tolerance: The system continues to operate despite network failures between nodes.

Network partitions are inevitable in distributed systems, so the theorem frames a choice between CP (consistency + partition tolerance) and AP (availability + partition tolerance). CP systems prioritize consistency during partitions, even if that means rejecting some requests. AP systems prioritize availability during partitions, even if that means serving stale data.

CAP outlines the broad tradeoff, but most real systems define more specific guarantees that can change depending on their configuration. As a result, many systems can lean toward either CP or AP behavior without clearly fitting into either category. In practice, the behavior of replication systems is usually described in terms of consistency guarantees. CAP defines consistency as a binary property, but there are actually many different kinds of consistency a system can provide.

Consistency

In a distributed database, replicas can’t always be synchronized; writes take time to propagate across nodes. However, systems can coordinate to hide this complexity from the user. Consistency describes how predictable reads and writes are while replicas may temporarily hold different versions of the same data. At the highest level, this is usually discussed in terms of strong vs. eventual consistency:

• Strong consistency: The system coordinates to behave as if there is only one up-to-date copy of the data. Once a write is committed, any subsequent reads must return that write.
• Eventual consistency: Replicas are allowed to temporarily diverge. Once a write is committed, replicas can still respond with stale data until the write is propagated.

This reflects the same tradeoff described by CAP. Strong consistency leans toward CP, ensuring correctness at the cost of more coordination. Eventual consistency leans toward AP, prioritizing performance and availability at the cost of stale reads. But between these two definitions, systems often provide narrower consistency guarantees that describe more specific behavior, such as:

• Read-after-write consistency: After a user writes data, that same user can immediately read their own write.
• Monotonic reads: Once a user sees a newer value, they will not later see an older value.
• Monotonic writes: Writes from the same user are applied in the order they were issued.
• Consistent prefix reads: Reads do not show later writes without also showing the earlier writes that came before them.

Ultimately, consistency is a tradeoff: stronger guarantees improve correctness, while weaker guarantees can improve performance, availability, and scalability. These tradeoffs are heavily shaped by the replication model, with the three main approaches being single-leader, multi-leader, and leaderless replication.

Single-Leader Replication

Single-leader replication is the simplest and most common replication model. One replica is elected as the leader, and all writes go through it. The leader applies writes in order, records them in its write-ahead log, then streams that log to follower replicas so they can replay the same changes in the same order. Because there is one source of truth for writes, this model is usually considered CP-leaning and naturally provides monotonic writes and consistent prefix reads.

Eventual consistency is often the default behavior for single-leader systems because followers often receive writes asynchronously after the leader commits them. This keeps reads and writes fast, but reads may return stale data. However, if the leader crashes before a committed write has been replicated, that write can be lost. To avoid this, systems use synchronous replication to a small quorum of replicas before considering the write committed. To ensure that followers don’t serve uncommitted data before the quorum is reached, an approach is for the leader to stream a commit index which tells followers the latest point up to which writes are committed.

With asynchronous replication, a core issue is that inconsistency causes unexpected behavior. For example, if a user reads from an up-to-date replica, then later reads from a stale replica, data would appear to have gone backwards from their perspective. Or, when a user writes to the leader, then later reads from a stale replica, they wouldn’t be able to see their own write. This introduces the need for session-level guarantees: consistency guarantees from the perspective of one user session, rather than globally across all users and replicas. Session-level guarantees can improve expected behavior without requiring as many additional constraints on the overall system. Eventual single-leader systems often provide session-level monotonic reads and read-after-write consistency to avoid these anomalies. Two common approaches are:

• Session stickiness: A simple approach to achieve monotonic reads is to route a user’s requests to the same replica. However, this guarantee breaks if the replica crashes. This also doesn’t provide read-after-write consistency.
• Versioning: After each read or write, the system returns the latest version the user has observed. Future requests are then served only by replicas that have reached at least that version. This is a more robust solution that guarantees both monotonic reads and read-after-write consistency.

Strong consistency is fundamentally harder to provide. The simplest approach is to synchronously replicate writes to every node before committing them. But with this approach, any replica outage would force the entire system to stop accepting writes, significantly impacting availability. In practice, there are broadly three main ways of implementing strong consistency in single-leader systems:

• Leader reads: Strong reads go to the leader because it has the latest committed writes, while replicas handle reads that can tolerate stale data. However, a leader cannot always know if it is still the valid leader, since it may be partitioned from the group. To make leader reads safe, systems can use leases: short agreements that replicas will not elect a new leader while the current leader serves reads.
• Fresh follower reads: Followers can serve strong reads if they can prove they are sufficiently up to date. This is difficult because a follower cannot know on its own whether the leader has accepted a newer write. Asking the leader directly would confirm freshness, but it defeats the purpose of reading from a follower if it’s going to contact the leader anyway. Systems like Google Spanner solve this using clocks: if a replica knows it has applied all writes up to a timestamp later than the read’s timestamp, it can safely serve the read without contacting the leader.
• Quorum reads: Let’s say we have a system with N replicas, where writes are synchronously replicated to W replicas, and reads contact R replicas. If R + W > N, then every read quorum overlaps with every write quorum, meaning a read is guaranteed to see at least one replica that has the latest committed write. This is an uncommon approach in single-leader systems since it requires extra work compared to leader reads.

Single-leader systems can tolerate some failures, but write interruptions are inevitable if the leader goes down. If a follower fails, single-leader systems stay operational as long as there remain enough followers for the leader to reach the write quorum. The failed follower can later recover by replaying the leader’s log. If the leader fails, writes are temporarily paused and the followers may elect a new leader using a consensus protocol. The new leader is typically chosen from the replicas with the most recent committed log entries, ensuring that already-committed writes are preserved.

Multi-Leader Replication

Multi-leader systems have multiple leaders that can all accept writes, with each leader usually having its own set of local followers. Each leader applies local writes, replicates those changes to its followers (similarly to single-leader), and also propagates them to the other leaders so the system eventually converges. This approach is less common than single-leader replication due to generally having weaker consistency, higher costs, and more complexity. However, it does have two significant advantages: higher write availability and lower write latency. If one leader fails, writes can often continue through another leader; and for global applications, users can write to a nearby leader instead of routing every write to one central location.

Multi-leader systems are primarily designed around eventual consistency. Their main advantages, lower write latency and higher write availability, come from allowing leaders to accept writes locally and replicate them asynchronously. Providing strong consistency would require coordination between leaders before committing writes, which would largely remove those benefits and make the system behave more like an expensive single-leader system. Strong reads can be handled through that coordination, but if a large portion of reads need strong consistency, a single-leader design is usually a better fit.

Because multiple leaders can accept writes independently, a major challenge is conflict resolution. If two leaders update the same record before seeing each other’s changes, the system must decide which value should survive or how the two changes should be merged. Common approaches include:

• Last-write-wins: The system keeps the write with the latest timestamp. Simple, but can silently lose updates if not accounted for.
• Conflict-free replicated data types (CRDTs): Some data structures are designed so concurrent updates can always be merged safely. For example, let’s say two users edit the same text document while connected to different leaders. A text CRDT preserves both edits and defines a deterministic order for merging them.
• Application-level merge logic: The system exposes unresolved conflicts to the application, then lets application-specific rules merge them.

Another challenge with multi-leader systems is that the lack of a single source of truth makes unexpected behavior much harder to prevent. While single-leader systems provide monotonic writes and consistent prefix reads out of the box, implementing these guarantees globally across a multi-leader system is nontrivial because multi-leader systems can’t typically provide a single global order of operations without significant coordination. For example, if two leaders accept different writes at the same time, once those writes are propagated, each leader will see the writes in opposite orders. Because of this, multi-leader systems usually provide more session-level guarantees instead of global guarantees.

In practice, one common approach requires session-aware routing plus versioning. The session must stay scoped to the same leader group, where writes are observed in a consistent order. After each read or write, the system returns a version. Future requests include that version, and the system only serves them from a node in that leader group that has reached at least that point. Together, this can provide read-after-write consistency, monotonic reads, monotonic writes, and consistent prefix reads within that session. However, this introduces another tradeoff: if the leader serving that session fails, then preserving the session’s guarantees would require the session’s writes to pause until a new leader is elected within the same leader group, removing the availability benefit offered by multi-leader replication.

Leaderless Replication

Leaderless systems have no fixed roles of leaders or followers; every node can accept both reads and writes. Rather than relying on a leader to replicate writes, consistency is achieved with quorum reads and writes. Clients can send writes directly to multiple replicas, and reads can query multiple replicas to find the latest value. This is described using quorum parameters: N replicas, W replicas required to acknowledge a write, and R replicas contacted during a read. If R + W > N, then every read quorum overlaps with every write quorum, so a read should see at least one replica with the latest committed value. With smaller quorums, the system can accept more failures and reduce latency, but consistency becomes weaker.

However, quorum reads and writes alone are not enough to keep every replica up to date. Some replicas may repeatedly miss writes if they are down or simply not included in the write quorum. Even though consistency can still be provided using quorum reads, stale replicas weaken the system’s ability to tolerate future failures and make low-quorum reads more likely to return outdated data. To prevent replicas from becoming boundlessly stale, leaderless systems usually rely on background repair mechanisms:

• Read repair: When a read contacts multiple replicas and finds that some have stale data, the system updates the stale replicas with the newer value.
• Anti-entropy: Replicas periodically compare their data in the background and repair any differences. To do this efficiently, they compare hashes over ranges of keys to narrow down mismatches.

Leaderless systems are mainly eventually consistent. Even when R + W > N, there are edge cases that make strong consistency unachievable without coordination between nodes. For example, two concurrent writes may be accepted by overlapping sets of replicas, leaving no single value held by a majority. A similar issue can happen if a write only partially succeeds: nodes that acknowledged the write have no way of knowing it didn’t reach the quorum without a leader or coordination layer. Reads that happen concurrently with writes are also ambiguous, since they may return either the old value or the new value depending on which replicas respond.

Monotonic reads and read-after-write consistency can be provided at the session level using versioning. But because reads and writes contact multiple replicas, leaderless systems can’t normally provide consistent prefix reads and monotonic writes, unlike multi-leader systems which can achieve this by routing a session’s requests to the same leader group.

To achieve strong consistency, some leaderless systems can add transaction coordination on top of quorum replication. In this model, any replica can temporarily coordinate a transaction, acting like a short-lived leader for that specific operation. The coordinator checks which other transactions conflict with it, gets replicas to agree on a deterministic order, and only commits once the system has a clear decision. However, once this coordination is added, the system loses much of the simplicity and availability benefits that make leaderless replication attractive in the first place.

Choosing the Right Replication Model

Replication is not about choosing the “best” model universally, but choosing the model whose tradeoffs match the system’s requirements.

When picking a database, the replication model is ultimately one of many things to consider. It is usually tied to the data model itself: relational databases tend to prioritize consistency, while key-value and wide-column databases tend to prioritize availability. Replication also isn’t a major concern until a system reaches meaningful scale; up until that point, a single primary is often enough to handle all reads and writes. But at global scale, the replication model directly shapes consistency, availability, and latency, making it one of the most important factors when choosing a distributed database.