What it is
Full-text search answers “which documents contain these words, best first?” without scanning every document. The structure that makes it fast is the inverted index: instead of mapping a document to its words, it maps each term to the list of documents that contain it (a posting list). Search engines (Lucene, Elasticsearch, Solr) add two things on top: segments, immutable files that make indexing fast and searchable within seconds, and sharding, which splits the index across machines.
Important
Key takeaway: A search query is a set operation over posting lists, ranked afterward. Keep writes cheap with immutable segments, shard by document (not by term), scope visibility at retrieval time (before ranking), and treat the slowest shard as your p99.
When you care
“Design search for posts or products” asks for the index structure, how new documents become searchable, how it scales, and what happens when results are private. The first answer is the inverted index; the senior follow-ups are freshness, sharding, and visibility.
Note
Interview signal: Saying “I’d filter by visibility at retrieval time, not after ranking, because filtering after wastes most of the ranker’s work and can leave the top K empty” is the most under-prepared point in a search design. It marks someone who has thought about private content.
The inverted index
For three documents:
| Doc | Text |
|---|---|
| 1 | the quick brown fox |
| 2 | the lazy brown dog |
| 3 | quick red fox |
the inverted index (after lowercasing and removing the word “the”) is:
| Term | Posting list (doc ids) |
|---|---|
| brown | 1, 2 |
| dog | 2 |
| fox | 1, 3 |
| lazy | 2 |
| quick | 1, 3 |
| red | 3 |
The query quick AND fox fetches the posting lists for each term, [1, 3] and [1, 3], and intersects them (a linear merge of
sorted lists, accelerated by skip pointers): result [1, 3]. brown OR red is a union. Posting lists also store the
term frequency and the positions within each document, which support relevance scoring and phrase queries (“quick brown”
requires brown to follow quick).
Analysis turns text into terms before indexing and before querying: tokenize, lowercase, remove stop words, and stem (“running” to “run”). The same analysis must run at index time and query time, or terms will not match.
Relevance. Candidates are scored with a text-relevance function, most commonly BM25: it rewards a term that appears often in a document (with diminishing returns, so repeating a word 50 times does not help), rewards rare terms (inverse document frequency), and normalizes by document length. Defaults of around k1 = 1.2 and b = 0.75 are typical. BM25 is the baseline for recall; a learned ranker refines it afterward.
Segments and near-real-time indexing
Rewriting a large index for every new document would be far too slow. Lucene-based engines use segment-based indexing:
- New documents go into an in-memory segment, together with a log for durability.
- Periodically (every second or so) the in-memory segment is refreshed: made searchable, and flushed to disk as an immutable segment.
- A background process merges small segments into larger ones, which also removes deleted documents. Segments are never edited in place.
- Deletes are tombstone markers in a per-segment bitmap, applied at query time and physically removed during a merge.
A query runs against every segment (in-memory and on disk) and merges the results. Near-real-time means a post indexed at time 0 is searchable at about 100 ms to 1 second, not a minute. The trade-off: an in-memory segment is more expensive to scan, and committing more often creates more segments and more merge work, so real pipelines refresh every 1 to 5 seconds. This is the same append-and-merge idea as an LSM-tree.
Worked example: ingest at 50,000 posts per second. One indexer cannot keep up, so partition the stream (for example, by post id, through a log) across many indexer instances, each owning a subset of shards. The log’s partitioning gives the parallelism, and each indexer consumes its partitions independently and builds its own segments.
Sharding the index
The index is too large for one machine (tens of terabytes for a large social network), so it is sharded. Two strategies:
| Dimension | Document sharding (by doc id) | Term sharding (by token) |
|---|---|---|
| Write throughput | Excellent: a write goes to one shard | Poor: a write touches a shard per term |
| Query | Scatter-gather: ask every shard, each returns its local top N, merge | Only the shards owning the query’s terms |
| Multi-word queries | Each shard scores locally | Intersections across shards |
| Hot spots | Spread by hashing | Common terms become hot shards |
| Used by | Elasticsearch, web-scale search | Historically interesting, rarely right today |
Choose document sharding and name its cost: with scatter-gather the slowest shard sets query latency, so shard-level p99 matters more than cluster-level p50. Mitigations:
- Request hedging: if a shard has not answered by its p95 latency, send the query to a replica.
- Per-shard timeouts with partial results: return what came back in 200 ms and drop the slow shard (“results may be slightly incomplete” beats a timeout).
- Replica selection by load: route to the least-loaded replica, not round robin.
Visibility and access control
The hardest problem in searching private content. The naive design retrieves candidates, ranks them, then filters by what the searcher may see. If only 10% of candidates are visible, the ranker wastes 90% of its work, and the top K can be empty after filtering. Instead, scope visibility at retrieval time, before ranking:
- Visibility tags in the index. Each posting carries a scope (
public, or a small-cardinality group id). The query supplies the searcher’s identity and group ids, and the index returns only postings whose scope intersects. Good for public and group-scoped content. - Per-user indexes for restricted content. For “friends only” posts, keep a smaller index per user of their friends’ posts, query it in parallel with the public index, and merge.
- A final check as defense in depth. Even with scoping, verify visibility before returning anything. Never rely on a single filter to protect private content.
Caution
Common mistake: Filtering for permissions after ranking. It wastes compute and leaks timing and result-count information; at scale it also returns short or empty pages. Put the permission filter into retrieval.
When to pick what
| Need | Choose | Why |
|---|---|---|
| Keyword search over documents | An inverted index | Set operations over posting lists |
| New content searchable within seconds | Segments with a short refresh interval | Immutable, mergeable |
| Scale beyond one machine | Document sharding with scatter-gather | Cheap writes; even load |
| p99 dominated by one slow shard | Hedged requests, partial results | Tail latency control |
| Private or group content | Visibility scoped at retrieval | Avoids wasted ranking and empty pages |
| Relevance beyond BM25 | A second-stage learned ranker | Refines the BM25 candidates |
Related
- Walkthrough: Designing a Post Search System — the full search design, freshness and private content included.
- Reference: Two-Stage Ranking and the Retrieval Funnel — what happens to the candidates once the index has returned them.
- Walkthrough: Designing a RAG System — keyword retrieval blended with vector search in a hybrid retriever.