Design Twitter search

01The design, in the six-step framework

1. Requirements

Functional

• Search tweets by keywords and hashtags, with results ordered by recency or by relevance (engagement plus recency).
• A new tweet is searchable within a few seconds; a deleted tweet disappears within seconds.
• Filters: language, from a user, with media, date range.
• Out of scope: user search, trends (see trending topics), personalisation.

Non-functional

• 500 million tweets a day (about 6,000/s, 20,000/s at peak); 1 billion searches a day (12,000/s, 50,000/s at peak).
• Query latency under 200 ms at p99 including ranking.
• The last week must be searchable at full speed; older history can be slower and on cheaper storage.
• Indexing lag under 10 s; availability 99.99 percent.

2. Core entities

• Tweet: id (time-ordered), author, text, language, created-at, engagement counters, deleted flag.
• Posting: term → list of tweet ids in descending time order with positions.
• Segment: an index over a time slice (for example 10 minutes of tweets), immutable once sealed.
• Tombstone: deleted tweet ids applied at query time until compaction.

3. API

• GET /search?q=&sort=recent|top&since=&until=&lang=&cursor= → tweet ids and hydrated tweets, with a cursor for the next page.
• Internal: index.append(tweet) from the tweet-creation stream; index.delete(tweet_id); shard.query(terms, filters, k, time_range).

4. High-level design

Indexing and searching:

1. Every new tweet is published to a stream. Each real-time shard's indexer consumes its partition (by tweet id hash), tokenises the text, and appends postings to an in-memory segment for the current 10-minute window; the tweet is searchable within a second or two.
2. Sealed segments are written to disk and periodically merged into larger archive segments by the compactor; after a week they leave the in-memory tier.
3. A search goes to all real-time shards (recent sort) or to real-time plus the relevant archive shards (date range). Each returns its top matches by time or score; the aggregator merges, ranks, drops tombstoned ids, and hydrates the tweets.

5. Deep dives

Why time-ordered postings and time-sliced segments?

Most searches want the newest tweets, and a feed of recent results stops as soon as it has k matches. If a term's posting list is stored newest first, a shard reads only the head of each list and stops early; for a common term with millions of postings that is the difference between scanning everything and scanning a few hundred entries. Time-sliced segments add a second win: a query with a date range opens only the segments that overlap it, and expiry is deleting whole segments rather than editing lists. The cost is that relevance ranking ("top") cannot stop early, so it reads a bounded window (say the last day) per term and ranks within it, and that is the documented behaviour of real tweet search.

How does a tweet become searchable in seconds and stay consistent with deletes?

The indexer appends to a mutable in-memory segment with per-term lists kept in insertion order, which is time order because tweet ids are time-ordered. No sorting is needed on write. A delete arrives on the same stream; the indexer records a tombstone that the aggregator applies to results until compaction rewrites the segment without the id. Because ingest is partitioned by tweet id hash, a given tweet always lands on the same shard, so append and delete are ordered for that tweet. If an indexer crashes it replays its stream partition from the last checkpoint; segments are rebuilt deterministically, so there is no state to copy.

Sharding and scatter-gather at 50,000 searches a second

Partition by tweet (document) rather than by term, for the reasons in web search: even load and cheap fan-out. With 20 real-time shards, each query touches 20 machines; each shard has enough replicas to carry its 50,000 queries/s share. Tail latency is handled with hedged requests and a deadline: a search returns at 150 ms with whatever shards answered, since missing one shard's recent tweets is invisible to most users. Fewer, bigger shards keep fan-out small; the limit is one shard's ingest rate of about 1,000 tweets/s per indexer and its memory for a week of postings, so 20 shards is comfortable and 50 is the growth plan.

Ranking "top" results without blowing the budget

A relevance query scores candidates by text match, engagement (likes, reposts, replies), author quality and recency decay. Engagement changes after indexing, so the index stores a compact, periodically refreshed engagement score per tweet rather than live counters; a tweet that goes viral an hour after posting is re-scored on the next refresh. Each shard returns its best few hundred from the bounded window, the aggregator merges and re-ranks the top few thousand with a heavier model, and caches the result page for popular queries for a few seconds, which is enough during a live event when the same query is issued thousands of times a second.

Hashtags, hydration and the cost of showing a result

Hashtags and mentions are indexed as their own terms with a type prefix, so #final and the word "final" are different postings and a hashtag query is an exact lookup rather than a text match. The index returns ids only; showing a result needs the tweet body, the author's current name and avatar, and live counts, which come from the tweet store in one batched read per page. That hydration step is where most of the end-to-end latency goes, so the aggregator asks for exactly the ten ids on the page, caches hydrated tweets for a few seconds during spikes, and shows a tombstoned or protected tweet as removed rather than failing the whole page. Pagination uses a cursor of (score, tweet id) with search-after semantics, so new tweets arriving between pages do not shift results.

Keeping the real-time tier available across regions

The in-memory week is rebuilt deterministically from the stream, so a new region's shards bootstrap by replaying the last seven days from the event log rather than copying memory images, which takes hours but needs no special protocol. Each region consumes the same global stream, indexes locally and serves its own users, giving region-local latency and independence during a cross-region outage; the archive tier is replicated as sealed segment files through object storage. A search issued during an indexer lag in one region may miss the last few seconds, which is an acceptable degradation that should be stated rather than hidden.

6. What a strong answer sounds like

• Do the index arithmetic and separate the week in memory from the year on disk; the tiers are the design.
• Explain newest-first postings and early termination; it is the one trick that makes recent search cheap.
• Describe ingest as an ordered stream per shard with deterministic replay, and deletes as tombstones.
• Show the bounded window and refreshed engagement score for relevance ranking.
• Expect follow-ups on hashtag spikes during an event, on multi-region replication of the real-time tier, and on how a date-range query across a year stays under the latency goal.
• Common mistake: a term-partitioned index or re-sorting posting lists on every insert.

02Where this question was reported

• interviewkickstart.com · Listed
• DesignGurus · Listed