Concept 13: Distributed Search Engines — Inverted Indexes, Relevance & Elasticsearch Architecture

System Design Bible — File 13 Difficulty: ★★★★☆ Prerequisites: File 02 (Caching — the memory hierarchy and latency numbers), File 04 (Sharding & Partitioning — you will shard the index), File 06 (Consistent Hashing — routing documents to shards), File 08 (Consensus & Replication — the cluster needs a coordinator and replicas), File 11 (Databases Deep-Dive — B-trees, LSM-trees, WALs, and why indexes exist at all), plus the fundamentals unpacked in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

Search feels like "a database with a LIKE query" until you understand four things that make it a completely different animal. Read this section slowly; every later section leans on it.

0.1Why your database cannot do search (the wall that forced search engines to exist)#

In File 11 you learned that a database makes lookups fast with an index — almost always a B-tree, a balanced tree of pages sorted by key value. A B-tree is magnificent at one specific job: given a key, find the row, or given a range of keys, walk them in order. It answers WHERE user_id = 42 in three or four disk reads instead of scanning a million rows.

Now ask the B-tree a search question: *"find every document containing the word distributed."* The B-tree on the body column is sorted by the entire value of the column — the full text of the document, character by character, starting at the first character. "Distributed systems are hard" and "A guide to distributed systems" sort into utterly different parts of the tree, even though both contain your word. The tree's ordering is useless to you, because the thing you're searching for is in the middle of the key, and a B-tree can only exploit prefixes. This is exactly why WHERE body LIKE '%distributed%' cannot use an index: a leading wildcard destroys the prefix property, and the database is forced into a full table scan — read every row, run a substring match on each. At 10 million documents of 2 KB each, that's 20 GB of reading per query. On an SSD at ~1 GB/s that's 20 seconds. Per query. For one user.

Worse, the question you actually want to ask is not even boolean. Real users type distributed database consistency and expect the best documents first — not "all 400,000 documents that contain at least one of these three words, in primary-key order." A B-tree has no notion of "better." It knows equality and ordering; it does not know relevance.

So there is a hard wall here, and it's made of physics and data structures: the index we use to find rows by key is structurally incapable of finding rows by content, and has no concept of ranking. Everything in this file is the consequence of inverting that data structure. Hold this: search engines exist because a B-tree is indexed by document → content, and search needs the exact opposite — content → document.

0.2Text is not a value; it's a bag of terms (why we must analyze before we can index)#

A database treats the string "The Distributed Systems Reader" as one atomic value. Comparing it to "distributed systems" yields not equal, full stop. But a human searching for distributed system clearly wants that document. Between them lie four separate mismatches, each of which a search engine must actively repair:

Mismatch 1 — the text contains many searchable units, not one. The document must be broken into individual words: The, Distributed, Systems, Reader. That splitting step is called tokenization, and each resulting unit is a token. Once a document is a set of tokens rather than one blob, we can index each token separately, which is precisely what makes "find documents containing this word" a key lookup instead of a substring scan.

Mismatch 2 — case. Distributed and distributed are different bytes but the same word to a user. So we lowercase everything at index time and at query time, so both sides land in the same bucket.

Mismatch 3 — morphology. Systems (plural) and system (singular) are different strings and the same concept. Reducing words to a common root — systems → system, running → run — is called stemming. It's a lossy, language-specific transformation, and the fact that it's lossy will bite us later (§4).

Mismatch 4 — noise. Words like the, a, of appear in nearly every document. They cost enormous index space and carry almost no discriminating power; removing them is stop-word filtering (a choice with its own trade-off, covered in §4).

The crucial insight, and the one candidates most often miss: whatever transformation you apply to the document at index time, you must apply the same transformation to the query at search time. If you stem the document's Systems down to system but don't stem the user's query systems, the two never meet and you return zero results. Hold this: search matches transformed text against transformed text — and the transformation pipeline is a design decision, not a detail.

0.3Immutability and sequential I/O (why segments exist)#

From File 11 you carry two physical facts: sequential I/O is dramatically faster than random I/O, and the unit of I/O is a page, not a record. Search engines take these facts to their logical extreme.

An inverted index (§2.1) is essentially a huge sorted dictionary of every distinct word mapped to a compressed list of document IDs. To be fast, that structure must be tightly packed, sorted, and compressed — every byte you don't read is a byte of I/O and CPU you save. But tightly packed compressed structures are catastrophic to update in place. Insert one document containing the word distributed, and you must splice a new document ID into the middle of a delta-compressed byte stream (§5.2), potentially reshuffling everything after it. The write amplification would be ruinous.

The resolution is the same one LSM-trees reached in File 11, arrived at independently: never modify; only append. New documents accumulate in an in-memory buffer; periodically that buffer is flushed to disk as a brand-new, completely immutable mini-index called a segment. Segments are never edited after birth — they are only created, searched, and eventually merged and deleted. This buys enormous properties for free: no locking on read (an immutable structure needs no read locks, so hundreds of concurrent searches can hammer the same segment), aggressive compression (you can pack it perfectly because nothing will ever be inserted), and OS page-cache friendliness (an immutable file caches perfectly — it never invalidates).

And it charges an unavoidable price, which you must be able to name in an interview: deletes and updates become fictions (§2.7), the number of segments grows without bound and must be continuously merged (§5.5), and a document is not searchable the instant you write it — it's only searchable once a segment containing it exists (§3.1). Hold this: an inverted index is fast because it's immutable, and every awkward behavior of a search engine — near-real-time visibility, deleted docs lingering, merge storms — is the bill for that immutability.

0.4Scatter-gather: what "distributed" costs you#

One machine's RAM and disk cannot hold the index for a billion documents, so the index is sharded (File 04) — split into N independent sub-indexes, each on a different machine. That decision is forced by the finiteness of a single machine, and it is unavoidable at scale. But notice what it does to a query.

For a key-value lookup, sharding is nearly free: you hash the key, you know exactly which shard holds it, you ask that one shard, done. One shard answers. For a search, you have no idea which shards hold matching documents — the matching documents are wherever they happen to be. So every query must go to every shard, and the results must be merged. This pattern is called scatter-gather, and it has three consequences that make distributed search fundamentally harder than distributed key-value storage:

First, every query touches every machine, so your cluster's total query throughput does not increase when you add shards — you've spread the data, not the work per query. Adding shards makes each shard's slice of work smaller (good for latency), but the query count multiplies (bad for overhead).

Second, your latency becomes the latency of the slowest shard, not the average. This is the tail-latency amplification problem: if each shard has a 1% chance of being slow — a GC pause (the JVM's garbage collector periodically stops the program to reclaim unused memory; a big heap can freeze for whole seconds), a cold page cache (the data it needs isn't in RAM yet, so it's paying disk reads), or a noisy neighbor (another workload on the same physical host stealing its CPU/disk) — then with 100 shards the probability that at least one is slow is 1 - 0.99^100 ≈ 63%. A query is not done until the last shard replies. This is why "just add more shards" is a wrong answer in an interview beyond a certain point.

Third, and most subtly, global truth is not locally knowable. Ranking (§6) depends on statistics like "how rare is this word across the whole corpus?" — but each shard only knows its own corpus. Sorting and paginating depend on a global order — but each shard only knows its own order. We will spend all of §8 on the tricks and compromises this forces. Hold this: search is scatter-gather, so tail latency and global-statistics approximation are its two permanent taxes.

0.5Relevance is a ranking problem, not a filtering problem#

A SQL WHERE clause returns a set: every row either qualifies or doesn't, and all qualifying rows are equally valid. Search returns a ranked list: 400,000 documents technically match distributed database consistency, but the user will look at ten of them, and if the right one isn't in the first three, your search engine has failed even though it was "correct."

This reframes the whole engineering problem. The job of a search engine is not "find the matching documents" — that's the easy half, solved by the inverted index. The job is "order the matching documents by how likely each is to satisfy this human's intent," which is a statistical scoring problem (§6) with no single correct answer. That is why search engines have scores attached to every hit, why those scores come from probabilistic models like BM25, and why serious search teams run continuous A/B tests on ranking rather than "verifying correctness." Hold this: matching is a data-structures problem; ranking is a statistics problem; a search engine must be excellent at both, and interviewers probe the second because most candidates only know the first.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

A distributed search engine is a system that ingests documents, breaks each one into terms, stores a term → list-of-documents mapping (the inverted index) sharded across many machines, and answers queries by looking up the query's terms in that mapping, intersecting or unioning the resulting document lists, scoring each surviving document for relevance, and returning the top-K in ranked order — all in tens of milliseconds over billions of documents.

The analogy that actually holds: the index at the back of a textbook. The book itself is ordered by page (document → content). If I ask "which pages discuss consistency?", reading all 900 pages is a full table scan. So the publisher builds an inverted structure: an alphabetical list of concepts, each followed by the page numbers where it appears — consistency … 44, 91, 210, 388. You find consistency in the alphabetical list in a second (it's sorted, so you binary-search it), and you get the page list instantly. Now ask a two-word question: "pages discussing both consistency and quorum?" You look up both, get two sorted lists of page numbers, and walk them together taking only the numbers present in both. That's it — that's an AND query, and it's the entire core algorithm of every search engine on earth. **Elasticsearch is that back-of-book index, built automatically, compressed brutally, spread across 500 machines, and augmented with a statistical model of which page you most likely wanted.**

To be precise about the layers, because interviewers conflate them and you shouldn't:

1.2"The Why" — The Physical and Economic Limits That Forced This#

Limit 1 — Scan cost is linear in corpus size, and corpora grew exponentially. As established in §0.1, a LIKE '%term%' query is O(total bytes). Wikipedia is ~100 GB of text; GitHub is hundreds of millions of repositories; Netflix's logs are terabytes per day. Linear scanning was never merely "slow" — at these sizes it is thermodynamically absurd, requiring you to read a data center's worth of disk to answer one question. The inverted index converts the query cost from O(size of corpus) to roughly O(number of documents containing your rare terms) — for a term appearing in 500 of 10 billion documents, that's a 20-million-fold reduction in work. This is the same trade the B-tree made in File 11 (pay storage and write cost at insert time to make reads logarithmic), applied to a different access pattern.

Limit 2 — RAM is finite and expensive; the index must be compressed and disk-resident but RAM-cacheable. An uncompressed posting list is a list of 4-byte integers; a real corpus produces hundreds of billions of them. Naively that's terabytes of RAM per node, which nobody can afford. So the index is compressed with specialized integer codecs (§5.2) that shrink it 4–10×, stored on disk, and read through the OS page cache — leaning on the memory hierarchy from File 02. The economics of RAM are precisely why the compression algorithms in §5 exist at all; they're not academic garnish.

Limit 3 — Single machines are finite, and failure is constant at scale. A billion-document index doesn't fit on one box, so it must be sharded (File 04); once you have 200 boxes, one is always dying (File 08's core lesson), so every shard must be replicated. Sharding and replication are therefore not optional features of a search engine — they are the load-bearing structure.

Limit 4 — Human attention is the real bottleneck. Users read ~10 results. So an engine that returns all 400,000 matches "correctly" but in arbitrary order is worthless, which forces the entire ranking apparatus of §6. This limit is not physical, it's cognitive — and it's the one that turns search from a data-structures exercise into a product.

1.3What It Solves — And the Price It Charges#

Notice every row has a price. That's the point — in an interview, "we'll add Elasticsearch" without naming at least the second copy of the data, the reindex-on-mapping-change trap, and the not-a-source-of-truth rule is a junior answer.

2The Recursive Sub-Concept Tree#

Every term used in the rest of this file, defined from scratch.

2.1Sub-Concept: The Inverted Index#

What it is. A mapping from term → the list of documents containing that term. It's called inverted because the natural ("forward") direction is document → its terms; we invert it.

Why it exists. §0.1: the forward direction cannot answer content queries without a scan; the inverted direction makes them a dictionary lookup.

How it works. Take three documents:

doc1: "distributed systems are hard"
doc2: "distributed databases are systems"
doc3: "hard databases"

Analyze each (lowercase, drop the stop word are, stem plurals) and record which documents each term appeared in:

TERM DICTIONARY (sorted)      POSTING LIST (sorted doc IDs)
--------------------------    -----------------------------
database          ──────────► [2, 3]
distributed       ──────────► [1, 2]
hard              ──────────► [1, 3]
system            ──────────► [1, 2]

Now distributed AND system = intersect [1,2] with [1,2] = [1,2]. distributed AND hard = intersect [1,2] with [1,3] = [1]. No document was ever read. That's the whole trick.

Why it works. Two properties do all the heavy lifting. (a) The term dictionary is sorted, so finding a term is a binary search / FST traversal (§5.1) — sub-microsecond, not a scan. (b) The posting lists are sorted by doc ID, which means intersecting two lists is a linear merge (walk both with two pointers, advance the smaller) rather than an O(n·m) nested loop, and sorted integers compress superbly (§5.2). Sortedness is not a convenience here; it is the source of both the speed and the compression.

Trade-off. You've bought O(matching-docs) reads instead of O(corpus) reads, and you pay for it in (a) storage for the whole second structure, (b) CPU at index time to analyze every document, and (c) the immutability constraints of §0.3.

2.2Sub-Concept: Term, Token, and Posting#

A token is what the tokenizer emits when it chops text — the raw word plus its position and character offsets. A term is what's left after the token has been through all the filters (lowercased, stemmed, etc.) — the actual string stored in the dictionary. Tokens are transient; terms are what live in the index. A posting is one entry in a term's list: at minimum a doc ID, but usually also the term frequency (how many times the term occurred in that document — needed for scoring in §6) and often the positions (where in the document, needed for phrase queries: "distributed systems" as an exact phrase requires knowing that systems occurs at position i+1 relative to distributed).

The trade-off here is explicit and configurable: storing positions typically doubles or triples the index size, and you only need them for phrase and proximity queries. If a field never needs phrase search (a tag list, a status code), you turn positions off (index_options: docs) and save that storage. This is the kind of concrete lever that separates candidates who've operated a search cluster from those who've read about one.

2.3Sub-Concept: Document, Field, and Mapping#

A document is the unit of indexing and retrieval — a JSON object. A field is one key in it (title, body, price, created_at). A mapping is the schema: it declares each field's type and, critically, how it will be analyzed.

The distinction that matters most, and the #1 source of real-world "why doesn't my search work" bugs:

Get this backwards and you get maddening behavior: searching a keyword field for distributed returns nothing (the only term is the full string), while aggregating a text field for "top titles" returns a nonsense bucket per word rather than per title. The standard production answer is a multi-field: index title as text for searching and title.keyword as keyword for sorting/faceting. The price is that you store the field twice — a real cost, consciously paid.

The mapping trap you must name in an interview: most mapping changes are not possible in place. The mapping decided how bytes were written into immutable segments; changing it can't retroactively rewrite them. Changing a field from text to keyword, or changing the analyzer, requires reindexing the entire corpus into a new index — which for a billion documents is hours-to-days of compute. Production teams therefore index into products_v1, point an alias named products at it, and when the mapping must change, build products_v2 in the background and atomically flip the alias. Benefit: zero-downtime mapping changes. Cost: double storage during the transition and a full reindex's worth of CPU. Mitigation: the alias flip is atomic, so at least there's no dark window.

2.4Sub-Concept: Segment#

A segment is a complete, self-contained, immutable mini inverted index on disk — its own term dictionary, its own posting lists, its own doc values, its own deletion bitmap. A Lucene index is just a set of segments plus a tiny file (the commit point) listing which ones are live.

Why it exists. §0.3: you cannot cheaply insert into a compressed sorted structure, so you don't. You buffer new documents in RAM and periodically write out a new segment.

How a search over segments works. To search the index, Lucene searches every live segment independently and merges the results. Ten segments = ten inverted-index lookups per term, merged. This is exactly the same "the read must consult every level" cost you saw in LSM-trees in File 11 — and it produces the same pressure: too many segments makes reads slow, so you must merge them in the background (§5.5). Search engines and LSM databases converged on this design because they face the identical physical constraint.

2.5Sub-Concept: Shard (Primary and Replica)#

A shard is a complete, independent Lucene index. This is the single most important sentence in Elasticsearch's architecture, and most candidates never say it. An Elasticsearch "index" is a logical thing — a name pointing at a set of shards. The actual searchable machinery is the shard.

A primary shard owns a slice of the documents; a document belongs to exactly one primary. A replica shard is a full copy of a primary living on a different node, serving two purposes at once: durability (if the primary's node dies, a replica is promoted — File 08's leader-failover applied here) and read throughput (searches can be served by either primary or replica, so replicas linearly increase read capacity). Writes must go to the primary and then be applied on the replicas (§7.3).

The rule to internalize: shard count for an index is fixed at creation time and cannot be changed (you can split/shrink into a new index, but not resize in place). Why? Because routing is shard = hash(_routing_id) % number_of_primary_shards — File 06's modulo-hashing problem exactly. Change the divisor and every document's home moves, invalidating the entire index. Elasticsearch's answer is not consistent hashing (which would allow growth) but immutable shard count + reindex, on the reasoning that shard rebalancing of gigabyte-scale Lucene indexes is expensive enough that you'd rather plan capacity than shuffle constantly. Benefit: dead-simple, deterministic routing with zero coordination. Cost: you must guess your future size at index-creation time. Mitigation: time-based indices (logs-2026-07-16) so each new index gets a fresh, right-sized shard count, plus aliases so clients never notice.

2.6Sub-Concept: The Translog (Write-Ahead Log for Search)#

Buffered documents live in RAM until they're written into a segment, and RAM does not survive a kill -9. So each shard keeps a translog — an append-only file on disk to which every write is appended before the write is acknowledged to the client. This is exactly File 11's write-ahead log idea, transplanted: make the durable record cheap and sequential, and let the expensive structured version (the segment) be built lazily. On crash recovery, the shard loads its last committed segments and replays the translog to reconstruct everything written since.

The tunable, and its trade-off: by default the translog is fsync'd to disk on every request before acknowledging, which costs a real disk sync per write (safe, slower). Set it to async with a 5-second interval and writes get much faster because you're batching syncs — but a crash can lose up to 5 seconds of acknowledged writes. Benefit: big throughput win on log/metrics ingestion. Cost: a bounded data-loss window. Mitigation: only ever do this when the source of truth is elsewhere (Kafka, File 07) so you can replay — which is precisely why log pipelines do it and order systems don't.

2.7Sub-Concept: Deletes, Updates, and the Tombstone Bitmap#

Segments are immutable, so you cannot delete a document. Instead, each segment carries a deletion bitmap — one bit per doc, "is this doc dead?" — which is mutable because it's tiny and separate. Deleting doc 7 sets bit 7. The document's terms remain in the posting lists forever; queries still find it and then filter it out at read time.

An update is therefore not an update at all: it is delete-then-insert. The old copy is marked dead in its old segment, and a brand-new copy is written into the new segment. This is the same out-of-place update / tombstone pattern as LSM-trees (File 11) and Cassandra.

Three consequences that make excellent interview material. (1) Deleted docs still cost you disk, page cache, and posting-list traversal until a merge physically removes them — a heavily-updated index can be 40% garbage. (2) **_doc_count and scoring statistics can be skewed by not-yet-purged deletes, so document frequencies are slightly off until merges catch up. (3) The space is only reclaimed by merging** (§5.5), which is why a delete-heavy index's disk usage can rise right after a mass delete before it falls: the merge must first write the new merged segment beside the old ones.

2.8Sub-Concept: Refresh, Flush, Commit, and "Near Real-Time"#

Four words people use interchangeably and shouldn't:

The trade-off dial here is one of the highest-leverage tunables in the whole system. A 1-second refresh means a new segment every second per shard, which is a lot of tiny segments and thus a lot of merge work. For a logging cluster where nobody cares whether a log line is searchable in 1 s or 30 s, setting refresh_interval: 30s can improve indexing throughput dramatically — fewer, bigger segments, far less merge amplification. For bulk backfills, teams set refresh_interval: -1 (off) and number_of_replicas: 0 during load, then turn both back on — often a 2–5× ingest speedup. Benefit: massive write throughput. Cost: data invisible to search for that window; no redundancy during the load. Mitigation: only for backfills into an index no one is querying yet, then flip the alias when it's warm.

2.9Sub-Concept: Doc Values (the columnar sidecar)#

The inverted index answers "which docs have term X?" It is terrible at the opposite question — **"for doc 7, what is the value of field price?"** — because that would require scanning every term in the dictionary to see which lists contain doc 7. But sorting, aggregating (faceting), and scripted scoring all need exactly that per-document lookup.

So Lucene writes a second, column-oriented structure at index time: doc values, a densely packed, on-disk column of docID → value, stored per field. Sorting by price reads the price column sequentially; a terms aggregation reads the category column sequentially. It's the same insight as an OLAP columnar store (compare with File 11's row-vs-column discussion): if you're going to touch one field across many documents, store that field's values adjacently.

Benefit: sorting and aggregations become sequential column reads and can run over off-heap, page-cached, memory-mapped files. Cost: more disk (you store every doc-values-enabled field a second time) and more index-time CPU. Mitigation: doc values are on by default for numerics/keywords but you should set doc_values: false on high-cardinality fields you never sort or aggregate on — a real, easy storage win. Note the pointed asymmetry: text fields have no doc values by default (they'd be enormous and meaningless), which is exactly why aggregating on a text field errors out and tells you to use field.keyword.

3Deep-Dive Mechanics — The Life of a Document and the Life of a Query#

3.1The Write Path (indexing one document, end to end)#

   CLIENT
     │  PUT /products/_doc/A17   {"title":"Distributed Systems","price":39}
     ▼
┌──────────────────────────────────────────────────────────────────────┐
│ COORDINATING NODE (any node; it's just the one that got the request) │
│   route: shard = murmur3(_id="A17") % num_primaries  →  shard 2      │
│   look up cluster state: primary of shard 2 lives on Node C          │
└──────────────────────────────────────────────────────────────────────┘
     │  forward
     ▼
┌──────────────────────────────────────────────────────────────────────┐
│ NODE C — PRIMARY shard 2                                             │
│  1. validate against mapping (types, dynamic-mapping decisions)      │
│  2. ANALYZE each text field  → terms  (see §4)                       │
│  3. append op to TRANSLOG          ─── durable, sequential, fsync    │
│  4. add to IN-MEMORY BUFFER        ─── NOT searchable yet            │
│  5. forward the op, in parallel, to every in-sync replica            │
└──────────────────────────────────────────────────────────────────────┘
     │                                   │
     ▼                                   ▼
  REPLICA (Node A)                    REPLICA (Node B)
  same steps 1–4 locally              same steps 1–4 locally
     │                                   │
     └──────────► ack ◄──────────────────┘
                    │
   primary waits for ALL in-sync replicas, then acks the client
                    │
                    ▼
        ══ every 1s: REFRESH ══►  buffer becomes a new immutable SEGMENT
                                  in the OS filesystem cache
                                  ⇒ DOCUMENT IS NOW SEARCHABLE
                    │
        ══ periodically: FLUSH ══►  fsync segments, truncate translog
                    │
        ══ background: MERGE ══►  many small segments → fewer big ones,
                                  physically purging deleted docs

Three things to notice, because each is an interview point.

First, the write is acknowledged only after all in-sync replicas have it. Elasticsearch replication is synchronous to the in-sync copies — it does not ack on the primary alone. Compare File 08: this is closer to a W = all-in-sync quorum than to Dynamo-style sloppy quorums. Benefit: a promoted replica never silently loses an acknowledged write. Cost: write latency = slowest replica's latency, and a sick replica drags your whole write path. Mitigation: the primary can ask the master to remove an unresponsive replica from the in-sync set, trading redundancy for availability — a deliberate, and dangerous, choice.

Second, durable ≠ searchable. After step 3, the write survives a crash. But it is invisible to search until the refresh at step ~1 s. Candidates who say "Elasticsearch is eventually consistent" are being imprecise; the accurate statement is "writes are durable on ack but searchable only after refresh — it's near-real-time by design, because segments are immutable and building one per document would be insane." That sentence is worth memorizing.

Third, this is why bulk indexing exists. Every single-document request pays routing, translog fsync, and replication round-trips. The _bulk API amortizes all of it across hundreds of docs in one request — commonly a 10× throughput improvement. Sizing rule of thumb: aim for 5–15 MB per bulk request, tuned empirically, because too-large bulks cause heap pressure and rejected requests.

3.2The Read Path — Query-Then-Fetch (the two-phase dance)#

The naive design — ask every shard for the full top-10 documents, merge, return — is disastrously wasteful: with 20 shards and a size: 10 query, you'd ship 200 full documents across the network to throw 190 away. Documents may be kilobytes each. So Elasticsearch uses query-then-fetch, a two-round-trip protocol whose entire purpose is to move IDs over the network in phase one, and bodies only for the ~10 winners in phase two.

  CLIENT: GET /products/_search {"query":{"match":{"body":"distributed database"}},"size":10}
      │
      ▼
┌────────────────────────────── COORDINATING NODE ──────────────────────────────┐
│ PHASE 1 — QUERY (scatter)                                                     │
│   send the query to ONE copy (primary OR replica) of EVERY shard              │
└───────────────────────────────────────────────────────────────────────────────┘
     │                │                │                │
     ▼                ▼                ▼                ▼
  Shard 0          Shard 1          Shard 2          Shard 3
  ───────          ───────          ───────          ───────
  for each live segment:
    • FST lookup "distributed"  → posting list
    • FST lookup "database"     → posting list
    • walk lists together (skip-list accelerated, §5.3)
    • score each match with BM25 (§6.3), using LOCAL statistics
    • keep a size-10 min-heap of the best
  return ONLY: [ (docID, score, shardID) × 10 ]      ◄── tiny payload, no bodies
     │                │                │                │
     └────────────────┴───────┬────────┴────────────────┘
                              ▼
                  coordinator merges 4×10 = 40 (id, score) pairs,
                  sorts by score, keeps the global top 10
                              │
┌───────────────────────────── PHASE 2 — FETCH (gather) ────────────────────────┐
│   ask ONLY the shards that own those 10 winners for their _source (+          │
│   highlighting, etc.) — typically 10 doc fetches total, not 40                │
└───────────────────────────────────────────────────────────────────────────────┘
                              ▼
                    assemble, return ranked JSON to client

Why it works: scores are comparable enough to pick the global winners from local top-Ks because each shard's top-10 provably contains any document that could be in the global top-10 from that shard (if a doc isn't in its own shard's top 10, it can't be in the global top 10 — a sound pruning argument). The one hole in that argument is that the scores themselves are computed from local statistics, which is precisely the flaw §8.1 addresses.

Cost: two network round-trips instead of one (higher latency floor, ~1 extra RTT), and the fetch phase re-reads documents that might have changed. Mitigation: for pure filtering with no scoring or no _source needed, the fetch phase is trivial; and Elasticsearch will skip phase 2 entirely for aggregation-only requests (size: 0), which is why analytics dashboards should always set size: 0.

4The Analysis Pipeline — Turning Text Into Terms#

Analysis is a three-stage chain, run identically at index time and query time (§0.2). Get one stage wrong and your search silently returns garbage or nothing at all — silently, because there is no error, just bad results.

  "The Distributed-Systems Readers, running FAST!"
        │
        ▼   [1] CHARACTER FILTERS  — operate on the raw character stream
        │        strip HTML tags; map "&" → "and"; normalize Unicode
        ▼
  "The Distributed-Systems Readers, running FAST!"
        │
        ▼   [2] TOKENIZER  — split the stream into tokens (exactly one tokenizer)
        │        `standard` splits on Unicode word boundaries, drops punctuation
        ▼
  [The] [Distributed] [Systems] [Readers] [running] [FAST]
        │
        ▼   [3] TOKEN FILTERS  — an ordered chain; add/remove/modify tokens
        │        lowercase → stop → stemmer → synonym → ascii_folding …
        ▼
  [distribut] [system] [reader] [run] [fast]        ← THESE are the terms indexed

4.1Tokenizers — pick one, and know why#

**standard applies the Unicode text-segmentation algorithm: split on word boundaries, discard punctuation. It's the right default for prose in space-delimited languages. Pro: language-agnostic-ish, sensible for English/French/German. Con:** it destroys things that aren't prose — C++ becomes c, 192.168.1.1 becomes four numbers, user@example.com splits into user and example.com. If your corpus is code or identifiers, standard will quietly ruin it.

**keyword emits the entire input as one token. Pro: exact-match semantics, tiny index, perfect for IDs/enums. Con: no partial matching whatsoever. Use when:** the field is an identifier, not language.

**ngram / edge_ngram** slices words into overlapping character runs: edge_ngram(2,10) on search produces se, sea, sear, searc, search. Why it exists: it's how you build search-as-you-type, because now the prefix sear is a real indexed term and a user's partial input is a normal term lookup — no wildcard scan. Pro: instant prefix matching at full index speed. Con: index size explodes — a word of length L generates ~L terms, so a 5–10× index-size blowup is normal. Critical gotcha: you use edge_ngram in the index analyzer but a plain standard analyzer at query time — this is the one place you deliberately break the "same analyzer both sides" rule, because if you also n-grammed the query, sea would match season via the shared gram se and precision would collapse. When to use which: edge_ngram for autocomplete on a bounded field like product titles; a dedicated completion suggester (an FST in RAM) when you need sub-millisecond suggestions and can accept a separate structure; wildcard/regexp queries never on a hot path, because a leading wildcard forces a term-dictionary scan — the original sin of §0.1 reappearing at term level.

**pattern splits on a regex you supply. Pro: full control (e.g., camelCase splitting for code search). Con:** you own the correctness, and regex tokenizers are slow and easy to make catastrophically backtracking.

4.2Token filters — the chain that decides your recall/precision balance#

Lowercase. Trivially cheap, huge recall win, essentially always on. Cost: you lose case as signal (US the country vs us the pronoun; IT vs it) — a real precision loss that nobody usually cares about but which matters enormously for code search (see GitHub in §11.1).

Stop words (the, a, of, and). Removing them shrinks the index (in English, stop words are ~30% of all tokens by volume) and speeds up queries (no more 100-million-entry posting list for the). Con — and this is the classic gotcha: removing them makes the phrase "to be or not to be" completely unsearchable, since every term is a stop word. Modern practice, and the right interview answer, is don't remove stop words: BM25 (§6.3) already down-weights ubiquitous terms to near-zero via IDF, and modern query execution can skip low-impact terms dynamically. Benefit of keeping them: phrases work, no semantic loss. Cost: a bigger index. Mitigation: BM25's IDF makes their score contribution negligible anyway, so the CPU cost is smaller than it looks.

Stemming (running → run, systems → system). Raises recall — plural and inflected queries now match. Costs precision, because stemming is a lossy heuristic, and algorithmic stemmers over-stem: the classic Porter-stemmer failure is universal, university, and universe all colliding on univers, so a search for university returns documents about the universe. When to use which: algorithmic stemmers (Porter/Snowball) are fast and dictionary-free but crude; lemmatization (dictionary-based, better → good) is far more accurate but slower and needs per-language dictionaries. Decision rule: stem aggressively for a document search where missing a result is worse than an odd one (a help center); stem lightly or not at all where precision is the product (legal e-discovery, code search).

Synonyms (laptop ⇄ notebook, nyc ⇄ new york). Enormous recall win in commerce search. Trade-off you must name: apply them at index time and you get faster queries (one term lookup) but every synonym change demands a full reindex; apply them at query time and you can edit them live, but each query expands into more terms and gets slower, and phrase scoring around multi-word synonyms gets subtly wrong. Decision rule: query-time synonyms for anything that changes weekly (merchandising); index-time for a stable, curated list where query latency is critical.

ASCII folding (café → cafe). Users don't type accents. Recall win; small precision loss in languages where accents are meaningful (résumé vs resume).

5Index Data Structures & Compression Algorithms — Exhaustive Breakdown#

This is the section that separates "I've used Elasticsearch" from "I understand it."

5.1The Term Dictionary: FST (Finite State Transducer)#

What it is. The structure that maps a term string → the file offset of its posting list. Lucene stores it as an FST: a minimized, deterministic automaton over the sorted term strings, sharing both prefixes and suffixes.

How it works. Naively you'd store every term string plus an offset — for 50 million distinct terms averaging 8 bytes, that's ~600 MB, too much to keep in RAM per shard. But sorted terms share enormous structure: distribute, distributed, distributes, distributing share ten characters. An FST is a graph where each edge consumes one character and carries an output value; walking the path spelled by your term accumulates (by addition) the output — the posting-list offset. Identical suffix structures are merged into the same states, so the shared tail ing exists once for the entire dictionary.

   Terms: "distributed"(→7), "distributes"(→9)

   d→i→s→t→r→i→b→u→t→e ──d──► (final, +7)
                        └──s──► (final, +9)
                        ▲
             shared prefix stored ONCE

Why it works. Prefix+suffix sharing gives a ~10–20× compression over raw strings, letting the term index live in RAM (or be memory-mapped and stay page-cached) while lookups remain O(length of the term) — independent of how many terms exist. Read that again: finding a term among 50 million takes time proportional to the term's length, not the dictionary's size.

Pros. Tiny, RAM-resident, O(k) lookup, and — because it's an automaton — it natively supports fuzzy matching (run a Levenshtein automaton in parallel with the FST and enumerate all terms within edit distance 2 without ever scanning) and prefix enumeration (walk the subtree).

Cons. Construction requires terms sorted upfront (fine — segments are built once, immutably) and is CPU-intensive; the FST is immutable, so you cannot add a term to an existing one. This is another force pushing toward the segment design.

Complexity. Lookup O(k) in the term length; build O(n·k); space roughly 10–20% of the raw term bytes.

When to use which. vs a hash table: hashing gives O(1) but needs the full term set in RAM uncompressed and supports no range/prefix/fuzzy queries — fatal for a search engine. vs a B-tree: supports prefixes and ranges but is far larger, and its whole raison d'être is mutability, which segments don't need. The decisive condition: when your key set is static, sorted, and must live in RAM while supporting prefix and fuzzy traversal, the FST wins on every axis.

5.2Posting-List Compression: Delta Encoding + Frame of Reference (PFOR)#

What it is. The technique that shrinks a posting list of sorted doc IDs from 4 bytes each to roughly 0.5–1.5 bytes each.

How it works, step by step. Start with a posting list:

[ 1002, 1005, 1009, 1017, 1020, 1025 ]        raw: 6 × 4 bytes = 24 bytes

Step 1 — Delta encoding. The list is sorted, so store each value's difference from the previous one:

[ 1002, 3, 4, 8, 3, 5 ]

The magic: deltas are small. A term appearing in 1% of documents has an average gap of ~100 — which fits in one byte rather than four. The sortedness of the posting list (§2.1) is what makes this possible; this is why sorted order is load-bearing, not incidental.

Step 2 — Bit packing (Frame of Reference). Take a block of 128 deltas, find the maximum among them, compute the bits needed for that max (here max delta = 8 → 4 bits), and pack every delta in the block into exactly that many bits:

  3 → 0011   4 → 0100   8 → 1000   3 → 0011   5 → 0101
  128 deltas × 4 bits = 64 bytes instead of 512  →  8× smaller

Step 3 — Handle the outliers (PFOR = Patched Frame of Reference). One freak delta of 100,000 in an otherwise tiny block would force all 128 values to 17 bits and destroy the compression. So PFOR picks a bit-width covering ~90% of values, packs those, and stores the few exceptions separately as "patches" applied after unpacking. Lucene's variant is PForDelta/FOR with a VByte-encoded tail for the final partial block.

Why it works. The compression exploits the statistical reality that document IDs of a given term are roughly uniformly scattered, so gaps cluster tightly around the mean gap — meaning almost all deltas share a bit-width. And crucially, bit-unpacking is SIMD-friendly (SIMD — Single Instruction, Multiple Data — is the CPU capability to apply one instruction to a whole vector of values at once, e.g. unpack 16 integers in a single operation instead of 16 separate ones): modern CPUs decode a block of 128 packed integers in a handful of instructions, so decompression is faster than reading the uncompressed version from disk would have been. That's the whole point — this compression is not a space/time trade-off, it's a **space and time win**, because we are I/O bound, not CPU bound (File 02's memory hierarchy, cashing out).

Pros. 4–8× smaller index (which multiplies your effective page cache — a compressed index that fits in RAM beats an uncompressed one that doesn't, by orders of magnitude); decoding is vectorized and nearly free.

Cons. You must decode a whole block to read any value in it — no random access into the middle. That's precisely why skip lists (§5.3) exist, and why deltas force you to always read a posting list forward from the start of a block.

Complexity. Decode O(1) amortized per posting; space ~0.5–1.5 bytes per doc ID versus 4 raw.

When to use which. vs VByte (variable-byte: 7 data bits + 1 continuation bit per byte): simpler and byte-aligned, but ~2× slower to decode because of the unpredictable branch on each byte, and less compact. Decision rule: use FOR/PFOR block packing for the long posting lists that dominate cost, and VByte for the short tail where a 128-value block doesn't exist. Lucene does exactly this.

5.3Skip Lists over Posting Lists#

What it is. A sparse index inside a posting list, letting you jump forward without decoding everything you skipped.

Why it exists — the motivating case. Consider AND(the, quokka). the has 100,000,000 postings; quokka has 5. The intersection walks both lists — but if you naively advance the one posting at a time to catch up to each of quokka's 5 doc IDs, you decode 100 million integers to produce at most 5 results. That's the pathological case, and it's common: every real query mixes a common word with a rare one.

How it works. Every 128 postings, Lucene records a skip entry: (doc ID at this point, byte offset in the file, decoder state). Multiple levels of these form a skip list (level 0 every 128, level 1 every 128², etc.). The operation advance(target) consults the top skip level, jumps to the last entry whose doc ID ≤ target, descends, and only then decodes the final block linearly.

 level 2:  [d=0]────────────────────────────────────────►[d=16384]
 level 1:  [d=0]───────────►[d=1024]──────────►[d=2048]──►[d=16384]
 level 0:  [0][128][256][384][512][640][768][896][1024]...
 postings: ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●

 advance(1500):  L2 → stay at 0 ... L1 → jump to 1024 → L0 → 1408 → decode ~92 values
                 (instead of decoding 1500)

Why it works. The skip structure turns "seek to doc ≥ X" from O(n) linear decode into O(log n) jumps plus one block decode. Combined with the "always drive the intersection from the rarest term" strategy — look up the smallest posting list first, then advance() the larger ones to each of its doc IDs — the cost of an AND query becomes proportional to the rarest term's frequency, not the commonest. That inversion is the single most important query-execution optimization in search.

Pros. Makes mixed common/rare AND queries fast; the memory cost is trivial (one entry per 128 postings ≈ 0.8% overhead).

Cons. Useless for OR queries (you must visit everything anyway); adds branchy complexity; and the skip data itself competes for page cache.

Complexity. advance() is O(log n) skips + O(block) decode; space ~1/128 of the list.

When to use which. This isn't optional — it's always on for long lists. The design lesson to state in an interview: cost is driven by your rarest term, so query planners should always start from the most selective clause. (This is the same principle as a SQL planner choosing the most selective index first — File 11.)

5.4Bloom Filters (and why search uses them sparingly)#

Sub-Concept: Bloom filter. A probabilistic set-membership structure. It's a bit array of size m plus k independent hash functions. To add element x, set the bits at h1(x) % m, h2(x) % m … hk(x) % m. To test membership, check those same k bits: if any is 0, x is definitively absent; if all are 1, x is probably present — it might be a false positive, because other elements' bits could have coincidentally covered all k positions. It never produces false negatives. That asymmetry is the whole value: it's a cheap, tiny filter that can definitively rule out work. With ~10 bits per element you get about a 1% false-positive rate — 100× smaller than storing the keys themselves.

In search engines, Bloom filters historically accelerated doc-ID existence checks at ingest time: to PUT a document with an existing _id, the engine must find and tombstone the old copy, which means asking every segment "do you have _id = A17?" — an FST lookup per segment, most of which return nothing. A Bloom filter over each segment's _id field answers "definitely not here" for ~99% of segments in a few bit-tests, skipping the FST entirely.

Pros. Kills a large fraction of pointless lookups for a few bits per doc; particularly valuable for update-heavy workloads. Cons. Costs RAM per segment; false positives mean you still occasionally do the full lookup for nothing; and — the reason Lucene has moved away from them — the FST term index is already so fast and so compact that the Bloom filter's RAM is often better spent on page cache for postings. Modern Lucene relies on the FST plus a _id field optimization instead. Complexity. O(k) hashes per query, O(m) bits total. When to use which: a Bloom filter earns its keep when the negative lookup is expensive (a disk seek in an LSM-tree's SSTable — File 11) and cheap-to-avoid. When the negative lookup is already a RAM-resident automaton walk, the filter is largely redundant. Decision rule: Bloom filters pay off exactly when a miss would otherwise cost you I/O.

5.5Merge Policy: Tiered Merging#

What it is. The background algorithm that decides which small segments to combine into bigger ones — the search-engine analogue of LSM compaction (File 11).

Why it exists. §2.8: a 1-second refresh means one new segment per shard per second, i.e. 86,400 segments a day if you never merged. Each query must consult each segment (§2.4), so query cost grows linearly with segment count, and deleted docs are never physically purged (§2.7). Merging is not housekeeping — it's a load-bearing part of read performance.

**How it works (Lucene's TieredMergePolicy). Segments are grouped into tiers** by size (roughly, by order of magnitude). The policy repeatedly looks for a tier holding more than segments_per_tier (default ~10) segments and merges a budgeted selection of them into one segment of the next tier up. Unlike the older "log-byte-size" policy, tiered merging is allowed to merge non-adjacent segments and explicitly favors segments with many deletions (reclaiming space is a scoring input). Merging is not a re-analysis: it's a streaming merge of already-sorted term dictionaries and posting lists — cheap per byte, but there are a lot of bytes.

 t0:  [s][s][s][s][s][s][s][s][s][s]   ← ten 5 MB segments (tier 0 full)
                    │ merge
                    ▼
 t1:  [   50 MB segment   ]  … accumulate ten of these …
                    │ merge
                    ▼
 t2:  [        500 MB segment        ]   (5 GB default max; beyond that,
                                          merging costs more than it saves)

Why it works. Each document is rewritten roughly O(log_T N) times as it climbs tiers (with T ≈ 10, that's ~3–4 rewrites for a very large index) — a bounded write amplification in exchange for keeping the live segment count logarithmic in the data volume rather than linear in time.

Pros. Keeps segment count small (so query cost stays low), physically purges tombstoned documents (reclaiming disk), and improves compression ratios (bigger blocks, longer shared prefixes in the FST).

Cons — the ones that bite in production. Merging is I/O and CPU intensive, and it competes directly with indexing and search for the same disks and cores; this is the infamous merge storm, where a bulk load triggers so much merging that search latency spikes. Merging also needs free disk headroom — merging two 100 GB segments requires writing a 200 GB output while the inputs still exist, so a cluster above ~50% disk on large segments can deadlock itself. And the default 5 GB max_merged_segment cap means giant segments stop merging entirely, so an old index can carry deleted docs forever.

Complexity. Amortized O(log_T N) rewrites per document; transient disk requirement of up to 2× the merged set.

When to use which. Alternatives worth naming: no merging (impossible — segment count explodes), aggressive merging to a single segment (_forcemerge?max_num_segments=1), and default tiered. **Decision rule: use tiered merging always for live indices; use _forcemerge to one segment ONLY on a read-only index that will never be written again** — the classic case being yesterday's log index in a time-series cluster, where force-merging shrinks it, purges every delete, and makes queries meaningfully faster forever. Force-merging a live index is a well-known self-inflicted outage: it creates one enormous segment above the merge cap that can never be merged again, so its deletes accumulate permanently.

5.6Comparison Table — The Index's Structures#

Decision rule for the whole set: the inverted index + FST + skips serve matching; doc values serve sorting/aggregating; stored fields serve displaying. **If you never match on a field, set index: false. If you never sort/aggregate on it, set doc_values: false. If you never display it, exclude it from _source.** Each of those is a direct, quantifiable storage cut, and naming them is how you answer "our cluster costs $400k/year, reduce it."

6Relevance & Ranking Algorithms — Exhaustive Breakdown#

Matching gets you the candidate set. Ranking is the product. Each algorithm below gets the full treatment.

6.1Boolean Retrieval#

What it is. The ancestor: a document either matches the boolean expression or it doesn't. No scores.

How it works. Intersect posting lists for AND, union for OR, and use a "not" list for exclusion. Our §2.1 example: distributed AND hard → intersect [1,2] and [1,3] → [1].

Why it works. It's exact set algebra over the index — and the sortedness of postings makes each operation a linear merge (§2.1).

Pros. Precise, predictable, explainable, and extremely fast; and it never needs to compute a score, which means it can be cached as a bitset (Elasticsearch's filter context does exactly this: cache the matching-doc bitset for status: active and reuse it across every query). Cons. With a big corpus, AND of many words returns nothing (too strict) and OR returns a million results in arbitrary order (useless — §0.5). Users don't think in boolean. Complexity. O(sum of posting-list lengths), reduced toward O(rarest list) by skip lists. When to use it. **For filters, always.** This is the single most actionable relevance tip in Elasticsearch: put anything with a yes/no answer (status: published, price < 100, created_at > X) in filter context, not query context. Filters skip scoring entirely and get bitset-cached, which is commonly a 2–10× latency win on a mixed query. Put only the free-text part in scoring context.

6.2TF-IDF (Term Frequency × Inverse Document Frequency)#

What it is. The foundational intuition of all relevance: a document is relevant to a term if it uses the term a lot (TF) and the term is rare across the corpus (IDF).

How it works.

Worked example. N = 10,000,000. Query: distributed quokka. distributed appears in 500,000 docs → IDF = log(20) ≈ 3.0. quokka in 50 docs → IDF ≈ 12.2. Doc A contains distributed ×10, quokka ×0 → score ≈ √10 × 3.0 ≈ 9.5. Doc B contains distributed ×1, quokka ×1 → score ≈ 3.0 + 12.2 = 15.2. Doc B wins, correctly — matching the rare term is worth far more than repeating the common one.

Why it works. It's a crude but shockingly effective model of information content: rarity ≈ informativeness (a Shannon-flavored intuition), repetition ≈ aboutness.

Pros. Simple, explainable, no training data, works out of the box in any language. Cons. TF grows without bound — spam a word 10,000 times and you win (keyword stuffing); length normalization is ad-hoc and gets long documents wrong; the model has no theoretical grounding, so its knobs can't be principledly tuned. Complexity. O(1) per posting, computed during the merge walk. When to use it. Essentially never today — BM25 dominates it on every axis and has been Lucene/Elasticsearch's default since 5.0. Know TF-IDF because it's the intuition BM25 formalizes, and because interviewers ask you to compare them.

6.3BM25 (Best Matching 25) — the default, and the one to know cold#

What it is. A probabilistic ranking function that keeps TF-IDF's intuition but fixes its two structural flaws: it saturates term frequency and it principledly normalizes for document length.

How it works. For each query term q in document D:

                                   f(q,D) · (k1 + 1)
 score(D,q) = IDF(q) ·  ─────────────────────────────────────────
                        f(q,D) + k1 · (1 − b + b · |D| / avgdl)

   f(q,D) = raw term frequency of q in D
   |D|    = length of D in terms;  avgdl = average doc length in the corpus
   k1     ≈ 1.2  (term-frequency saturation knob)
   b      ≈ 0.75 (length-normalization knob, 0 = off, 1 = full)
   IDF(q) = ln(1 + (N − df + 0.5)/(df + 0.5))     ← smoothed; never negative

The two fixes, made concrete.

Fix 1 — TF saturation. Look at the shape of f/(f + k1): with k1 = 1.2, going from 1 → 2 occurrences raises the TF factor from 0.45 to 0.62 (+38%); going from 20 → 21 raises it from 0.94 to 0.95 (+1%). The curve asymptotes. Ten mentions is meaningfully more relevant than one; a thousand mentions is barely more relevant than ten. This is what kills keyword stuffing, and it is the single most quotable property of BM25 in an interview. k1 controls how fast it saturates — lower k1 = faster saturation = TF matters less.

Fix 2 — principled length normalization. The b · |D|/avgdl term scales the penalty by how much longer than average this document is. A 2× average-length document must contain roughly 2× the occurrences to score equally, because we expect long docs to contain everything by chance. b = 0 disables it entirely (right for a title field, where length carries no such signal — a short title isn't "more about" anything); b = 0.75 is the empirical sweet spot for prose bodies.

Worked example. avgdl = 500. Query quokka, IDF = 12. Doc A: 500 words, quokka ×3 → denominator 3 + 1.2·(1 − 0.75 + 0.75·1.0) = 3 + 1.2 = 4.2; numerator 3 · 2.2 = 6.6 → factor 1.57 → score ≈ 18.9. Doc B: 5,000 words (10× average), quokka ×3 → denominator 3 + 1.2·(0.25 + 7.5) = 3 + 9.3 = 12.3; numerator 6.6 → factor 0.54 → score ≈ 6.4. Same three mentions; the short focused document wins 3×. That is the algorithm doing exactly what a human would.

Why it works. BM25 is derived from the probabilistic relevance framework — it approximates "the probability this document is relevant given these query terms," with the saturation and normalization falling out of a 2-Poisson model of term occurrence rather than being bolted on. That derivation is why its two knobs are meaningful and tunable, unlike TF-IDF's arbitrary damping.

Pros. Best-in-class relevance with zero training data; two interpretable knobs; ~40 years of empirical validation; cheap enough to score millions of docs per query per shard. Cons. It is purely lexical — it has no idea car and automobile are related, so vocabulary mismatch kills it (mitigated by synonyms, §4.2, or vectors, §6.5). It ignores document quality entirely (a spam page and a canonical reference score identically if the text is similar), which is why every real system blends BM25 with business signals (§6.4). Its scores are not comparable across queries — a score of 15 means nothing absolute, so "return everything above 10" is a bug, not a feature. And it depends on corpus-wide statistics (N and df) that a sharded system doesn't have — the whole subject of §8.1. Complexity. O(1) per (term, matching doc); the dominant cost is walking posting lists, not the arithmetic. Modern Lucene additionally uses block-max WAND, which stores each block's maximum possible score and skips whole blocks that cannot beat the current 10th-best score — often a 2–10× speedup for top-K queries by never scoring most matches at all. When to use it. Default. Always start here. Only add vectors (§6.5) or LTR (§6.6) when you have measured that lexical matching is losing you real queries.

6.4Function Score / Boosting — blending relevance with business reality#

What it is. A wrapper that combines the BM25 text score with non-textual signals: recency, popularity, price, geo-distance, personalization.

How it works. You compose a final score, e.g. final = bm25 × log(2 + views) × decay(age), where decay is typically a Gaussian or exponential function of the document's age (gauss(created_at, origin=now, scale=7d) gives ~1.0 for today's docs and falls toward 0 over weeks). Field-level boost factors multiply a subquery's contribution (title^3 says a title match is worth 3× a body match — which is right, because a title is a human's own summary of the document).

Worked example. Two news articles both score BM25 = 10 for election results. Article A is from 2016 with 1M views; B is from today with 1K views. Pure BM25 ties. With × gauss(age, scale=3d): A gets ×0.001, B gets ×0.99 → B wins decisively. This is why a news search that ignores recency is broken regardless of how good its BM25 is.

Pros. Injects domain knowledge that text alone cannot express; cheap; fully explainable (you can print the multiplier chain via the _explain API). Cons. The weights are hand-tuned magic numbers that quickly become unmaintainable — every merchandising request adds a multiplier, and after 20 of them nobody can predict the ranking or safely change anything. Popularity boosts create a rich-get-richer feedback loop (popular things rank higher → get clicked more → rank higher still), which entrenches incumbents and buries new inventory. Complexity. O(1) per candidate doc, but function scores need doc values (§2.9) for the fields involved, so they add I/O. When to use it. When you have obvious, strong, non-textual signals (recency in news/logs, distance in local search, stock status in commerce). Decision rule: use function scoring when you can name the signal and its direction in one sentence; graduate to learning-to-rank (§6.6) the moment your hand-tuned weights exceed roughly five and start fighting each other.

6.5Vector / Semantic Search (kNN with HNSW)#

What it is. Ranking by meaning instead of by shared words. An embedding model maps each document and query into the same high-dimensional vector space (say 768 dims) such that semantically similar texts are geometrically close. Retrieval becomes: find the k nearest vectors to the query vector, by cosine similarity.

Why it exists. BM25's fatal blind spot: the query how to fix my car making a weird noise shares zero terms with the perfect document titled Diagnosing Unusual Engine Sounds in Automobiles. Lexical retrieval returns nothing. Embeddings put those two texts nearly on top of each other, because the model learned that car≈automobile and weird noise≈unusual sounds from a giant corpus.

How it works. Exact kNN means comparing the query vector against every document vector — O(N·d), i.e. 10M docs × 768 dims × 4 bytes = 30 GB of dot products per query. Absurd. So we use approximate nearest neighbor, in practice HNSW (Hierarchical Navigable Small World).

Sub-Concept: HNSW. Build a multi-layer proximity graph. Each vector is a node connected to its ~M nearest neighbors. The top layer is a sparse random subset with long-range links (an "express highway"); each layer down is denser and more local. To search: enter at the top layer, greedily walk to the neighbor closest to your query, and when you can't improve, drop a layer and repeat with finer granularity. It's a skip list generalized to metric space — the top layers get you into the right neighborhood in a few hops, the bottom layer refines. Lookup is O(log N) hops instead of O(N) comparisons.

 L2 (sparse):     ●───────────────────────●            ← long hops
                   \                     /
 L1 (denser):    ●──●────●──────●───────●──●
                     \    \    /       /
 L0 (all nodes):  ●●●●●●●●●●●●●●●●●●●●●●●●●●●●●        ← final refinement
                              ▲ query lands here

Pros. Catches paraphrase, synonymy, and cross-lingual matches that BM25 structurally cannot; ~95–99% recall vs exact kNN at a tiny fraction of the cost; sub-10 ms at millions of vectors. Cons — be specific here, this is where candidates hand-wave. (a) Memory: HNSW graphs must be RAM-resident to be fast (random graph traversal on disk = death by seeks), costing roughly num_vectors × dims × 4 bytes × 1.1 — 10M × 768 dims ≈ 31 GB per shard replica, which is a real budget line, mitigated by scalar/product quantization down to int8 (~4× smaller) at some recall cost. (b) Approximate means you can silently miss the true best result and never know. (c) Terrible at exact matching — search a product SKU or an error code and the embedding shrugs; vectors are fuzzy by construction. (d) Deletes are awkward — removing a node can disconnect the graph, so deletes are tombstoned and only cleaned on merge, and heavy churn degrades recall. (e) The embedding model itself must be run at index time and query time, adding inference latency and a hard versioning problem: changing the model invalidates every vector and requires reindexing everything. Complexity. Search O(log N) hops × M distance computations; build O(N log N); space O(N·d) in RAM. When to use which. Decision rule: use BM25 when the user's words are likely the document's words (code, IDs, names, error messages, legal); use vectors when they're likely not (natural-language questions, support search, discovery); and in production, use BOTH — hybrid retrieval. The standard hybrid is: run BM25 and kNN in parallel, then fuse the two ranked lists with Reciprocal Rank Fusion: RRF_score(d) = Σ over lists of 1/(60 + rank_of_d_in_list). RRF is beloved because it needs no score normalization at all — it only uses ranks, sidestepping the fact that a BM25 score of 15 and a cosine of 0.87 are incomparable quantities. Alternatives to HNSW worth naming: IVF (cluster vectors, search only the nearest few clusters — much less RAM, lower recall, better for billion-scale on disk) and product quantization (compress vectors lossily, ~10–30× smaller, used by FAISS at Meta scale). Use HNSW up to tens of millions of vectors per shard; IVF+PQ beyond that or when RAM is the binding constraint.

6.6Learning to Rank (LTR)#

What it is. Replace hand-tuned weights (§6.4) with a machine-learned model — typically gradient-boosted trees (LambdaMART) — trained on real user behavior to order results.

How it works. A two-stage pipeline, and the two-stage-ness is the point. Stage 1 (retrieval/recall): BM25 (and/or kNN) cheaply narrows 10 million docs to ~1,000 candidates — this must be fast, so it's the index doing what the index is good at. Stage 2 (reranking/precision): for those 1,000 only, compute a rich feature vector — BM25 score per field, title match, freshness, click-through rate, price, seller rating, personalization signals, query-document embedding similarity — and run the model to reorder. Training labels come from click logs (with click-position bias correction) or human judgments, and the model optimizes a ranking metric like NDCG (Normalized Discounted Cumulative Gain — rewards putting good results high, with a logarithmic discount by position, because position 1 matters vastly more than position 10).

Why it works. The expensive model only touches 1,000 docs instead of 10,000,000, so you can afford 100× the computation per document. Every large-scale ranking system on earth — Google, Amazon, Airbnb, LinkedIn — is this two-stage shape.

Pros. Large, measurable relevance gains (5–20% NDCG over hand-tuning is typical); it learns interactions between signals that no human would find; it adapts automatically as behavior shifts. Cons. Needs lots of behavioral data (a cold-start non-starter for a new product); the model is a black box, so "why is this result #1?" becomes unanswerable to the merchandising team; click-bias feedback loops (you can only learn from what you showed, so the model entrenches its own past choices unless you deliberately inject exploration); and it adds real infrastructure — a feature store, training pipelines, model deployment, monitoring for drift. Complexity. Reranking is O(candidates × features × trees) — typically 5–30 ms for 1,000 candidates. When to use it. Decision rule: BM25 until you have traffic; BM25 + a few function-score signals until hand-tuning breaks (~5 competing weights); LTR once you have millions of labeled interactions AND a team to own the pipeline. Reaching for LTR before you have click data is a classic over-engineering tell in an interview.

6.7Ranking Comparison Table & Decision Rule#

The decision rule, in one breath: "Filters in filter context; BM25 for text; add function-score decay when recency or distance obviously matters; add kNN + RRF when your users ask questions in words your documents don't use; add LTR only once you have the click data and the team to own it — and never skip a rung, because each rung costs an order of magnitude more operational complexity than the one below."

7Distributed Architecture — Shards, Replicas, Cluster State & Coordination#

7.1The Cluster Picture#

┌──────────────────────────── ELASTICSEARCH CLUSTER ────────────────────────────┐
│                                                                               │
│  MASTER-ELIGIBLE NODES (3, odd number — quorum = 2)                           │
│   ┌────────┐   ┌────────┐   ┌────────┐                                        │
│   │ M1 ★   │◄─►│ M2     │◄─►│ M3     │   elected master owns CLUSTER STATE:   │
│   │(elected)│   │        │   │        │    • index metadata + mappings         │
│   └────────┘   └────────┘   └────────┘    • shard→node allocation table       │
│        │  publishes cluster state          • node membership                   │
│        │  (2-phase, quorum-committed)      NOT in the data path!               │
│        ▼                                                                       │
│  ┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐                │
│  │ DATA D1   │   │ DATA D2   │   │ DATA D3   │   │ DATA D4   │                │
│  │  P0  R2   │   │  P1  R0   │   │  P2  R1   │   │  R0  R1   │                │
│  └───────────┘   └───────────┘   └───────────┘   └───────────┘                │
│    P = primary shard,  R = replica    (a primary and its replica are NEVER    │
│                                        placed on the same node — that would    │
│                                        make the replica useless)               │
│                                                                               │
│  COORDINATING NODES (optional, dedicated)   ← scatter/gather + merge only     │
│  INGEST NODES (optional)                    ← run transform pipelines         │
└───────────────────────────────────────────────────────────────────────────────┘

Node roles, and why separating them matters. A master-eligible node maintains cluster state and makes allocation decisions; it does no searching. A data node holds shards and does the actual work. A coordinating node holds no data and only scatters/gathers. The reason to dedicate masters is a beautiful failure story: if your master also holds data, then a heavy aggregation that pushes that node into a long garbage-collection pause makes the master unresponsive, the cluster thinks it died, an election starts, and now a slow query has caused a cluster-wide control-plane outage. Benefit of dedicated masters: the control plane is isolated from data-plane load. Cost: three more machines that hold nothing. Mitigation: they can be small — masters need CPU and a little RAM, not disk.

7.2Cluster State and the Elected Master (consensus, applied)#

The cluster state is a single data structure — index metadata, mappings, the shard→node routing table, node membership — that every node must agree on. Two nodes disagreeing about where shard 3's primary lives means writes going to two places. So the cluster state needs consensus (File 08).

Elasticsearch 7+ uses Zen2, a Raft-flavored protocol: master-eligible nodes elect a leader; the leader publishes each state update in two phases (publish → commit) and only commits once a quorum (majority) of master-eligible nodes has acknowledged. That quorum requirement is what prevents split-brain — the scenario where a network partition leaves two halves of the cluster each electing a master, each accepting writes, and each diverging irreparably.

Sub-Concept: Quorum and split-brain, concretely. With 3 master-eligible nodes, a majority is 2. Partition them into {M1} and {M2, M3}: the lone M1 cannot reach 2 and therefore steps down and refuses writes; the {M2,M3} side elects a master and continues. Exactly one side survives — by arithmetic, not by luck. With an even number, say 4 split 2–2, neither side has 3, so the whole cluster stalls: you got the downside of more nodes with no availability gain. This is why the master-eligible count is always odd. (Pre-7.x you set minimum_master_nodes by hand, and setting it wrong was the single most common cause of catastrophic split-brain data loss in Elasticsearch's history; 7.x computes it automatically via a voting configuration — a rare case of a system removing a footgun by removing the knob.)

Notice the deliberate architecture: consensus is used for the control plane (metadata) but NOT for the data plane (documents). Every document write does not go through Raft — it goes to a primary, which replicates to its in-sync replicas directly. Benefit: writes don't pay a consensus round-trip, so throughput is enormous. Cost: the data plane's guarantees are weaker than Raft's; under nasty partitions you can lose acknowledged writes in edge cases — this is exactly the class of issue Jepsen famously surfaced in older versions (Jepsen is Kyle Kingsbury's independent test framework that subjects distributed databases to injected partitions, clock skew, and crashes while checking whether their consistency claims actually hold; "failed its Jepsen test" is the industry's shorthand for "the marketing said safe, the partitions said otherwise"). Mitigation: primary terms + sequence numbers + a documented, honest position — Elasticsearch is not a system of record. Say that in an interview and you've distinguished yourself.

7.3Replication, In-Sync Copies, and Failover#

Each write goes to the primary, which assigns a monotonically increasing sequence number and forwards to the in-sync replicas; the primary acks the client only after they all respond (§3.1). Each primary also carries a primary term — a number incremented on every failover — so a stale primary that comes back after a partition is recognized (its term is old) and demoted rather than allowed to overwrite newer data. Term + seqno together are how a promoted replica figures out precisely which operations it's missing and requests only those, instead of copying the whole shard.

Failover flow. The master pings nodes; when D2 misses its checks, the master marks its shards unassigned, promotes a replica of P1 to primary (bumping the primary term), and updates the cluster state. Cluster health goes yellow (all primaries assigned, some replicas missing) rather than red. After index.unassigned.node_left.delayed_timeout (default 1 minute), the master starts building fresh replicas elsewhere.

That one-minute delay is a wonderfully instructive design decision. Without it, a node restarting for a 30-second config change would trigger the cluster to copy hundreds of gigabytes across the network to rebuild replicas — only for the node to return and make the whole copy redundant. Benefit of the delay: transient blips cost nothing. Cost: you run at reduced redundancy for that minute. Mitigation: for planned maintenance, explicitly disable shard allocation first (cluster.routing.allocation.enable: primaries), restart, re-enable — the standard rolling-restart procedure.

Health colors, precisely: green = all primaries and all replicas assigned. Yellow = all primaries assigned, ≥1 replica isn't — fully functional, reduced redundancy, and notably a single-node dev cluster is permanently yellow because a replica can never be placed on the primary's own node. Red = at least one primary is unassigned → you are missing data, some queries return partial results. Knowing that yellow is not an emergency and red is an outage is basic operational literacy.

7.4Routing and the Sharding Math#

shard = hash(routing) % number_of_primary_shards, where routing defaults to _id. It's plain modulo hashing — File 06 tells you exactly why the shard count is then frozen forever: changing the divisor remaps nearly everything.

Custom routing is the escape hatch worth knowing. If you route by customer_id, all of one customer's documents land on one shard — so a query filtered to that customer can be sent to that single shard instead of scattered to all 20, eliminating the scatter-gather tax of §0.4 entirely. Benefit: 20× less work per query and vastly better tail latency. Cost: hotspots — your one whale customer with 40% of the data lands on one shard and melts it, and you cannot rebalance them off it. Mitigation: route by customer only when tenant sizes are bounded and similar; for whales, give them a dedicated index. This "route to co-locate vs. spread to balance" tension is the same one File 04 raised about partition keys, and it never goes away.

Sizing rules that carry real weight in an interview:

8Distributed Search Is Harder Than It Looks — Scoring, Pagination & Aggregation#

§0.4 promised that "global truth is not locally knowable." Here's the bill.

8.1The Distributed IDF Problem#

BM25 needs N (total docs) and df (docs containing the term) — corpus-wide numbers. But each shard computes its score using only its own N and df. Usually that's harmless: with random routing, term distribution is statistically similar across shards, so local IDF ≈ global IDF.

It breaks — visibly and confusingly — when shards are small or skewed. Imagine 5 shards; the term quokka appears in 100 docs total but, by bad luck or custom routing, 90 of them live on shard 1. Shard 1 computes df = 90 out of its 200,000 docs → a low IDF (locally it's a common word). Shard 2 sees df = 2 out of 200,000 → a very high IDF. The same document, with identical text, scores differently depending on which shard it happens to live on, and the merged global ranking is wrong. The classic bug report is "my test index with 5 shards and 10 documents returns nonsense ordering, but it's perfect with 1 shard" — that's this, exactly.

The fix and its price. search_type=dfs_query_then_fetch adds a preliminary round trip: ask every shard for its local term statistics, sum them into true global stats, then run the query with those corrected numbers distributed to all shards. Benefit: exactly correct IDF. Cost: an extra full network round-trip on every query — a real latency tax. Mitigation, and the right production answer: don't pay it. Instead make the problem disappear by having enough documents per shard that random distribution makes local ≈ global. Statistical convergence is free; DFS is not. Use DFS only for tiny indices where correctness of ordering matters more than latency.

8.2The Deep Pagination Problem#

A user asks for from: 10000, size: 10 — page 1,001. To find the global documents 10,001–10,010, the coordinator must ask every shard for its top 10,010 (any of them might be in the global window), then merge and discard 99.9% of what it received.

With 20 shards: 200,200 (id, score) pairs shipped and sorted to return 10 results. Memory and CPU scale linearly with page depth × shard count — so page 10,000 is a cluster-killer. This is why Elasticsearch hard-caps from + size at 10,000 by default (index.max_result_window). That limit isn't arbitrary conservatism; it's a guardrail against an O(depth × shards) fan-out that would OOM your coordinator.

The three alternatives, with their decisive conditions:

**search_after (cursor pagination). Instead of an offset, pass the sort values of the last result you saw** (e.g. [score, _id]), and each shard resumes from that point using its sorted structures. Cost is constant per page regardless of depth. Pro: infinitely deep, cheap, and it's live (sees new data). Con: you can only go forward, one page at a time — no "jump to page 500," so it's unusable for a classic numbered pager. Use when: infinite scroll, or any API-driven full walk. This is the default right answer, and it's the exact same cursor-vs-offset trade-off as in a SQL API (File 11).

**scroll. Freezes a point-in-time snapshot of the index and hands you a cursor to walk it all. Pro: perfectly consistent view — essential for exporting or reindexing, since a live index would shift under you. Con: it pins segments so they can't be merged away, so a forgotten scroll context leaks disk and heap; it's stateful and expensive. Use when: batch export/reindex only — never** for user-facing pagination. (Modern versions supersede this with search_after + a PIT (point-in-time) ID, getting both consistency and statelessness.)

Just don't. Nobody visits page 1,001. If they're trying to, they don't want pagination — they want a better query, or a bulk export API. Saying "I'd cap the result window at 10k and offer search_after for programmatic access, because deep pagination is a UX smell" is a strong interview move.

8.3The Distributed Aggregation Problem (and how to be honest about approximation)#

A terms aggregation — "top 10 categories by document count" — hits the same wall. Each shard returns its top 10 and the coordinator sums them. But consider category X ranked #11 on every one of 20 shards: it appears in zero shard responses, yet its true global total might beat everything. Your "top 10" is simply wrong, and nothing in the response tells you so unless you look.

**Mitigation 1 — shard_size. Ask each shard for its top N × 1.5 + 10 (the default heuristic) rather than top N. More candidates → far lower chance of missing a globally-big-but-locally-#11 term. Benefit: accuracy approaching exact. Cost:** more memory and network per query, growing with shard_size × shards.

**Mitigation 2 — read doc_count_error_upper_bound. Elasticsearch tells you** the maximum count it might have missed. A mature answer isn't "aggregations are approximate, oh well" — it's *"I'd surface doc_count_error_upper_bound, and if it's non-zero and material, raise shard_size until it isn't."*

Cardinality aggregation ("how many unique users?") uses HyperLogLog.

Sub-Concept: HyperLogLog. Counting distinct items exactly requires remembering every item you've seen — O(unique) memory, which for a billion user IDs is gigabytes per shard, and then you'd have to ship those sets around to merge them. HLL instead hashes each item to a uniformly random bit string and tracks only the maximum number of leading zeros seen. The intuition is a coin-flip argument: seeing a hash starting with 10 zeros is a 1-in-1024 event, so you've probably seen ~1024 distinct items. One estimator is wildly noisy, so HLL splits the hash space into m buckets (say 4,096), keeps a per-bucket max-leading-zeros in ~5 bits, and combines them with a harmonic mean to crush the variance. Result: count a billion distinct items in ~1.5 KB with ~2% error. The property that makes it perfect for scatter-gather: HLL sketches are mergeable — combining two shards' sketches is a per-bucket max(), giving exactly the sketch you'd have built over the union. Benefit: O(1) memory, trivially distributable. Cost: it's an estimate, ±2%, and it can never be made exact. Mitigation: Elasticsearch keeps exact counts below a configurable precision_threshold (small sets are exact) and switches to HLL above it — best of both.

The pattern across all three problems is the same, and it's the thesis of this section: in a scatter-gather system, exact global answers require either extra round-trips or unbounded memory, so mature systems return principled approximations and tell you the error bar.

9Pros, Cons & Trade-offs#

Benefits (with the WHY for each)#

Full-text queries in milliseconds over billions of documents. Because the inverted index converts O(corpus bytes) scanning into O(matching postings) traversal (§0.1), with skip lists making it O(rarest term) (§5.3), and block-max WAND skipping even most of that (§6.3). This isn't a constant-factor speedup; it's a complexity-class change.

Relevance ranking out of the box. BM25 gives genuinely good ordering with zero training data and zero tuning (§6.3), because it encodes a decades-validated probabilistic model of what "aboutness" means. You get an 80th-percentile search product on day one.

Horizontal scalability of data volume. Shards are independent Lucene indices (§2.5), so adding nodes adds capacity linearly, and replicas add read throughput linearly. Nothing needs to coordinate on the data path.

Aggregations and analytics on the same data. Doc values (§2.9) give you a columnar store alongside the inverted index, so the system that finds your documents also facets, buckets, and charts them — which is why Elasticsearch quietly became the world's default log-analytics engine, not just a search engine.

Near-real-time visibility. ~1 second from write to searchable (§2.8) — fast enough that it feels live, achieved without giving up the immutability that makes reads fast. That's an engineering compromise, and a good one.

Schema flexibility with dynamic mapping. Throw arbitrary JSON at it and it infers types — enormously valuable for logs, where you can't know the shape in advance.

Costs & Trade-offs (be rigorous — this is what interviews probe)#

It is not a database, and treating it like one is the #1 production disaster. No multi-document ACID transactions, no joins (denormalize or use the limited nested/join field types, both of which have severe costs), no read-your-writes guarantee (refresh delay, §2.8), and a replication model that has historically been shown to lose acknowledged writes under adversarial partitions (§7.2). Mitigation, non-negotiable: the source of truth is Postgres/Kafka/S3; Elasticsearch is a derived index that you must be able to rebuild from scratch at any time. If you can't rebuild it, you've built a time bomb.

A full second copy of your data — sometimes more. Inverted index + doc values + _source + replicas typically means Elasticsearch storage runs 1.5–3× your raw data. Mitigation: index: false on display-only fields, doc_values: false on never-aggregated fields, _source excludes, best_compression codec, and ILM tiering to cheap storage (§7.4).

The mapping is nearly immutable; the reindex is your recurring tax. §2.3. Mitigation: aliases + versioned indices + a reindex pipeline you build before you need it. Teams that skip this take downtime on their first mapping mistake.

JVM heap is a hard, unforgiving wall. Keep heap ≤ 31 GB (above that the JVM loses compressed ordinary object pointers, so a 32 GB heap actually holds less usable data than a 31 GB one — an infamous cliff), and leave half the machine's RAM to the OS page cache, because that's what makes segment reads fast (File 02, the memory hierarchy, deciding your hardware spec). Oversharding, huge aggregations, and giant bulk requests all cause heap pressure → long GC pauses → nodes appearing to leave the cluster → shard reallocation storms → cascading failure.

Every query touches every shard. §0.4. Mitigation: custom routing when the access pattern allows (§7.4), fewer/bigger shards, and query-phase timeouts so one sick shard can't hold the whole response hostage.

Operational complexity is real and permanent. Cluster sizing, shard planning, ILM policies, JVM tuning, merge tuning, version upgrades, snapshot strategy. Mitigation: if search isn't your core differentiator, use a managed service (Elastic Cloud, OpenSearch Service) and spend your engineers on ranking instead of on GC flags.

Relevance is never "done." It's a product surface requiring continuous measurement (NDCG, click-through, zero-result rate) and A/B testing — permanently.

The senior rule: Never make Elasticsearch your system of record. Index into it from a durable log or database you can replay, keep the mapping versioned behind an alias, and be able to rebuild the entire cluster from scratch in an afternoon. Every team that has ignored this has learned it the expensive way.

10Interview Diagnostic Framework (Symptom → Solution)#

11Real-World Engineering Scenarios#

11.1GitHub Code Search (Blackbird) — when the standard analyzer is wrong#

GitHub ran code search on Elasticsearch for years and eventually wrote their own engine (Blackbird). The reason is the most instructive lesson in this file: code is not prose, and every default in a text search engine is tuned for prose.

Takeaway: the analysis chain is not a detail — it is the product decision. When your corpus isn't prose, every default (tokenizer, lowercasing, stemming, positions) is wrong, and knowing which default to break is the whole job. Say this in an interview when someone asks "would you use Elasticsearch for X?" — the answer depends entirely on whether X is prose.

11.2Uber Eats — search where relevance means geography and time#

When you open Uber Eats, the "search" is not "which restaurants match pizza" — it's "which of the restaurants that can actually deliver to me right now best match pizza, ranked by what I'll probably order."

Takeaway: in most real products, text relevance is one signal among many, and the biggest latency win comes from ruthlessly ordering cheap, selective, cacheable filters before expensive scoring. When you design a search system on a whiteboard, draw the filter funnel before you draw BM25.

11.3Netflix / Large-Scale Log Analytics — the Elasticsearch that isn't search#

Netflix (like Uber, Slack, and essentially every large engineering org) runs enormous Elasticsearch clusters where nobody is doing full-text search — they're doing time-bounded, filtered analytics over petabytes of logs and traces. The architecture is different enough to be worth its own case study.

Takeaway: the largest Elasticsearch deployments on earth barely use relevance ranking — they use the inverted index as a distributed, columnar, time-partitioned filter engine. When an interviewer says "design a logging/observability system," the answer is Kafka → time-based indices → ILM tiering → filters-and-aggregations, and the interesting engineering is entirely in cost, cardinality, and ingest tuning, not in BM25.

12Interview Gotchas & Failure Modes#

Classic Questions (and the crisp answers)#

"Why can't a database just do full-text search?" Because a B-tree is indexed by the whole value and only exploits prefixes, so a mid-string match forces a full scan — O(corpus). And a WHERE clause returns a set, not a ranked list, while search's actual job is ordering by relevance. You need the index inverted (content → doc) and a scoring model. *(Postgres has tsvector/GIN, which is a genuine inverted index — a fine answer up to a few million docs, but it lacks distribution, BM25 tuning, and aggregations, so name it as the "don't add a cluster yet" option.)*

"Explain BM25 and how it improves on TF-IDF." Same intuition — frequent term in this doc, rare term in the corpus — but two fixes. TF saturates via f/(f + k1), so the 100th occurrence adds nearly nothing (killing keyword stuffing), and length normalization is principled, scaling the penalty by |D|/avgdl with a tunable b. It's derived from a probabilistic relevance model, so its knobs mean something.

"Why is Elasticsearch 'near real-time' and not real-time?" Because segments are immutable. A document is durable the moment it's in the translog, but it's only searchable once it's inside a segment, and segments are built on refresh — every ~1 s. Building a segment per document would be insane, so NRT is the deliberate price of the immutability that makes reads fast and lock-free.

"What happens when you delete a document?" Nothing is deleted. A bit is set in the segment's deletion bitmap; the terms stay in the posting lists and are filtered out at query time. The space is only reclaimed when a merge rewrites the segment without the dead docs. An update is a delete plus an insert of a whole new document.

"Why can't you change the number of shards?" Routing is hash(_id) % num_primaries. Change the divisor and virtually every document maps to a different shard — the File 06 modulo problem. Elasticsearch chose deterministic, coordination-free routing over rebalanceability; the escape hatches are _split/_shrink into a new index, or time-based indices where each new index picks a fresh count.

"How do you pick shard count?" Target 10–50 GB per shard; keep shards ≤ ~20 per GB of heap per node; shards ≥ node count so nothing idles, but not so many that fan-out and heap explode. For time-series, don't guess at all — roll over by size with ILM.

"How does the cluster avoid split-brain?" Cluster state changes are quorum-committed by an elected master via Zen2 (Raft-like), with an odd number of master-eligible nodes so a partition mathematically leaves at most one side with a majority. Note the design: consensus governs metadata, not documents — document writes go primary → in-sync replicas without a consensus round-trip, which is fast but is exactly why it's not a system of record.

"Why is my score different for the same document on different shards?" Because IDF is computed from local shard statistics. With enough docs per shard it converges to global; with small or skewed shards it doesn't. Fix it with dfs_query_then_fetch (costs a round-trip) or, better, with enough documents that the statistics converge for free.

"When would you use vector search instead of BM25?" When the user's words won't be the document's words — natural-language questions, paraphrase, discovery. Never for exact tokens like SKUs, error codes, or identifiers, where embeddings are actively bad. In production, run both and fuse with RRF, which needs no score normalization because it only uses ranks.

"How do you keep Elasticsearch in sync with your database?" CDC (change data capture): Debezium reads the DB's replication log → Kafka → an indexer service → bulk-index. Why not dual writes? Because writing to the DB and to Elasticsearch as two independent operations has no atomicity: one succeeds, the other fails, and you silently diverge forever. The log-based approach gives you ordering, replayability, and backpressure — and it means you can always rebuild the index from scratch, which §9's senior rule demands.

Failure Modes & Mitigations#

Oversharding ("a thousand tiny shards"). Each shard costs heap for its FST and segment metadata, a slot in the cluster state, and a task per query. Thousands of 200 MB shards means a bloated cluster state that the master must publish to every node on every change, heap pressure, and a fan-out of thousands of tasks per query. → Mitigation: consolidate with _shrink or reindex to 10–50 GB shards; use ILM rollover by size rather than creating an index per tenant per day.

Mapping explosion. One service starts emitting {"error_a3f9": ...} with a new field name per request; dynamic mapping obediently adds each one. The mapping grows to 50,000 fields, the cluster state becomes hundreds of megabytes, publishing it saturates the master, and the cluster falls over. → Mitigation: mapping.total_fields.limit, dynamic: strict (or false) in production indices, and use flattened fields for arbitrary key-value blobs.

Heap pressure → GC pause → phantom node failure → reallocation storm. A giant aggregation or a huge bulk request fills the heap; a stop-the-world GC pause of 30 seconds makes the node stop answering pings; the master concludes it's dead and starts relocating its shards, which copies hundreds of gigabytes across the network, which saturates the network, which makes other nodes miss pings. The cluster tears itself apart under load it created. → Mitigation: heap ≤ 31 GB (compressed-oops cliff); circuit breakers (on by default) to reject requests that would blow the heap; search.max_buckets; delayed allocation (§7.3) so a blip doesn't trigger a copy; dedicated master nodes so the control plane can't be starved by data-plane GC.

Merge storms. A bulk backfill creates segments faster than merging can consolidate them; merge threads saturate disk I/O; search latency goes through the roof; the segment count keeps climbing anyway. → Mitigation: refresh_interval: -1 and replicas: 0 during the backfill, then restore both; throttle with indices.store.throttle; give merges fast NVMe; never _forcemerge a live index (you'll create an unmergeable giant segment that accumulates deletes forever).

Hot shard from custom routing. You routed by tenant_id for locality; your biggest customer is 40% of the corpus and now one node is at 100% CPU while nineteen idle, and you cannot rebalance them off. → Mitigation: route by tenant only when tenant sizes are bounded; give whales dedicated indices; use a composite routing key (tenant_id + bucket) to spread big tenants across a few shards while keeping locality.

The unbounded query. A user submits a leading-wildcard *error*, a regexp with catastrophic backtracking, or a terms aggregation over a million-cardinality field. One query eats the cluster. → Mitigation: query timeouts and terminate_after; disallow wildcard/regexp on hot paths via a query-sanitizing service in front (never expose the raw DSL to the internet — it's a remote-code-quality footgun); search.max_buckets; keep search users in a separate thread pool from ingest.

Silent relevance rot. Nobody changed the code, but someone added synonyms, a boost, and a new field, and now the zero-result rate has doubled. → Mitigation: treat relevance as a product surface with real metrics (NDCG on a judgment set, zero-result rate, click-through at position, abandonment) and never ship a ranking change without an A/B test. The single most common failure of a search team is having no way to tell whether a change made things better.

13Whiteboard Cheat Sheet#

╔══════════════════════════════════════════════════════════════════════════════╗
║  DISTRIBUTED SEARCH — BOARD DUMP                                             ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ WHY: B-tree = doc→content, prefix-only ⇒ LIKE '%x%' = full scan O(corpus).   ║
║      Search needs content→doc  AND  ranking (users read 10 results).         ║
║      ⇒ INVERT THE INDEX + SCORE IT.                                          ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ CORE STRUCTURE                                                               ║
║   term dict (FST, RAM, O(term len))  ──►  posting list (sorted doc IDs)      ║
║        distributed ─► [1,2,17,90…] +tf +positions   ◄── skip list every 128  ║
║   AND = intersect (drive from RAREST term!)   OR = union                     ║
║   + doc values  = columnar docID→value  (sort/aggregate)                     ║
║   + stored _source = original JSON (display only)                            ║
║   + deletion bitmap = tombstones (purged only by MERGE)                      ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ SEGMENTS (why everything is weird)                                           ║
║   buffer ──refresh 1s──► SEGMENT (immutable, searchable)  ⇒ NEAR-REAL-TIME   ║
║   write ──► TRANSLOG (durable on ack)  ──flush──► fsync + truncate           ║
║   many small ──TIERED MERGE──► few big  (~10/tier, cap 5GB)                  ║
║   immutable ⇒ no read locks + max compression + NRT + tombstones + merges    ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ COMPRESSION:  [1002,1005,1009,1017] ─delta─► [1002,3,4,8] ─FOR pack 4 bits─► ║
║               128/block, SIMD decode, PFOR patches outliers → 4–8× smaller   ║
║               (space win AND time win: we are I/O bound, not CPU bound)      ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ ANALYSIS (same chain at INDEX and QUERY time — or you get 0 results!)        ║
║   char filters → TOKENIZER (standard|keyword|edge_ngram|pattern) →           ║
║   token filters (lowercase → stop? → stem → synonym → asciifold)             ║
║   text = analyzed (search it)   |   keyword = one term (filter/sort/agg it)  ║
║   edge_ngram at INDEX only, standard at QUERY  ← autocomplete                ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ SCORING                                                                      ║
║   BM25 = IDF · f(k1+1) / (f + k1(1 − b + b·|D|/avgdl))    k1=1.2  b=0.75     ║
║        saturating TF (kills stuffing) + length norm (short focused doc wins) ║
║        IDF = ln(1 + (N−df+.5)/(df+.5))  ⇒ stop words auto-deweighted         ║
║   ladder: FILTER (cached bitset, no score) → BM25 → function-score(decay,    ║
║           popularity) → kNN hybrid (RRF: Σ 1/(60+rank)) → LTR (2-stage)      ║
║   block-max WAND: skip blocks that can't beat current #10                    ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ QUERY PATH — QUERY THEN FETCH                                                ║
║   client → coordinator ─scatter→ ALL shards (1 copy each)                    ║
║        each: FST → postings → skip-merge → BM25 (LOCAL stats!) → top-K ids   ║
║   ←── (id,score) only ── merge → global top 10 ── FETCH _source for those 10 ║
║   scatter-gather taxes: p99 = SLOWEST shard | local IDF ≠ global | deep page ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ CLUSTER                                                                      ║
║   3 dedicated MASTER-eligible (odd! quorum=2, Zen2/Raft) → cluster state     ║
║      consensus for METADATA only — docs go primary→in-sync replicas          ║
║   shard = hash(_id) % num_primaries  ⇒ SHARD COUNT FROZEN FOREVER (File 06)  ║
║   shard = a whole Lucene index.  P and R never on same node.                 ║
║   green=all assigned | yellow=replica missing (fine) | red=PRIMARY missing!  ║
║   SIZING: 10–50 GB/shard · ≤20 shards per GB heap · heap ≤31 GB (oops cliff) ║
║           half of RAM to page cache · time-series ⇒ ILM hot→warm→cold→delete ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ DISTRIBUTED GOTCHAS                                                          ║
║   IDF skew  → dfs_query_then_fetch (extra RTT) or just more docs/shard       ║
║   deep page → from+size caps at 10k; use search_after+PIT; scroll=export only║
║   terms agg → approximate! raise shard_size, read doc_count_error_upper_bound║
║   cardinality → HyperLogLog: ~1.5 KB, ±2%, MERGEABLE (max per bucket)        ║
╠══════════════════════════════════════════════════════════════════════════════╣
║ DANGER: NOT A DATABASE. no txn, no joins, refresh lag, can lose acked writes ║
║   ⇒ SoT = Postgres/Kafka. CDC (Debezium→Kafka→bulk), NEVER dual writes.      ║
║   ⇒ alias + versioned index (products_v1) — mapping change = FULL REINDEX    ║
║   ⇒ MUST be rebuildable from scratch                                         ║
║ KILLERS: oversharding · mapping explosion · GC pause→reallocation storm ·    ║
║          merge storm · hot shard from routing · leading-wildcard query       ║
║ INGEST TUNING: _bulk 5–15 MB · refresh_interval 30s (or −1 + replicas 0 for  ║
║          backfill, then restore) · force-merge ONLY read-only indices        ║
║ COST: index:false (never match) · doc_values:false (never sort/agg) ·        ║
║       _source excludes · best_compression · ILM tiering                      ║
╚══════════════════════════════════════════════════════════════════════════════╝

14One-Sentence Summary for an Interviewer#

"A distributed search engine solves the problem that a **B-tree is indexed document→content and therefore can't answer LIKE '%x%' without an O(corpus) scan, and has no notion of relevance — so it inverts the index (term → delta-compressed, skip-list-accelerated posting list, fronted by an FST term dictionary that finds any of 50 million terms in O(term-length)), builds it out of immutable segments (which is exactly why it's near-real-time, why deletes are tombstones, and why background tiered merging is load-bearing), ranks with BM25 (saturating TF kills keyword stuffing** and |D|/avgdl length-normalization makes the short focused document win), and shards the whole thing so every query is a scatter-gather — which buys unlimited corpus size but permanently taxes you with tail latency at p99 = the slowest shard, local-vs-global IDF skew, approximate aggregations, and deep-pagination fan-out — and the senior move is to say it is not a database: put the source of truth in Postgres or Kafka, feed the index by CDC behind a versioned alias because any mapping change means a full reindex, keep shards at 10–50 GB with heap under 31 GB and half of RAM left to the page cache, put every yes/no clause in filter context so it's a cached bitset, and climb the relevance ladder — filters → BM25 → function-score decay → hybrid kNN with RRF → learning-to-rank — only one rung at a time, because each rung costs an order of magnitude more operational complexity than the one below it."

End of File 13. Next → File 14: Vector Databases & AI Infrastructure (embeddings, HNSW, quantization, RAG) — §6.5's kNN detour gets its own chapter, where the curse of dimensionality kills every index you know and approximation becomes the only way out. Prompt me to continue.