Build it

Build a tiny document-sharded search engine in TypeScript, the same search in Postgres, and a hedged-request helper you can use for real reads. All of it was run with Node 22, TypeScript and PostgreSQL 16 or later. You can also try the two core ideas in your browser: the Practice section has an auto-checked inverted index and a hedged-request exercise.

1. One shard: an inverted index with intersection and scoring

   Each shard maps words to posting lists. A search intersects the lists, starting from the shortest, and scores each match so rare words count more.

   TypeScriptCopy

   // shard.ts: one index shard, an inverted index over some of the documents
   export type Hit = { doc: number; score: number };
   type Posting = { doc: number; tf: number };          // tf: times the word appears in doc
   
   export const tokenize = (text: string): string[] =>
     text.toLowerCase().split(/[^a-z0-9]+/).filter(Boolean);
   
   export class Shard {
     private postings = new Map<string, Posting[]>();   // word -> posting list
     private docLen = new Map<number, number>();        // doc -> number of words
   
     add(doc: number, text: string): void {
       const words = tokenize(text);
       this.docLen.set(doc, words.length);
       const counts = new Map<string, number>();
       for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
       for (const [w, tf] of counts) {
         const list = this.postings.get(w) ?? [];
         list.push({ doc, tf });
         this.postings.set(w, list);
       }
     }
   
     // Documents that contain ALL query words, best first
     search(query: string, k: number): Hit[] {
       const lists = [...new Set(tokenize(query))].map((w) => this.postings.get(w) ?? []);
       if (lists.length === 0 || lists.some((l) => l.length === 0)) return [];
       lists.sort((a, b) => a.length - b.length);       // rarest word first: smallest list
       let scores = new Map(lists[0].map((p) => [p.doc, 0]));
       for (const list of lists) {
         const idf = Math.log(1 + this.docLen.size / list.length); // rare words weigh more
         const next = new Map<number, number>();
         for (const p of list) {
           const sofar = scores.get(p.doc);
           if (sofar !== undefined) next.set(p.doc, sofar + (p.tf / this.docLen.get(p.doc)!) * idf);
         }
         scores = next;                                 // keep only docs in every list
       }
       return [...scores].map(([doc, score]) => ({ doc, score }))
         .sort((a, b) => b.score - a.score).slice(0, k);
     }
   }

2. Split documents across shards, fan out, merge

   Documents go to shards by id, split by document like Google's. A query goes to all shards in parallel and each returns only its top k, so the merge is small. Each shard scores with its own document count, a simplification real engines also make.

   TypeScriptCopy

   // search.ts: split documents across shards, fan a query out, merge the answers
   import { Shard, Hit } from './shard';
   
   class MiniSearch {
     private shards: Shard[];
     constructor(n: number) { this.shards = Array.from({ length: n }, () => new Shard()); }
   
     add(doc: number, text: string): void {
       this.shards[doc % this.shards.length].add(doc, text);   // document-partitioned
     }
   
     async search(query: string, k = 3): Promise<Hit[]> {
       // Every shard answers in parallel with its own top k ...
       const parts = await Promise.all(this.shards.map(async (s) => s.search(query, k)));
       // ... and the root keeps the best k of all of them
       return parts.flat().sort((a, b) => b.score - a.score).slice(0, k);
     }
   }
   
   const docs = [
     'Jasmine rice 5 kg bag, best price in town',
     'Soybean oil 5 litre bottle, fortified',
     'Basmati rice 1 kg, aromatic, for biryani',
     'Rice cooker 1.8 litre, non-stick pot',
     'Red lentils 1 kg, split',
     'Brown rice 5 kg, long grain, wholegrain',
   ];
   
   const engine = new MiniSearch(3);
   docs.forEach((text, i) => engine.add(i + 1, text));
   
   (async () => {
     for (const q of ['rice 5 kg', 'litre', 'rice biryani', 'sugar']) {
       const hits = await engine.search(q);
       const shown = hits.map((h) => `doc ${h.doc} (${h.score.toFixed(2)})`).join(', ');
       console.log(q.padEnd(12), shown || 'no match');
     }
   })();

   TerminalCopy

   npm init -y && npm i -D typescript @types/node
   npx tsc --target es2022 --module commonjs --strict --types node --outDir dist shard.ts search.ts
   node dist/search.js

   OutputCopy

   rice 5 kg    doc 6 (0.35), doc 1 (0.32)
   litre        doc 2 (0.18), doc 4 (0.14)
   rice biryani doc 3 (0.26)
   sugar        no match

   Doc 3 (basmati, 1 kg) does not match "rice 5 kg" because every word must be present. Doc 4, the rice cooker, matches "litre" but scores lower than the oil, because "litre" is a smaller share of its words.

3. The same search in Postgres

   A tsvector column is the per-row word list, and a GIN index on it is the inverted index: word to rows. Weight the title above the body. Create the database with UTF-8 encoding if you will store names in other scripts, such as Hindi, Arabic or Bengali.

   SQLCopy

   CREATE TABLE page (
     id     bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
     url    text NOT NULL UNIQUE,
     title  text NOT NULL,
     body   text NOT NULL,
     -- normalised words with positions; a title match counts more than a body match
     doc    tsvector GENERATED ALWAYS AS (
              setweight(to_tsvector('english', title), 'A') ||
              setweight(to_tsvector('english', body),  'B')) STORED
   );
   CREATE INDEX page_doc_gin ON page USING gin (doc);   -- word -> list of rows
   
   INSERT INTO page (url, title, body) VALUES
    ('/rice/jasmine',   'Jasmine rice 5 kg',  'Everyday rice for busy kitchens. 5 kg bag.'),
    ('/rice/basmati',   'Basmati rice 1 kg',  'Long aromatic grains, the classic choice for biryani.'),
    ('/oil/soybean',    'Soybean oil 5 litre','Fortified with vitamin A. Cooking oil for frying.'),
    ('/kitchen/cooker', 'Rice cooker',        'Cooks 1.8 litre of rice. Non-stick pot.'),
    ('/blog/biryani',   'How to cook biryani','Use basmati rice, ghee, and whole spices.');
   
   -- Search: intersect, rank, and cut a snippet around the matching words
   SELECT url,
          round(ts_rank(doc, q)::numeric, 3) AS rank,
          ts_headline('english', title || '. ' || body, q, 'MaxWords=14, MinWords=5') AS snippet
   FROM page, websearch_to_tsquery('english', 'basmati rice biryani') AS q
   WHERE doc @@ q
   ORDER BY rank DESC
   LIMIT 10;

   OutputCopy

          url       | rank  |                          snippet
   -----------------+-------+-----------------------------------------------------------
    /rice/basmati   | 0.995 | <b>Basmati</b> <b>rice</b> 1 kg. Long aromatic grains, the classic choice for <b>biryani</b>
    /blog/biryani   | 0.913 | <b>biryani</b>. Use <b>basmati</b> <b>rice</b>, ghee
   (2 rows)

   websearch_to_tsquery turns the search box text into 'basmati' & 'rice' & 'biryani': an intersection, as in step 1. It also accepts quotes for phrases ("5 kg" rice) and or. Check that the index is used; on a five-row table you must turn off sequential scans to see it, on a real table the planner picks it alone (Query plans).

   SQLCopy

   SET enable_seqscan = off;   -- only for this demo on a tiny table
   EXPLAIN (COSTS OFF)
   SELECT url FROM page WHERE doc @@ websearch_to_tsquery('english', 'rice biryani');

   OutputCopy

    Bitmap Heap Scan on page
      Recheck Cond: (doc @@ '''rice'' & ''biryani'''::tsquery)
      ->  Bitmap Index Scan on page_doc_gin
            Index Cond: (doc @@ '''rice'' & ''biryani'''::tsquery)

4. A hedged-request helper

   This sends the call to the first replica. If it is still running after hedgeAfterMs, or if it fails, it sends one backup to the second replica. The first answer wins and the other call is cancelled through its AbortSignal. Use it only for reads or idempotent calls. The Practice section asks you to write a smaller version of this logic yourself.

   TypeScriptCopy

   // hedge.ts: ask one replica; if it is slow, also ask a second and take the first answer
   export type Call<T> = (replica: string, signal: AbortSignal) => Promise<T>;
   
   export async function hedged<T>(replicas: string[], call: Call<T>, hedgeAfterMs: number): Promise<T> {
     const controllers: AbortController[] = [];
     const send = (replica: string) => {
       const c = new AbortController();
       controllers.push(c);
       return call(replica, c.signal);
     };
     let backup: Promise<T> | undefined;
     const sendBackup = () => (backup ??= send(replicas[1]));   // never more than one backup
   
     let timer: ReturnType<typeof setTimeout> | undefined;
     const first = send(replicas[0]);
     const racers: Promise<T>[] = [first];
     if (replicas.length > 1) {
       racers.push(new Promise<T>((resolve, reject) => {          // slow: hedge after the delay
         timer = setTimeout(() => sendBackup().then(resolve, reject), hedgeAfterMs);
       }));
       racers.push(first.catch(() => sendBackup()));              // failed fast: back up now
     }
     try {
       return await Promise.any(racers);                          // whoever answers first wins
     } catch (e) {
       throw e instanceof AggregateError ? e.errors[0] : e;       // all failed: show the first error
     } finally {
       clearTimeout(timer);
       controllers.forEach((c) => c.abort());                     // cancel the loser
     }
   }

   With a real HTTP read, pass the signal to fetch so the losing request is really cancelled:

   TypeScriptCopy

   import { hedged } from './hedge';
   
   type SearchResult = { hits: { id: number; name: string }[] };
   
   export function searchArticles(q: string): Promise<SearchResult> {
     const replicas = ['http://search-a.internal:4100', 'http://search-b.internal:4100'];
     return hedged(replicas, async (base, signal) => {
       const res = await fetch(`${base}/search?q=${encodeURIComponent(q)}`, { signal });
       if (!res.ok) throw new Error(`${base} answered ${res.status}`);   // 5xx: let the backup win
       return (await res.json()) as SearchResult;
     }, 50);                                         // about your p95 for this call, in ms
   }

5. Prove it with a fan-out simulation

   Each query fans out to 20 shards and waits for all of them. About 1 call in 50 is slow (200 to 300 ms). Run 400 queries plain, then hedged after 20 ms.

   TypeScriptCopy

   // tail.ts: 400 queries, each fanning out to 20 shards. About 1 call in 50 is very slow.
   import { hedged, Call } from './hedge';
   
   let calls = 0;
   const fakeLeaf: Call<string> = (replica, signal) => {
     calls++;
     const slow = Math.random() < 0.02;                       // a GC pause, a busy disk ...
     const ms = slow ? 200 + Math.random() * 100 : 5 + Math.random() * 10;
     return new Promise((resolve, reject) => {
       const t = setTimeout(() => resolve(replica), ms);
       signal.addEventListener('abort', () => { clearTimeout(t); reject(new Error('aborted')); });
     });
   };
   
   async function query(shards: number, hedge: boolean): Promise<number> {
     const start = performance.now();
     await Promise.all(Array.from({ length: shards }, (_, i) => {
       const replicas = [`shard${i}-a`, `shard${i}-b`];
       return hedge ? hedged(replicas, fakeLeaf, 20) : fakeLeaf(replicas[0], new AbortController().signal);
     }));
     return performance.now() - start;                        // a query waits for its slowest shard
   }
   
   const pct = (xs: number[], p: number) => xs.sort((a, b) => a - b)[Math.ceil((p / 100) * xs.length) - 1];
   
   (async () => {
     for (const hedge of [false, true]) {
       calls = 0;
       const times: number[] = [];
       for (let batch = 0; batch < 40; batch++) {             // 40 batches of 10 queries
         times.push(...await Promise.all(Array.from({ length: 10 }, () => query(20, hedge))));
       }
       const extra = ((calls / 8000 - 1) * 100).toFixed(1);   // 400 queries x 20 shards = 8000
       console.log(`${hedge ? 'hedged' : 'plain '}  p50 ${pct(times, 50).toFixed(0)} ms` +
         `  p99 ${pct(times, 99).toFixed(0)} ms  calls ${calls} (+${extra}%)`);
     }
   })();

   TerminalCopy

   npx tsc --target es2022 --module commonjs --strict --types node --outDir dist hedge.ts tail.ts
   node dist/tail.js

   OutputCopy

   plain   p50 14 ms  p99 296 ms  calls 8000 (+0.0%)
   hedged  p50 15 ms  p99 35 ms  calls 8149 (+1.9%)

   Numbers change a little per run; the shape does not. With 20 shards and a 2% slow rate, about one plain query in three hits a slow shard (1 − 0.98²⁰ is about 33%), so the plain p99 is the slow time. Hedging adds about 2% more calls and brings the p99 near the normal time, the same trade Google measured. Running far more queries at once in one Node process makes timers fire late and the numbers noisy; that is a limit of the simulation.