Ch.17: System Design: How Search Finds the Right Page

0:00 You search for Falcon X2 firmware reset. The results appear instantly. You follow the first one, and halfway down the page it says X1. Wrong camera. Impressively fast, though. Our camera is fictional. The search problem isn't. Today we're designing the engine that finds the right page, not just a page containing the right words. That mismatch leads to two paths on this map. Across the top, we collect pages and build an index. Below, a query retrieves candidates, ranks them and returns links. We'll trace this same picture again at the end.

0:33 We'll ground it in the crawler standard and Lucene, the open-source search library. Source links are in the description. First, the engine must discover permitted public pages, keep their searchable copies current, and return ordered links with useful snippets. Those are our functional requirements. And understand a phrase or an ordinary typo, without quietly changing the camera model. Updates and removals count too. No private pages, ads or generated answers in this design. For non-functional requirements, let's choose a hundred million pages and 10,000 peak queries per second.

1:08 Made-up workload, not Google's numbers. Our end-to-end target is 300 milliseconds at the 95th percentile. Meaning 95% of requests finish within that budget. But a fast wrong answer still fails. We also need useful relevance, controlled crawler load and a freshness policy. Freshness can't mean every page is instantly up to date. We'll revisit important, changing sources more often, then measure the lag we actually achieve. With relevance in our requirements, my first thought is a better ranking model.

1:39 The official X2 page ought to beat the old copy. Is it in the index? Ah. If we never fetched it, I've bought a better judge for a trial with missing evidence. And even an indexed page can be missing from the candidates we send that judge. Keep those failures separate: not indexed, not retrieved, or ranked badly. Let's actually get the page first. Where does the crawler discover it? For that discovery path, take a crawler starting from known URLs and sitemaps, then following fetched links. Record already scheduled URLs so loops don't keep adding the same work. The pending frontier needs priority and scheduling by host.

2:18 Why isn't a priority queue enough? A newly discovered site could fill the top of it. Our workers would hammer one server. Keep that host's URLs together with a next-eligible fetch time. So urgency doesn't cancel its appointment. We can fetch elsewhere while it waits, instead of making the whole crawler sleep. Before that scheduled fetch, check robots: the site's file of crawler rules. RFC 9309 defines how to interpret it. It is not a password or an access grant. Then an allowed path doesn't entitle us to get around a login.

2:51 And a server failure fetching robots isn't a blank permission slip. Correct. We honor the rules and restrict crawling to the public scope we chose. Our per-host delay is a scheduling policy, not something that RFC prescribes for every website. Faster coverage has a limit: somebody else's server has to tolerate our curiosity. Once we fetch a page, strip navigation noise and extract its useful text. A content fingerprint can identify exact duplicates, with equality checked before discarding a match. For example, our bad copy changes one sentence in the retained body text.

3:26 Its fingerprint changes. Now 10 copies look like 10 independent answers. That's where near-duplicate grouping helps: compare short runs of text that overlap, rather than requiring every word to match. We can then put similar pages in one result group. Careful, X1 and X2 manuals might differ in one crucial instruction. Looking alike doesn't mean we can swap them. Same caution with URLs. Consider a page whose parameter selects the product, not a tracking code. Blindly deleting it can merge different manuals.

3:59 Right. We can't lose track of which manual we kept. Give each retained document a stable identifier, with its source URL and fetch version. That identifier will travel through the index. And preserve enough provenance to explain a result later. When someone reports the wrong reset instructions, "that's what the model said" is not a useful incident record. We need to find the actual page version that produced the snippet. Now, how does its text become searchable? Now make that lookup concrete. Document 7 is our X2 manual.

4:30 19 is an X1 forum post. 42 is a general firmware article. Instead of storing only document to words, build word to documents. So the entry for firmware lists 7, 19 and 42. X2 points only to 7. Those document references are postings. A dictionary of terms pointing to postings lists is the inverted index. Nice. The query no longer asks the entire collection whether it contains X2. It goes straight to the list that already knows. But a list of document IDs doesn't establish a phrase. Imagine factory at the beginning of a page and reset at the end.

5:08 Store word positions too. If factory appears at position 12 and reset at 13, that occurrence matches the phrase factory reset. There it is: neighboring positions, not just two words somewhere on a page. We also need compatible text processing when indexing and querying. Otherwise the query asks for a token, a searchable text unit, that we never stored. Right. Normalize ordinary language where useful, but keep identifiers like X2 meaningful. Search shouldn't improve my spelling by buying me a different camera.

5:40 Now both manuals mention reset. How do we order them? My cheap first pass would count query-word occurrences. What breaks? Then a page saying reset 300 times wins. The classic TF-IDF idea combines frequency within a document with rarity across documents. A common word carries less discriminating weight. X2 tells us more than the. But repetition can still dominate that simple starting point. We choose BM25 for our baseline. Repetition has diminishing returns, and it normalizes for document length.

6:13 More text doesn't automatically win. Still a word-matching score, not a certificate that the instructions are correct. But that word score leaves out source authority. Where do links fit? PageRank is a classic example. Imagine repeatedly following web links, with occasional random jumps. Pages visited more often accumulate more weight. Links from influential pages matter, not just how many links arrive. But a well-connected old manual can still be the wrong answer. Yes, authority is one clue, along with query matches and freshness where it matters.

6:45 It doesn't prove a page is right. First, let's find promising candidates without scoring every match. With authority and freshness reserved for the later ranker, BM25 still has to find candidates. Do we evaluate millions of reset matches just to return 10 links? We can prove a block cannot win, then skip it. Lucene developer Adrien Grand described why an earlier attempt got stuck. As the collection changed, maintaining useful maximum scores became difficult. Hold on. We need to know how good an unread document could be?

7:18 A safe ceiling, yes. BM25's bounded scores helped unblock that work. Let's put numbers on what the ceiling buys us. With that ceiling in mind, take a toy top-10 BM25 search. The 10th-best hit scores 8. If no document in a block can score above 5, we can skip it. A ceiling of 9 means we still have work to do. To prove that ceiling, group postings into blocks. Stored frequency and length information can bound each query term's contribution; combine those bounds for the whole BM25 retrieval score. Collecting 50 candidates would use the 50th-place threshold instead.

7:56 Oh, so the shortcut still owes us a proof. A quick sample wouldn't give us that. It also changes what we're asking for. Finding the best hits can skip losers. An exact total count of every matching document may require additional work. Don't promise both for the price of one. But even with skipping, the index or query load can outgrow one machine. Let's partition by document ID. Each shard holds some documents and the postings for those documents. A query goes to the needed logical shards; each returns a bounded list of candidates.

8:28 Then a coordinator merges those lists. The word X2 can exist on several shards, because different X2 pages landed on different partitions. Right. We're dividing the collection of documents, not assigning X words to one server and F words to another. For this partitioning plan, try 100 logical shards. 10,000 queries per second becomes a million shard scoring requests per second. Additional query phases add more traffic, even before retries. Ugh. The client sends one request; the cluster feels 100.

8:59 It's easy to look at the client request rate and miss the work behind it. More shards can make each search smaller, but increase coordination and request overhead. That arithmetic alone doesn't tell us the right shard count. Or the hardware. We'd measure the actual query mix, index size and queueing. Replicas help distribute the work, but don't make this multiplication disappear. With those copies available, choose one per logical shard for each query. Extra copies let us spread requests or recover from failure.

9:30 I think the nearest healthy copy is the obvious starting point. But imagine its queue is full while a slightly farther copy is idle. The health check won't settle that for us. Include recent response time and outstanding work in routing, then measure the result. So replication gives us another place to ask. The hard part is choosing a copy without creating more work than we remove. But suppose X2 is rare in one shard and common in another. Its rarity bonus changes depending on where a document landed.

10:02 How do we compare those scores? For this design, combine term and field statistics across the searched shards before scoring: how rare each query word is and the typical text length. Compare like fields, such as title against title, while retaining each document's own counts and length. That costs another distributed phase. Yes, that trades response time for better score comparisons. Now we can merge local winners on the same basis. But what if a different final ranker wants a page that never makes the shortlist?

10:33 Here's a concrete case. In our toy replay, the corrected manual is candidate 21. We keep 20. Then the expensive ranker never sees it. Try 50 candidates. If that admits the manual, candidate recall improves: more of the useful answers survive retrieval. And if the wider list breaches our deadline, 50 isn't an acceptable fix by itself. Right. Test cheaper scoring or better first-stage retrieval, then measure again. 20 and 50 are example cutoffs, not production recommendations. We found a missed answer, but the latency budget still gets a vote.

11:07 Now the winners need titles, URLs and snippet material. We don't need to move the full text of every candidate across the network. Unless the richer ranker needs some of that text earlier. Fair correction. Fetch what each stage requires, for the bounded set it handles. Keep document identity and version attached, so the displayed snippet belongs to the result we ranked. A result assembled from different versions could look fresh and still be wrong. How do we keep that view coherent when the user requests the next page?

11:38 For this design, keep the bounded final ordered shortlist and the display material for its document versions for a short session. Bind the cursor to that list and its next position. When the list ends or expires, stop pagination or ask for a new search. Ah, the final ranking, not the earlier retrieval order. Removal checks still apply to every page; that saved list isn't permission to resurrect a deleted result. That version issue gets sharper when the manufacturer fixes its reset instructions. When do users see the update?

12:12 We have to discover the change, fetch it, process it and expose the updated index state to search. Each step can add delay. I'd been thinking about the last step. A fast index refresh doesn't help if we revisit the site next week. Precisely. And rebuilding the entire index for each change would be wasteful. Write new chunks of the index, called segments. Search those alongside the older chunks, then merge segments in the background. What happens to the old version's postings? Mark the old document version invalid and filter it from search; a later merge can reclaim its space.

12:48 A refresh makes new segments searchable. That's visibility, not a full durable index commit. Elastic also logs changes for crash recovery; searchable and recoverable are different questions. Now imagine our crawler captures the old manual and its processing stalls. A later fetch gets the correction and finishes first. Then the old work arrives. If we accept arrival order, we revert the correction. Assign monotonic fetch versions per document before dispatch, then atomically check and apply only a newer version.

13:19 Those versions order our fetch jobs, not some perfectly known history of the whole website. Yes, that's our rule. Replaying the same version must be idempotent: whether we process it once or twice, it must not create a second search result. Same version logic for deletion. Otherwise replaying an old successful fetch could resurrect a removed page. And our result cache might still advertise it. Imagine the product owner asking, "If we removed it, why are we still recommending it?" That's a fair demand.

13:50 Cache reuse is a freshness decision, not just a speed trick. For this design, propagate removal state, invalidate tracked cached results, and bound other cache lifetimes. Check selected results against authoritative removal state before displaying them. If that check is unavailable, omit the result. That last check costs something. But we've explicitly chosen not to trade known removals for a prettier latency graph. With those freshness checks, we still owe the user 300 milliseconds. The query budget needs parsing, the statistics phase, retrieval, ranking and returning the result.

14:24 Plus network time and queueing. And adding the stages' 95th percentiles doesn't prove the overall target. Different requests can be slow in different places. Trace complete requests, then use stage allocations to guide the design. Especially retrieval. Waiting for 100 shards exposes us to stragglers; the average shard's time can look lovely while the user waits for the slow one. Then retry the slow shard against another replica? Maybe, within a bounded policy and the remaining deadline. Retrying every slow request during overload adds more work to an already overloaded system. The rescue boat arrives carrying more passengers.

15:02 Exactly. Measure queue depth and replica latency, limit retries, and stop work the response no longer needs. If a partition can't answer, choose explicitly between a marked partial result and a clear failure. Not a normal-looking list that silently excludes the shard with the official manual. Now even a complete response can answer the wrong query. Take a user who misspells firmware. For a basic spelling check, compare that ordinary word with dictionary terms a few letter edits away, then offer firmware as a suggestion.

15:35 But expanding X2 to X1 breaks our running example. Keep the original query and protect meaningful identifiers. If we suggest a materially different query, make that choice visible. Phrase matches can preserve intent too. Another extension is retrieval by similarity in meaning, not just shared words. Test that when people use different vocabulary from the pages they need. Alongside, not as an excuse to forget exact terms. A fluent interpretation of the wrong model number is still wrong. Now we need four separate measurements.

16:07 First, coverage and freshness: are useful pages present, and how far behind their sources are they? Second, candidate recall: do answers we know are useful make it to the ranker? Third, final relevance: does the order help people finish representative search tasks? Fourth, latency and availability, measured end to end and including partial responses. Keep human relevance judgments in the evaluation. A click can mean the snippet was tempting, not that the page solved the problem. Otherwise we optimize the wrong camera page until everybody clicks it faster.

16:40 With those measurements, suppose someone reports that same wrong-camera result. We check, and the current official X2 page isn't indexed. I'd trace discovery, scheduling and crawl permission. Then follow the fetch and parsing through publication to the searchable index. Find the first stage that never produced usable output. Ranking changes cannot repair a page that didn't reach the index. Now suppose it is indexed but absent from the candidate set. Inspect the stored terms, query interpretation and candidate cutoff.

17:11 Compare retrieval strategies against the known useful answer. Finally, it reaches the final ranker and loses to the old copy. Now inspect the actual scores and duplicate group. Check whether we rewarded a recent fetch of old instructions, overweighted repetitions, or lost the model identifier. This is where a ranking change might actually help. And if ordering is good but requests time out, we're in a different incident. Follow the trace into queueing, shard fan-out or expensive ranking. Same user complaint, four possible causes.

17:42 Buying a larger model before locating the loss could leave every one of them intact. Now replay with the corrected official manual admitted. It matches X2 and the reset phrase. The old copy matches lots of words, but its procedure is for X1. For this example, store the model each manual describes. On an exact-model query, sort matching manuals first, then use the word score within that group. X2 beats X1; being official or recent isn't enough. We'd check both the recorded model and the ordering against human judgments across more than this one query.

18:18 A clean example isn't an evaluation set. There we go. We know why this result changed. Now that rule has to survive the rest of the evaluation set. Now return to the same full architecture picture. Follow the corrected manual along the upper path: scheduled fetch, parsed text, duplicate checks, versioned index update. It becomes available to search. Now follow the query below. Preserve X2, retrieve across the document shards, merge candidates, spend richer ranking on the shortlist, then assemble the winning link and snippet.

18:50 Those paths meet at the index. Crawling controls what evidence exists, retrieval controls what survives, and ranking chooses what leads. The deadline constrains the whole trip. So that fast wrong result has a trace now. We can locate the stage that lost the useful answer. And choose a repair for that stage, rather than replacing the whole search engine on a hunch. Locate the loss before buying the fix. Thanks for listening to Learning Podcasts.