Design a Distributed Counter

The problem: counting across nodes without a bottleneck

A naive distributed counter (every increment goes through one centralized counter, guarded by a Distributed Lock Service lock) works but makes that single counter a contention point and availability bottleneck — every increment serializes through it. A CRDT-based counter takes a fundamentally different approach: each node tracks its own state independently, and a well-designed MERGE operation guarantees all nodes converge to the same correct total, with no central coordination needed for individual increments at all.

CRDTs, properly explained

Conflict-free Replicated Data Types are data structures whose merge operation is commutative (order of merging doesn't matter), associative (grouping of merges doesn't matter), and idempotent (merging the same state twice has no additional effect beyond merging it once) — these three properties together GUARANTEE that no matter what order updates arrive in, or how many times a given state gets merged, every replica converges to the identical final state. This is a genuinely different consistency mechanism than quorum-based consensus (Design a Leader Election Algorithm) — no leader, no voting, just a mathematically-guaranteed convergence property built into the data structure itself.

G-Counter: the simplest CRDT

class GCounter {
    Map<String, Long> perNodeCounts = new HashMap<>(); // nodeId -> that node's own increment count

    void increment(String nodeId) {
        perNodeCounts.merge(nodeId, 1L, Long::sum); // each node only ever increments ITS OWN entry
    }

    long value() {
        return perNodeCounts.values().stream().mapToLong(Long::longValue).sum(); // total = sum across all nodes
    }

    void mergeFrom(GCounter other) {
        for (var entry : other.perNodeCounts.entrySet()) {
            perNodeCounts.merge(entry.getKey(), entry.getValue(), Math::max); // merge = take the MAX per node
        }
    }
}

Each node ONLY ever increments its OWN entry in the map (never another node's) — this is the key design constraint that makes the merge trivially safe: merging is just taking the max of each node's independently-reported count, which is commutative, associative, and idempotent essentially by definition of max. The overall counter VALUE is the sum across all nodes' individual counts — a node increments locally with zero coordination, and the total eventually reflects everyone's increments once merges propagate.

Vector clocks: tracking causality without trusting wall-clock time

class VectorClock {
    Map<String, Long> clock = new HashMap<>(); // one logical counter per node

    boolean happenedBefore(VectorClock other) {
        // this happened-before other if EVERY entry in this is <= the corresponding entry in other,
        // and at least one is strictly less
    }
}

Wall-clock timestamps across different machines can't be trusted for ordering events (clock skew, network delay mean "timestamp A < timestamp B" doesn't reliably mean A actually happened first) — a vector clock instead tracks a per-node logical counter, letting the system determine whether one update definitively HAPPENED-BEFORE another (causally related) or whether they were CONCURRENT (neither caused the other, genuinely independent) — this distinction matters for CRDTs and other eventually-consistent systems specifically to detect genuine conflicts vs simple ordering.

Gossip protocol: how state actually propagates

Rather than every node broadcasting every update to every other node (which doesn't scale), a gossip protocol has each node periodically pick a few RANDOM peers and exchange state with them — over successive rounds, this epidemic-style spread propagates updates to the entire cluster without any central coordinator and without the O(n²) broadcast cost of everyone talking to everyone; it's the standard mechanism underlying how CRDT-based and other eventually-consistent systems actually converge in practice.

The trade-off vs a centralized counter with a distributed lock

Centralized + lock:  simple to reason about, STRONGLY consistent reads always, but
                      every increment serializes through the lock — real contention
                      and availability bottleneck at high write volume
CRDT-based:           no contention on increments, survives node/partition failures
                      gracefully, but reads are only EVENTUALLY consistent (a node's
                      local view can briefly lag the true global total)

This mirrors the eventual-vs-strong-consistency trade-off underlying this entire course (HLD Fundamentals Refresher's CAP discussion) — a CRDT-based counter is the right choice when raw increment throughput matters more than instantaneous read accuracy (a "like count" or view-count, per the connection to earlier HLD systems); a centralized, lock-guarded counter is right when every read must reflect every prior write immediately (an inventory count in E-Commerce Checkout & Inventory, where the strong-consistency requirement is non-negotiable).

Follow-up questions this topic invites — and their answers

Q: Can a G-Counter support decrements, for something like a 'net score' that goes up and down? A: Not directly — a G-Counter is grow-only by design (the merge operation relies on values only ever increasing); a PN-Counter (Positive-Negative Counter) extends the idea with TWO G-Counters internally (one tracking increments, one tracking decrements), with the value being their difference, while preserving the same CRDT merge guarantees.

Q: How would you decide the gossip round frequency? A: A trade-off between convergence speed (more frequent gossip converges faster) and network overhead (more frequent gossip means more constant background traffic) — similar in shape to the heartbeat-frequency trade-off in Design a Leader Election Algorithm, tuned against how quickly the application actually needs updates to propagate.

Q: Is a vector clock's size a scaling concern? A: Yes — a vector clock grows with the number of distinct nodes that have ever contributed an update, which can become large in a big, churning cluster; some systems use PRUNING strategies (dropping entries for nodes that have been inactive/removed for a long time) to bound this growth, accepting a small loss of precision for older history.

Q: How does this connect to view-count problems from earlier HLD systems in this course? A: Directly — a video's view count (Video Streaming Platform) or a social post's like count is exactly the use case where CRDT-based eventual consistency is the right trade-off: massive write volume (every view/like is an increment), no real harm in a brief display lag, and strong consistency would add unnecessary contention for a number that's inherently approximate to the end user anyway.