Bird
Raised Fist0

HyperLogLog for Cardinality Estimation - Counting Unique Users Cheaply

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
HyperLogLog for Cardinality Estimation - Counting Unique Users Cheaply
Efficiently estimate unique user counts at massive scale using HyperLogLog probabilistic data structure
mediumBloom Filters and Probabilistic Data StructuresFreq: medium
Prerequisites:HashingProbabilistic Data Structures
⚙️
Functional Requirements
  • Ingest user activity events and update unique user counts per time window (e.g., daily, hourly).
  • Provide approximate unique user count queries with configurable accuracy and latency.
  • Support multiple aggregation dimensions (e.g., by region, platform).
  • Allow retention of historical cardinality estimates for at least 30 days.
  • Support incremental updates without full recomputation.
  • Expose APIs for real-time and batch query access.
📊
Non-Functional Requirements
  • Handle 2 billion daily active users (DAU) generating ~40 events per user per day.
  • Provide 99.99% availability for cardinality query APIs.
  • Ensure query P99 latency under 100ms for cardinality requests.
  • Store cardinality data with less than 1TB storage per day after compression and replication.
  • Support write throughput of approximately 925K events per second at peak.
❓
Clarifying Questions to Ask
  • What is the acceptable error rate or accuracy target for cardinality estimates?
  • What are the primary aggregation dimensions (e.g., time windows, regions)?
  • Is the system expected to support real-time updates or batch processing?
  • What is the retention period for historical cardinality data?
  • Are there any constraints on storage cost or infrastructure budget?
  • What is the expected query load and SLA for cardinality queries?
Out of Scope
✗ Exact unique user counts (system provides approximate counts only).
✗ User-level data storage or retrieval (only aggregate cardinalities).
✗ Complex user profile or attribute storage.
✗ Real-time streaming analytics beyond cardinality estimation.
📌
Assumptions
  • 2 billion DAU generating 40 events per user per day.
  • Average event size is 100 bytes.
  • Retention period of 30 days for cardinality data.
  • Replication factor of 3 for durability.
⚡
QPS Calculation
write qps2B users × 40 events/day ÷ 86400 seconds ≈ 925,926 events/sec
peak write qpsAssuming 2× peak factor: 925,926 × 2 ≈ 1.85M events/sec
read qpsAssuming 1M cardinality queries/day: 1M ÷ 86400 ≈ 11.6 queries/sec
💾
Storage Estimate
daily raw event storage2B × 40 × 100 bytes = 8 TB/day
HLL per counter size12 KB per HyperLogLog sketch (standard precision p=14)
number of countersAssuming 1000 aggregation keys (regions/platforms/time buckets)
daily HLL storage1000 × 12 KB = 12 MB/day
retention storage12 MB × 30 days = 360 MB
with replication360 MB × 3 = 1.08 GB total storage for HLL data
🖥️
Server Estimate
ingestion serversAssuming each server handles 50K events/sec, need 1.85M ÷ 50K = 37 servers
query serversAssuming each server handles 1000 queries/sec, need 12 servers
🏗️
Architecture Diagram
Architecture Diagram
           +----------------+
           | User Activity  |
           | Event Sources  |
           +-------+--------+
                   |
                   v
           +----------------+
           | Kafka Cluster  |
           | (Event Buffer) |
           +-------+--------+
                   |
                   v
           +----------------+
           | Stream Process |
           | (Apache Flink) |
           +-------+--------+
                   |
                   v
           +----------------+
           | HyperLogLog    |
           | Aggregation DB |
           | (Redis HLL or  |
           |  RocksDB + HLL)|
           +-------+--------+
                   |
                   v
           +----------------+
           | Query API Srv  |
           +----------------+
🧩
Components
Kafka Cluster
Durable event buffer to decouple ingestion from processing
Why thisKafka supports high throughput (millions of msgs/sec), partitioning, and retention for replay
Why notRabbitMQ lacks Kafka's horizontal scalability and partitioning at 1.85M msg/sec
Apache Flink Stream Processor
Real-time aggregation of events into HyperLogLog sketches per key
Why thisFlink provides exactly-once semantics and stateful stream processing with low latency
Why notSpark Streaming has higher latency and weaker exactly-once guarantees at this scale
HyperLogLog Aggregation DB
Store and merge HyperLogLog sketches for cardinality estimation
Why thisRedis with native HLL commands supports fast in-memory HLL operations with TTL for retention
Why notCassandra requires complex manual merging logic and higher storage overhead for HLL
Query API Server
Expose cardinality estimates via REST/gRPC APIs with low latency
Why thisStateless API servers can horizontally scale and cache HLL results for sub-100ms P99 latency
Why notDirect DB queries increase latency and reduce throughput under high QPS
User Activity Event Sources
Generate user events for ingestion (mobile apps, web clients)
Why thisEvents are the raw input for cardinality estimation; must be reliable and timestamped
Why notBatch logs lack real-time freshness and increase latency for cardinality updates
🔄
Data Flow
1
User Activity Event Sources → Kafka Cluster
Publish user events with user_id and metadata
Kafka buffers and partitions events for scalable processing
2
Kafka Cluster → Apache Flink Stream Processor
Consume events in real-time, group by aggregation keys
Flink maintains stateful HLL sketches per key
3
Apache Flink Stream Processor → HyperLogLog Aggregation DB
Update HLL sketches incrementally using Redis PFADD or RocksDB merges
Efficiently merges new user hashes into existing sketches
4
Query API Server → HyperLogLog Aggregation DB
Fetch HLL sketches and compute cardinality estimates
API server merges sketches if needed and returns approximate counts
5
Query API Server → Client
Return cardinality estimate with error bounds
Clients receive fast approximate unique user counts

Practice

(1/5)
1. A distributed system requires a component to ensure a single value is agreed upon by a majority of nodes despite failures. Which component best handles this consensus requirement?
easy
A. A consensus algorithm like Paxos or Raft to coordinate agreement
B. A distributed cache like Redis to store the agreed value
C. A load balancer to distribute requests evenly among nodes
D. A message queue like Kafka to buffer messages before processing

Solution

  1. Step 1: Identify the role of consensus algorithms

    Consensus algorithms like Paxos and Raft are designed to ensure agreement on a single value among distributed nodes despite failures.

  2. Step 2: Eliminate other options

    Redis is a cache and does not guarantee consensus; load balancers distribute load but do not coordinate agreement; Kafka buffers messages but does not ensure single-value agreement.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Consensus algorithms guarantee majority agreement despite failures [check]
Hint: Consensus algorithms ensure majority agreement despite failures [check]
Common Mistakes:
2. In the Redlock algorithm request flow, at Step 4 the client attempts to acquire locks on all Redis masters. What happens if the client successfully acquires locks on only 3 out of 5 masters within the timeout?
easy
A. The client proceeds with the lock assuming majority success
B. The client releases any acquired locks and retries later
C. The client holds partial locks and waits for the rest to acquire
D. The client escalates to a centralized lock coordinator

Solution

  1. Step 1: Trace client lock acquisition at Step 4

    Redlock requires majority of Redis masters to be locked within timeout to consider lock acquired.

  2. Step 2: Handle partial lock acquisition

    If fewer than majority locks acquired, client must release any partial locks to avoid deadlocks and retry.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Partial lock acquisition -> release all and retry [check]
Hint: Partial locks -> release all, no partial ownership [check]
Common Mistakes:
3. If Kafka is unavailable, what exactly breaks in the tweet delivery pipeline?
medium
A. Tweets are stored in the DB but timeline caches become permanently stale
B. Tweets are lost immediately with no retry and followers see no updates
C. Tweet ingestion blocks; fan-out delivery waits synchronously causing user write latency spikes
D. Delivery workers switch to synchronous RPC calls causing partial delivery and blocking

Solution

  1. Step 1: Role of Kafka in delivery pipeline

    Kafka buffers tweets asynchronously for fan-out; unavailability stops new fan-out events.

  2. Step 2: Trace failure impact

    Tweets still persist in DB, but without Kafka, timeline caches don't get updated, causing stale timelines.

  3. Step 3: Eliminate other options

    Immediate loss (A) is prevented by DB persistence; ingestion blocking (B) unlikely as writes decouple; synchronous RPC fallback (D) not implemented.

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Kafka outage stalls fan-out, causing stale timeline caches [check]
Hint: Kafka outage stalls fan-out, stale timelines appear [check]
Common Mistakes:
4. For a faceted search system with frequent filter updates and millions of documents, which architecture better balances update latency and query freshness?
medium
A. Use a near-real-time indexing system that streams document changes to shards asynchronously
B. Use a batch indexing pipeline that rebuilds the entire inverted index every hour
C. Use a write-through cache that updates inverted indexes synchronously on every document change
D. Use a static precomputed index refreshed monthly with manual invalidation

Solution

  1. Step 1: Compare update latency and query freshness trade-offs

    Batch rebuilds have high latency; synchronous writes hurt write throughput; static monthly refresh is too stale.

  2. Step 2: Identify near-real-time indexing benefits

    Streaming updates asynchronously balances freshness and throughput, allowing queries to see recent changes with low delay.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Near-real-time streaming -> balanced freshness and update latency [check]
Hint: Near-real-time streaming balances freshness and throughput [check]
Common Mistakes:
5. Without the DAU Estimator component, what exactly breaks in the system's capacity planning process?
medium
A. Bandwidth estimation fails because DAU directly affects total data transfer calculations
B. The system cannot estimate peak QPS, causing under-provisioning of servers
C. Storage estimation becomes inaccurate because DAU is a key multiplier for daily data volume
D. User authentication fails because DAU tracks active sessions

Solution

  1. Step 1: Identify DAU Estimator role

    DAU Estimator provides daily active user count critical for bandwidth calculations as bandwidth depends on total active users.

  2. Step 2: Eliminate other options

    The system cannot estimate peak QPS, causing under-provisioning of servers is incorrect because peak QPS depends on instantaneous requests, not just DAU; Storage estimation becomes inaccurate because DAU is a key multiplier for daily data volume is partially true but storage depends more on total objects, not DAU alone; User authentication fails because DAU tracks active sessions is unrelated to authentication.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Bandwidth depends directly on DAU for total data transfer [check]
Hint: Bandwidth depends directly on DAU count [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