Search Suggestion

In the previous case, the response could be prepared at write time, because for whom it would be prepared was known the moment it was written. Here that property is gone: a user requests a search suggestion on every keystroke, and what they will type is not known in advance. If the response cannot be prepared at write time, it has to be prepared at read time, and this time the read threshold is small enough to fit between keystrokes. This lesson measures which structure can hold that threshold, and what update lag does to the results.

Constraints

Functional requirements. F1: at most 10 suggestions are returned for a given prefix. F2: suggestions are ordered by query frequency. F3: new queries enter the suggestion pool. F4: a blocked query is never suggested.

Scope reduction. Spelling correction, personalization, semantic matching, and multilingual support are outside this design. A suggestion is given only for a prefix up to 10 characters long; beyond that, the client filters the list it already has. This reduction pays off in the design’s most expensive line item.

Code	Threshold	Threshold’s source
G1	the median suggestion response does not exceed 20 ms	the gap between two keystrokes
G2	the suggestion structure does not exceed 8 GB	for the structure to stay in a single node’s memory without splitting
G3	a new query’s lag before entering the suggestion list does not exceed 600 seconds	for a rising query to be caught the same day

Assumptions

Code	Assumption	Value	Rationale
VA1	daily searches	20,000,000	number of completed searches
VA2	suggestion requests per search	12	every typed character produces one request
VA3	peak factor	3	the ratio of the peak-hour rate to the daily average
VA4	distinct query count	30,000,000	long tail, most queries are asked only a few times
VA5	new queries added per day	300,000	one percent of the pool renews every day
VA6	query frequency distribution	Zipf, exponent 1	rank-r query’s frequency is proportional to 1/r
VA7	suggestion list length	10	F1’s list

Back-of-the-Envelope Estimate

// suggestion/estimate.mjs — the back-of-the-envelope estimate from VA1-VA7 and turning the
// thresholds into numbers
const VA = { dailySearches: 20e6, suggestionsPerSearch: 12, peakFactor: 3, distinctQueries: 30e6, dailyNewQueries: 300_000, listLength: 10 };
const DAY = 86_400, MEMORY = 8e9, WINDOW = 600;      // MEMORY: G2 threshold, WINDOW: G3 threshold
const b = (x, n = 2) => x.toFixed(n);

const suggestionPeak = (VA.dailySearches * VA.suggestionsPerSearch / DAY) * VA.peakFactor;
const searchPeak = (VA.dailySearches / DAY) * VA.peakFactor;
console.log(`peak suggestion requests/s = ${b(suggestionPeak)}   peak searches/s = ${b(searchPeak)}   ratio = ${b(suggestionPeak / searchPeak)}`);
console.log(`G2's byte budget per query = ${b(MEMORY / VA.distinctQueries)} bytes (${MEMORY / 1e9} GB / ${(VA.distinctQueries / 1e6)} million queries)`);
console.log(`new queries accumulated in the G3 window = ${b(VA.dailyNewQueries / DAY * WINDOW)} (${VA.dailyNewQueries.toLocaleString("en-US")} per day)`);
console.log(`the rebuild job runs ${b(DAY / WINDOW)} times a day; each run scans ${(VA.distinctQueries / 1e6)} million queries`);

const doubled = (VA.dailySearches * VA.suggestionsPerSearch * 2 / DAY) * VA.peakFactor;
console.log(`VA2 sensitivity: suggestion requests per search 12 -> 24 makes peak ${b(doubled)} requests/s; the memory budget does not change, because the structure does not depend on request count`);

peak suggestion requests/s = 8333.33   peak searches/s = 694.44   ratio = 12.00
G2's byte budget per query = 266.67 bytes (8 GB / 30 million queries)
new queries accumulated in the G3 window = 2083.33 (300,000 per day)
the rebuild job runs 144.00 times a day; each run scans 30 million queries
VA2 sensitivity: suggestion requests per search 12 -> 24 makes peak 16666.67 requests/s; the memory budget does not change, because the structure does not depend on request count

Three numbers determine the design. Peak suggestion requests run at 8333.33 per second — twelve times search, because every character produces a request. G2’s 8 GB threshold turns into a budget of 266.67 bytes per query, and this turns the data structure choice into a budget question. G3’s window ties the rebuild job to 144 runs a day, with 2083.33 new queries accumulating on each run.

Measuring the Structures

The prefix tree (trie) is the structure established in the Data Structures course’s Tries lesson. Its mechanics are not re-explained here; what this case measures are its two parameters — depth and the ready list kept per node.

// suggestion/structures.mjs — the memory and search cost of a prefix tree versus a flat list,
// and update lag's effect on the freshness of results. The query set is generated with a
// hand-written generator. IT IS A MODEL.
const SEED = 20260730, QUERIES = 50_000, WORDS = 4000, SAMPLE = 2000, K = 10, VA4 = 30e6;
const NODE_BYTES = 48, RECORD_OVERHEAD = 8;                 // accounting: node 48 bytes, 8 bytes overhead per record
let s = SEED % 2147483647;
const rand = () => (s = (s * 48271) % 2147483647) / 2147483647;
const pick = (a) => a[Math.floor(rand() * a.length)];

const SYLLABLES = ["ka", "le", "mi", "tu", "ro", "sa", "ne", "bi", "dol", "gar", "ver", "tan", "yi", "us", "ce"];
const vocabulary = [];
for (let i = 0; i < WORDS; i += 1) {
  let k = "";
  for (let h = 0, n = 2 + Math.floor(rand() * 2); h < n; h += 1) k += pick(SYLLABLES);
  vocabulary.push(k);
}
const queries = [], seen = new Set();
while (queries.length < QUERIES) {
  const n = 1 + Math.floor(rand() * 3);
  let q = pick(vocabulary);
  for (let i = 1; i < n; i += 1) q += " " + pick(vocabulary);
  if (seen.has(q) === false) { seen.add(q); queries.push(q); }
}
const frequency = new Float64Array(QUERIES);              // Zipf: rank r -> 1e6/r
for (let i = 0; i < QUERIES; i += 1) frequency[i] = 1e6 / (i + 1);

const root = new Map(), atDepth = new Int32Array(64);
for (const q of queries) {                          // prefix tree: each node is a Map
  let d = root, k = 0;
  for (const c of q) {
    k += 1;
    let child = d.get(c);
    if (child === undefined) { child = new Map(); d.set(c, child); atDepth[Math.min(k, 63)] += 1; }
    d = child;
  }
}
const b = (x, n = 2) => x.toFixed(n);
const characters = queries.reduce((a, q) => a + q.length, 0);
console.log(`model: ${QUERIES.toLocaleString("en-US")} distinct queries, average length ${b(characters / QUERIES)} characters`);
console.log(`\n${"structure".padEnd(30)}${"nodes".padStart(11)}${"bytes per query".padStart(19)}${"GB at VA4 queries".padStart(20)}`);
console.log(`${"flat list".padEnd(30)}${"-".padStart(11)}${b((characters + QUERIES * RECORD_OVERHEAD) / QUERIES).padStart(19)}` +
  `${b((characters + QUERIES * RECORD_OVERHEAD) / QUERIES * VA4 / 1e9).padStart(20)}`);
let accumulated = 1;
for (let d = 1; d <= 63; d += 1) {
  accumulated += atDepth[d];
  if ([6, 8, 10].includes(d) === false && d !== 63) continue;
  const bytes = accumulated * (NODE_BYTES + K * 4);       // node + the node's ready list
  console.log(`${`prefix tree, depth ${d === 63 ? "full" : d}`.padEnd(30)}${accumulated.toLocaleString("en-US").padStart(11)}` +
    `${b(bytes / QUERIES).padStart(19)}${b(bytes / QUERIES * VA4 / 1e9).padStart(20)}`);
}

// Request frequency is Zipf-weighted: since frequency is 1/r, rank is drawn from a QUERIES^u distribution.
const weightedPick = () => Math.min(QUERIES - 1, Math.floor(Math.pow(QUERIES, rand())) - 1);
const sorted = queries.map((q, i) => [q, i]).sort((a, c) => (a[0] < c[0] ? -1 : a[0] > c[0] ? 1 : 0));
const binaryLog = Math.ceil(Math.log2(QUERIES));
const treeUnits = [], listUnits = [], range = [];
for (let i = 0; i < SAMPLE; i += 1) {
  const q = queries[weightedPick()], prefix = q.slice(0, 1 + Math.floor(rand() * Math.min(10, q.length)));
  let lo = 0, hi = sorted.length;                   // binary search for the start of the range
  while (lo < hi) { const o = (lo + hi) >> 1; if (sorted[o][0] < prefix) lo = o + 1; else hi = o; }
  let n = 0;
  while (lo + n < sorted.length && sorted[lo + n][0].startsWith(prefix)) n += 1;
  treeUnits.push(prefix.length + 1);                        // descent + reading the node's ready list
  listUnits.push(binaryLog + n);
  range.push([lo, n]);
}
const percentile = (a, p) => [...a].sort((x, y) => x - y)[Math.floor(p * a.length)];
const mean = (a) => a.reduce((x, y) => x + y, 0) / a.length;
console.log(`\n${"search".padEnd(32)}${"average units".padStart(16)}${"p99".padStart(8)}`);
for (const [name, a] of [["prefix tree (ready list is read)", treeUnits], ["flat sorted list (binary + scan)", listUnits]])
  console.log(`${name.padEnd(32)}${b(mean(a)).padStart(16)}${String(percentile(a, 0.99)).padStart(8)}`);

// Update lag: a share of queries rises over time; the suggestion list built from an old
// snapshot is compared against the correct list at that moment.
const RISING = 0.02, HALF_LIFE = 3600;
const rising = new Uint8Array(QUERIES);
for (let i = 0; i < QUERIES; i += 1) rising[i] = rand() < RISING ? 1 : 0;
const topK = (lo, n, f) => {
  const p = [];
  for (let i = 0; i < n; i += 1) { const j = sorted[lo + i][1]; p.push([f(j), j]); }
  p.sort((x, y) => y[0] - x[0]);
  return p.slice(0, K).map((x) => x[1]);
};
console.log(`\n${"lag".padStart(9)}${"rise factor".padStart(15)}${"overlap in top 10".padStart(19)}${"prefixes with a changed top".padStart(30)}`);
for (const lag of [600, 3600, 21_600, 86_400]) {
  const factor = 1 + lag / HALF_LIFE;
  let overlap = 0, topChanged = 0;
  for (const [lo, n] of range) {
    const old = topK(lo, n, (j) => frequency[j]);
    const fresh = topK(lo, n, (j) => frequency[j] * (rising[j] ? factor : 1));
    const set = new Set(fresh);
    overlap += old.filter((x) => set.has(x)).length / Math.max(1, Math.min(K, n));
    if (old[0] !== fresh[0]) topChanged += 1;
  }
  console.log(`${`${lag} s`.padStart(9)}${b(factor).padStart(15)}${b(overlap / range.length, 4).padStart(19)}` +
    `${b(topChanged / range.length, 4).padStart(30)}`);
}

const PEAK = 8333.33;                                 // from the estimate block: peak suggestion requests/s
console.log(`\nunits/s at peak: prefix tree ${b(mean(treeUnits) * PEAK)}, flat sorted list ${b(mean(listUnits) * PEAK)} ` +
  `(ratio ${b(mean(listUnits) / mean(treeUnits))})`);

model: 50,000 distinct queries, average length 15.42 characters

structure                           nodes    bytes per query   GB at VA4 queries
flat list                               -              23.42                0.70
prefix tree, depth 6                4,588               8.07                0.24
prefix tree, depth 8               24,762              43.58                1.31
prefix tree, depth 10              86,967             153.06                4.59
prefix tree, depth full           357,080             628.46               18.85

search                             average units     p99
prefix tree (ready list is read)            6.10      11
flat sorted list (binary + scan)         1047.32    6593

      lag    rise factor  overlap in top 10   prefixes with a changed top
    600 s           1.17             0.9979                        0.0000
   3600 s           2.00             0.9898                        0.0015
  21600 s           7.00             0.9546                        0.0795
  86400 s          25.00             0.8382                        0.1640

units/s at peak: prefix tree 50833.31, flat sorted list 8727688.18 (ratio 171.69)

The first table turns depth into a budget decision. At full depth, the prefix tree wants 628.46 bytes per query, 18.85 GB at VA4 scale — more than double G2’s 8 GB threshold. Cut to a depth of 10, it drops to 153.06 bytes per query, 4.59 GB, and falls under the threshold. This is where the scope reduction pays off: not suggesting for a prefix longer than ten characters is not a convenience, it is the constraint that lets the tree fit the budget. Cost does not grow linearly with depth — the move from 6 to 8 multiplies bytes fivefold, from 8 to 10 three and a half fold.

The second table gives the search cost. The unit is a visited node or a compared record, not a duration. The prefix tree spends an average of 6.10 units and 11 units at p99: cost depends on prefix length, not query count, so the worst case is bounded too. In the flat sorted list, binary search finds the start of the range, but every matching record still has to be scanned: 1047.32 units on average, 6593 at p99. At peak load the difference is 50,833.31 against 8,727,688.18 units/s, that is 171.69-fold.

The third table gives the price of update lag. Within G3’s 600-second window, the top ten suggestions’ overlap is 0.9979, and no prefix’s top suggestion changes. When the window grows to an hour, overlap is 0.9898; at six hours, 0.9546, and the top changes for 0.0795 of prefixes; for a structure rebuilt once a day, overlap drops to 0.8382 and the top suggestion is wrong for 0.1640 of prefixes. Freshness does not decay linearly: the first ten minutes are nearly free, the first day is expensive.

Design

• Prefix tree, depth 10 (Data Structures, Tries). The parameter is depth; it stays under G2 at 4.59 GB.
• Materialized view (Scaling the Data Layer, Materialized Views). Each node holds that prefix’s first 10 suggestions ready; the parameter is 10 records × 4 bytes per node, and this is what brings the search cost down from a subtree walk to 6.10 units.
• Replication (Data Distribution, Replication). Every suggestion node holds a full copy of the structure in memory; the parameter is 4.59 GB per copy.
• Push-based distribution (Traffic Layer, Push and Pull Based Distribution). The structure is built in bulk and pushed to the nodes; the parameter is the 600-second period, that is, 144 runs a day.
• Task queue and background job (Application Layer, Task Queues and Background Jobs). The parameter is the 30 million queries scanned per rebuild run.
• Edge caching (Traffic Layer, Content Delivery Networks). Since the suggestion response is not personal, it can be cached at the edge; the parameter is that its lifetime is 600 seconds, the same as G3. In the previous case, this exact reason kept this pattern from being usable.

Two deliberately unused patterns. Sharding (Data Distribution, Sharding) is not used: since the structure fits a single node at 4.59 GB, sharding would turn every request into scatter–gather and break p99. Cache-aside (Scaling the Data Layer, Cache-Aside) is not used: the whole structure is already in memory, there is no store behind it to warm up.

Eliminated Alternative: A Flat Sorted List

The alternative design does not build a tree; it keeps queries in a sorted array, finds the prefix by binary search, and scans the matching range. What it wins was measured, and it is large: 23.42 bytes per query, 0.70 GB at VA4 scale, less than a sixth of what the prefix tree uses; and since no depth limit is needed, long prefixes are served too.

The number that eliminates it is in search cost: an average of 1047.32 units against 6.10, and 8,727,688.18 against 50,833.31 units/s at peak load. The real problem is not the average but the tail — 6593 units at p99, because short prefixes match thousands of records, all of which must be sorted by frequency. G1 is the threshold for fitting between keystrokes, and a structure that breaks p99 cannot carry that threshold. The alternative wins if a different constraint changes: had suggestions been given only for long prefixes, the matching range would shrink and the two structures would converge; what decides it is how many records the shortest prefix matches.

Failure Behavior and What Is Given Up

If the rebuild job stops, the structure freezes and requests keep being answered — the symptom of this failure is not an error but a shift in freshness. The third table counts this shift: if the job stops for an hour, the top ten’s overlap is 0.9898; for six hours, 0.9546, and the top suggestion is wrong for 0.0795 of prefixes; for a day, 0.8382 and 0.1640. Graceful degradation (Resilience and Reliability, Graceful Degradation) arrives on its own here, because the read path does not depend on the build path.

If a suggestion node drops, no request is lost: because every node keeps a full copy, the load spreads to the others, and only the capacity share shrinks. This is the second payoff of preferring replication over sharding.

What is given up is depth and freshness. A prefix longer than ten characters finds no ready list and is left to the client’s filtering; a new query is not suggested for up to 600 seconds. Both were bought deliberately: in exchange, the structure fit a single node’s memory, and search cost dropped to prefix length.

Summary

• Peak suggestion requests reach 8333.33/s, twelve times search; G2’s 8 GB threshold turns into a budget of 266.67 bytes per query.
• At full depth, the prefix tree wants 628.46 bytes per query and 18.85 GB — outside the budget. Cut to depth 10, it becomes 153.06 bytes and 4.59 GB; this is where the scope reduction pays off.
• Keeping the first 10 suggestions ready per node brings search down to an average of 6.10 units and 11 units at p99.
• A flat sorted list uses less than a sixth of the memory (0.70 GB) but spends 1047.32 units on average, 6593 at p99; the difference at peak load is 171.69-fold, and the elimination comes from the tail.
• Update lag does not decay linearly: at 600 seconds, overlap is 0.9979 and the top change rate is 0.0000; at a day, overlap is 0.8382 and the top suggestion is wrong for 0.1640 of prefixes.
• What is given up is the ready list for a prefix longer than ten characters and a 600-second freshness window.

Next Step

In all three cases, the response was a record: a target link, a list of posts, a list of suggestions. The bytes carried were small, and the expensive line item was compute or memory; the network was never a constraint. In the next case this changes: the same system carries both personal responses of a few hundred bytes and large, unchanging files resent on every request. When the two travel the same path, one breaks the other’s queue. The question is where the two kinds of traffic get split, and what the split does to the request count and the bytes that reach the origin.