FINDING NEEDLES · CHAPTER 18

Production search architecture

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.

~16 min read2,000,000 productsTested Python

What you'll learn

  • Why search is a funnel of stages, each cheaper per document than the next
  • How to add up a latency budget, and why parallel stages cost their slowest part
  • What a query cache does to the average, and what it does not do to the tail
  • How a deleted product disappears: tombstones first, merges later
  • Why shards wait for the slowest shard, and how replicas carry the load

Before you start

A furniture shop at lunchtime

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.

Cheap on many, expensive on few

Catalogue2,000,000 products
Retrieve: BM25 and ANN, side by side, fused with RRFkeeps 1,000 · cost does not grow with the catalogue
Feature ranker: a small model over price, stock, clicks, text scoresreads 1,000 · keeps 100 · 0.01 ms each
Cross-encoder: reads query and product togetherreads 100 · keeps 20 · 0.4 ms each
Snippets and page20 results

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

MANIM Production: ingest/index/serve/observe under SLOs.

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.

Add it up before you ship it

Write every stage down with what it costs. A fixed cost per query, plus a cost per document times the documents it reads.

StageReadsCost
Parse the query—5 ms
BM25 (12 ms) and ANN (18 ms), in parallelthe index18 ms
Fuse with RRF1,0002 ms
Feature ranker1,000 × 0.01 ms10 ms
Cross-encoder100 × 0.4 ms40 ms
Snippets and page205 ms
Total80 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?

The fastest search is the one you skip

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.

#QueryResultCache after (oldest first)
1sofamisssofa
2oak tablemisssofa, oak table
3sofahitoak table, sofa
4desk lampmissoak table, sofa, desk lamp
5sofahitoak table, desk lamp, sofa
6oak tablehitdesk lamp, sofa, oak table
7bookshelfmisssofa, oak table, bookshelf
8sofahitoak table, bookshelf, sofa
9rugmissbookshelf, sofa, rug
10oak tablemisssofa, 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.

Deleted is a mark, not an erase

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.

IdProductState
101oak dining tablelive
102oak benchtombstone (sold out)
103pine dining tablelive
104oak desklive
105walnut dining tabletombstone (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.

Two indexes, one product

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.

Split the data, copy the splits

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.

Shards

Split the data. Each one holds a part. You add shards when the index outgrows a machine.

Replicas

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 budget you can re-run

The costs are invented, but the arithmetic is the same arithmetic you would do with real measurements.

production.py80 ms · depth 150 · 4 of 10 hits
"""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)

Mistakes learners make

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.

What to remember

  • Search is a funnel: 2,000,000 → 1,000 → 100 → 20. Cheap stages read many, expensive stages read few.
  • The budget adds up to 80 ms of 100 ms. Parallel retrievers cost 18 ms, not 30 ms. The reranker can read at most 150.
  • An LRU cache hit 4 of 10 queries and cut the average from 81 ms to 49 ms. The misses are still 81 ms.
  • Deletes are tombstones skipped at query time, removed by a merge. Worst-case staleness here is 5 seconds.
  • 4 shards of 500,000. The query waits for the slowest. 5 copies of each shard carry 900 queries per second.

Check yourself

1. Why not run the cross-encoder on all 1,000 candidates?

At 0.4 ms each that is 400 ms, four times the whole budget. Even the remaining 60 ms only pays for 150 documents.

2. The cache hit rate rises from 0.4 to 0.8. What happens to the slowest queries?

Nothing. The average falls from 49 ms to 17 ms, but a miss still costs 81 ms. The tail is made of misses.

3. A product is deleted. Why does its id still appear in the postings?

Segments are never edited. The delete is a tombstone that search filters out. A later merge writes a new segment without it.

4. One of four shards is slow at 40 ms. How long does the retrieve stage take?

40 ms. The coordinator needs every shard’s top list before it can merge.

Go to the source

Keep going