System design practice

Trending Topics

medium Based on a system published by Twitter streaming queues caching top-k real-world

Twitter's trends: count tweets in the stream, rank ahead of time, serve from a cache.

Solve it in your browser Read the lesson first

Twitter shows every user a short list of trends: the terms, hashtags and names whose volume is suddenly growing, worldwide or in their country or city. A trend is not the most-tweeted term (that would be "the" and "lol" forever) but a term tweeted much more than usual. Finding them means counting every term of every tweet in sliding windows, per location, and comparing each count with its own baseline.

Twitter's first trends system ran on a single machine and could only look at a small window of tweets. Its replacement, launched in 2015, counts in a distributed stream processor (Summingbird on Storm) that reads the firehose of new tweets, detects terms whose volume is anomalous, and hands the candidates on to be ranked and published.

Build the counting and serving side: the Tweet Service and the tweet store exist; add everything that turns tweets into trends lists and serves them.

Functional requirements

Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.

Scale

Constraints

What is given

problem.proschi declares the user, the tweets service (sixteen replicas) and the tweetstore (Cassandra, three replicas), and holds the traffic, requirements and tests. Add Kafka, the detector, the cache, the database, the trends API, the connections and the four use cases.

Ranking by growth over a baseline is the detector's own logic; the simulation only sees the calls. The rates of trends reads and publishes are assumptions for this exercise: Twitter has not published them.

Based on

Twitter has not published the trends serving path in detail, so the cache in front of a small database is an assumption in the spirit of TSAR, not a description of the production system. The count-min sketch and top-K heap are the textbook way to find heavy hitters in a stream, not a claim about Twitter's code.

How your design is checked

You write the design as text in Proschi. Tests run in your browser: a simulation of the traffic above checks latency, availability, cost and what happens when a machine fails. How the simulation works.

Start designing

Lesson · 11 min read

Learn it: Trending Topics #

What you'll learn #

The problem, explained #

Two systems exist: the Tweet Service (sixteen replicas) and the tweet store (Cassandra, three replicas), through which users post. You add everything that turns tweets into trends and serves them.

Four use cases:

Limits: Post tweet p99 under 80 ms; Get trends p99 under 50 ms and 99.99% available; durable posts; no single machine failure may break a latency limit; and $11,000 a month, including the existing Tweet Service and tweet store.

The given tests check four things:

Back-of-the-envelope #

tweets at a busy peak
20k / s
counter updates (12 per tweet)
240k / s
publishes (1,000 locations every 5 s)
200 / s
trends reads
30k / s
fewer rankings than per-reader ranking
150×

Tweets. 20k a second at a busy peak. Twitter reported about 5,700 a second on average in 2013 and a record of 143,199 in one second: peaks many times the average are real.

Counter updates. Each tweet has about four terms, each counted in three locations: 12 updates per tweet.

QuantityArithmeticRate
Counter updates20k × 12240k/s
Publishes1,000 locations / 5 s200/s
Trends readsgiven30k/s
Cache misses1% of 30k300/s

Look at the first row. As a Redis call per update (ZINCRBY, about 100k operations a second per replica), the increments alone need more than two Redis replicas before any reader arrives. In the detector's memory, 240k a second is trivial.

Deep dive Memory for the windows

A count-min sketch with 2,000 columns and 5 rows of 4-byte counters is 40 KB. One per location per time bucket: 1,000 locations × 12 five-minute buckets for an hour × 40 KB ≈ 480 MB, spread across the detector fleet. The dimensions are illustrative, not Twitter's, but the order of magnitude shows windows fit in RAM.

Read side. A trends list is fifty short strings, a few kilobytes; 1,000 of them, a few megabytes, fit in one cache easily. Reads are what need API replicas: 30k / 2k per service replica = 15 at 100%, so more than that with headroom and a lost replica.

In Proschi's numbers.

Concepts #

Sliding windows and baselines, in memory #

"Trending now" means "in the last N minutes". A tumbling window is a fixed bucket (12:00 to 12:05); a sliding window covers the last N minutes at any moment. The standard implementation keeps a ring of small tumbling buckets (say one per minute), sums the latest N and drops the oldest as time moves on. Memory stays bounded and expiry is constant-time.

Stream processors must also pick a clock: when the tweet was created (event time) or processed (processing time). For trends, slightly late tweets matter little, so processing time with small buckets is usually fine.

Windows also give the baseline. Ranked by raw count, "the" and "lol" would trend forever. A detector compares a term's current count with its own history (the same hour yesterday, or a long moving average) and ranks by how unusual the ratio is. The simulation does not see this, but it is why windows and ranking live together in the detector's memory, not in a shared store.

Trade-off. State in a process dies with it, so you rebuild it by replaying the log. When not to do it: when the state is too large for the fleet's memory, or other services must query it; then use a stream processor's managed state store or a real database. In Proschi, "counting in memory" is simply a consumer step that calls nothing else:

title "Stateful stream consumer"

log    "Event Log"        [Kafka] x3
worker "Window Counter"   [Java]  x4

log -> worker : consume

usecase "Count event" {
  log     -> worker : Event term=worldcup loc=23424977
  worker --> log    : commit offset
}

Count-min sketch and top-k #

An exact counter for every term in every location is impossible: the vocabulary is unbounded. A count-min sketch is a small 2D array of counters, d rows by w columns, with one hash function per row:

Collisions can only add, never subtract, so the estimate never undercounts; with w and d chosen right the overcount is bounded with high probability (Cormode and Muthukrishnan, 2005).

A sketch answers "how often did X appear?" but cannot list the most frequent items. Pair it with a min-heap of size k: after each update, if the term is in the heap, update its count; otherwise, if its estimate beats the heap's smallest entry, swap it in. The heap holds the current heavy hitters.

Trade-offs. Estimates are approximate and only overcount. You cannot delete from a basic sketch (use bucketed windows instead). Heavy hitters by volume are not trends on their own. When not to use it: small, bounded key spaces (a few thousand products), where an exact hash map is cheaper and simpler. In Proschi the sketch and heap are invisible: they are the consumer step above.

Precompute and serve from a cache #

When many readers ask the same few questions, answer each once and store it. Here about 1,000 questions ("trends for location X"), refreshed every five seconds, meet 30k readers a second. Writing the ranked list to a cache turns each read into one key lookup. A small database holds the last published list so a cold or failed cache can be refilled (cache-aside on the read path).

When not to use it. With a huge number of rarely repeated questions (arbitrary user-defined queries), precomputing wastes work; compute on demand and cache the popular answers.

Deep dive The pattern in Proschi: precomputed answers
title "Precomputed answers"

user  "User"         [Actor]
job   "Ranker"       [Java]       x2
api   "Read API"     [REST API]   x2
cache "Answer Cache" [Redis]      x2
db    "Answer Store" [PostgreSQL] x2

job  -> cache : SET
job  -> db    : SQL
user -> api   : HTTPS
api  -> cache : RESP
api  -> db    : SQL

usecase "Publish" {
  job    -> cache : SET top:eu top 10
  cache --> job   : ok
  job    -> db    : UPSERT answers eu
  db    --> job   : ok
}

usecase "Read" {
  user -> api : GET /top/eu
  alt "Hit" {
    api    -> cache : GET top:eu
    cache --> api   : top 10
  } alt "Miss" {
    api    -> cache : GET top:eu
    cache --> api   : nil
    api    -> db    : SELECT answer FROM answers
    db    --> api   : top 10
    api    -> cache : SET top:eu top 10
    cache --> api   : ok
  }
  api --> user : 200
}

Designing it step by step #

Step 1: scope. Clarify what a trend is (unusual growth), the locations (about 1,000), freshness (seconds is fine), list length (fifty) and personalisation (none). Ask for the peak tweet and read rates.

Step 2: high-level design. Three paths:

PathFlowNote
Writeuser → Tweet Service → tweet store → 201, plus one produce to the firehoseAlmost unchanged; use an async send so the post never waits for Kafka
Streamfirehose → detectorSliding-window sketches and top-k heaps per location in memory; each detector instance owns a slice of the key space, keeping state local
Readuser → load balancer → trends API → cacheFalls back to the trends database on a miss

Step 3: deep dive.

Where do the counts live?

What if a detector dies? Its windows are lost, but Kafka still holds the recent tweets: a replacement replays the last window's worth of offsets and rebuilds. Trends for that slice are briefly off, which is acceptable. A long baseline (yesterday's counts) is too much to replay, so snapshot it to durable storage from time to time.

Which store backs the cache? Tiny data (one row per location), written 200 times a second: a small relational database with a replica is plenty, read only on the 1% of misses.

Sizing. API replicas for 30k reads at well under 70% with one lost, two replicas per new store, a detector sized for 20k events, and the whole bill, existing services included, within budget.

Step 4: wrap-up. Mention spam and manipulation filtering before ranking, personalised trends (rank per user cluster), hot partitions (one term exploding worldwide lands on one detector shard), and that the model does not simulate the windows or the ranking logic.

Common mistakes #

Counting while posting (wrong/count-while-posting). The Tweet Service bumps a dozen Redis counters before answering. Every post waits on Redis, and a tweet spike is a Redis write spike. In Proschi the cache saturates (about 135% of capacity) and the post p99 breaks, failing "Posting a tweet never waits for counting" and p99 of Post tweet < 80 ms.

A counter per term in Redis (wrong/counter-per-term-in-redis). Same increments, moved into the detector. The post is fine, but the detector hammers the shared cache readers also use. It fails "Tweets are counted in the stream, in memory", survive any node failure, and the Get trends p99 (the readers' cache is saturated).

Counting at read time (wrong/count-at-read-time). Every trends request runs a GROUP BY over the last hour of tweets: work grows with readers instead of locations, and the tweet store (the source of truth for every tweet) runs hot. It fails "Trends are ranked ahead of time and served from a cache" and cannot survive losing a store replica.

Reading trends from the database (wrong/read-trends-from-database). The cache is written but never read, so all 30k reads hit two MySQL replicas, which run hot and cannot lose one. It fails the ranked-ahead-of-time test and survive any node failure.

Also watch for: ranking by raw volume (stop words win), unbounded per-term state with no expiry, and a single detector process that sees every tweet (Twitter's old trends system ran on one JVM and could only look at a small window).

In the interview #

Likely follow-ups:

Further reading #

Now design it

Review cards for this problem

Short questions on the ideas it needs, from the review cards. Review them daily so they stick.

More system design problems