Courses › System Design › Question Breakdowns

Design Twitter Search

Inverted indexes, sharding by word vs. by tweet, scatter-gather and ranking.

Design search over every tweet (or post, or message): users type words and get matching tweets back, newest or most relevant first. The core is an inverted index, and the interesting decisions are about time: almost all searches want recent tweets, so the index is organized around recency, from how it's partitioned to how it recovers from failure.

Requirements

Functional

  • Users can search tweets by keywords, with AND / OR / NOT and exact phrases
  • Results come back newest first or top (ranked), with pagination
  • A new tweet is searchable within ~10 seconds

Out of scope: people search, spelling correction, typeahead (see Design Typeahead).

Non-functional

  • Latency: results in under ~300ms at the 99th percentile
  • Freshness matters more than completeness during a spike: search must keep up with breaking news
  • Scale: ~500M new tweets/day, ~2B searches/day

[!TIP] Back-of-the-envelope 500M tweets/day is ~6k/second, peaking several times higher during big events. Searches run at ~23k/second. A tweet yields ~12 indexed terms; with tweet IDs delta-encoded in sorted posting lists, a posting costs ~2 bytes. So the index grows by 500M × 12 × 2 B ≈ 12 GB a day. A week of tweets is ~85 GB, which fits in memory with room to spare; ten years is ~45 TB, which belongs on SSD. That split is the design.

Core Entities

  • Tweet: time-sortable tweet ID, author, text, created at, engagement counts
  • Posting list: term → sorted list of tweet IDs (plus a few bits of per-posting data such as position)
  • Index segment: an immutable chunk of the index covering a fixed time range

API

GET /v1/search?q="world cup" final -replay&sort=latest&limit=20&cursor=
→ { tweets[]: { id, author, text, createdAt, likes }, nextCursor }

High-Level Design

writer = client "Tweet Writers" @0,0
ingest = service "Ingest Service" @1,0
log = queue "Tweet Log\n(Kafka)" @2,0
rt = service "Realtime Index\n(last 7 days, RAM)" @3,0
arch = service "Archive Index\n(older, SSD)" @3,1
build = service "Segment Builder\n(batch)" @2,1
db = store "Tweet Store" @4,0.5
user = client "Searcher" @0,2
broker = service "Search Broker" @2,2
writer -> ingest
ingest -> log
ingest -> db
log -> rt
log -> build
build -> arch
user -> broker : query
broker -> rt : fan out
broker -> arch : only if needed
broker --> db : hydrate tweets
  • The realtime tier consumes the tweet log and indexes each tweet within seconds, holding the last ~7 days in memory.
  • The archive tier holds everything older as immutable segments on SSD, built in batch from the same log.
  • The search broker queries the realtime tier first and goes to the archive only when it needs more results (an old or rare query), then merges, ranks and hydrates.

Twitter's production search (Earlybird) used this realtime/archive split.

Deep Dives

1. The inverted index

For each tweet, tokenize the text, normalize it (lowercase, Unicode folding, keep hashtags and @mentions as whole terms), and append the tweet ID to each term's posting list. Posting lists are sorted by tweet ID, and IDs are time-sortable, so:

  • AND is an intersection of sorted lists, OR a merge, NOT a difference, each linear
  • Newest first means reading the lists backwards and stopping after 20 matches (early termination), which is why most queries are cheap
  • Sorted IDs delta-encode well: the gaps between consecutive IDs are small, so variable-length integers shrink a posting from 8 bytes to ~2

Phrase queries ("world cup") also need each term's position in the tweet, stored alongside the posting.

2. Partitioning: by time, then by tweet

  • By time first. Each segment covers a time range, say a few hours of tweets. A "latest" query reads the newest segments and stops early. The archive holds tens of thousands of segments, but most queries never touch it.
  • By tweet within a time range. A day's tweets are split across N partitions by hash of tweet ID, and each partition indexes all terms of its tweets. Every query fans out to all N partitions in the tiers it needs, but each partition answers from its own slice without any cross-machine joins.

Why not shard by term? A term's posting list would live on one machine, so #WorldCup during the final would melt that machine, and multi-term queries would join lists across machines. Partitioning by tweet spreads a hot term across every partition.

3. Recovering a lost partition

Partitions have replicas, so a single failure is just a failover. Losing every replica of a realtime partition is rare, but rebuilding it is easy because of the time-based layout: the new server knows exactly which time range and which hash slice it owns, so it replays the tweet log for that range and keeps only the tweets that hash to it. No mapping from tweets to servers needs to be stored anywhere.

Archive segments are immutable files, so recovery means copying them from durable storage (S3) to a new machine.

4. Ranking for "Top" results

"Top" can't simply sort everything by score: there are far too many matches. Instead, each partition runs a cheap first-pass score (recency, engagement, author reputation, a text match) over its candidates and returns its best few hundred. The broker merges these and runs a heavier model on a few thousand candidates. Engagement counts change constantly, so they're kept in a separate in-memory table that partitions read at scoring time, not stored in the posting lists.

5. Caching and spikes

  • Cache result pages for popular queries for a few seconds. During an event, thousands of people run the same query, but results must still update almost live.
  • Cache tweet bodies for hydration; recent tweets are the hottest.
  • When ingest spikes, the realtime tier keeps indexing first and lets ranking quality drop a little, so the site keeps up with the news.

What's expected at each level

  • Mid-level: a tweet store plus an inverted index; AND/OR as list intersection and merge.
  • Senior: index size from compressed postings, tweet-vs-term partitioning, scatter-gather with a broker, early termination for recency.
  • Staff: realtime vs. archive tiers, recovery by log replay, two-stage ranking, behavior under event spikes.