Back
+20 XP
Concept

CRDT Foundations: The Grow-Only Counter (G-Counter)

Conflict-Free Replicated Data Types (CRDTs) guarantee convergence across replicas without central coordination locks. A G-Counter assigns each node a private increment slot; replicas merge by taking the component-wise maximum across all node keys ➕📈.

python
class GCounter:
    def __init__(self, node_id):
        self.node_id = node_id
        self.slots = {node_id: 0}

    def inc(self, step=1):
        self.slots[self.node_id] += step

    def value(self):
        return sum(self.slots.values())

    def merge(self, other):
        # LUB (Least Upper Bound): component-wise maximum
        all_keys = set(self.slots) | set(other.slots)
        for k in all_keys:
            self.slots[k] = max(self.slots.get(k, 0), other.slots.get(k, 0))

c_east = GCounter("US-East")
c_west = GCounter("US-West")

c_east.inc(10)
c_west.inc(15)

c_east.merge(c_west)
print(f"Converged Counter: {c_east.value()} 🚀")

# 34. CRDT Foundations: The Grow-Only Counter (G-Counter) When millions of users tap "Like" on a viral video, funneling every increment through a single PostgreSQL master row creates catastrophic row-lock contention and bottlenecks 🛑. ```python # Traditional Locking: # BEGIN TRANSACTION; # SELECT likes FROM videos WHERE id = 1 FOR UPDATE; -- BLOCKS EVERYONE! # UPDATE videos SET likes = likes + 1 WHERE id = 1; # COMMIT; ``` ### The CRDT Join-Semilattice A State-based CRDT (CvRDT) relies on a mathematical structure called a **join-semilattice**: 1. **Commutativity**: $\text{merge}(A, B) = \text{merge}(B, A)$. The arrival order of network packets does not matter. 2. **Associativity**: $\text{merge}(\text{merge}(A, B), C) = \text{merge}(A, \text{merge}(B, C))$. Message batching order does not matter. 3. **Idempotence**: $\text{merge}(A, A) = A$. Duplicate network packets received across flaky WiFi cause zero double-counting ➕. In a G-Counter, node $i$ only increments `slots[i]`. When syncing, we take $\max(\text{slot}_A[k], \text{slot}_B[k])$. Because $\max$ is commutative, associative, and idempotent, convergence is mathematically guaranteed. --- ### Interactive Pop-Quiz 🧠 #### What mathematical property ensures that two CRDT replicas can exchange state in any network order and always arrive at identical state? - [ ] The merge operation forms a join-semilattice that is associative, commutative, and idempotent ➕ - [ ] The SHA-256 hash of both nodes matches the TCP header sequence - [ ] The operating system syncs memory pages via mmap before writes - [ ] The network switch guarantees zero packet loss between replicas --- ### Practical Challenge 🎯 Implement `GCounter` with `inc(val=1)`, `value()`, and `merge(other)`. Node 1 increments by 7. Node 2 increments by 12. Merge Node 2 into Node 1, merge Node 1 into Node 2, assert both have value 19, and print the converged value. <details> <summary>Solution</summary> ```python class GCounter: def __init__(self, node_id): self.node_id = node_id self.slots = {node_id: 0} def inc(self, val=1): self.slots[self.node_id] += val def value(self): return sum(self.slots.values()) def merge(self, other): for k in set(self.slots) | set(other.slots): self.slots[k] = max(self.slots.get(k, 0), other.slots.get(k, 0)) n1 = GCounter("N1") n2 = GCounter("N2") n1.inc(7) n2.inc(12) n1.merge(n2) n2.merge(n1) assert n1.value() == 19 and n2.value() == 19 print(n1.value()) ``` </details>

Checkpoint

What mathematical property ensures that two CRDT replicas can exchange state in any network order and always arrive at identical state? 🧠

Practice

Implement `GCounter` with `inc(val=1)`, `value()`, and `merge(other)`. Node 1 increments by 7. Node 2 increments by 12. Merge Node 2 into Node 1, merge Node 1 into Node 2, assert both have value 19, and print the converged value. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks