Data & analytics
Full-text search - the inverted index and the shard that is slow
How an inverted index answers a query across shards, and why the slowest shard sets every response time.
What this board gets wrong on purpose
The tension
Documents are partitioned by id across 24 shards, which makes indexing local and cheap and makes every query touch all 24 - so query latency is the maximum of 24 shard latencies, and with each shard slow 1 percent of the time, 21 percent of queries see a shard's p99. The defences each cost something real: hedging a second request to a replica after the p95 adds about 5 percent load and does nothing when the slowness is the query itself; fewer, larger shards cut the fan-out but make a shard recovery copy 120 GB instead of 40; partitioning by TERM instead means a query touches only the shards holding its terms, but a two-word query becomes a cross-shard join and the shard holding "the" melts. Relevance has its own quiet error: each shard scores with its own document frequencies, so a rare term looks common on one shard and the merged top 10 is not the true top 10 unless you pay a second round trip. Deep pages are a fan-out multiplier - page 500 asks every shard for its top 5,010. And the index is a derived copy that trails the database by a refresh interval plus the change stream's lag, so a product taken down at noon can still be found at 12:00:02, and anything that needs read-your-write must go to the database instead.
Practise this as an interview
Take Full-text search - the inverted index and the shard that is slow as a timed system design interview on a blank board - on your own, with the requirements to check yourself against, or with a candidate you invite.
Start here
Why this design
Product search, log search, help-centre search and code search are all the same machine: an inverted index, split into shards, queried by scatter-gather. Elasticsearch, OpenSearch, Solr and Vespa differ in the details and not in the shape. The interview question "design search for a store with 200 million products" is really three questions - how is a document turned into terms, how does a query find and rank the documents holding them, and what happens when the index is spread over 24 machines - and the third is where most answers stop too early.
What you will learn
- What an inverted index is on disk: a term dictionary, posting lists of doc ids compressed with delta encoding, and why the same analyzer must run at index and query time.
- How BM25 scores a match and how WAND skips most of a posting list to find the top 10 without scoring everything.
- Why a document-partitioned query waits for every shard, and the exact number: 1 - 0.99^24 = 21 percent of queries meet a slow shard.
- What hedged requests buy (p99 from 140 ms to about 45 ms) and what they cost (about 5 percent more load).
- Why a document is searchable one second after it is written: immutable segments, refresh, and merge.
- The sizing: 200 M documents, 1 TB of index per copy, 24 shards of about 42 GB, 12 nodes, 120,000 shard queries a second at peak.
How to read this board
- Press play: eight steps follow one query out to the shards and back, then one product change from the database into a segment.
- ASK: the shopper, the analyzer and the index alias - both parallelograms, because a query passes through them.
- SCATTER-GATHER: the coordinator, three of the 24 shards with the slow one in red, the hedge to a replica, and the merge.
- INDEX: the database, the change stream, the indexer, the in-memory buffer, segments and the merger.
- Pages 1 to 6 in order, then the DATA MODEL: the source rows, the outbox, the index versions, shards, synonyms and the query log that measures the tail.
1 · Requirements
Ask these before drawing anything
- How fresh must results be? One second is the cheap answer. "Immediately after I save" means the product page reads the database and search is allowed to lag.
- What is a match? Exact words, stems ("running" finds "run"), synonyms ("tv" finds "television"), typos, other languages. Every one is an analyzer decision, and changing one later means reindexing everything.
- How is relevance judged? Text score alone, or text plus popularity, price and stock? Business signals are where search quality actually comes from, and they must be in the index to be cheap.
- Are there filters and facets? "Under $100, brand Sony, in stock" is a filter that must be fast, and a facet count per brand is an aggregation over every match, not just the top 10.
- How deep do people page? Almost never past page 5 - but crawlers and exports do, and they are the ones that hurt.
- Is the tail or the average the target? The fan-out makes them very different numbers.
Functional
- Keyword search over title, description and brand with stemming, synonyms and one-edit typo tolerance.
- Filters on price, brand, category and stock; facet counts on brand and category.
- Ranking by BM25 blended with sales rank and a stock boost.
- A product change is searchable within 2 seconds; a takedown disappears within 2 seconds.
- Reindex with a new analyzer without downtime.
Non-functional
- 5,000 queries/s at peak, 1,500 average.
- p50 under 20 ms and p99 under 60 ms at the coordinator, top 10 results with facets.
- 2,000 document updates/s sustained, 20,000/s during a catalogue import.
- Losing any node loses no data and no availability; losing a zone degrades latency, not results.
- Results are deterministic for a given index state - the same query twice returns the same order.
Out of scope
- Semantic or vector search. It is a second retrieval path with its own index and is blended in at ranking, not a change to this one.
- Personalised ranking per user.
- Search over data the user is not allowed to see - per-document permissions are a filter problem big enough for its own board.
The rest of this board
Available on Tier Slate
This page publishes the question. The answer — 5 more written pages, an 8-step narrated walkthrough and a 6-table schema — is the board itself, and it opens in Tierslate.
- 5written pages
- 8walkthrough steps
- 6tables41 columns
5 pages behind this one
- Capacity estimation
- Storage estimation
- Availability
- How it works
- Deployment plan
More boards
Pipelines, metrics and the lag between event and answer.
- Ad serving - an auction inside a page load
- Analytics pipeline - the lag between an event and the answer
- Log aggregation - the index is bigger than the data
- Metrics and monitoring - cardinality is the thing that kills you
- Recommendation engine - retrieve a thousand, rank twenty
- Leaderboard - a sorted set and the rank nobody stores
- Search autocomplete - an answer before the word is finished
- View counter - counting a million clicks without a million writes
- Uptime monitor and status page - checking from outside
- A/B testing platform - assignment is the easy half
- ETL and the data warehouse - yesterday, correctly