Bird
Raised Fist0

Design a Distributed Counter - Sharded Counters, CRDT for Eventual Consistency

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Distributed Counter - Sharded Counters, CRDT for Eventual Consistency
Scalable, fault-tolerant distributed counters using sharding and CRDTs for eventual consistency
hardInfrastructure and Platform SystemsFreq: medium
Prerequisites:System Design FundamentalsCAP TheoremDistributed Systems BasicsCRDT Concepts
⚙️
Functional Requirements
  • Support increment and decrement operations on counters distributed across multiple shards.
  • Provide eventual consistency guarantees using CRDTs to merge concurrent updates without conflicts.
  • Allow querying the current approximate value of the counter with low latency.
  • Support high write throughput (millions of increments per second) with horizontal scalability.
  • Enable fault tolerance and availability during node failures or network partitions.
  • Support configurable retention and TTL for counters to manage storage.
📊
Non-Functional Requirements
  • System must handle up to 2 billion daily active users generating counter updates.
  • Write availability SLA of 99.99% with eventual consistency within seconds.
  • Read latency P99 under 100ms for counter queries.
  • System must sustain peak write QPS of at least 1 million increments per second.
  • Data durability with replication factor of 3 across data centers.
❓
Clarifying Questions to Ask
  • What is the expected read-to-write ratio for the counters?
  • Are counters global or scoped to entities like users, sessions, or features?
  • What is the acceptable staleness window for eventual consistency?
  • Should the system support decrement operations or only increments?
  • Is there a maximum counter value or overflow behavior to consider?
  • What is the retention period for counter data and archival requirements?
Out of Scope
✗ Strong consistency or linearizability guarantees for counters.
✗ Complex transactional operations involving counters and other entities.
✗ Real-time analytics or aggregation beyond simple counter values.
✗ User authentication and authorization mechanisms.
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 counter update messages per day on average
  • Each counter update message is approximately 100 bytes
  • Retention period of 30 days for counter data
  • Replication factor of 3 for durability
⚡
QPS Calculation
write qps2,000,000,000 × 40 / 86,400 ≈ 925,926 writes/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2,777,778 writes/sec
read qpsAssuming read-to-write ratio 1:5, read_qps = 925,926 / 5 ≈ 185,185 reads/sec
💾
Storage Estimate
daily storage925,926 writes/sec × 100 bytes × 86,400 sec ≈ 8 TB/day
retention storage8 TB/day × 30 days = 240 TB
with replication240 TB × 3 (replication factor) = 720 TB total storage
🖥️
Server Estimate
write shard serversAssuming each server handles 10,000 writes/sec, need 2,778,000 / 10,000 = 278 servers
read cache serversAssuming Redis nodes handle 20,000 reads/sec, need 185,185 / 20,000 ≈ 10 servers
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          | Client/Producer|
          +--------+-------+
                   |
                   v
          +--------+--------+
          |  API Gateway    |
          +--------+--------+
                   |
                   v
          +--------+--------+
          |  Write Router   |
          +--------+--------+
           /        |        \
          v         v         v
 +---------+  +---------+  +---------+
 |Shard 1  |  |Shard 2  |  |Shard N  |
 |CRDT DB  |  |CRDT DB  |  |CRDT DB  |
 +----+----+  +----+----+  +----+----+
      |            |            |
      +------------+------------+
                   |
                   v
          +--------+--------+
          |  Aggregator    |
          +--------+--------+
                   |
                   v
          +--------+--------+
          |  Read Cache    |
          +----------------+
🧩
Components
API Gateway
Receives client requests and performs authentication, rate limiting, and routing.
Why thisEnvoy proxy provides high-performance L7 routing with built-in observability and TLS termination.
Why notNginx lacks native distributed tracing and dynamic configuration needed at this scale.
Write Router
Routes counter update requests to appropriate shard based on consistent hashing of counter ID.
Why thisConsistent hashing with Ketama algorithm minimizes shard remapping on node changes, ensuring even load distribution.
Why notStatic modulo-based sharding causes massive data reshuffling when shards scale up or down.
Shard CRDT Databases
Stores partial counter states as PN-Counters (Positive-Negative Counters) CRDTs for each shard.
Why thisApache Cassandra supports wide-column storage with tunable consistency and linear scalability for high write throughput.
Why notPostgreSQL requires manual sharding and does not scale linearly at 2.7M writes/sec; B-tree writes become bottleneck.
Aggregator Service
Periodically merges shard CRDT states to compute global counter values for queries.
Why thisCustom microservice using Akka Streams enables efficient CRDT merges with backpressure and fault tolerance.
Why notBatch MapReduce jobs introduce unacceptable latency and do not support near real-time reads.
Read Cache
Caches aggregated counter values to serve low-latency read queries.
Why thisRedis Cluster provides sub-millisecond read latency with TTL support and automatic failover.
Why notMemcached lacks persistence and cluster management, risking data loss and manual scaling.
🔄
Data Flow
1
Client → API Gateway
Send increment/decrement request with counter ID and delta
API Gateway authenticates and rate limits requests
2
API Gateway → Write Router
Forward validated request
Write Router uses consistent hashing on counter ID to select shard
3
Write Router → Shard CRDT DB
Apply delta update to PN-Counter CRDT in selected shard
Writes are idempotent and commutative for eventual consistency
4
Shard CRDT DB → Aggregator Service
Periodically stream partial CRDT states
Aggregator merges shard states to compute global counter
5
Aggregator Service → Read Cache
Update aggregated counter values
Read Cache serves low-latency queries with TTL-based freshness
6
Client → Read Cache
Query current counter value
Read Cache returns approximate global counter value with low latency

Practice

(1/5)
1. A web API receives sudden bursts of 10,000 requests per second but must process them at a steady rate of 1,000 requests per second to avoid backend overload. Which component best smooths this traffic to a steady rate without dropping requests?
easy
A. A leaky bucket queue that drains requests at a fixed rate
B. A token bucket that allows bursts up to a maximum token count
C. A fixed-size thread pool that rejects excess requests immediately
D. A simple FIFO queue without rate limiting

Solution

  1. Step 1: Identify smoothing mechanism

    The leaky bucket algorithm enforces a fixed output rate by draining requests steadily, smoothing bursts.

  2. Step 2: Eliminate alternatives

    A fixed-size thread pool that rejects excess requests immediately rejects excess requests immediately, not smoothing them. A token bucket that allows bursts up to a maximum token count (token bucket) allows bursts, not smoothing to steady rate. A simple FIFO queue without rate limiting has no rate control, so bursts pass through.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Leaky bucket drains at fixed rate, smoothing bursts [check]
Hint: Leaky bucket smooths bursts by fixed-rate draining [check]
Common Mistakes:
2. If the reverse proxy responsible for SSL termination crashes, what exactly breaks in the request flow?
medium
A. Clients can still connect directly to backend servers without interruption
B. Clients' SSL handshakes fail, so connections never reach backend servers
C. Backend servers receive unencrypted traffic, exposing internal data
D. The reverse proxy forwards requests without decrypting, causing backend errors

Solution

  1. Step 1: Understand reverse proxy SSL termination failure

    If the reverse proxy crashes, SSL termination stops, so backend servers receive unencrypted traffic if clients connect directly or fallback occurs.

  2. Step 2: Eliminate other options

    Clients cannot connect directly if proxy is mandatory; SSL handshake fails only if proxy blocks connection; proxy can't forward encrypted requests without decrypting if crashed.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Reverse proxy crash exposes backend to unencrypted traffic [check]
Hint: Reverse proxy crash exposes backend to unencrypted traffic [check]
Common Mistakes:
3. For a system requiring globally unique IDs with high throughput and low latency, which approach is best considering the trade-offs of coordination overhead and ID ordering?
medium
A. Use a distributed consensus protocol (e.g., Paxos) to assign IDs synchronously
B. Use a database auto-increment primary key with sharding
C. Use a centralized Ticket Server allocating ID blocks to clients for local use
D. Use client-generated UUIDs combined with a timestamp prefix

Solution

  1. Step 1: Evaluate coordination overhead

    Consensus (A) ensures strong consistency but adds latency and limits throughput; DB auto-increment with sharding (D) risks collisions and complex coordination.

  2. Step 2: Assess ordering and uniqueness

    UUIDs (C) are unique but unordered and can cause issues in ordered systems; Ticket Server (B) balances uniqueness, ordering, and throughput by allocating ID blocks.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Ticket Server -> high throughput, low latency, ordered IDs [check]
Hint: Centralized block allocation beats consensus and UUIDs for throughput [check]
Common Mistakes:
4. At 10x scale, which component in a strongly consistent distributed database is most likely to fail first, and why?
hard
A. The storage engine, because disk I/O cannot keep up with the increased write volume
B. The network switches, because increased traffic causes packet loss and retransmissions
C. The client SDK, because it cannot handle the increased number of concurrent connections
D. The consensus leader node, because it becomes a bottleneck handling all write coordination and replication

Solution

  1. Step 1: Identify bottleneck in strong consistency

    The consensus leader node handles all write coordination and replication, becoming a bottleneck as scale increases.

  2. Step 2: Eliminate other options

    Network switches are scalable with proper design; client SDKs scale horizontally; storage engines can be sharded or scaled independently.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Consensus leader node bottlenecks write coordination at scale [check]
Hint: Consensus leader bottlenecks writes at scale [check]
Common Mistakes:
5. At 10x scale, which component in the News Feed system is most likely to fail first and why?
hard
A. The database, because it cannot handle the increased write volume for posts
B. The Delivery Workers, because they cannot process the exponentially larger fan-out queues fast enough
C. The cache layer, because cache invalidation traffic grows superlinearly with user count
D. The fan-out message queue (Kafka), because partition count limits prevent scaling beyond a threshold

Solution

  1. Step 1: Analyze bottlenecks at 10x scale

    Database (A) can be sharded; cache (C) scales horizontally; Kafka (D) can add partitions but has limits.

  2. Step 2: Delivery Workers face exponential fan-out growth

    Fan-out queues grow with followers; Delivery Workers must push updates to millions more followers, causing processing lag and backlog.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Delivery Workers bottleneck due to fan-out processing load [check]
Hint: Delivery Workers bottleneck on fan-out processing at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard