System design deep dive · HLD
Design Twitter Trending Topics: real-time hashtag counting at global scale.
Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for the ingestion path and the top-K compute path, and an entity-relationship diagram for the rollup data model - with the reasoning an interviewer expects behind every box and arrow.
1. Clarify requirements before drawing any box
A trending-topics system is deceptively simple to state and easy to over-engineer. Pinning down exactly what "trending" means - and how approximate the answer is allowed to be - decides whether the design lives or dies under a live-event traffic spike.
Functional requirements
Non-functional requirements
2. Back-of-the-envelope capacity estimation
These numbers are the entire justification for the design's central decision: an approximate counting structure instead of an exact hash-map counter. Walk through them in order - each row sets up the next.
| Metric | Assumption | Resulting estimate |
|---|---|---|
| Post volume (global firehose) | ~500 million posts/day | ~5,800 posts/sec average; 50,000-100,000+ posts/sec during a major live event (8-17x average) |
| Posts containing ≥1 hashtag | ~15-20% of all posts | ~870-1,160 hashtagged posts/sec average; ~15,000-20,000/sec at peak |
| Hashtag-occurrence events | ~1.3 hashtags per hashtagged post | ~1,100-1,500 occurrences/sec average; ~22,000-26,000 occurrences/sec at peak - the increment rate every aggregator must sustain |
| Distinct active hashtag vocabulary | Long-tail: most tags used a handful of times, a few used millions | 1-5 million distinct hashtags active in a rolling 15-minute window during a major global event |
| Naive exact counter memory (hash map per hashtag, per region, per bucket) | ~500 tracked regions × 15 one-minute buckets × up to ~100K locally-active tags each × ~100 bytes/entry | Tens of GB, growing linearly with vocabulary size and with region × bucket count |
| Count-Min Sketch memory (fixed structure) | Width 2,048 × depth 4 × 4-byte counters = 32KB per sketch instance | 500 regions × 15 buckets × 32KB ≈ 240MB total - independent of how many distinct hashtags actually appear |
3. High-level design (HLD)
The HLD names the major components and the data flow between them, without committing yet to cluster sizes, partitioning schemes, or specific deployment topology - that belongs in the architecture diagram in the next section.
What each box owns
Post firehose (Kafka)
Every new post flows through here, partitioned by a coarse region key derived from the poster's locale/geo. Partitioning by region up front means a regional aggregation cluster only ever has to process its own region's volume - it never has to filter out the other 490 million daily posts that belong elsewhere.
Hashtag extraction
Lightweight text processing: a regex/tokenizer pulls out #tags (optionally a keyword-phrase extractor for un-hashtagged trending phrases), and tags the resulting event with a region derived from the poster's locale. It is stateless, so it scales horizontally with ingestion volume alone - it holds no counters and can be scaled up during a spike without any coordination.
Regional and global aggregators (Flink + Count-Min Sketch)
Each regional cluster consumes only its own Kafka partitions and maintains a Count-Min Sketch per 1-minute tumbling bucket for that region. A separate, always-on global cluster subscribes to every partition and maintains its own global sketch - it does not wait for or derive from the regional clusters, because a topic can trend globally through broad, diffuse volume that never exceeds any single region's local threshold.
Baseline store and spike detector
The baseline store holds a slow-moving historical average rate per hashtag (an exponentially weighted moving average). On a periodic tick - not per event - the spike detector reads each active hashtag's current sliding-window estimate from the sketch, compares it against that hashtag's own baseline, and computes a rate-of-change score. Decoupling this from per-event processing keeps its cost proportional to the number of active hashtags, not the number of posts.
Top-K sorted sets and the Trending API
Redis holds one bounded sorted set per region+window (top 200 entries, never the whole vocabulary), updated incrementally by the spike detector's tick. The Trending API is a thin, stateless read service that does nothing but read the top of that sorted set - all the computation already happened upstream, so a client request never triggers a scan or a resort.
4. Detailed architecture diagram
The architecture diagram answers "how is this actually deployed?" - specifically, how ingestion is partitioned by region, why a global path runs in parallel rather than deriving from regional results, and where the durable rollup store sits relative to the real-time hot path.
| Decision | Choice | Reasoning |
|---|---|---|
| Windowing strategy | 1-minute tumbling buckets, summed over the trailing 10-15 buckets | A literal sliding window recomputed per event is O(events); bucketed rollups are O(buckets) and expire cheaply by dropping the oldest bucket. |
| Counting structure | Count-Min Sketch (width ~2,048, depth 4) per region+bucket | Fixed memory regardless of hashtag cardinality; a viral tag gets a small, bounded overcount, while a rare tag costs nothing extra to track. |
| Regional vs global aggregation | A separate, always-on global Flink job - not derived synchronously from regional results | The global path must not wait on every regional cluster's tick to finish, and a topic can trend globally through diffuse volume that's sub-threshold in any single region. |
| Top-K maintenance | Bounded Redis sorted set per region+window, updated with incremental ZADD | Avoids resorting the entire hashtag universe on every tick; ZREVRANGE for the top 50 is O(log N + 50), not O(all hashtags). |
5. Sequence diagrams for the two critical flows
One flow is on the hot ingestion path (every post), the other runs on a periodic tick (every few seconds, independent of post volume). Keeping them decoupled is exactly what lets the trending computation stay cheap even at 100,000 posts/sec.
5.1 Real-time hashtag extraction and counting
Step 5 is deliberately drawn as a dashed, non-blocking arrow: the extraction service publishes the same tagged event to the global aggregator without waiting on the regional aggregator's ack in step 3 - both increments happen independently, so a slow regional cluster can never hold up the global count. Steps 4 and 6 never touch a per-hashtag hash map; they touch a fixed number of Count-Min Sketch cells regardless of how many distinct hashtags exist in that bucket.
5.2 Top-K / trending computation (periodic tick)
Steps 1-6 run on a fixed cadence, entirely independent of how many posts arrived that second - a 100,000-post/sec spike changes the counters the tick reads in step 2, but never changes how often the tick fires or how much work each firing does. Steps 7-10 are the whole client-facing read path: the Trending API performs zero aggregation or comparison at request time, it only reads the already-ranked sorted set, which is what keeps read latency flat regardless of write volume.
6. Entity-relationship (ER) diagram and schema
These three tables model the periodically-persisted, queryable rollup layer only - the in-memory Count-Min Sketch counters and Redis sorted sets that do the actual real-time counting live entirely inside the stream processors and are never modeled as relational rows.
Key modeling decisions
| Storage layer | What lives here | Why |
|---|---|---|
| Relational rollup store (Postgres) | hashtag_counts and trend_windows, once rolled up to 1-minute/15-minute granularity | Low volume once rolled up (thousands of active hashtags × a handful of windows, not per-event); simple range queries (WHERE window BETWEEN ...) power historical trend charts; sits entirely off the hot path. |
| In-memory probabilistic + streaming state | Count-Min Sketch counters (Flink task-manager memory / RocksDB) and Redis top-K sorted sets | Does the actual heavy lifting at 20,000+ increments/sec; never queried directly by clients and never treated as the durable source of truth - it's regenerable from the raw post stream on replay. |
7. Deep dives interviewers actually probe
Exact counting vs. Count-Min Sketch: why a hash map doesn't scale here
A hash-map-per-hashtag exact counter needs one entry per distinct hashtag that has ever appeared in a given region+bucket. During a viral event the vocabulary is both huge and skewed - millions of one-off tags alongside a handful used millions of times - and that table has to exist per region, per 1-minute bucket, simultaneously. Count-Min Sketch replaces the map with a small fixed-size 2D array of counters: hash the hashtag with k independent hash functions, increment the k cells it maps to, and estimate its count as the minimum of those k cells (the minimum cancels out most of the hash-collision noise from other hashtags sharing a cell). The error is strictly one-directional - it can only overcount, never undercount - and is bounded by the sketch's width and depth, not by how many distinct hashtags exist.
// Count-Min Sketch: fixed WIDTH x DEPTH regardless of hashtag cardinality
int[][] table = new int[DEPTH][WIDTH]; // e.g. 4 x 2048, ~32KB total
void increment(String tag) {
for (int d = 0; d < DEPTH; d++) {
int col = hash(tag, seed[d]) % WIDTH;
table[d][col]++;
}
}
long estimate(String tag) {
long min = Long.MAX_VALUE;
for (int d = 0; d < DEPTH; d++) {
int col = hash(tag, seed[d]) % WIDTH;
min = Math.min(min, table[d][col]);
}
return min; // always >= true count, error is bounded and one-directional
}Sliding window vs. tumbling buckets: how the 10-15 minute window is actually implemented
A literal sliding window - recomputing the count over exactly "the last 900 seconds" on every single event - means every increment also has to expire whatever fell off the trailing edge, which is expensive at 20,000+ events/sec. Instead, the aggregator keeps a fresh Count-Min Sketch per 1-minute tumbling bucket and sums the trailing 10-15 buckets to approximate the sliding window. The trade-off is granularity: the window's effective boundary only moves in 1-minute steps, so a hashtag's reported count can be up to one bucket-width stale at the edges. A 1-minute bucket was chosen specifically because it's small enough to keep the near-real-time freshness requirement (spikes visible within ~60 seconds) while being large enough that per-bucket overhead (allocating and later garbage-collecting a sketch) stays a small fraction of total processing cost.
Detecting "trending" as a rate-of-change signal, not raw volume
A naive "top hashtags by raw count in the window" list would be dominated forever by whatever is perennially popular - generic tags that always have huge volume, not necessarily anything happening right now. The spike detector instead compares each hashtag's current sliding-window estimate against its own historical baseline (an exponentially weighted moving average maintained per hashtag), producing a score such as current/baseline or a normalized z-score. A tag that jumps from a baseline of 50/min to 5,000/min scores far higher than a tag that's steady at 50,000/min, which is exactly the signal that makes "trending" mean "emerging" rather than "generically popular."
Regional segmentation and the roll-up hierarchy
Regional aggregation clusters are deliberately kept separate from the global one rather than having the global list synchronously derive from regional results, for two reasons: first, the global tick must not block on every regional cluster finishing its own tick, especially when one region is under a traffic spike; second, a topic can trend globally through broad, diffuse volume - meaningful upticks spread thinly across dozens of regions - without ever crossing any single region's local trending threshold. The regions table's parent_region_id lets a query roll a city's numbers up into its country and then into global for display purposes, but the counting itself always happens independently at each level, never by summing children synchronously at read time.
Spam and manipulation resistance
Coordinated bot posting or duplicate-account amplification can artificially inflate a hashtag's count within minutes - exactly the timescale the system is designed to react to. Two mitigations sit in the extraction stage, before anything reaches the sketch: deduplicating by unique author per short time window (e.g. count a given author's use of a tag at most once per 10 seconds, regardless of how many times they post it), and down-weighting or dropping events from accounts whose posting velocity or account-age/follower profile matches known bot patterns. Both run at extraction time specifically because it's the cheapest point to filter - rejecting a bad event before it costs a sketch increment is far cheaper than trying to subtract it out later.
What happens when a Flink task manager crashes mid-window?
The Count-Min Sketch state lives in RocksDB-backed Flink state, checkpointed periodically (e.g. every 10-30 seconds) to durable storage. On a task manager crash, Flink restores the last checkpoint and replays Kafka events from the corresponding offset, so at most a few seconds of increments are ever redone - not lost, and not double-applied beyond Flink's exactly-once state semantics. This is also the reason the sketch state is never treated as a durable source of truth in its own right: it's fully regenerable from the raw post stream, which is exactly what makes it safe to keep purely in memory/local disk rather than in a replicated database.
Post a Comment
Add