Design Twitter search

01Functional requirements

A search index is a separate structure built from posts to find matching text quickly. A new post appears only after a background program copies its words into the index and the search engine exposes that update. An index hit is therefore only a possible result until the service checks the post’s current text, deleted state and audience. We will follow three short posts and a garden search through that path.

1. FR1: Match explicit text queries. Search existing post text using AND, OR or quoted phrases. A phrase requires words in the requested order at adjacent positions. Use the same analyzer, meaning the same text-to-term rules, for stored posts and queries.

2. FR2: Filter and order results. Apply author/time filters and offer recent-first or an explicitly requested relevance order with documented tie-breakers. A filter never grants that author's private permissions.

3. FR3: Page a query view. Return size-limited result pages with a continuation cursor tied to the chosen index view and order. Report when the cursor expires or a required index partition is unavailable. Return partial results only under an explicitly supported partial-results contract.

4. FR4: Reflect source changes. Process post creates, edits and deletes into a recoverable search index, while reporting that new posts can take time to become searchable.

5. FR5: Enforce current visibility. Return only bodies, snippets and metadata the caller may currently read. The source post/version/audience remains authoritative, including during reranking.

Out of scope

• Media-content search, typeahead, direct-message search and generated answers.
• Exact live counts/facets without an equivalent current-visibility mechanism.
• Meaning-based retrieval under the existing word-matching modes; introduce a semantic mode explicitly if related wording should also qualify.

Example: For p81 “Garden opens Saturday”, p82 “Garden sale Sunday” and p83 “Library opens Saturday”, AND garden saturday yields p81 before current-state filtering.

02Nonfunctional requirements

Planning load: ten million new posts and 200 million searches/day, with an illustrative tenfold query peak. These are proposed interview targets to validate under the stated conditions.

1. NFR1: Query latency. At least 95% of measured primary-region queries must finish within 300 ms at the agreed peak, including checks against current source records. Cap query terms, phrase length, page size and work sent to index partitions.

2. NFR2: Search freshness. An ordinary new post should become searchable within five seconds of being saved in the main post database. Include time waiting for the indexer and time before the search engine exposes indexed changes; a short final refresh cannot hide an upstream backlog.

3. NFR3: Current result correctness. Before returning text or snippets, verify the current source version, deletion state and audience. If the post changed since indexing, drop it or test the query again on the permitted current text. If a required private-permission check is unavailable, omit the result or fail the request rather than expose unchecked content.

4. NFR4: Recoverable indexing. A successfully saved post change must remain recoverable for indexing after a worker crash. Keep its pending or replayable change record until the agreed repair policy can recover it. Repeated delivery or delayed older work must not restore a newer deleted post.

5. NFR5: Stable traversal. While its saved index view is valid, a cursor continues one defined result order. Current permission can still remove a result between pages. If the saved view expires, tell the caller to restart rather than silently continue a different ordering.

6. NFR6: Honest completeness. If required shards are unavailable and partial results are unsupported, fail the query. Current filtering may shorten a page; it never permits unchecked filler hits or unfiltered exact totals.

7. NFR7: Bounded AI and cache use. A cached ID or optional model score cannot grant permission or change the requested word-matching rule. Check that returned posts still match AND/OR/phrase requirements and check current visibility again after model scoring.

03Estimate ingestion and query fan-out

Use decimal units:1 KB is 1,000 bytes. Count external queries, their internal index work and retained data separately.

1. New source posts. Ten million posts/day give 10,000,000 ÷86,400 ≈116 creates/second. Edits, deletes, retries and bursts add work. A successful source write needs retained indexing work even if the search program is temporarily down.
2. Queries. Two hundred million searches/day give about 2,315 queries/second. Assume a tenfold peak of 23,150/second. Benchmark the complete query, including current post/permission reads, at that peak.
3. Source bytes. One year at ten million posts/day is 3.65 billion posts. At 1 KB each, source records occupy 3.65 TB before copies. Retention and source storage are separate from the structures used to search words.
4. Index bytes. At a measured planning budget of 2 KB/indexed post, 3.65 billion ×2 KB =7.3 TB. One extra full copy gives 14.6 TB. Partitioning divides that dataset; replicas copy it for recovery and eligible reads.
5. Internal calls. If every query touches 20 partitions, 2,315 ×20 =46,300 partition requests/second on average, or about 463,000 at peak. Each additional partition adds coordination. Time filters can avoid older partitions only when the query truly excludes their data.
6. Posting IDs. At 20 distinct terms/post and eight bytes per uncompressed posting ID, new IDs alone use 10 million ×20 ×8 =1.6 GB/day, or 11.2 GB over seven days. Word positions, term dictionaries, caches and copies add space; compression changes the actual result.
7. Candidate verification. If 20 partitions return 50 IDs each, the coordinator can receive 1,000 candidates for one query. Cap that work and read current metadata in batches. One network call per candidate would multiply latency and load.

The entire index need not fit in memory. Measure compressed disk size and the frequently accessed data kept hot by representative queries before choosing machine counts.

04Define search requests, results and retries

Ben’s client sends a search request to the query handler. The three example posts are p81 “Garden opens Saturday”, p82 “Garden sale Sunday” and p83 “Library opens Saturday”. The handler must find matching words and then check whether Ben may read each current post.

POST /search
Content-Type: application/json

{"terms":["garden","saturday"],"mode":"AND","authorId":null,"before":null,"order":"recent","limit":20,"cursor":null}

{"items":[{"postId":"p81","text":"Garden opens Saturday","version":1}],"cursor":"<index-view-and-sort-key>","partial":false,"indexedThrough":"2026-10-24T12:00:00Z"}

1. Read the query fields. terms supplies the words, mode chooses the supported AND/OR/phrase behavior, and author/time filters narrow the search. order chooses recent-first or the documented relevance order. The example asks for garden AND saturday, returning up to 20 results.
2. Use the caller’s identity. The server obtains Ben’s identity from authentication. authorId is only a filter; typing Mira’s author ID does not grant her private access.
3. Return an honest result. Each item includes its source post ID, permitted text and version. The cursor continues a defined index view and sort position. partial:false means the required index partitions answered, not that every source post has already been indexed.
4. Handle retry and errors. A query is read-only and may be repeated, but results may change without a valid continued view. Return 400 for syntax errors,429 when throttled and 503 when a required partition is unavailable and partial results are unsupported. Reject queries exceeding documented work limits; mark supported partial results explicitly.
5. Keep modes distinct. An optional model may reorder valid matches for an explicit relevance request. Meaning-based retrieval requires a separately introduced semantic mode; it must not silently turn an AND or phrase query into “related wording.”

05Choose source records and index access paths

The main post database accepts creates, edits, audience changes and deletes. Search keeps another, rebuildable representation for word lookup. It is not a second place to decide the latest body or permission.

• Source-change recording: the post handler saves a change record with the post in one transaction. This pending work table is an outbox. A relay reads it and notifies the indexer, the background program that updates search structures.
• Text analysis: the indexer converts text into stored terms. Lowercasing makes Garden match garden; splitting text into words is tokenization. Optional stemming groups related word forms. The query handler must apply the same chosen rules.
• Version checking: the search document stores the source version it represents. Before applying an event, the indexer compares that version with the highest version already accepted for the same post ID. Repeated or older versions do not replace newer state.
• Deletion evidence: after deleting a document, retain its highest deleted version, called a tombstone. Otherwise delayed older creation work could insert it again.
• Phrase support: postings retain word positions when phrase matching is required. A list of matching document IDs alone does not show whether two words were adjacent.
• Recovery: the post ID joins search candidates to the main record. The query handler uses it to verify current version, text eligibility and audience before returning bodies or snippets.

06Make the derived index recoverable

First search the three example posts on one logical index. An inverted index maps a word to the post IDs containing it. Each word’s ID list is a posting list.

Build searchable records

1. The post handler commits p81/version 1 and its pending search-change record in the main database. Acknowledging that source write does not yet make it searchable.
2. The relay reads the pending record and sends it to the indexer. If the send worked but the relay crashed before recording progress, it may send the same record again.
3. The indexer looks up p81’s accepted source version. For a new version, it replaces that post’s indexed terms and records the version together. An equal-version retry does not add another logical document; an older version is rejected.
4. The search engine performs a refresh, making newly indexed changes visible to new queries. Waiting for the relay, indexing and refresh contribute separately to the five-second freshness target.

Answer Ben’s query

1. The query handler applies the same text rules to garden and saturday. Garden’s list is [p81,p82]; saturday’s is [p81,p83].
2. For AND, retain IDs present in both lists: only p81. For OR, combine and remove duplicates to obtain p81,p82,p83.
3. For the phrase “garden opens”, also inspect the word positions in p81. Garden followed immediately by opens qualifies; both words appearing somewhere would not prove the phrase.
4. Order candidates by the chosen rule, initially recency with a stable time/ID tie-break. Read the main post records and permission needed for the caller.
5. Return p81’s current permitted text only if its current version still qualifies. If it changed since indexing, omit it until catch-up or re-evaluate the query on the permitted current text.

One indexer can read outbox records directly and maintain one logical dataset with a replica. A separate log service is not required for this small baseline. Retain source work for replay: being visible to a search is not itself proof that a lost index can be reconstructed.

07Compare term sharding with document sharding

A partition, also called a shard, owns only part of the index. Decide what is divided before adding machines.

Follow document sharding for Ben’s AND query:

1. The coordinator, the query program combining answers, sends garden AND saturday to A and B.
2. A looks up garden [p81] and saturday [p81,p83], so its local intersection is p81.
3. B looks up garden [p82] and an empty saturday list, so its local result is empty.
4. A and B return local matches; the coordinator merges them and performs the current-source checks before returning text.

Each shard still has an inverted index. Document sharding does not mean scanning all raw post bodies. More shards spread storage but add calls:20 queried shards at 2,315 external queries/second produce about 46,300 internal calls/second before retries. Read replicas are additional copies of a shard, not further division of its documents; the chosen copy must meet the freshness rule.

First test whether a larger search machine meets measured needs. Add document shards when storage, ingestion or query work no longer fits one logical partition. The next architecture stage also exposes a durable log between the source and indexers so separate workers can resume their own change streams.

08Distribute queries and state the ranking cost

Keep the same query and permission checks when requests span many machines:

1. Place documents. Hash a post ID to its document owner. That owner’s indexer maintains term lists for its assigned posts. Replicas can share eligible query load.
2. Request local matches. The coordinator sends Ben’s query to every relevant shard and asks for a bounded number of its best matching IDs. A required missing shard must fail the request unless the API explicitly supports partial results.
3. Merge one order. Combine recent-first results using the same time/ID sort. For relevance, use scores with compatible meaning across shards; arbitrary local score scales cannot be compared just because both are numbers. Use the search engine’s supported distributed scoring behavior.
4. Check current records. Read source metadata in batches, remove repeated IDs and reject deleted, forbidden or mismatched results. Fetch extra candidates only within a work limit; current filtering may leave a short page.
5. Continue a defined view. A point-in-time view retains a fixed searchable index state for a limited lifetime. A search-after cursor records the last sort key within that view so the next page continues after it. If the view expires, tell the client to restart.
6. Keep permission current. The view freezes index traversal, not source audience rules. Each page still checks present access; a post becoming private must disappear from later responses even if the old view lists it.

Time-bucket indexes group posts by age for retention and time-filtered queries. Include every bucket the query can match. Hashing inside a bucket can spread recent writes. These savings are useful only when their extra routing and maintenance cost fits the measured workload.

09Rebuild safely and choose the next optimization

Separate recovery from optional caching. A replica can replace a failed node, but a lost dataset or changed index schema requires reconstructing search data.

Rebuild while posts continue changing

1. Take a consistent source snapshot and record which change-log position it includes, or the corresponding positions for partitioned logs. This saved boundary is the snapshot’s watermark.
2. Copy that snapshot into a new index generation. Keep later creates, edits and deletes in the retained log while the copy runs.
3. Replay changes after the saved watermark. If p82 changed during copying, this step updates its copied old version before the new index serves readers.
4. Compare expected record counts and run known queries that include a new post, an edit and a deletion. Confirm those cases reflect the replayed source versions. Only then switch the reader alias, the stable name pointing readers to the chosen index generation.
5. Keep the old generation until rollback needs and existing cursor lifetimes are resolved. Retain deletion versions while older events may still be replayed; otherwise a rebuild can restore removed posts.

Cache only when repeated queries waste significant shard work

1. The coordinator builds a key from normalized query, filters, order, access context and index generation.
2. On a miss, it uses the shard path and stores a bounded candidate-ID list with its index-view context.
3. On a hit, it saves that index work but still reads current source version and permission before producing text or snippets. A cache entry is not a lasting grant.

Measure source-to-search delay, oldest unapplied change, shard timeouts, removed stale candidates and expensive-query resource use. Cap phrase, wildcard and broad-prefix work where supported. More frequent refresh can shorten final visibility delay but adds indexing work; it cannot drain an upstream backlog by itself.

10Trace a post change and a search

Use Ben’s query and Mira’s p81 deletion to test the complete path:

1. Mira’s post handler saves p81/version 1 with its pending search change. The indexer records its terms/positions and refresh makes it searchable.
2. Ben’s query handler normalizes garden and saturday, then each required shard intersects its local lists.
3. The coordinator combines candidates and reads their current source metadata in batches. It checks Ben’s permission, deletion state and source version before returning p81’s text or a snippet.
4. Mira deletes p81 at version 2. A new source read now sees deletion, so the query handler returns no p81 body even while an old index view or cache contains its ID.
5. The indexer removes p81 and retains deletion version 2. If a delayed version 1 event arrives, its version comparison rejects it rather than inserting the document again.
6. If Mira instead edited out saturday, an old index hit is no longer evidence of a current match. Drop it until reindexing or test the query against permitted current text.

Do not expose unchecked exact totals or facets either. If a count includes private hits without equivalent current checks, it can leak their existence even when bodies are omitted. Leave exact totals out unless the design can enforce the same visibility rules.

11Protect correctness and measure the pipeline

Name which program can continue and which result is no longer established:

1. The indexer stops. Source posts can remain saved with their outbox work while search grows older. Measure oldest unapplied work and source-to-search delay; slow intake when finite backlog limits require it. A successful query response must not hide growing lag.
2. Delivery repeats. The indexer compares (postId,sourceVersion) with saved version state. Equal versions do not create another document; lower versions cannot overwrite a newer edit or deletion.
3. A document was removed but old work remains. Keep the deletion version until that work can no longer return. Physically removing only the searchable body forgets why an old create must be rejected.
4. A required shard is missing. Fail rather than return an apparently complete answer from only the available shards. Supported partial responses must be explicitly marked.
5. Private verification is unavailable. Omit unchecked content or fail under the agreed policy. Neither a cached snippet nor a snapshot supplies current permission.
6. A query is too expensive. Bound terms, phrases, scans and per-shard work, rate-limit excessive callers and watch slowest responses. Adding shards can increase query calls and waiting as well as capacity.

Replicas, retention and frequent refresh trade storage and processing cost for availability and freshness. They do not replace the main-source checks protecting current access.