TOUGH TONGUE AI
  • Home
    LogoTOUGH TONGUE AI

    RESOURCES

    Loading...

    HomeLibrarySD Mock · Design Twitter Search

    SD Mock · Design Twitter Search

    SD Mock · Design Twitter Search

    Overview

    Design Twitter's tweet search on a live architecture board — drag components, wire them up, and defend your design to an expert interviewer who watches every move.

    Your Instructions

    Design Twitter Search

    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):

    • Notepad. Shared notes. Requirements, capacity math, schema, and end-of-session feedback live here. You can type in it too.
    • Architecture board. Your design canvas. Drag typed components, wire them, label edges, mark scaled tiers as distributed. If it is not on the board, it is not in your design.

    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."

    Design choices interviewers probe

    Read this before you go in. These are the decisions, and why they matter.

    Size the postings, not the vocabulary

    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.

    Word-sharding vs document-sharding

    The 21 TB index must be partitioned across ~150 servers. Two natural keys, opposite failure modes.

    • By word: 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.
    • By tweet (document): 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.

    Time-ordered TweetIDs

    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.

    The rebuild story

    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.

    Freshness

    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.

    Ranking without shipping everything

    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.

    Deleting a tweet

    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.

    Reference solution

    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.

    Requirements (lock these or take the defaults)

    • Store every tweet durably; search across all of them by word
    • Boolean queries: terms joined with AND / OR; text only
    • Sort modes: latest first (default), best matched, most liked; paginated
    • Scale: 1.5B users, 800M DAU; 400M tweets/day at ~300 bytes; 500M searches/day
    • Freshness: not pinned — propose a bound (under a minute) and design to it; asking is a strong signal
    • Recent tweets are searched far more — that licenses hot/cold tiering
    • Out of scope unless wrap-up: phrase/prefix/typo queries, media, trending, personalization

    Capacity

    • Storage: 400M × 300 B = 120 GB/day (~1.4 MB/s); five years ≈ 200 TB → ÷ 0.8 disk-fill × 2 copies = 500 TB → ~125 DB servers at 4 TB
    • IDs: 400M × 365 × 5 ≈ 730B tweets in five years; fits 2^40 → 5-byte TweetID from an ID service
    • Index — the chain that gets graded: keep the last 2 years in memory = 292B tweets; × 5 B = 1,460 GB of IDs; × ~15 indexed words per tweet (40 words minus stop-words) ≈ 21 TB; ÷ 144 GB RAM ≈ ~152 index servers. The vocabulary itself is 2.5 MB — noise.
    • Rates: 400M ÷ 86,400 ≈ 4,600 tweets/s (~70K postings inserts/s); 500M searches ÷ 86,400 ≈ ~5,800 queries/s

    Rough numbers are fine; the ×15 postings step and the two-year scoping move are what get graded.

    Components to put on the board

    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)
    
    • App Server (Service). Accepts tweets and searches. Parses the boolean expression, and after the aggregator returns IDs, hydrates them into full tweets. Mark distributed behind the load balancer.
    • ID Service (Service). Hands out 5-byte time-ordered TweetIDs. Without time-ordering, "latest first" and range filters stop being free.
    • Tweet DB (MySQL). ~125 shards keyed by hash(TweetID), each with a fault-tolerance copy. The chapter starts from a two-column MySQL table. This is durability; search never scans it.
    • Index Builder (Worker). Tokenizes, lowercases, drops stop-words, appends (TweetID, popularity) to ~15 postings lists on the owning index shard, and records the ID in the reverse map. Replicated — it is where the rebuild story lives.
    • Index Server (Service, ×~152). An in-memory partition of the inverted index: word → sorted postings. Primary plus secondary replica each. Evaluates the full boolean expression locally and returns its top page.
    • Aggregator (Service). Fans each query to all index shards, merge-sorts the partial top-k lists, pages the result. Several behind the load balancer; it is the component that makes document-sharding viable.
    • Hot Tweets (Memcached). LRU cache in front of the database for the hydration step. Interest in a tweet decays with time, so LRU fits.
    • Ingest (Kafka, optional). Buffers the write burst between app tier and Index Builders; a lagging index server catches up by replaying.

    Walk it: tweet 101 "India wins the cricket final", then query india AND cricket

    1. The App Server gets a 5-byte TweetID (101) from the ID Service and writes the tweet to Tweet DB shard hash(101) plus its copy.
    2. The tweet passes to an Index Builder, which tokenizes, drops stop-words ("the"), and keeps ~4 terms: india, wins, cricket, final.
    3. The builder appends (101, popularity 950) to each term's postings list on index shard hash(101), and adds 101 to that shard's HashSet in the reverse map. The tweet is now searchable — seconds after posting.
    4. A user searches india AND cricket, latest first. An App Server parses the expression and hands it to an Aggregator.
    5. The Aggregator fans out to all ~152 index shards. Each intersects its local india and cricket lists — a linear merge, since postings are sorted by time-ordered ID — and returns only satisfying IDs, newest first, capped to the page size. Here: {101}.
    6. The Aggregator merge-sorts the partials, takes the top page, and returns the IDs with a page_token cursor.
    7. The App Server hydrates 101 from Memcached (fallback: its DB shard) and assembles user name, text, timestamp, likes.

    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.

    Schema

    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
    
    • Tweet DB sharded by hash(TweetID) across ~125 servers, one extra copy each
    • Index sharded by hash(TweetID) (document-sharding) across ~152 in-memory servers, primary + secondary
    • No public index API — indexing is an internal consequence of posting

    Scaling and wrap-up

    • Aggregator bottleneck: more aggregators behind the LB, hierarchical partial aggregation, tighter per-partition top-k
    • Hot/cold tiering: two years in RAM, older on disk with relaxed latency; a query planner routes by time range
    • First metrics: post-to-searchable lag, p99 query latency, per-shard memory skew
    • If time: phrase/proximity queries (positions in postings — a big multiplier on 21 TB), CJK tokenization, spam filtering before indexing, trending as a by-product of the write stream, social-graph ranking at the aggregator

    Equally defensible variants

    Word-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.

    More in System Design Interview Prep: AI Coach Edition

    • SD Coach · Unique IDs and the URL Shortener
    • SD Mock · Design Pastebin
    • SD Coach · News Feeds and Typeahead
    • SD Mock · Design Facebook News Feed
    • SD Mock · Design Twitter
    • SD Mock · Design Typeahead Suggestion
    • SD Coach · Rate Limiting
    • SD Mock · Design an API Rate Limiter
    • SD Coach · Event-Driven Systems and Notifications
    • SD Mock · Design a Notification System
    • SD Coach · Async Jobs, Schedulers and Crawlers
    • SD Mock · Design a Web Crawler
    View the full course (43 sessions) →