Bird
Raised Fist0

Count-Min Sketch for Frequency Estimation at Scale

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
🏗️
Count-Min Sketch for Frequency Estimation at Scale
Design a scalable Count-Min Sketch system to estimate item frequencies with bounded error for billions of users
mediumBloom Filters and Probabilistic Data StructuresFreq: medium
Prerequisites:HashingProbabilistic Data StructuresDistributed Systems BasicsStreaming Data Processing
⚙️
Functional Requirements
  • Support approximate frequency estimation of arbitrary items with bounded error using Count-Min Sketch.
  • Ingest high-throughput streaming data (e.g., user events) continuously and update sketches in near real-time.
  • Support queries for frequency estimates with low latency (sub-100ms P99).
  • Provide configurable error bounds (ε, δ) for frequency estimates via sketch parameters.
  • Support time-windowed frequency queries (e.g., last hour, last day) via sketch snapshots or time-buckets.
  • Expose APIs for both batch and streaming ingestion and frequency queries.
📊
Non-Functional Requirements
  • Scale to 2 billion daily active users generating 40 events per user per day (~80B events/day).
  • Handle peak write throughput of ~1.5 million writes per second (peak factor 1.6x).
  • Provide 99.99% availability for ingestion and query APIs.
  • Ensure query latency P99 under 100ms for frequency lookups.
  • Store sketches with retention of 30 days, supporting time-windowed queries.
❓
Clarifying Questions to Ask
  • What is the expected error tolerance (ε, δ) for frequency estimates?
  • Are frequency queries expected to be real-time or batch?
  • What is the maximum item cardinality (number of unique items)?
  • Is the data ingestion ordered or can it be out-of-order?
  • What is the retention period for frequency data and time-window granularity?
  • Are there any SLAs on data freshness or eventual consistency?
Out of Scope
✗ Exact frequency counts without approximation.
✗ Heavy hitter detection or top-k queries (only frequency estimation).
✗ User-level personalization or user-specific sketches.
✗ Complex query patterns beyond frequency estimation (e.g., joins, filters).
📌
Assumptions
  • 2 billion daily active users (DAU).
  • Each user generates 40 events/messages per day on average.
  • Average event size is 100 bytes.
  • Peak write throughput is 1.6x average.
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qps925,926 × 1.6 ≈ 1,481,481 writes/sec
read qpsAssuming 10% of writes generate queries: 925,926 × 0.1 ≈ 92,593 reads/sec
💾
Storage Estimate
daily storage bytes2B × 40 × 100 bytes = 8,000,000,000,000 bytes = 8 TB/day
retention days30
total storage bytes8 TB × 30 = 240 TB
with replication 3x240 TB × 3 = 720 TB
🖥️
Server Estimate
ingestion servers[object Object]
query servers[object Object]
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Event Sources |
          +--------+-------+
                   |
                   v
          +----------------+
          |   Kafka Topic  |
          +--------+-------+
                   |
                   v
          +----------------+
          |  Stream Process|
          | (Flink/Spark)  |
          +--------+-------+
                   |
                   v
          +----------------+
          | Count-Min Sketch|
          |  Updater Store |
          +--------+-------+
                   |
                   v
          +----------------+
          |  Query API Srv |
          +--------+-------+
                   |
                   v
          +----------------+
          |  Client Apps   |
🧩
Components
Kafka Cluster
Durable, scalable ingestion buffer for streaming events
Why thisKafka supports high-throughput partitioned logs with replication and retention, enabling decoupling of ingestion and processing at 1.5M writes/sec peak
Why notRabbitMQ lacks partitioning and throughput at this scale; Kinesis is costly and less flexible for 2B DAU scale
Stream Processing (Apache Flink)
Real-time aggregation and update of Count-Min Sketch data structures from event streams
Why thisFlink provides exactly-once semantics, low latency, and stateful stream processing with native support for windowing and fault tolerance
Why notSpark Streaming has higher latency and weaker exactly-once guarantees; Storm lacks native state management
Count-Min Sketch Updater Store (Redis Cluster)
In-memory store holding Count-Min Sketch arrays for fast updates and queries
Why thisRedis supports fast atomic increments, TTL for time-windowed data, and cluster sharding for horizontal scale with sub-100ms P99 latency
Why notCassandra has higher write latency and is not optimized for atomic increments; Memcached lacks persistence and atomic counters
Query API Server
Expose frequency estimation APIs to clients with low latency
Why thisStateless API servers horizontally scale behind load balancers, caching frequent queries and aggregating sketch results from Redis
Why notMonolithic servers limit scale and increase latency; direct client access to Redis risks security and throttling issues
Monitoring & Alerting (Prometheus + Grafana)
Track ingestion rates, query latencies, error rates, and system health
Why thisPrometheus provides time-series metrics collection with alerting rules; Grafana offers rich dashboards for operational visibility
Why notNagios lacks native metrics collection for streaming systems; CloudWatch is vendor locked and less customizable
🔄
Data Flow
1
Event Sources → Kafka Cluster
Publish user events/messages to Kafka topic partitions
Decouples ingestion from processing; supports 1.5M writes/sec peak
2
Kafka Cluster → Stream Processing (Flink)
Consume events in real-time with exactly-once semantics
Enables windowed aggregation and sketch updates
3
Stream Processing → Count-Min Sketch Updater Store (Redis)
Increment sketch counters atomically per event hash
Redis cluster shards by item hash for horizontal scale
4
Query API Server → Count-Min Sketch Updater Store (Redis)
Query frequency estimates by aggregating sketch counters
Low latency queries with caching and sharding
5
Client Apps → Query API Server
Send frequency estimation requests
APIs support batch and streaming queries

Practice

(1/5)
1. In the newsfeed system, at Step 4 the Delivery Worker reads a fan-out event from Kafka and attempts to deliver it to followers. What happens if a follower's device is offline at this step?
easy
A. Delivery Worker marks the message as sent but not delivered, queues for retry later
B. Delivery Worker drops the message to avoid blocking other deliveries
C. Delivery Worker retries immediately until the follower is online
D. Delivery Worker pushes the message to the follower's device cache directly

Solution

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

    The Delivery Worker reads fan-out events from Kafka and attempts delivery. If the follower is offline, immediate retry (A) would block and reduce throughput. Dropping messages (C) causes data loss. Pushing directly to device cache (D) is impossible if offline.
  2. Step 2: Understand retry mechanism

    The system marks the message as sent but not delivered, queues it for retry later when the follower reconnects, ensuring eventual delivery without blocking.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Offline followers cause queued retries, not immediate blocking [check]
Hint: Offline followers cause queued retries, not immediate blocking [check]
Common Mistakes:
2. Without the message queue (Kafka) in the architecture, what exactly breaks when Alice sends a message to Bob during a partial regional outage?
medium
A. Messages are buffered locally on Alice's client until Bob reconnects
B. Alice's message is immediately delivered but Bob's client shows duplicate messages
C. Alice's send blocks waiting for Bob's server response; if Bob's server crashes, the message is lost with no retry
D. The system automatically retries sending messages indefinitely without blocking

Solution

  1. Step 1: Understand Kafka's role in decoupling

    Kafka buffers messages asynchronously, preventing blocking and enabling retries during outages.
  2. Step 2: Analyze failure without Kafka

    Without Kafka, synchronous calls block sender until receiver responds; if receiver crashes, message is lost with no retry (B). However, buffering on client (C) is incorrect as buffering is server-side.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    No Kafka -> synchronous send blocks and message loss on receiver crash [check]
Hint: No Kafka -> send blocks, no retry, message lost on crash [check]
Common Mistakes:
3. For the Explore page, you must recommend trending photos to users with low latency and high freshness. Which architecture best fits this constraint?
medium
A. Use a batch job that runs every 6 hours to compute trending photos and store results in a database
B. Use a CDN to cache Explore page content globally and invalidate cache every hour
C. Use client-side polling every minute to fetch trending photos from a static cache
D. Use a streaming pipeline that updates trending scores in real-time and stores results in a fast key-value store

Solution

  1. Step 1: Analyze freshness and latency requirements

    Trending photos must be updated with low latency and high freshness, ruling out long batch intervals.
  2. Step 2: Evaluate architectures

    Batch jobs every 6 hours (A) are too stale. Client polling (C) adds load and latency. CDN cache invalidation (D) is coarse-grained and slow. Streaming pipeline (B) updates trending scores in real-time and stores in fast KV store, meeting freshness and latency.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Streaming pipeline enables real-time trending updates [check]
Hint: Real-time streaming pipelines enable fresh trending data [check]
Common Mistakes:
4. If the message queue (e.g., Kafka) between the upload service and transcoding pipeline fails, what exactly breaks in the video processing flow?
medium
A. Uploaded videos are accepted but never reach transcoding, so no processed versions are generated
B. Upload service blocks until transcoding completes, causing upload timeouts
C. Videos are transcoded multiple times causing duplicate outputs
D. View counts increment incorrectly due to missing transcoding metadata

Solution

  1. Step 1: Trace failure impact of message queue outage

    The queue decouples upload and transcoding. Without it, upload service cannot enqueue transcoding jobs. Uploads succeed but transcoding workers receive no tasks, so no processed videos are generated. Blocking upload (B) is incorrect because upload is asynchronous. Duplicate transcoding (A) is unrelated. View count errors (D) happen downstream, not due to queue failure.
  2. Step 2: Confirm exact failure mode

    Uploads accepted but stuck before transcoding is the precise failure.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Queue failure causes transcoding jobs to be lost, no processed videos [check]
Hint: Queue failure means no transcoding jobs dispatched [check]
Common Mistakes:
5. At 10x scale, which component is most likely to become the bottleneck first in a read-heavy CQRS system with read replicas, and why?
hard
A. Event queue, because increased write events overwhelm its processing capacity
B. Primary database, because write throughput scales linearly with read volume
C. Read replicas, because replication lag increases and they cannot keep up with read demand
D. Client-side caches, because cache invalidation traffic grows exponentially

Solution

  1. Step 1: Analyze scaling impact on components

    Write volume and event propagation increase 10x, stressing the event queue.
  2. Step 2: Compare bottlenecks

    Primary DB writes scale with writes, not reads; read replicas scale horizontally; client caches don't cause exponential invalidation.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Event queue overwhelmed first due to write event surge [check]
Hint: Event queue chokes first as write events surge 10x [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