Twitter Search

The problem

"Design search for Twitter." People type a word or a hashtag and see matching tweets, newest first, including tweets posted seconds ago. During a big match, a large share of all searches are the same hashtag.

This practice problem reuses the pattern of the Search Engine: an inverted index from each word to the ids of the tweets that contain it, split over servers that a search asks at once. What's new is time. Tweets must be searchable within seconds, most searches want the newest matches, likes keep changing after a tweet is indexed, and a trending search arrives thousands of times a second. Park image search and spelling correction.

The numbers

From the interviewer: 100 million tweets a day, as in Twitter at Scale, with about 20 words each, and one index entry of about 4 bytes per word, as in the Search Engine.

• Index per day: 100 million × 20 = 2 billion entries × 4 bytes = 8 GB.
• The last week: 56 GB, which fits in the memory of a server that keeps about 100 GB of index (say). Ten years, about 30 TB, never will.
• Writes: 100 million a day is about 1,000 tweets a second (a day ≈ 100,000 s), 5,000 at busy hours, each adding its id to about 20 lists: 100,000 list appends a second.

Real time: a recent index in memory

An index built in batches every few hours, or even every few minutes, is behind a live match. Writing each tweet into the big index of all past tweets means 100,000 changes a second to long packed lists that searches read all the time.

Instead, the indexer reads every new tweet from the tweet stream, the queue of new tweets from Twitter at Scale, and appends its id to its words' lists in a recent index in memory. The tweet is searchable about a second after it's posted. Tweet ids grow with time, as in Unique IDs, so appending keeps each list in time order, newest at the end, with no sorting. Each day's part is written out, packed tight, to the archive. It's the Search Engine's fresh index, except that here it answers most searches.

Newest first: slices by day

The index is cut into slices, one per day. A search for the 20 newest matches starts with today's slice, reads each list from its newest end, and moves to older slices only while it needs more. For a rare word like sourdough:

day        matches   running total
today      8         8
1 ago      7         15
2 ago      9         24: take 5, stop
3–5 ago    15, 3, 12 not read

Three slices, and the older ones are never opened. A common word fills its 20 from the last minutes of today. Paging works the same way: the next page asks for matches older than the last tweet id shown, a cursor.

Splitting: by day, then by tweet id

Today's slice is the hot one: it takes all 5,000 tweets a second and nearly every search reads it. One server per day would overload today's server while those for the 3,650 older days of 10 years sit idle. Splitting by word puts #worldcup on one server during the final. So each day is split by tweet id over several servers: ids spread evenly, and a search asks all of a day's servers at once and merges their answers, the Search Engine's scatter-gather, over only the days it needs. Today's servers get the most copies; old days need few.

Ranking: recency and engagement

Top results mix how new a tweet is with how much people engage with it. What never changes sits in the index: the words, the language, and the time, which is inside the tweet id. Likes and retweets climb for hours, so they live in a counter store by tweet id, as in Distributed Counter, updated as people engage. Whether the searcher follows the author depends on who's asking, so it comes from their follow list. Each server scores its few hundred newest matches, reading their counts in one batch, and the best are merged.

Trending: a cache of seconds

During a final, about 10,000 searches a second are for #worldcup, and each would read all of today's servers. A result cache that keeps each answer for a few seconds, say 5, works it out once every 5 seconds instead: 50,000 searches answered by one. A minute, the Search Engine's choice, could hide a goal from the results for up to a minute; no cache sends all 10,000 a second to the servers just when they're busiest.

Same pattern as the Search Engine

The inverted index, the fresh index for new documents, the scatter-gather over shards and the result cache all carry over. What changed is their weight: the fresh index became the main one, shards are cut by time first, recency is the first ranking signal, and the cache lives seconds instead of a minute.

Summary

• Scope: search tweets by word, newest first, searchable within seconds.
• Data: an inverted index cut into daily slices; tweet ids grow with time.
• API: GET /search?q=…&cursor=…, 20 tweets a page.
• Busy path: read the newest slices first and stop at 20.
• Numbers: about 8 GB of index a day; 5,000 tweets a second at busy hours.
• Services: the indexer reads the tweet stream into a recent index in memory.
• Scale: each day split by tweet id; older days in the archive.
• Ranking: recency, plus live likes and retweets.
• Trending: results cached for a few seconds.