1Show the Level 1 solution
2**A.**
31. **False.** A B-tree helps prefixes (`'kerala%'`), not a word in the middle.
42. **True.** Otherwise "Database" in the query won't match "database" in the index.
53. **False.** Start from the **shorter** list (the rarer word); fewer checks.
64. **False.** BM25 saturates: extra repeats add less and less.
75. **False.** It's a rebuildable copy without multi-document transactions; orders belong in the database.
8
9**B.**
101. **Synonyms** (DB → database).
112. **CDC** (or an outbox) instead of a nightly batch.
123. **More replicas** (more copies to share the queries).
134. **Field boost** on the title.
145. **Trie or edge n-grams.**
Show the Level 2 solution
1. 2,000,000 × 1 KB = 2 GB; 2 GB ÷ 500 MB/s = **4 seconds** per search, so about **0.25 searches a second** for the whole database. Hopeless.
2. 2,000,000 × 200 = **400 million** postings at most (fewer, since repeated words in one book share a posting).
3. Walk the **"kerala"** list (50 items) and check each against "recipes": **50 checks**, instead of 20,000.
4. 3 × (1 primary + 2 replicas) = **9 shard copies**. Each query needs one copy of each of the 3 shards, so total capacity ≈ 9 × 200 ÷ 3 = **600 queries a second** (assuming even spread and no other bottleneck).
1Show the Level 3 solution
2Tested solution (Python 3), the key parts:
3
4```python
5STOPWORDS = {"a", "an", "the", "of", "and", "or", "to", "in", "for", "on", "with", "is"}
6
7def stem(word): # tiny on purpose; use a real stemmer in production
8 for suffix in ("ing", "s"):
9 if word.endswith(suffix) and len(word) - len(suffix) >= 3:
10 return word[: -len(suffix)]
11 return word
12
13def analyze(text):
14 words = re.findall(r"[a-z0-9]+", text.lower())
15 return [stem(w) for w in words if w not in STOPWORDS]
16
17
18class InvertedIndex:
19 def search_and(self, query):
20 terms = analyze(query)
21 lists = sorted((set(self.postings.get(t, {})) for t in terms), key=len)
22 result = lists[0] # rarest term first
23 for other in lists[1:]:
24 result = result & other
25 return sorted(result)
26
27 def bm25(self, query, k1=1.2, b=0.75):
28 avg = sum(self.doc_len.values()) / len(self.doc_len)
29 scores = Counter()
30 for t in analyze(query):
31 for doc, positions in self.postings.get(t, {}).items():
32 tf = len(positions)
33 norm = tf * (k1 + 1) / (tf + k1 * (1 - b + b * self.doc_len[doc] / avg))
34 scores[doc] += self.idf(t) * norm
35 return scores
36
37 def apply_change(self, event):
38 doc_id, version, text = event
39 if version <= self.version.get(doc_id, 0):
40 return False # stale or duplicate: ignore
41 self.version[doc_id] = version
42 if text is None:
43 self.remove(doc_id)
44 else:
45 self.add(doc_id, text)
46 return True
47```
48
49All checks pass: "database" finds books 2 and 6; the phrase "system design" finds only book 5; TF-IDF scores the triple "databases" title **3×**, BM25 about **1.9×**; "dat" completes to data, database, date; a late version-2 event is ignored after version 3; and the sharded search returns the same top results. The full file, including the trie and phrase search, is in `code/ch19_search.py`.
1Show the Level 4 solution
2**The bug:** books go through `analyze()` when indexed ("Database" becomes "database"), but the **query doesn't**. The lookup is for the raw string "Database", with a capital D, and no such term exists in the index. Multi-word queries fail too: "database internals" is looked up as one term.
3
4**The fix:** run the **same analyzer** on the query, then intersect the posting lists:
5
6```python
7def search(self, query):
8 terms = analyze(query) # same analyzer as indexing
9 if not terms:
10 return []
11 return sorted(set.intersection(*(self.postings.get(t, set()) for t in terms)))
12```
13
14In the tested demo, "Database" now returns books 2 and 6.
1Show the Level 5 (sketch) solution
21. **Sync:** the books table is the truth. Changes go through an **outbox** (or CDC) into a queue; an indexer applies them with **version checks** and handles deletes. A nightly or weekly reindex into a fresh index, switched by alias, repairs drift. Price and stock changes flow the same way, typically visible within a few seconds.
32. **Analyzer and ranking:** English analyzer (lowercase, stop words, stemming) plus synonyms ("DB" → database); author names with a lighter analyzer; ISBN as an exact keyword. BM25 with **title boosted** over description, plus popularity and in-stock as score factors. Filters for price and category don't affect score.
43. **Autocomplete:** edge n-grams on titles and authors, or a trie built hourly from popular searches and titles, with the top 5 stored per prefix; cached at the edge for one- and two-letter prefixes; client debounces keystrokes.
54. **Sharding:** 2 million books is small for a search engine: a single primary shard may be enough; choose, say, **2 to 3 primaries** for growth and **2 replicas** each for throughput and failover. Measure before adding more.
65. **Cluster down:** the rest of the site keeps working. Search falls back to cached results for top queries and a strict-timeout title-prefix query on a database read replica, behind a rate limit, with a "search is limited right now" message.