Problem RestatementProblem
Design product search for a large marketplace (asked at Amazon). Users type free text ("running shoes") and add filters: price range, brand, rating, and nested categories (Clothing → Shoes → Running). The results page also shows facets, lists of filter values with counts ("Nike (1,203)", "Adidas (987)"), which update as filters are applied. The catalog and traffic are huge, filters combine freely, and results need stable pagination.
RequirementsRequirements
- Full-text search with relevance ranking.
- Filters: numeric ranges (price), exact values (brand, color), a category tree, availability.
- Facet counts for the current query and filters.
- Sorting: relevance, price, rating, newest.
- Pagination that doesn't repeat or skip items.
- Latency under ~200 ms at thousands of QPS, and catalog changes visible within minutes.
1.1 Scale
- 500M products, 20K search QPS at peak.
ArchitectureArchitecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
CAT[("Catalog DB")] -->|"CDC changes"| K[("Kafka")]
K --> IDXR["Indexer - build search documents"]
IDXR --> ES[("Search cluster - shards x replicas")]
U["Shoppers"] --> API["Search API"]
API --> QC[("Query cache")]
API --> ES
API --> RR["Re-ranker - personalization"]
PR["Price / stock updates"] --> KA search engine like Elasticsearch/OpenSearch (or a custom Lucene-based system) holds the index.
Index Design
Each product becomes a document:
{ "product_id": 991, "title": "Men's Trail Running Shoe", "brand": "Nike",
"category_path": ["clothing", "clothing/shoes", "clothing/shoes/running"],
"price_cents": 8999, "rating": 4.4, "in_stock": true, "attributes": { "color": ["blue","black"], "size": ["9","10"] },
"sales_rank": 1234, "created_at": "2026-08-01" }- Text fields (title, description) go into an inverted index: word → list of products.
- Filter and facet fields (brand, color, price, category) are stored as doc values (column-style storage), which makes filtering and counting fast.
- Nested categories: store every ancestor path (
clothing,clothing/shoes, ...). Filtering on "Shoes" matches all subcategories with one term, and facet counts per level come from these terms.
Query Execution
- Parse the text, and match against the inverted index (with synonyms and typo tolerance).
- Apply filters as fast bitset operations (they don't affect scoring and are cacheable).
- Score matches (BM25 text relevance + business signals like sales and rating) and take the top N.
- Compute facets with aggregations over the matching set: terms counts for brand and color, range buckets for price, category counts.
- Multi-select facets: when the user selects Brand = Nike, the brand facet should still show counts for other brands (computed with all filters except brand). This is done with "post filters" or separate aggregations per facet.
Deep Dive — Paging through results that keep changingDeep dive
The user scrolls to page 12 of "running shoes" while the catalogue is being reindexed continuously.
OFFSET 220 LIMIT 20
Ask the search engine to skip the first 220 results and return the next 20.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
P12["Page 12 - offset 220"] --> SHARD["Every shard must produce its top 240"]
SHARD --> MERGE["Coordinator merges, discards 220"]
MERGE --> COST["Cost grows with the page number"]
NEW["A product is indexed while the user reads page 11"] --> SHIFT["Everything shifts by one"]
SHIFT --> DUP["An item seen on page 11 appears again on page 12"]Deep offsets are expensive — each shard computes and ships results that are immediately thrown away — and unstable, because the offset is a position in a list that is changing underneath the reader.
A search_after cursor
Instead of a position, remember the sort values of the last item and ask for results after them. Cost no longer grows with depth, because each shard seeks directly into its sorted index.
Nearly right, and it has a subtle failure: when several products share the same sort value — the same price, the same rating — "after this value" is ambiguous, so items can be skipped or repeated at the boundary. On a marketplace where thousands of items cost exactly $49.99, that boundary is hit constantly.
Cursor with a tie-breaker, and a snapshot when it matters
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SORT["Sort key: price, then product_id"] --> CUR["Cursor: (49.99, 'B07X...')"]
CUR --> NEXT["search_after - deterministic, no ties possible"]
NEXT --> PAGE["Next 20 - stable and cheap at any depth"]
SESS["Browsing session"] --> PIT["Optional point-in-time snapshot"]
PIT --> FROZEN["Results do not shift while paging"]
LIVE["Product page and checkout"] --> SRC[("Source of truth - live price and stock")]- Append
product_idas the final sort key. It is unique, so no two documents share a full sort tuple and the cursor is unambiguous. This one line is the difference between a cursor that is usually right and one that is always right. - Pin a point-in-time snapshot for the session when stability matters more than freshness. Paging then happens against a fixed view, so nothing shifts mid-scroll.
- Let search be slightly stale. Price and stock updates stream into the index within seconds to minutes, and that is fine — because the product page and checkout read the source of truth, so nobody is charged a price the index happened to be holding.
That last division is the one to state: search optimises for recall and latency across millions of documents; money optimises for correctness on one row. Trying to make the search index transactionally correct is how both goals get lost.
PerformanceScale
- Shards split the 500M documents (e.g., 50 shards × ~10M docs), and replicas multiply query capacity.
- Caching: a filter cache (bitsets for common filters like
in_stock=true), and a query-result cache for popular searches (short TTL). - Routing by category or region can limit which shards a query hits.
- Personalization happens as a re-rank of the top ~200 results, to keep the engine query fast.
Wrap-UpWrap-up
Index each product with text fields in an inverted index and filter and facet fields as doc values, storing every category ancestor path for nested categories. Run queries as text match + bitset filters + scoring, compute facet counts with aggregations (excluding a facet's own filter for multi-select), merge shard results, and paginate with search_after cursors and ID tie-breakers. Keep the index fresh via CDC, and scale with shards, replicas, filter and query caches, and a light re-ranking layer.