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
Post tweet: a user posts a tweet. The Tweet Service stores it in the tweet store and answers 201. It also hands the tweet to the firehose (Kafka), without waiting for anything to count it.
Count tweet: a stream processor (the trend detector) takes a tweet from Kafka, extracts its terms and adds them to its sliding-window counts for every location the tweet belongs to (city, country, worldwide).
Publish trends: every five seconds, the detector ranks each location's terms by how unusual their growth is, and publishes the top fifty: to a cache that readers use, and to a small database so the cache can be refilled.
Get trends: a user opens a location's trends. Two scenarios: "Cache hit", answered from the cache, and "Cache miss", where the list is read from the database and put back in the cache.
Use these use case and scenario names exactly: the traffic, requirements and tests in problem.proschi refer to them.
Scale
20k tweets per second at a busy peak. Twitter averaged about 5,700 a second in 2013, and its record second was 143,199.
Each tweet updates about a dozen counters: around four terms, each in three locations.
About 1,000 locations, each published every 5 seconds: 200 publishes per second.
30k trends reads per second; 99% find the list in the cache.
Constraints
Posting a tweet never waits for counting: the tweet is stored before the answer, the firehose gets it asynchronously, and the post touches no cache.
The detector keeps its windows in memory: counting a tweet calls no cache and no database. Only ranked lists leave it.
Trends are ranked ahead of time. A read never counts anything and never touches the tweet store.
p99 of Post tweet under 80 ms, of Get trends under 50 ms.
Get trends available 99.99% of the time.
Losing any single machine must not break a latency limit.
At most $11,000 / month, the Tweet Service and the tweet store included.
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
Building a new trends experience, Twitter Engineering, 2015: the largest change to trends since 2008; the old system on a single JVM that saw only a small window of tweets; trend detection rebuilt on Summingbird over Storm, reading the firehose, detecting anomalies and surfacing candidates for post-processing.
TSAR, a TimeSeries AggregatoR, Twitter Engineering, 2014: Twitter's pattern of pre-aggregating events (tens of billions a day) in Summingbird and publishing the results to Manhattan and to Nighthawk, its sharded Redis cache, for reads.
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.
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:
Post tweet: store the tweet, answer 201, and hand the tweet to the firehose (Kafka) asynchronously. The post never waits for counting and never touches a cache.
Count tweet: the trend detector (a stream processor; Twitter used Summingbird on Storm) reads each tweet from Kafka, extracts its terms, and updates in-memory window counts for each of its locations: city, country, worldwide. It calls no cache and no database.
Publish trends: every five seconds, the detector ranks each location's terms by unusual growth and writes the top fifty to a cache (for readers) and a small database (to refill the cache).
Get trends: a user opens a location's list. "Cache hit" is served from the cache; "Cache miss" reads the database and puts the list back.
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:
Posting writes the tweet store before answering, calls a queue but never waits for it, and never calls a cache.
Counting starts at a queue and touches no cache or database.
Publishing writes a cache.
Reading trends checks the cache before any database, never touches a database on a hit, and never touches the tweet store.
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.
Quantity
Arithmetic
Rate
Counter updates
20k × 12
240k/s
Publishes
1,000 locations / 5 s
200/s
Trends reads
given
30k/s
Cache misses
1% of 30k
300/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.
The Tweet Service runs at about 63% from posts alone (20k ÷ 32k). A synchronous Redis call per post adds latency to a path already using most of its p99 budget.
The tweet store takes posts at about a third of capacity (20k ÷ 60k). A GROUP BY per reader adds 30k reads a second and pushes it hot.
Each replica has a fixed price (services $100, Redis $150, MySQL $400, Kafka $200). The existing systems take $3,100 of the $11,000, so the new tiers must be lean.
"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:
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:
Add a term: increment one cell per row.
Estimate its count: take the minimum of its d cells.
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.
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] x2api "Read API"[REST API] x2cache "Answer Cache"[Redis] x2db "Answer Store"[PostgreSQL] x2job -> cache : SETjob -> db : SQLuser -> api : HTTPSapi -> cache : RESPapi -> db : SQLusecase"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}
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:
Path
Flow
Note
Write
user → Tweet Service → tweet store → 201, plus one produce to the firehose
Almost unchanged; use an async send so the post never waits for Kafka
Stream
firehose → detector
Sliding-window sketches and top-k heaps per location in memory; each detector instance owns a slice of the key space, keeping state local
Read
user → load balancer → trends API → cache
Falls 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.
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).