In distributed computing, keeping data consistent across multiple nodes is always a tricky problem. Traditional methods for ensuring consistency, like consensus protocols, often need complex synchronisation that can slow everything down and hurt scalability. Conflict-Free Replicated Data Types (CRDTs) offer an elegant solution by enabling replicas to reach eventual consistency without requiring heavy coordination. CRDTs are designed to be conflict-free, which means replicas can independently modify data and still end up in the same state. This post takes a deep dive into how CRDTs work, including a detailed analysis of common types, with code examples.

The Concept of CRDTs

CRDTs are specialized data structures made for distributed systems where concurrent updates happen often. Unlike usual data structures, CRDTs have properties that guarantee consistency across replicas. Each replica of a CRDT can evolve independently, and when merged with others, the resulting state will always converge to the same value. CRDTs can be divided into two main types:

• State-based CRDTs (also called Convergent Replicated Data Types, CvRDTs): These maintain a mutable state and periodically merge their state with others.
• Operation-based CRDTs (also called Commutative Replicated Data Types, CmRDTs): These share operations directly and ensure those operations are applied consistently.

Fundamental Properties of CRDTs

1. Commutativity: The order in which updates are applied doesn’t affect the final outcome.
2. Idempotency: Applying the same update multiple times has the same effect as applying it just once.
3. Associativity: The way updates are grouped doesn’t affect the final merged state.

Now let’s explore some common CRDT examples, with Python code snippets to help illustrate each type.

1. Grow-Only Counter (G-Counter)

This CRDT only allows increments, making it ideal for counting occurrences across distributed nodes without conflict. Each replica can only increment its value, and the final count is obtained by summing all replicas.

Usage: Riak, a distributed database that uses G-Counters for applications that require counting occurrences (e.g., page views or event counts) across distributed servers.

class GCounter:
    def __init__(self):
        self.counts = [0, 0]

    def increment(self, node_id):
        self.counts[node_id] += 1

    def merge(self, other):
        self.counts = [max(self.counts[0], other.counts[0]), max(self.counts[1], other.counts[1])]

    def value(self):
        return sum(self.counts)

# Example usage
node_a = GCounter()
node_b = GCounter()

# Node A operations
node_a.increment(0)
node_a.increment(0)

# Node B operations
node_b.increment(1)
node_b.increment(1)

# Merge the two nodes
node_a.merge(node_b)
print(f"Final value: {node_a.value()}")

2. PN-Counter (Positive-Negative Counter)

Allows both increments and decrements by maintaining separate counters for positive and negative changes. This is useful for distributed counters that may increase or decrease.

Usage: Implemented in Couchbase and Redis (with Redis’s CRDT modules), where it can support use cases like keeping track of inventory counts, where items can be added or removed.

class PNCounter:
    def __init__(self):
        self.positive = [0, 0]
        self.negative = [0, 0]

    def increment(self, node_id):
        self.positive[node_id] += 1

    def decrement(self, node_id):
        self.negative[node_id] += 1

    def merge(self, other):
        self.positive = [max(self.positive[0], other.positive[0]), max(self.positive[1], other.positive[1])]
        self.negative = [max(self.negative[0], other.negative[0]), max(self.negative[1], other.negative[1])]

    def value(self):
        return sum(self.positive) - sum(self.negative)

# Example usage
node_a = PNCounter()
node_b = PNCounter()

# Node A operations
node_a.increment(0)
node_a.decrement(0)

# Node B operations
node_b.increment(1)
node_b.increment(1)

# Merge the two nodes
node_a.merge(node_b)
print(f"Final value: {node_a.value()}")

3. Grow-Only Set (G-Set)

A Grow-Only Set is one of the simplest CRDTs—elements can be added but never removed. This makes G-Sets great for use cases where you need an append-only approach.

Here’s a step-by-step breakdown of what’s happening in the image:

1. Initial State:
   Both Node A and Node B start with the same element in their sets:

   • Set: {'banana'}

2. User A’s Update on Node A:

   • User A adds the element 'orange' to Node A’s set.
   • After the addition, Node A’s set becomes:
     • Set: {'banana', 'orange'}

3. User B’s Update on Node B:

   • User B independently adds the element 'apple' to Node B’s set.
   • After the addition, Node B’s set becomes:
     • Set: {'banana', 'apple'}

4. Merging the Sets:

   • When Node A and Node B synchronize (or merge), their sets combine all unique elements from each set.
   • Since CRDTs are designed to avoid conflicts and only grow with new additions, the merged set at both nodes now includes all unique elements:
     • Set: {'banana', 'orange', 'apple'}

5. Final State:

   • After merging, both Node A and Node B have identical sets with the elements:
     • Set: {'banana', 'orange', 'apple'}

This ensures consistency across nodes without conflicts, as each node grows only by adding new elements.

class GCounter:
    def __init__(self):
        self.counts = {}  # node_id -> count
        
    def increment(self, node_id):
        if node_id not in self.counts:
            self.counts[node_id] = 0
        self.counts[node_id] += 1
        
    def merge(self, other):
        # Take maximum count for each node
        for node_id, count in other.counts.items():
            self.counts[node_id] = max(
                self.counts.get(node_id, 0),
                count
            )
            
    def value(self):
        return sum(self.counts.values())

4. Two-Phase Set (2P-Set)

The Two-Phase Set (2P-Set) CRDT maintains two separate sets: an “Add-Set” and a “Remove-Set”. Elements can be added to the Add-Set and removed by adding them to the Remove-Set. During a merge operation, elements that are in the Add-Set but not in the Remove-Set are considered part of the final merged set. This design allows for more expressive conflict resolution compared to a simple Grow-Only Set (G-Set), as elements can be both added and removed independently on different nodes. 2P-Set is useful in scenarios where elements need to be dynamically added and removed, such as user permissions, shopping carts, or task lists. Many distributed databases and collaborative applications use 2P-Set CRDTs, including Apache Cassandra, Riak, and Google’s Yggdrasil. The ability to both add and remove elements makes 2P-Set a more flexible data structure compared to a G-Set.

class TwoPhaseSet:
    def __init__(self):
        self.add_set = set()
        self.remove_set = set()

    def add(self, element):
        self.add_set.add(element)

    def remove(self, element):
        self.remove_set.add(element)

    def merge(self, other):
        self.add_set.update(other.add_set)
        self.remove_set.update(other.remove_set)

    def value(self):
        return self.add_set - self.remove_set

# Example usage
node_a = TwoPhaseSet()
node_b = TwoPhaseSet()

# Node A operations
node_a.add("banana")
node_a.remove("banana")

# Node B operations
node_b.add("apple")
node_b.remove("apple")

# Merge the two nodes
node_a.merge(node_b)
print("Final set:", node_a.value())

Conclusion

Conflict-Free Replicated Data Types (CRDTs) provide a powerful way to build distributed systems that achieve eventual consistency without costly coordination. We looked at some common CRDTs like G-Counter, PN-Counter, and provided Python examples to demonstrate their implementations. These CRDTs are incredibly useful in applications like collaborative editing, distributed databases, and real-time synchronization.

When building distributed systems, CRDTs can simplify handling concurrent modifications and ensure all nodes converge to a consistent state.