Distributed Counter — CRDT (Multi-Region Grow-Only Counters)

The CRDT (Conflict-free Replicated Data Type) counter architecture is the production-grade solution for globally distributed counting at extreme scale. It solves two fundamental problems that the sharded counter approach does not address: cross-region write latency and conflict-free convergence without coordination.

The cross-region latency problem is severe. When a video goes viral globally, increment traffic arrives simultaneously from US-East, EU-West, AP-Southeast, and other regions. In the sharded counter approach, all writes must route to the single region hosting the Redis cluster. Users in EU-West experience 80-120ms of additional latency (cross-Atlantic round-trip) just to reach the counter infrastructure. Users in AP-Southeast face 150-250ms. During viral peaks at 20M inc/sec globally, this cross-region traffic creates a bandwidth bottleneck and multiplies the effective write latency by 5-10x compared to local writes.

CRDTs solve this with a mathematically elegant property: the merge operation is commutative, associative, and idempotent. A G-Counter (Grow-only Counter) is a vector of N components, one per region. Each region independently increments its own component. The global count is the sum of all components. The merge operation takes the component-wise maximum: merge(A, B)[i] = max(A[i], B[i]). This guarantees that regardless of the order in which regions exchange state, or how many times the same state is received, the counters converge to the same correct value.

The architecture places a complete counter stack in each region: ApiGateway, LoadBalancer, CounterService, LocalCounterCache (Redis), and DedupCache (HyperLogLog). Local writes complete in ~2ms — the same latency as a single-region sharded counter. The cross-region coordination happens asynchronously via MergeStream (Kafka with cross-region replication). MergeWorker consumes events from all regions, applies the CRDT merge, and writes the globally consistent count to CounterDB.

Per-user deduplication is critical for counters like 'likes' where each user should count at most once per item. The CRDT variant uses HyperLogLog (HLL) — a probabilistic data structure that estimates the cardinality of a set using only ~12KB of memory per counter key, regardless of the number of unique users. CounterService issues PFADD dedup:{key} {user_id} before incrementing. PFADD returns 1 if the user is likely new (with ~2% standard error), 0 if likely already counted. The trade-off is that ~2% of legitimate first-time users are falsely rejected — their increment is silently dropped.

Time-bucketed aggregation adds an analytics dimension. AggregationWorker reads merged counts and computes per-minute, per-hour, and per-day rollups stored in CounterDB. This enables historical queries like 'views per hour for the last 7 days' without scanning billions of raw increment events.

The CRDT counter pattern appears in interviews for global-scale systems — TikTok (videos viewed across continents), YouTube (global view counts), and large-scale IoT platforms (device event counting across edge locations). Interviewers at senior levels expect candidates to articulate why CRDTs are preferable to consensus-based approaches (Paxos, Raft) for counters, explain the G-Counter merge semantics, and reason about the HyperLogLog accuracy trade-off.

The progression from naive (single row) to sharded (single region, distributed writes) to CRDT (multi-region, zero-coordination convergence) demonstrates increasing sophistication in handling the fundamental tension between write throughput, read freshness, global availability, and data consistency.

The CRDT counter system uses 9 components organized into a region-local write path with async cross-region merge. The components are: CounterClient, ApiGateway, MainLB, CounterService, LocalCounterCache (Redis CRDT shards + merged counts), DedupCache (Redis HyperLogLog), MergeStream (Kafka), MergeWorker, AggregationWorker, and CounterDB (PostgreSQL).

The write path is fully region-local. A request enters through the regional ApiGateway (JWT auth, rate limiting at 2.5M RPS), routes to MainLB, and reaches CounterService. CounterService first checks DedupCache via PFADD to determine if this user has already been counted for this key. If the user is new (PFADD returns 1), CounterService INCRs a random sub-counter shard in LocalCounterCache and publishes a counter_increment event to MergeStream (Kafka). The entire write path completes in ~10ms, with no cross-region hop. If the user is a duplicate (PFADD returns 0), the increment is silently dropped and the response returns immediately.

LocalCounterCache serves dual purposes. It stores the region-local sharded sub-counters (counter:{region_id}:{key}:{shard_id}) for incoming writes, and it caches the last known merged global count (counter:{key}:merged) for fast approximate reads. The 16-node Redis cluster handles 2M+ INCR/sec and 1M+ GET/sec for the local region.

DedupCache is a separate Redis cluster dedicated to HyperLogLog structures. Each counter key has one HLL (dedup:{key}) that tracks all user IDs that have incremented this counter. Each HLL uses ~12KB when fully populated (2^14 registers). The 8-node cluster supports 2M+ PFADD/sec. TTL of 24 hours expires HLL state for cold counters, reclaiming memory.

MergeStream (Kafka) carries increment events both within the region (to MergeWorker) and across regions (via MirrorMaker or Kafka cross-region replication). Events are partitioned by counter_key (256 partitions) for parallel processing. The topic schema includes region_id, enabling MergeWorker to maintain the per-region CRDT vector.

MergeWorker is the CRDT convergence engine. It consumes events from MergeStream, maintains the G-Counter vector per key ({region_id: count}), and applies the merge operation (component-wise max). Every 10 seconds, it writes the merged global count and the full CRDT vector to CounterDB, and writes the merged count back to LocalCounterCache for fast approximate reads. With 60 workers processing in parallel, merge completes within seconds of the last region's update.

AggregationWorker computes time-bucketed rollups (per-minute, per-hour, per-day) from the merged counts in CounterDB. These rollups are written to a separate counter_aggregations table optimized for historical range queries. 20 workers handle the aggregation workload with 60-second processing cycles.

CounterDB (PostgreSQL) provides durable storage for two table types: the counters table (merged global counts with full CRDT vectors) and the counter_aggregations table (time-bucketed rollups). It serves exact-count reads for the 10% of traffic that requires global accuracy. 128 partitions with 3 replicas provide throughput and durability.