FINDING NEEDLES · CHAPTER 18
Every chapter so far asked how to score well. A live search box also has to answer in 100 milliseconds, for thousands of people, while the catalogue changes underneath it.
An online furniture shop sells 2,000,000 products. Someone types “oak dining table”. The page has 100 ms to show twenty results, or it feels slow and they leave.
You already have every piece you need. BM25 from chapter 3. Dense retrieval from chapter 7. Reciprocal rank fusion from chapter 10. A cross-encoder from chapter 9. The question in this chapter is not which piece scores best. It is how much each piece may cost, and on how many products.
Think of hiring. You do not interview two million people. A quick filter reads every CV and keeps a thousand. A phone screen keeps a hundred. Only twenty get the long interview. Each stage spends more time per person on fewer people. Search architecture is that same funnel, with a stopwatch on it.
The first stage must have high recall. If the right table is not in its 1,000, nothing later can bring it back. The last stage must have high precision. It only orders what it is handed.
lunch · pipeline · SLO · canary
The per-document costs are what force the shape. The cross-encoder costs 0.4 ms per product. Run it over all 1,000 candidates and that one stage takes 400 ms, four times the whole budget. Run it over the whole catalogue and it takes 2,000,000 × 0.4 ms = 800 seconds. The index exists so that the first stage never has to look at most products at all.
Write every stage down with what it costs. A fixed cost per query, plus a cost per document times the documents it reads.
| Stage | Reads | Cost |
|---|---|---|
| Parse the query | — | 5 ms |
| BM25 (12 ms) and ANN (18 ms), in parallel | the index | 18 ms |
| Fuse with RRF | 1,000 | 2 ms |
| Feature ranker | 1,000 × 0.01 ms | 10 ms |
| Cross-encoder | 100 × 0.4 ms | 40 ms |
| Snippets and page | 20 | 5 ms |
| Total | 80 ms |
80 ms against a budget of 100 ms leaves 20 ms of slack for the network and for bad days. The two retrievers run at the same time, so that row costs the slower one, 18 ms. Run them one after the other and it would cost 12 + 18 = 30 ms. Parallel stages cost their maximum. Sequential stages cost their sum.
each stage pays once per query, plus once per document it reads. Two stages that run side by side cost only the slower of the two.
Now ask the useful question: how deep can the cross-encoder go? Everything except the cross-encoder costs 40 ms. That leaves 60 ms, and 60 / 0.4 = 150 documents. Rerank 150 and you land exactly on 100 ms. Rerank 200 and you are at 120 ms, over budget. Depth is the knob that trades quality for time.
Interactive · Spend the budget
How deep can the reranker read, and what does a cache buy you?
Search traffic repeats itself. “sofa” is typed thousands of times a day, and the answer does not change between the first and the second time. A cache keeps recent result pages keyed by the query. A hit costs a 1 ms lookup. A miss costs the lookup plus the full funnel, 1 + 80 = 81 ms.
Replay ten queries through a cache that holds three. When it is full, it throws out the query used least recently.
| # | Query | Result | Cache after (oldest first) |
|---|---|---|---|
| 1 | sofa | miss | sofa |
| 2 | oak table | miss | sofa, oak table |
| 3 | sofa | hit | oak table, sofa |
| 4 | desk lamp | miss | oak table, sofa, desk lamp |
| 5 | sofa | hit | oak table, desk lamp, sofa |
| 6 | oak table | hit | desk lamp, sofa, oak table |
| 7 | bookshelf | miss | sofa, oak table, bookshelf |
| 8 | sofa | hit | oak table, bookshelf, sofa |
| 9 | rug | miss | bookshelf, sofa, rug |
| 10 | oak table | miss | sofa, rug, oak table |
4 of 10 queries hit. Query 10 misses even though “oak table” was seen twice: the cache was too small to keep it. The average latency is now
hits cost the lookup, misses cost the lookup plus the funnel. With h = 0.4 the average falls from 81 ms to 49 ms.
Push the hit rate to 0.8 and the average drops to 17 ms. But look at what did not move. Every miss still takes 81 ms. The rare, long query, the one a cache never sees twice, is exactly the slow one. A cache fixes the average. It does nothing for the slowest 1% of queries, which is the number people complain about.
A cached page also goes stale. When the oak table sells out, its cached pages must expire or be thrown away. That is the next problem.
An inverted index is fast because its postings are packed and sorted. Rewriting them on every price change would be slow. So engines in the Lucene family write new documents into a small new segment and never edit an old one. A refresh, by default about once a second in Elasticsearch, makes the new segment searchable. That is called near-real-time search.
A delete cannot edit the old segment either. It adds the id to a list of tombstones. The postings still contain the product. Search skips it at query time.
| Id | Product | State |
|---|---|---|
| 101 | oak dining table | live |
| 102 | oak bench | tombstone (sold out) |
| 103 | pine dining table | live |
| 104 | oak desk | live |
| 105 | walnut dining table | tombstone (sold out) |
The postings for “oak” are still [101, 102, 104]. With the tombstones applied, the search returns 101 and 104. Later a background merge rewrites small segments into one bigger one and drops the dead ids for good. An update is a delete plus a fresh insert.
Freshness has a worst case you can add up too. If your ingestion pipeline (parse, enrich, embed) takes 4 seconds and the refresh runs every second, a sold-out sofa can still show for up to 4 + 1 = 5 seconds. Faster refresh means more tiny segments and more merging. That is the trade.
A hybrid shop keeps a text index and a vector index. They are written by different workers, and the vector side waits for an embedding model. For a few seconds a new product can exist in BM25 and not yet in ANN. Fusion must accept a candidate that only one side returned, and the delete must reach both indexes, or the dense side will keep showing a product the text side already removed.
One machine may not hold 2,000,000 products and their vectors, or answer every query alone. Split the catalogue into 4 shards of 500,000 products each. A coordinator sends the query to every shard and merges what comes back.
Two consequences follow. First, every shard must return its own top 1,000. The best 1,000 overall could all live on one shard. The coordinator merges 4 × 1,000 = 4,000 candidates and keeps 1,000. Second, the coordinator waits for every shard. With shard times of 15, 16, 17 and 18 ms, the stage takes 18 ms. If one shard has a slow moment at 40 ms, the whole query takes 40 ms. With more shards, it gets more likely that at least one of them is slow on any given query. Engines fight this by sending a duplicate request to a second copy when the first is late.
Split the data. Each one holds a part. You add shards when the index outgrows a machine.
Copy a shard. Each copy holds the same part. You add replicas when the traffic outgrows a copy, or for safety when a machine dies.
At peak the shop sees 900 queries per second. One copy of a shard handles 200. Each shard needs ⌈900 / 200⌉ = 5 copies, so the cluster runs 4 × 5 = 20 copies of shards in all.
Then you watch it. Track the 50th and 99th percentile latency per stage, the cache hit rate, how often a stage times out, and how many results a query returns. When the cross-encoder runs late, a good system skips it and serves the feature ranker’s order. A worse page beats an error page.
The costs are invented, but the arithmetic is the same arithmetic you would do with real measurements.
"""A latency budget, a query cache and tombstones for a toy furniture shop.
Every number is made up but round, so you can redo it by hand.
Real shops measure these costs; the arithmetic stays the same.
"""
import math
CATALOGUE = 2_000_000 # products in the shop
BUDGET_MS = 100 # what the search box may spend per query
# Candidate generation: two retrievers run side by side (chapter 10).
BM25_MS = 12
ANN_MS = 18
# The funnel after that. Per-document costs are in milliseconds.
RERANK_MS_PER_DOC = 0.4
def funnel(depth=100):
"""Each stage: (name, fixed ms, ms per document, documents in, documents out).
`depth` is how many candidates the cross-encoder reads.
"""
return [
("parse query", 5, 0.0, 0, 0),
("retrieve (BM25 + ANN)", max(BM25_MS, ANN_MS), 0.0, CATALOGUE, 1000),
("fuse with RRF", 2, 0.0, 1000, 1000),
("feature ranker", 0, 0.01, 1000, depth),
("cross-encoder", 0, RERANK_MS_PER_DOC, depth, 20),
("snippets + render", 5, 0.0, 20, 20),
]
def stage_ms(stage):
"""Fixed cost plus per-document cost times how many documents go in."""
_, fixed, per_doc, docs_in, _ = stage
return round(fixed + per_doc * docs_in, 3)
def total_ms(depth=100):
return round(sum(stage_ms(s) for s in funnel(depth)), 3)
def rerank_cost_ms(depth):
"""Cross-encoder cost if it had to read `depth` documents."""
return round(depth * RERANK_MS_PER_DOC, 3)
def max_rerank_depth(budget=BUDGET_MS):
"""Deepest rerank that still fits: everything else is fixed."""
rest = total_ms(0)
return int(round((budget - rest) / RERANK_MS_PER_DOC, 6))
# A cache in front of the whole funnel.
CACHE_MS = 1
QUERY_LOG = [
"sofa", "oak table", "sofa", "desk lamp", "sofa",
"oak table", "bookshelf", "sofa", "rug", "oak table",
]
def lru_hits(log=QUERY_LOG, capacity=3):
"""Replay the log through a least-recently-used cache. Return hit flags."""
cache = [] # most recent at the end
flags = []
for query in log:
if query in cache:
cache.remove(query)
flags.append(True)
else:
if len(cache) == capacity:
cache.pop(0) # evict the least recently used
flags.append(False)
cache.append(query)
return flags
def mean_latency_ms(hit_rate, miss_ms):
"""A hit costs the lookup. A miss costs the lookup plus the funnel."""
return round(hit_rate * CACHE_MS + (1 - hit_rate) * (CACHE_MS + miss_ms), 3)
# Freshness: a segment never changes. Deletes are marks, not erasures.
SEGMENT = {101: "oak dining table", 102: "oak bench",
103: "pine dining table", 104: "oak desk", 105: "walnut dining table"}
TOMBSTONES = {102, 105} # sold out, marked deleted
def search_segment(word, segment=SEGMENT, deleted=TOMBSTONES):
"""Match inside the immutable segment, then skip tombstoned ids."""
hits = [doc for doc, text in sorted(segment.items()) if word in text.split()]
return [doc for doc in hits if doc not in deleted]
def merge(segment=SEGMENT, deleted=TOMBSTONES):
"""A merge writes a new segment without the dead documents."""
return {doc: text for doc, text in segment.items() if doc not in deleted}
def worst_staleness_s(pipeline_lag_s=4, refresh_s=1):
"""A change becomes searchable after the pipeline and the next refresh."""
return pipeline_lag_s + refresh_s
# Shards and replicas.
SHARDS = 4
SHARD_MS = [15, 16, 17, 18] # ANN time on each shard; the slowest decides
def per_shard_docs(catalogue=CATALOGUE, shards=SHARDS):
return catalogue // shards
def fan_out_ms(shard_ms=SHARD_MS):
"""The coordinator waits for every shard."""
return max(shard_ms)
def replicas_needed(peak_qps=900, qps_per_copy=200):
"""Copies of each shard needed to absorb the peak."""
return math.ceil(peak_qps / qps_per_copy)
Tuning only the last stage. A perfect reranker cannot rank a product the first stage dropped. Measure the recall of the first 1,000 before you buy a bigger cross-encoder.
Budgeting the average. 49 ms on average still means many 81 ms queries. Plan for the 99th percentile, and for the slowest shard, not the typical one.
Adding parallel stages as if they were in series. BM25 and ANN side by side cost 18 ms, not 30 ms. Get this wrong and you cut a stage you could have afforded.
Asking each shard for top 1,000 ÷ 4. If the best tables sit on one shard, you just threw most of them away. Each shard returns the full depth.
Forgetting the cache on delete. The index skips the tombstone, but a cached result page from a minute ago still shows the sold-out bench.
At 0.4 ms each that is 400 ms, four times the whole budget. Even the remaining 60 ms only pays for 150 documents.
Nothing. The average falls from 49 ms to 17 ms, but a miss still costs 81 ms. The tail is made of misses.
Segments are never edited. The delete is a tombstone that search filters out. A later merge writes a new segment without it.
40 ms. The coordinator needs every shard’s top list before it can merge.