Loading...

A 20-minute mock system design interview. You drive the pace. Jump to the board when you are ready; skip capacity math if you want. The interviewer grades your thinking, not a template match.
This is the inverted index question. Signal concentrates in three places: sizing the index honestly (the postings lists, not the vocabulary, are the cost), the word-sharding vs document-sharding trade-off, and how a dead index server is rebuilt without scanning the whole tweet store. "Put it in Elasticsearch" is allowed as an opening sentence — then you design what Lucene would be doing internally.
Two shared surfaces (only one is on screen at a time; use the panel arrow to switch):
Build incrementally while you talk. Trace one tweet from posting to searchable, then one query — india AND cricket — through your diagram to a page of results. Argue the tradeoff, not "industry standard."
Read this before you go in. These are the decisions, and why they matter.
The word list is tiny: ~500K words (300K English + 200K proper nouns) at ~5 chars is 2.5 MB. Candidates who stop there have sized the index at 0.00001% of its real cost. The cost is the postings lists: every indexed tweet's ID appears once per indexed word. A tweet has ~40 words, but stop-words are dropped, leaving ~15 — so each TweetID is duplicated ~15 times across the index. That ×15 step is where hand-waving collapses, and the whole capacity section below is built on it.
The 21 TB index must be partitioned across ~150 servers. Two natural keys, opposite failure modes.
hash(word) puts a term's entire postings list on one server. Single-word queries touch one box. But a trending hashtag makes that box the bottleneck for the whole service, and some words grow vastly bigger lists than others, so memory drifts apart forever. Consistent hashing patches the skew, not the hot words.hash(TweetID) puts all of a tweet's words on one server. Every query fans out to every server through an aggregator that merges partial results. That fan-out buys balance (no hot server from a single term), simple rebuilds (each server's tweet set is well-defined), and a bonus strong candidates spot unprompted: each server holds whole tweets, so it evaluates india AND cricket locally and ships only satisfying IDs.The chapter lands on document-sharding. Either choice can pass if you name the axis — read amplification vs balance — and commit. Word-sharding with no plan for trending terms fails the probe.
A dedicated ID service hands out 5-byte time-ordered IDs (730B tweets in five years fits in 2^40). Keep postings sorted by TweetID and, because IDs embed time, they are sorted by creation time: intersection is a linear merge of sorted lists, "latest first" is free, and a time-range filter is a range scan. If you choose real 64-bit Snowflake IDs instead, say the index grows 8/5 ≈ 1.6× (roughly 35 TB, not 21). Noticing that is a good sign.
Every index server has a secondary replica. The interesting question is both dying. Under document-sharding the brute-force rebuild is scanning the entire 500 TB tweet store and hashing every ID to find this server's tweets — slow, and while it runs, queries silently miss tweets. The fix: the Index Builder keeps a reverse map, server → HashSet{TweetIDs}. A rebuilding server asks for its set, fetches exactly those tweets, re-tokenizes, rebuilds. HashSet because adds and removes must be O(1). The Index Builder is itself replicated, and the same map is the hook for deletions and rebalancing.
The write stream is ~4,600 tweets/s, ~70,000 postings insertions per second across the index. Propose a bound (seconds to a minute) and a mechanism: synchronous insert (freshest; appends are cheap only because time-ordered IDs are always the largest); a delta index per server — small, write-optimized, merged into the main index every few seconds (the Lucene segment idea; reaching for it is a strong signal); or a queue (Kafka) between the app tier and the Index Builders so bursts do not back up into tweet posting and a lagging server can replay.
Store a popularity number next to each TweetID in the postings. Each partition sorts its local matches, returns only its top page; the aggregator merge-sorts and returns the global top. Scatter-gather top-k — the same pattern as Yelp's nearest-places merge. The stored score goes stale as likes keep arriving; say so, and propose a periodic re-score piggybacked on index maintenance rather than touching postings on every like. "Best matched" adds a relevance score (TF-IDF/BM25) computed at query time.
A deleted tweet is still referenced from ~15 postings lists. Two stages: tombstone it so the index server or aggregator filters it at read time immediately, then purge asynchronously via the reverse map — remove from each postings list, the HashSet, and the tweet store. An edit is a delete plus re-index.
One complete design you can study, then rebuild in your own words. Do not recite it. In the interview, draw your graph and defend the choices.
Rough numbers are fine; the ×15 postings step and the two-year scoping move are what get graded.
Two responsibilities: store every tweet in a partitioned database, and build and serve an in-memory inverted index. Writes flow through the Index Builder into one index shard; reads fan out through an aggregator to all shards and come back as IDs that get hydrated from cache and database. The reverse map lives with the builder, off the query path, waiting for a rebuild.
Web Client / Mobile Client
→ Load Balancer
→ Service "App Server" (parse AND/OR, hydrate results; mark distributed)
→ Service "ID Service" (5-byte time-ordered TweetIDs)
→ MySQL "Tweet DB" (~125 shards by hash(TweetID), 1 extra copy)
→ Kafka "Ingest" (optional buffer)
→ Worker "Index Builder" (tokenize, drop stop-words,
insert postings; holds ReverseMap; replicated)
→ Service "Index Server" (in-memory postings, ~152 shards
by hash(TweetID); primary + secondary;
mark distributed)
→ Service "Aggregator" (fan out query to all index shards,
merge-sort top-k, page; mark distributed)
→ Service "Index Server" (same tier, read path)
→ Memcached "Hot Tweets" (hydration cache, LRU)
hash(TweetID), each with a fault-tolerance copy. The chapter starts from a two-column MySQL table. This is durability; search never scans it.india AND crickethash(101) plus its copy.hash(101), and adds 101 to that shard's HashSet in the reverse map. The tweet is now searchable — seconds after posting.india AND cricket, latest first. An App Server parses the expression and hands it to an Aggregator.Index server dies: the secondary takes over. Both die: fetch the shard's TweetID set from the Index Builder's reverse map, fetch exactly those tweets, re-tokenize, rebuild. The full-scan alternative is slow across 500 TB and silently drops tweets from results while it runs.
Tweet deleted for policy: its ID still sits in ~15 postings lists. Tombstone now (filtered at read time), purge asynchronously through the reverse map.
Popularity drift: stored scores go stale as likes arrive. Re-score periodically with index maintenance; accept minutes of staleness rather than touching postings per like.
Tweet(TweetID 5B, TweetText ≤300B, UserID, CreatedAt, LikeCount)
Postings: word → [(TweetID, popularity), …] — sorted by TweetID (= by time)
ReverseMap: index_server → HashSet{TweetID} — on the Index Builder
HotTweets: TweetID → Tweet — Memcached, LRU
hash(TweetID) across ~125 servers, one extra copy eachhash(TweetID) (document-sharding) across ~152 in-memory servers, primary + secondaryWord-sharding with consistent hashing plus an explicit hot-word plan (replicate hot terms, split their lists). Elasticsearch/Lucene named as the implementation, provided you still design the sharding, rebuild, and ranking internals. A delta index vs a queued insert for freshness. What matters is that you can argue the tradeoff.