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
45 min · senior
senior

You are building a distributed counter system for a 50M DAU startup that tracks user interactions (likes, views, etc.) globally. The system must handle high write throughput, provide eventual consistency with conflict-free replicated data types (CRDTs), and support sharded counters to avoid write hotspots. Counters must be encrypted at rest and in transit. The system should provide P99 read latency under 200ms and tolerate network partitions gracefully.

Constraints
  • Encryption at rest and in transit is mandatory due to privacy regulations.
  • System must handle 50M DAU generating up to 10K increments per second globally.
  • P99 read latency must be under 200ms for counter queries.
  • Counters must be eventually consistent using CRDTs to allow offline increments and conflict-free merges.
  • Sharded counters must avoid write hotspots and scale linearly with traffic.
📋
Guided Steps
1/5
Step 1
Choosing the Data Model and CRDT Type
Which CRDT type and data model will you use to represent distributed counters that support increments and merges without conflicts?
💡 Hint
Consider CRDTs that support commutative increments and merges like G-Counters or PN-Counters.
Key Decision
Use G-Counters (Grow-only Counters) CRDT implemented as a vector of shard counts, enabling commutative increments and conflict-free merges.
Interviewer Expectation
Mid-level: Names G-Counters as CRDT type. Senior: Explains why G-Counters fit increment-only counters and how vector shards enable conflict-free merges without coordination.
⚠️Common Wrong Answer
Using a centralized counter or a strongly consistent database counter, which creates write hotspots and blocks availability under partitions.
Step 2
Sharding Strategy to Avoid Write Hotspots
How will you shard counters to distribute write load and scale linearly with traffic?
💡 Hint
Think about partitioning counters by user ID or counter ID and using consistent hashing or fixed shards.
Key Decision
Shard counters by fixed number of shards per counter ID, each shard stored as a separate key in Cassandra with partition key = (counter_id, shard_id) for linear write scaling.
Interviewer Expectation
Mid-level: Suggests sharding by counter ID. Senior: Explains fixed shard count per counter to bound read complexity and why Cassandra partition key design avoids hotspots and enables efficient range queries.
⚠️Common Wrong Answer
Using a single key per counter in a database like Redis, causing write hotspots and throttling at high QPS.
Step 3
Data Storage and Encryption
Which storage technology will you use to store shards and how will you ensure encryption at rest and in transit?
💡 Hint
Consider a distributed wide-column store with native encryption support and TLS for network security.
Key Decision
Use Apache Cassandra with client-side encryption enabled and TLS for in-transit encryption, leveraging Cassandra’s LSM-tree writes for high throughput and linear scalability.
Interviewer Expectation
Mid-level: Names Cassandra for storage. Senior: Details Cassandra’s encryption options, LSM-tree write amplification benefits, and why alternatives like MongoDB or Redis fail at this scale due to single-node bottlenecks or lack of native encryption.
⚠️Common Wrong Answer
Using Redis without encryption or a relational DB that cannot handle 10K writes/sec per counter shard.
Step 4
Read Path and Latency Optimization
How will you design the read path to achieve P99 latency under 200ms for counter queries?
💡 Hint
Consider caching layers and read aggregation strategies to minimize database calls and network hops.
Key Decision
Use Redis as a read-through cache for aggregated counter values with TTL-based invalidation and background aggregation workers updating cache asynchronously.
Interviewer Expectation
Mid-level: Mentions caching with Redis. Senior: Explains cache invalidation strategy, eventual consistency trade-offs, and how background aggregation merges shards to reduce read latency.
⚠️Common Wrong Answer
Reading directly from Cassandra on every request, causing high read latency and increased load.
Step 5
Handling Offline Increments and Conflict Resolution
How will clients sync offline increments and how does the system resolve conflicts?
💡 Hint
Think about CRDT merge semantics and client-side vector shard updates.
Key Decision
Clients maintain local shard counters and sync increments by sending shard deltas to the server, which merges them using G-Counter CRDT merge rules ensuring conflict-free eventual consistency.
Interviewer Expectation
Mid-level: Describes offline increments buffered client-side. Senior: Explains vector shard delta merges, idempotency, and how CRDT guarantees no lost increments despite concurrent updates or network partitions.
⚠️Common Wrong Answer
Using last-write-wins or centralized locking, causing lost increments or blocking availability.
🔌
API Design Challenge
Sketch 3 core API endpoints for the distributed counter system that support incrementing counters, reading current counts, and syncing offline increments.
Hints
  • How does the client send increments to avoid hotspots and enable offline usage?
  • How does the client read the current counter value with low latency?
  • How does the client sync offline increments and resolve conflicts?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of CRDT (G-Counters) for conflict-free increments and merges.
  • Sharding counters to avoid write hotspots and scale linearly.
  • Use of Cassandra with encryption for scalable, durable storage.
  • Read caching layer (Redis) to meet P99 latency SLA.
Good to Have - 30%
  • Client-side offline increment buffering and delta sync.
  • Background aggregation workers for cache updates.
  • Detailed encryption strategy covering at rest and in transit.
Bonus - 10%
  • Discussion of failure modes and recovery for shard merges.
  • Consideration of shard count tuning based on traffic patterns.
Anti-patterns to Avoid
Single key per counter in a database causing write hotspots and throttling under high QPS, leading to system bottlenecks and degraded performance.
Strongly consistent counters using distributed locks causing high latency and availability loss during network partitions, reducing system reliability.
Using last-write-wins conflict resolution leading to lost increments and inaccurate counts, compromising data correctness.
Polling-based client sync causing excessive load and poor offline support, resulting in scalability issues and bad user experience.
Storing counters in relational databases without horizontal scaling causing bottlenecks and inability to handle high write throughput.
Ignoring encryption at rest and in transit exposing sensitive user data to potential breaches and violating privacy regulations.
✅
Model Answer
▼ Reveal

The system uses G-Counters CRDTs with vector shards to enable conflict-free increments and merges. Counters are sharded by fixed shard counts per counter ID and stored in Apache Cassandra with encryption at rest and TLS in transit. Redis serves as a read-through cache to meet P99 latency under 200ms. Clients maintain local shard counters for offline increments and sync deltas to the server, which merges them using CRDT rules. Background workers aggregate shard counts and update Redis asynchronously. The design avoids hotspots, scales linearly, and ensures security compliance.

Key Decisions
  • Use G-Counters CRDT implemented as vector shards for conflict-free increments and merges
  • Shard counters by fixed shard count per counter ID stored as separate keys in Cassandra
  • Choose Apache Cassandra for storage due to LSM-tree write optimization and native encryption support
  • Use Redis as a read-through cache to meet P99 read latency SLA
  • Implement client-side offline increment buffering and delta sync to support offline usage
  • Enforce TLS for all network communication and enable client-side encryption for data at rest
  • Design background aggregation workers to merge shards and update cache asynchronously
  • G-Counters CRDT with vector shards to enable commutative, conflict-free increments and merges.
  • Fixed shard count per counter ID stored as separate keys in Apache Cassandra for linear write scalability.
  • Apache Cassandra chosen for LSM-tree write optimization, native encryption at rest, and TLS for in-transit encryption.
  • Redis as a read-through cache to aggregate shards and serve low-latency reads under 200ms P99.
  • Client-side local shard counters enabling offline increments and sync via shard delta merges.
  • Background aggregation workers to merge shard counts periodically and update Redis cache asynchronously.
  • TLS encryption enforced for all client-server and inter-node communication to meet security constraints.
  • Partition key design in Cassandra as (counter_id, shard_id) to avoid hotspots and enable efficient range scans.

Practice

(1/5)
1. A messaging platform must handle 1 million messages per second with guaranteed ordering per conversation and durability. Which component best decouples message ingestion from fan-out delivery while preserving ordering?
easy
A. Use a Kafka topic partitioned by conversation ID
B. Use a relational database with row-level locks for ordering
C. Use a Redis pub/sub channel for message delivery
D. Use a simple in-memory queue per chat server

Solution

  1. Step 1: Identify Kafka's role in decoupling ingestion and delivery

    Kafka partitions by conversation ID ensure ordering per conversation and durability via replication.

  2. Step 2: Eliminate other options

    Redis pub/sub lacks durability and ordering guarantees; relational DBs can't handle 1M writes/sec with locking overhead; in-memory queues lack durability and don't scale across servers.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Kafka with conversation_id partition -> ordering within conversation guaranteed [check]
Hint: Kafka partitions preserve ordering and durability [check]
Common Mistakes:
2. In a system design interview, at step 4, you explain your choice of caching layer to reduce latency. What happens at this step when the cache misses the requested data?
easy
A. The cache silently returns stale data without fetching fresh data
B. The cache duplicates the request to multiple backends simultaneously
C. The cache returns an error immediately to the client without fallback
D. The cache triggers a backend fetch and updates itself before returning data

Solution

  1. Step 1: Trace cache behavior on miss at step 4

    On a cache miss, the cache should fetch fresh data from the backend to serve the request.

  2. Step 2: Confirm cache updates itself before responding

    This ensures subsequent requests hit the cache, reducing latency and load on backend.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Cache miss triggers backend fetch and cache update [check]
Hint: Cache miss triggers backend fetch and update [check]
Common Mistakes:
3. In a token bucket rate limiter, at step 4 the Request Handler checks the token count before processing a request. What happens if the bucket is empty at this step?
easy
A. The token count is reset to maximum and the request proceeds
B. The request is immediately processed and the token count goes negative
C. The request is rejected or delayed until tokens are refilled
D. The request is queued indefinitely without token consumption

Solution

  1. Step 1: Trace Request Handler token check at Step 4

    If the token bucket is empty, no tokens are available to allow immediate processing.

  2. Step 2: Determine request fate

    The request must be rejected or delayed until tokens refill; processing without tokens violates rate limits.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Empty bucket -> reject or delay request [check]
Hint: No tokens? Delay or reject request [OK]
Common Mistakes:
4. If the message queue (Kafka) is unavailable during the flash sale, what exactly breaks in the order processing pipeline?
medium
A. Payment service retries indefinitely, causing duplicate charges
B. Order requests block at the API layer, causing client timeouts and lost orders
C. Orders are accepted but payment processing is delayed indefinitely
D. Orders are accepted but inventory updates are lost, causing overselling

Solution

  1. Step 1: Trace Kafka's role in order processing

    Kafka decouples order acceptance from inventory update; if Kafka is down, inventory update messages are lost or not sent.

  2. Step 2: Analyze failure impact

    API layer (B) uses async calls, so requests don't block. Payment retries (D) are independent. Accepting orders without inventory update (C) causes overselling.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Kafka down -> inventory updates lost -> overselling risk [check]
Hint: Kafka outage loses inventory updates causing overselling [check]
Common Mistakes:
5. At 10x traffic scale during a flash sale, which component is most likely to fail first and why?
hard
A. The relational database because it cannot handle 10x write throughput without sharding
B. The API Gateway because it maintains stateful user sessions and cannot horizontally scale easily
C. The cache layer because TTL expiration floods the database with cache misses
D. The inventory service because distributed locking causes contention and latency spikes

Solution

  1. Step 1: Identify stateful components under load

    API Gateway maintains user session state (e.g., WebSocket connections), which are sticky and stateful, limiting horizontal scaling.

  2. Step 2: Compare other components

    Relational DB (A) can be sharded; cache (C) TTL floods are mitigated by pre-warming; inventory locking (D) is optimized with partitioning. API Gateway statefulness causes connection limits and bottlenecks first.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    API Gateway stateful sessions limit horizontal scaling [check]
Hint: Stateful API Gateway limits scaling under 10x load [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