Search Autocomplete and Inverted Index: Staff Interview Calibration and Runbooks

Chapter 16 of Part II, Production System Blueprints, continued from Search Autocomplete and Inverted Index: Deep Dives, Data Models, and Failure Modes. This lesson covers sections 7 to 10 of the chapter.

7. Ten Probing Follow-Up Questions (With Staff Answers)

Q1: "Why not use Redis Sorted Sets (ZSET) for autocomplete instead of a custom Trie?"

Senior Trap: "We can store prefixes as keys in Redis and fetch top completions with ZRANGE."

Staff Answer: "Redis ZSETs work for toy datasets, but at scale they suffer from massive memory explosion. Storing every prefix of every search term as an independent ZSET key generates hundreds of millions of Redis keys, duplicating strings repeatedly and consuming hundreds of gigabytes of expensive RAM. Furthermore, updating scores during traffic spikes causes lock contention on popular keys. Our in-memory Trie/FST compresses prefixes and suffixes into a 2.8 GB memory-mapped file that serves 100,000 QPS locally with zero network hops."

Q2: "How do you handle typo-tolerance and spelling correction in autocomplete?"

Senior Trap: "Run Levenshtein distance on all dictionary words for every keystroke."

Staff Answer: "Calculating Levenshtein edit distance dynamically against 20,000,000 words takes 150ms per keystroke, violating our 15ms budget. Instead, we use two optimizations: (1) Precomputed Common Typos: For high-volume search queries, the offline Spark pipeline analyzes query reformulations (e.g. users typing "iphnoe" followed immediately by "iphone") and inserts the correct suggestion directly under the mistyped prefix node; (2) FST Levenshtein Automata: For full-text search queries, we compile the query into a DFA that intersects the Lucene FST terms dictionary in O(N) time bounded strictly by edit distance <= 2."

Q3: "What happens if a document shard in Elasticsearch crashes during a search query?"

Senior Trap: "The search query fails and returns an HTTP 500 error."

Staff Answer: "Search queries should never fail completely due to a single shard dropout. The Query Broker implements Graceful Degradation with Partial Results: If Shard 18 fails to respond after its hedged timeout, the coordinator returns the aggregated results from the remaining 63 shards along with a metadata header: {"shards_successful": 63, "shards_total": 64, "partial_results": true}. Viewers still see relevant search results instantaneously, and the UI displays a non-intrusive indicator if necessary."

Q4: "How do you ensure autocomplete suggestions reflect breaking trending news within minutes?"

Senior Trap: "Rebuild the entire 20-million word Trie every 60 seconds."

Staff Answer: "Compiling the full master Trie takes 15 minutes of Spark compute and cannot run every minute. We use a Two-Tier Trie Hierarchy: (1) The Master Trie contains stable long-term query frequencies and updates every 6 hours; (2) The Trending Delta Cache is a small in-memory HashMap updated in real time by an Apache Flink stream that detects sudden velocity spikes (e.g. an earthquake or celebrity death). At query time, the gateway merges the top 2 suggestions from the Trending Delta Cache with the top 3 suggestions from the Master Trie in < 0.2ms."

Q5: "Why do search engines use BM25 instead of simple TF-IDF?"

Senior Trap: "BM25 is just a newer version of TF-IDF with different constants."

Staff Answer: "Standard TF-IDF has a critical mathematical flaw: term frequency (TF) scales linearly without bound. If an author keyword-stuffs the word 'laptop' 500 times on a page, TF-IDF will rank that spam page higher than a genuine high-quality review. BM25 solves this by introducing Term Frequency Saturation: as TF increases, the score approaches an asymptotic ceiling governed by the parameter k1 (typically 1.2). Adding a 50th occurrence of a word yields almost zero incremental score. Furthermore, BM25 normalizes for document length (b = 0.75), preventing long encyclopedic articles from dominating short product descriptions."

Q6: "How do you achieve near-real-time indexing (NRT) in Lucene without killing search performance?"

Senior Trap: "Call commit() on the index after every document write."

Staff Answer: "Calling fsync() / commit() on every write is disastrous: it forces disk flushes, invalidates the OS page cache, and drops write throughput to < 100 docs/sec. Lucene achieves Near-Real-Time indexing by decoupling Flushing from Committing: writes are buffered in RAM and flushed every 1.0 second into the OS page cache as a new searchable in-memory segment (the refresh operation). Searching against in-memory segments is near-instantaneous. Durability is guaranteed separately by an append-only Transaction Log (Translog) that fsyncs periodically."

Q7: "How do you handle personalized autocomplete without blowing up memory?"

Senior Trap: "Build a custom Trie for every single registered user."

Staff Answer: "Building personalized Tries for 150 million users would require petabytes of RAM and is operationally unmanageable. We decouple Global Retrieval from Personalization: The in-memory Trie returns the top 10 globally popular suggestions for the typed prefix. The client application layer or API Gateway then applies a lightweight client-side or edge filter: if the user frequently purchases Sony audio equipment, it boosts "sony headphones" to the #1 slot while demoting "bose headphones" to #2. The core Trie remains completely stateless, shared, and globally cacheable."

Q8: "Why is Document Sharding preferred over Term Sharding for search?"

Senior Trap: "Document sharding is easier to code."

Staff Answer: "In Term Sharding, words are partitioned across nodes. A multi-word query like 'apple watch bands' requires the coordinator to fetch the entire posting list for 'apple' from Shard A, 'watch' from Shard B, and 'bands' from Shard C, and then intersect millions of document IDs across the data center network. This saturates switch backplanes and introduces massive network serialization latency. In Document Sharding, each shard holds a complete subset of documents; term intersection executes entirely in local CPU cache on each shard. The coordinator only gathers the top 100 scored document IDs."

Q9: "How do you prevent autocomplete from suggesting out-of-stock or discontinued products?"

Senior Trap: "Update the Trie immediately whenever an item runs out of stock."

Staff Answer: "Writing inventory mutations into the Trie on every stock change creates write contention on read-heavy data structures. We enforce Downstream Inventory Masking: The Trie returns query completion phrases, not specific SKUs. When the user taps a suggestion, the search coordinator executes the full query against the inverted index, where inventory_count > 0 is applied as an in-memory bitset filter on DocValues. Products with zero inventory are suppressed or pushed to the bottom of the search results page."

Q10: "How do you update the in-memory Trie on serving nodes without dropping active queries?"

Senior Trap: "Restart the Trie server with the new file or lock the Trie with a write mutex."

Staff Answer: "Acquiring a write lock blocks 100,000 QPS of read traffic, causing instant request queuing and timeouts. We use Blue/Green Hot Atomic Pointer Swapping with mmap: The Trie server downloads the new 2.8 GB immutable FST binary into a separate memory region via mmap. Once the file is fully verified and checksummed, the server executes a single atomic pointer swap in memory (atomic.StorePointer). In-flight queries finish on the old pointer; new queries immediately hit the new FST. The old FST is unmapped cleanly after all active readers complete."

8. Production Hardening & Operational Runbooks

Production SLOs & Alert Thresholds

Metric	Target Threshold	Severity & Action
Autocomplete Latency	< 15ms (Global p99)	P1 Alert: Check client cache rate & Trie CPU saturation
Full-Text Search SLA	< 45ms (Global p99)	P2 Alert: Check hedged queue & shard GC pause frequency
Index Replication Lag	< 1.0s CDC latency	P2 Alert: Autoscale Debezium indexing consumer pods
Trie Memory Footprint	< 80% host RAM	P2 Alert: Compact FST suffix trie; prune low-weight terms

Operational Incident Runbook: Mitigating Shard JVM GC Pause Storms

When an inverted index node experiences Stop-The-World (STW) garbage collection pauses:

1. Step 1 (Validate Hedging Engagement): Verify on the Query Broker dashboard that speculative hedged requests have automatically fired for the affected shard. If hedged queries are returning healthy results, the customer SLA is preserved.
2. Step 2 (De-register Slow Replica from Active Ring): Execute an API call to the cluster coordinator to remove the pausing shard replica from the active scatter-gather ring: POST /_cluster/reroute?exclude_node=<ip>.
3. Step 3 (Audit Lucene Segment Count): Check if the node has over 100 small unmerged Lucene segments: GET /<index>/_segments. High segment counts cause Lucene to allocate massive segment searcher thread pools that trigger young-generation GC exhaustion. Execute an off-peak force-merge (_forcemerge?max_num_segments=5).

9. The Five Structural Fault Lines

Every design decision in search and autocomplete architectures represents a fundamental engineering tradeoff:

The 5 Structural Fault Lines

Fault Line	Option A vs Option B	Who Pays?
1. Suggestion Latency vs RAM	Precomputed Top-5 at Node vs DFS Traversal	Precomputed: Memory pays (2.5x). DFS: CPU & Users pay 85ms lag
2. Index Sharding Strategy	Document Partitioning vs Term Partitioning	Doc Shard: Coordinator pays net. Term Shard: Shard pays join tax
3. Near-Real-Time Freshness vs I/O	1.0s Refresh Interval vs 30s Refresh	Fast: High I/O & Segment churn. Slow: Product pays stale search
4. Scatter-Gather Tail Latency	Speculative Hedged Req vs Monolithic Waiting	Hedged: Cluster pays 2% extra. Waiting: Users pay 180ms spikes
5. Autocomplete Mutability	Memory-Mapped FST File vs Dynamic Concurrent	FST: Batch delay on new terms. Dynamic: Lock contention tax

10. Chapter Summary & Staff Decision Matrix

Staff Decision Matrix: Search & Autocomplete

Decision Point	Default Staff Position
Autocomplete Engine	Dedicated in-memory Trie / FST (decoupled from ES)
Suggestion Precomput.	Top-5 completions pre-baked directly at every node
Autocomplete Refresh	30-minute Spark FST batch build + atomic mmap swap
Inverted Index Sharding	Document-Partitioned Sharding (sharded by doc_id)
Relevance Scoring	BM25 with term frequency saturation (k1=1.2, b=0.75)
Tail Latency Defense	Speculative Hedged Requests at p95 shard baseline
Near-Real-Time Indexing	1.0s refresh interval to in-memory Lucene segments
Segment Merge Policy	Tiered merge policy throttled to 20 MB/sec I/O

The Staff Invariant Checklist

Before concluding a search and autocomplete system design interview, verify that you have addressed these four core engineering criteria:

• I have decoupled keystroke autocomplete from document search: Autocomplete is handled by an in-memory Trie/FST cluster with sub-2ms latency, protecting the disk-backed inverted index from keystroke storms.
• I have precomputed Top-K completions at Trie nodes: Lookups are O(L) pointer hops, eliminating dangerous recursive subtree traversals during peak traffic.
• I have defended against scatter-gather tail latency: The query coordinator uses speculative hedged requests to bypass shards suffering JVM GC pauses.
• I have chosen Document Sharding over Term Sharding: Sharding by doc_id allows multi-term boolean intersection to execute locally in CPU cache without inter-node network joins.