Eventual Consistency & Conflict Resolution

1. From Strong to Eventual Consistency

Strong consistency guarantees that a read will always return the most recently written value. Eventual consistency makes a looser promise: if no new updates are made to a given data item, all replicas will eventually converge to the same value. In the interim, reads might return stale data.

This is a common pattern in large-scale systems where data is replicated across multiple data centers.

The core trade-off is choosing between the guarantees of a CP system and the benefits of an AP (Available and Partition-Tolerant) system. Opting for eventual consistency typically yields:

• Higher Availability: The system can continue to accept reads and writes even if some replicas are temporarily disconnected.
• Lower Latency: Users can be served by their nearest replica, providing a faster response without waiting for a global consensus protocol to complete.

But how do you decide when this trade-off is acceptable? The choice is not arbitrary; it's driven by the product's functional requirements and the user experience.

The following video provides an excellent framework for making this decision by analyzing the impact on reliability, functional correctness, and user experience across several real-world examples.

As the video demonstrates, the key is to ask: "What is the real-world impact if a user sees stale data for a short period?"

• For an Amazon inventory count, the impact is high (selling phantom items), so strong consistency is required.
• For a Twitter 'like' count, the impact is low (seeing 99 likes instead of 100), so eventual consistency is a great choice to improve performance and scalability.

2. The Challenge: Write Conflicts

When you build a system with a single leader (like the Raft-based systems from our last lesson), all writes go to one place, establishing a clear, unambiguous order of operations. This prevents write conflicts.

However, many highly available, eventually consistent systems use a multi-leader or leaderless architecture. In this model, multiple replicas can accept write operations concurrently. This is what enables high availability and low latency, but it also creates a problem: what happens if two users update the same piece of data on two different replicas at the same time? This is a write conflict.

The rest of our lesson will focus on the strategies used to handle these conflicts.

3. Detecting and Resolving Conflicts

To handle a conflict, you must first detect it. A naive approach is to just let the last write win, but this often leads to data loss. A more robust method involves tracking the history of data to see if writes were concurrent.

Detecting Conflicts with Version Vectors

A version vector (or vector clock) is a mechanism used to detect causality between events in a distributed system. Instead of a single version number, each replica maintains a vector of counters, with one counter per replica in the system.

When a system detects that two versions of an object have vector clocks that are not causally ordered (i.e., they happened concurrently), it knows a conflict has occurred. Now, it must be resolved.

Let's explore the "menu" of resolution strategies you can choose from.

Let's summarize and contextualize the most important strategies for a system design interview.

Strategy 1: Last Write Wins (LWW)

• How it works: Each write includes a timestamp. When a conflict is detected, the write with the latest timestamp is kept, and all others are discarded.
• Pros: Simple to implement, and resolution is automatic and fast.
• Cons: Prone to silent data loss. If two users update a record concurrently, one user's update will be completely lost without any notification. This is often unacceptable. It also relies on perfectly synchronized clocks, which is a hard problem in distributed systems.
• Interview Takeaway: Acknowledge LWW as the simplest strategy, but immediately point out its data loss problem, showing that you understand its risks. It's only suitable for data where losing an update is acceptable (e.g., updating a user's last-seen timestamp).

Strategy 2: Application-Side Resolution

• How it works: The database detects a conflict and, instead of choosing a winner, it preserves all conflicting versions (often called "siblings"). It then returns all versions to the client application and says, "You decide."
• Pros: No data loss. Highly flexible, as the application's business logic can make an intelligent decision.
• Cons: Pushes complexity to the application developer. Increases latency for the end-user if they need to be prompted for a manual merge.
• Classic Example: An e-commerce shopping cart. If a user adds an item on their laptop and another on their phone concurrently, we don't want LWW to discard one of the items. The application can receive both versions of the cart and merge them by taking the union of the items.

Strategy 3: Automatic Resolution with CRDTs

Conflict-Free Replicated Data Types (CRDTs) are a more advanced and powerful approach. They are data structures mathematically designed so that concurrent updates can be merged automatically without conflicts, guaranteeing that all replicas will converge to the same final state.

This is a fantastic topic to bring up in a senior interview to demonstrate depth of knowledge.

As the video explains, there are two main types of CRDTs:

1. State-Based CRDTs (Convergent Replicated Data Types): Each replica can send its full state to other replicas. The magic is in the merge function, which must be associative, commutative, and idempotent. This means the order and number of times states are merged doesn't matter, which makes them robust and a great fit for gossip protocols.
2. Operation-Based CRDTs (Commutative Replicated Data Types): Replicas transmit the operations (e.g., increment, add(item)), not the entire state. This is more lightweight but often requires a more reliable messaging layer to ensure operations aren't lost or duplicated.

Many common data types have CRDT implementations:

• Counters: G-Counter (grow-only), PN-Counter (increment/decrement). Perfect for 'like' counts, page views.
• Sets: G-Set (grow-only), 2P-Set (add and remove), OR-Set (Observed-Remove Set). Ideal for managing tags on a post or items in a cart.
• Registers: LWW-Register.

Special Cases: OT and Tombstones

• Operational Transformation (OT): A different approach primarily used for real-time collaborative text editing (e.g., Google Docs). It's extremely complex and specific. Mentioning it shows you know the landscape, but you're unlikely to be asked to design it.
• Tombstones for Deletes: In a distributed system, how do you replicate a DELETE? If you just remove the data, the system can't distinguish between "data never existed" and "data was deleted." A conflict can occur if one replica processes a DELETE while another processes an UPDATE. A tombstone is a marker that says "this data was deleted at this time." It's a special type of write that propagates through the system, ensuring deletes eventually win over earlier updates.

4. Summary of Strategies

Here is a summary table to help you structure your thoughts for an interview.

Conclusion

Today we've journeyed to the "Available" side of the CAP theorem, embracing eventual consistency to build highly available and performant systems.

Key Takeaways:

• Eventual consistency is a deliberate design choice that prioritizes availability and low latency over immediate, strong consistency.
• This choice is driven by business requirements: if brief periods of stale data do not harm the user experience or break core functionality, eventual consistency is a powerful tool.
• Adopting a multi-leader or leaderless architecture for high availability introduces the problem of write conflicts.
• You have a toolkit of conflict resolution strategies, from the simple-but-risky Last Write Wins to the robust Application-Side Resolution and the advanced, automatic merging of CRDTs. Knowing their trade-offs is key to senior-level system design.

In many eventually consistent systems, operations that don't need to be synchronous are handled in the background. For example, the video mentioned updating a "likes" count asynchronously using a queue. This is a perfect segue into our next topic.

Next Lesson Preview: Our next lesson is "Apply message queues for asynchronous processing in system design contexts." We will explore how message queues like RabbitMQ and Kafka serve as the backbone for building reliable, scalable, and eventually consistent workflows in distributed systems.