Bird
Raised Fist0

HyperLogLog for Cardinality Estimation - Counting Unique Users Cheaply

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
▶
Request Trace
Step 1/5
User Activity Event Sources

Generate user activity event

User performs an action triggering an event sent to Kafka

Protocol:Kafka Producer API
BeforeUser activity event exists only on client device
AfterEvent is sent to Kafka Cluster and durably stored
Kafka Cluster

Store and buffer event

Event is appended to Kafka topic partition for processing

Protocol:Kafka internal storage
BeforeEvent just received from producer
AfterEvent durably stored and available for consumers
Apache Flink Stream Processor

Consume event and update HyperLogLog sketch

Processes event stream, updates cardinality sketch for user set

Protocol:Kafka Consumer API
BeforeEvent available in Kafka topic partition
AfterHyperLogLog sketch updated in memory for current window
Apache Flink Stream Processor

Persist updated sketch to aggregation DB

Writes compressed HyperLogLog sketch to aggregation database

Protocol:Batch write/update API
BeforeSketch updated in Flink memory but not persisted
AfterSketch persisted in HyperLogLog Aggregation DB
Query API Server

Receive cardinality query and fetch sketch

Client requests unique user count; server queries aggregation DB

Protocol:REST API
BeforeQuery API Server idle, aggregation DB holds latest sketches
AfterServer returns estimated unique user count to client
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────────────┐
│ User Activity Event Sources    │
│ (mobile apps, web clients)    │
└───────────────┬───────────────┘
                │ Kafka Producer API
                ▼
┌───────────────────────────────┐
│ Kafka Cluster                  │
│ (durable event queue)          │
└───────────────┬───────────────┘
                │ Kafka Consumer API
                ▼
┌───────────────────────────────┐
│ Apache Flink Stream Processor  │
│ (real-time event processing,   │
│  HyperLogLog aggregation)      │
└───────────────┬───────────────┘
                │ Batch write/update
                ▼
┌───────────────────────────────┐
│ HyperLogLog Aggregation DB     │
│ (stores compressed cardinality│
│  sketches per time window)     │
└───────────────┬───────────────┘
                │ Query via REST API
                ▼
┌───────────────────────────────┐
│ Query API Server               │
│ (serves cardinality estimates │
│  to clients)                  │
└───────────────────────────────┘

This architecture ingests user activity events from external sources into a Kafka Cluster, which acts as a durable, partitioned event queue. Apache Flink consumes these events in real time, updating HyperLogLog sketches that probabilistically estimate unique user counts. These sketches are periodically persisted to the HyperLogLog Aggregation DB, which stores compressed cardinality data efficiently. When clients query the system, the Query API Server fetches the latest sketches and returns cardinality estimates. This design balances high-throughput event ingestion with low-memory, approximate counting, enabling cheap and scalable unique user estimation.

Primary Focus

✓

Practice

(1/5)
1. A large-scale messaging platform needs to isolate failures to prevent cascading outages during regional network partitions. Which architectural component best limits the blast radius by decoupling service dependencies?
easy
A. Use synchronous REST calls between microservices with retries
B. Use direct TCP socket connections between services for low latency
C. Implement asynchronous message queues with backpressure and dead-letter queues
D. Rely on a single monolithic database to coordinate all service state

Solution

  1. Step 1: Identify failure isolation mechanism

    Asynchronous message queues decouple services, buffering requests and preventing direct cascading failures during outages.
  2. Step 2: Evaluate alternatives

    Synchronous REST calls (A) cause blocking and cascading failures; monolithic DB (C) is a single point of failure; direct TCP (D) lacks buffering and backpressure.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Async queues buffer and isolate failures, limiting blast radius [check]
Hint: Async queues buffer failures, blocking calls cascade [check]
Common Mistakes:
2. In a Cache Aside pattern, at step 3 the application checks the cache and finds a miss. What happens next at step 4?
easy
A. The application queries the database, then updates the cache with the retrieved data
B. The cache automatically loads data from the database without application intervention
C. The application returns a null response to the user and retries later
D. The cache triggers a background refresh asynchronously and returns stale data

Solution

  1. Step 1: Understand Cache Aside flow

    On cache miss, application queries DB and updates cache explicitly.
  2. Step 2: Eliminate other options

    Cache Aside does not auto-load cache (A); it does not return null or stale data (C, D).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Application loads DB and updates cache on miss [check]
Hint: Cache Aside: app loads DB and updates cache on miss [check]
Common Mistakes:
3. In the Pastebin system request flow, at Step 4 the Expiration Worker scans stored snippets to remove expired entries. What state does the worker observe for a snippet whose TTL just expired but is still being accessed by a user?
easy
A. The snippet is immediately deleted and inaccessible to the user
B. The snippet remains accessible until the worker completes the deletion batch
C. The snippet is marked as expired but still served until a manual cleanup
D. The snippet is locked and user requests are blocked until deletion finishes

Solution

  1. Step 1: Trace Expiration Worker behavior at Step 4

    The worker deletes expired snippets in batches; deletion is not instantaneous upon TTL expiry.
  2. Step 2: Understand user access during deletion

    Until deletion completes, the snippet remains accessible; no locking or blocking occurs.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Batch deletion delays snippet removal, keeping it accessible briefly [check]
Hint: Expiration deletion is batch-based, not instant [check]
Common Mistakes:
4. A public API receives unpredictable bursts of traffic that can overwhelm backend services. Which component is best suited to protect the system from overload?
easy
A. A distributed cache like Redis to store frequent requests for faster responses
B. A rate limiter that enforces request quotas per client IP or API key
C. A load balancer that evenly distributes requests across servers
D. A message queue to buffer incoming requests before processing

Solution

  1. Step 1: Identify the protection mechanism against traffic bursts

    Distributed cache (A) improves response time but doesn't limit request rate; load balancer (C) distributes load but can't prevent overload from bursts; message queue (D) buffers but can be overwhelmed if bursts are too large.
  2. Step 2: Recognize rate limiter role

    Rate limiter (B) enforces quotas per client, directly preventing backend overload by rejecting or delaying excess requests.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Rate limiter enforces quotas to prevent overload [check]
Hint: Rate limiter controls request bursts to protect backend [check]
Common Mistakes:
5. Without explicitly defining system constraints during your 45-minute design answer, what failure mode is most likely to occur in your final design?
medium
A. The system will automatically scale without bottlenecks
B. Design decisions will conflict, causing unclear trade-offs and incomplete coverage
C. You will produce a perfect design that requires no iteration
D. The system will default to a microservices architecture regardless of needs

Solution

  1. Step 1: Trace impact of missing constraints

    Without constraints, design choices conflict and trade-offs are unclear, leading to incomplete or inconsistent design.
  2. Step 2: Exclude unrealistic outcomes

    Automatic scaling or perfect design without iteration is unrealistic; architecture does not default automatically.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Missing constraints -> conflicting design decisions [check]
Hint: Constraints prevent conflicting designs [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