Comparing Conflict Resolution in Distributed Systems

1. The Inevitability of Conflict

In multi-leader and leaderless systems, the ability for multiple nodes to accept writes simultaneously is a feature, not a bug. It provides low write latency and high availability, even during network partitions. The unavoidable side effect is the potential for write conflicts.

Let's watch a short segment that perfectly illustrates how a simple concurrent write scenario in a multi-leader setup creates a conflict that the system must resolve.

As the video shows, when two clients perform operations concurrently without knowledge of each other, the system ends up with two divergent histories for the same piece of data. Now, the database must decide which version to keep.

2. Strategy 1: Last-Write-Wins (The Simple Path)

The most straightforward way to resolve a conflict is to declare a single winner. Last-Write-Wins (LWW) is a policy that does exactly this: it picks one version—the one with the latest timestamp—and discards all others. While simple to implement, this approach is fraught with peril, primarily due to the unreliability of time in a distributed system.

This next video segment does an excellent job dissecting why relying on timestamps is so problematic.

The core issue is that LWW leads to silent data loss. Because the system unilaterally discards a write without notifying anyone, an update can be permanently lost. This might be acceptable for transient data like user session information, but it's catastrophic for critical data like items in a shopping cart or user profile updates.

To drive this point home, let's look at another example that shows how LWW can cause data loss even if we could magically synchronize all clocks perfectly.

As you saw, the root cause is that the second client based its write on an old version of the data. When it overwrote the entire value, it also overwrote the concurrent change made by the first client.

A slight mitigation exists in column-family stores (like Apache Cassandra), where each column can have its own timestamp. This allows the system to merge changes at a more granular level, as long as the concurrent writes don't touch the same column. However, for a concurrent update to the same column, the data loss problem remains.

3. Strategy 2: Version Vectors (The Causal Path)

If LWW's data loss is unacceptable, we need a strategy that preserves all concurrent changes. This is the goal of version vectors (often called vector clocks). Instead of discarding data, version vectors provide a mechanism to detect that a conflict has occurred and delegate the resolution to the application.

The core idea is to replace a single timestamp with a list of counters, one for each replica (or client) that has modified the object. This vector tracks the causal history of the data. By comparing the vectors of two versions, a system can determine if one is an ancestor of the other (a sequential update) or if they are on different branches of history (a concurrent update).

Now, let's see how this works in detail.

When a conflict is detected (i.e., the versions are concurrent, not descendants), the database doesn't make an arbitrary decision. It embraces the conflict and returns all divergent versions to the client. The client is then responsible for semantic reconciliation—merging the conflicting versions in a way that makes sense for the application. For a shopping cart, this might mean taking the union of all items from the conflicting versions.

Let's trace this process with a diagram.

Here is a step-by-step breakdown of the diagram:

1. Initial State: The key K has value U and an empty version vector {}. Both C2 and C3 read this state.
2. Concurrent Writes:
   • C2 performs PUT K: {}: W.
   • C3 performs PUT K: {}: V.
3. First Write Arrives: Replica A receives C3's write first. It updates the value to V and creates a new version vector {(A, 1)} (marking the first write it has seen for this key). It returns this new context to C3.
4. Second Write Arrives (Conflict Detected): Replica A now receives C2's write. It sees that C2's write was based on the empty vector {}, which is not an ancestor of its current vector {(A, 1)}. This is a concurrent write. Replica A preserves both values, creating a "sibling" list [W, V]. It increments its vector clock counter to (A, 2) to reflect this new merged state and sends this context back to C2.
5. Causally Dependent Write: Client C3, which holds the context {(A, 1)}, now wants to write Z. It sends PUT K: {(A, 1)}: Z.
6. Another Conflict: Replica A receives this write. It sees that the write's context {(A, 1)} is an ancestor of its current state {(A, 2)} but that a concurrent change (W) has happened since. It cannot simply overwrite the data. It merges Z into the list of siblings, resulting in the final conflicting state [W, V, Z] and a new version vector {(A, 3)}. The database would now return all three values to any client that reads key K.

For a final, concise reading to solidify these concepts, please review the following text.

4. Comparison and Advanced Alternatives

The choice between LWW and version vectors is a classic system design trade-off between simplicity and data safety.

For a senior engineer, it's also valuable to be aware of more advanced approaches that build on these ideas:

• Conflict-free Replicated Data Types (CRDTs): These are data structures (like sets or counters) specifically designed so that concurrent operations are commutative. No matter the order in which replicas receive updates, they are mathematically guaranteed to converge to the same state. This automates the merge process that version vectors leave to the client.
• Immutable Data Modeling (Event Sourcing): A fundamentally different approach is to never mutate data at all. Instead, you store an immutable, append-only log of operations (events). Conflicts over state are avoided because there is no mutable state to conflict over. The current state is derived by replaying the event log. This pattern aligns well with your experience with Kafka and event-driven architectures.

Conclusion

In this lesson, we tackled the critical problem of resolving write conflicts in highly available distributed systems. You are now equipped to articulate the deep trade-offs between the most common resolution strategies.

Key Takeaways:

• Conflicts are inevitable in multi-leader and leaderless systems that prioritize write availability.
• Last-Write-Wins (LWW) resolves conflicts by picking the newest timestamp, a simple approach that risks silent data loss due to clock skew and read-modify-write races.
• Version vectors resolve conflicts by detecting concurrency and forcing the client application to perform semantic reconciliation. This preserves data but increases application complexity.
• The choice between them is a direct trade-off between data safety and implementation complexity, a crucial point to discuss in any system design interview.

So far, we have discussed systems that allow conflicts and provide mechanisms to resolve them after the fact. But what if your application cannot tolerate any divergence, even temporarily? For that, we need to prevent conflicts from happening in the first place. This requires moving from eventual consistency to strong consistency, which is achieved through consensus algorithms. In our next lesson, we will begin our exploration of this topic by dissecting the Raft consensus algorithm.