Skip to content

Trending Topics / Top-K Service#

Problem statement (interviewer prompt)

Design a real-time "trending topics" / top-K hashtags service for Twitter-scale traffic. Identify the top 10 + top 100 hashtags over a sliding 5-minute / 1-hour / 1-day window, with bounded memory, using probabilistic structures (CMS + heap or Space-Saving).

flowchart LR
  E[[Event stream]]
  CMS[Count-Min Sketch]
  HEAP[Top-K heap]
  API[Top-K API]
  E --> CMS --> HEAP --> API

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class CMS,HEAP,API service;
    class E queue;

flowchart TB
  subgraph Source
    EVT[Events: clicks, hashtags, queries]
    KAFKA[[Kafka]]
  end

  subgraph Stream[Stream layer]
    DECAY[Time decay applier]
    CMS[Count-Min Sketch<br/>per window]
    SS[Space-Saving / Heavy Keepers]
    SPIKE[Spike detector<br/>z-score / EWMA]
    WIN[Sliding windows 1m / 5m / 1h]
  end

  subgraph Storage
    TOPK[(Top-K materialized lists)]
    HIST[(Historical baselines)]
    DASH[(Dashboards)]
  end

  subgraph Serve
    API[Top-K API]
    PER[Personalization overlay]
    SAFE[Safety filter - banned trends]
  end

  EVT --> KAFKA --> Stream
  Stream --> Storage
  Storage --> Serve

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class EVT,DECAY,CMS,SS,SPIKE,WIN,API,PER,SAFE service;
    class TOPK,HIST,DASH datastore;
    class KAFKA queue;

Algorithms#

  • Count-Min Sketch sized for ε, δ guarantees.
  • Space-Saving / Heavy Keepers: maintains top-K with bounded memory.
  • Decay: exponential decay on counts so old activity fades.
  • Spike detection: compare to historical baseline (z-score, EWMA control chart).

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag Concept What it is Page
HLD Pub/Sub & message brokers topics, consumer groups, delivery semantics pub-sub-pattern
HLD Probabilistic data structures Bloom, HLL, Count-Min, MinHash, t-digest probabilistic-data-structures

Quick reference#

Functional#

  • Top-K items across windows.
  • Per-region, per-category trends.
  • Spike detection.
  • Safety filters.

Non-functional#

  • Refresh < 60 s.
  • Bounded memory regardless of cardinality.

Trade-offs#

  • Streaming approximate vs batch exact: streaming wins for freshness.
  • Per-window storage keeps explainability.
  • Personalization adds latency; serve global trends + overlay.

Refs#

  • Cormode et al. on CMS / Space-Saving.
  • Twitter trends architecture talks.
  • ByteByteGo "Design top-K service".

FAQ#

A stream processor counts hashtag frequencies in a sliding window using Count-Min Sketch, maintains a min-heap of the top-K, and merges shard results periodically into a global trending list.

What is Count-Min Sketch?#

CMS is a 2D array of counters with d hash functions. Each event increments d cells; queries take the minimum across rows. It uses constant memory regardless of distinct keys.

Why use a heap with Count-Min Sketch?#

CMS gives approximate counts for any key, but you still need the top-K. A min-heap of size K holds candidate items; new items only enter if their CMS count exceeds the heap's minimum.

Sliding gives smoother results because counts roll continuously. Tumbling is simpler and cheaper but produces step-jumps at boundaries. Trending UIs usually want sliding for the better UX.

How do you merge top-K across shards?#

Each shard emits its local top-K. A merger union-sums the candidate set and re-selects the global top-K. Errors from CMS are bounded by the sketch's width parameter.

Video walkthrough

Top-K System Design Breakdown : via Hello Interview