Trie-based search engine

The problem

Three public properties needed search: a banking site, a research publication site, and a promotions catalogue behind a paginated JSON API. Each had its own CMS and deploy pipeline, and every page existed in both Georgian and English.

Two facts shaped the design. Georgian is agglutinative, so the word a user types is rarely the exact form on the page. And Georgian speakers often type Georgian words phonetically on a Latin keyboard. Exact token matching returns nothing for most real queries in either case.

The approach

The service crawls each site through its sitemap, extracts the readable text, builds a character trie per {channel, language} pair and answers queries from process memory. Crawling runs on worker threads on a schedule; the HTTP layer only ever reads.

                       ┌─────────── indexing worker ────────────┐
  cron 09:00 ─────────▶│  per channel: sitemap XML → url list   │
  POST /refresh ──────▶│    ┌── chunk worker ─┐                 │
                       │    ├── chunk worker  ├─ HTML → text    │
                       │    └── chunk worker ─┘   (bot UA)      │
                       └───────────────┬────────────────────────┘
                                       │ partial postMessage
                                       │ { entries, cacheDelta }
                                       ▼
                     build a trie per { channel, language }
                                       │
                              merge — never wipe
                                       ▼
  GET /search ────────▶   ┌──────────────────────────────────┐
  x-channel, x-language   │ "CHANNEL-LANG" → search service  │
                          │ read-only · main thread · memory │
                          └──────────────────────────────────┘

The index

A trie in memory, not a search cluster

The corpus is thousands of pages — tens of megabytes of text, comfortably inside a Node heap. A managed search service would add a deployment, a network hop per query and another failure domain. But the language is what settled it. Off-the-shelf analyzers have no useful Georgian stemmer, and a prefix trie is a crude stemmer — the right one for a language that inflects at the end of words. Looking up სესხ reaches სესხი, სესხის and სესხები in one walk, with no linguistic rules to maintain. Lookup is O(query length), independent of corpus size.

How words are stored

Each character is a node. A non-word character ends the current word and resets the cursor to the root, so every word is inserted from the root rather than a whole field becoming one long path. Word-ending nodes hold a Set of document indices, so a term in both title and body costs one entry. Autocomplete suggestions come from collecting the subtree under the query node, using an explicit stack instead of recursion — Georgian compounds make the trie deep.

One index per replica; the rebuild is the sync

Each replica builds its own tries with no coordination, because the index is derived state, not a source of truth. All replicas rebuild from the same sitemaps on the same daily cron and converge without exchanging a message; /refresh re-crawls a single replica on demand. Replicas can differ for a few minutes mid-crawl, which is invisible on marketing search and buys a design with no leader, no quorum and nothing to fail over. If strict freshness ever mattered, the ingestion worker could write to a shared store instead.

The query

Expand the query, not the index

Each query is walked in up to three forms: as typed, transliterated, and with synonyms substituted. Transliteration is a greedy longest-match over a small table — three characters, then two, then one — so the trigraph tch and digraphs win over their prefixes, turning Latin sesxi into სესხი. The direction follows the index's language. Synonyms are stored as prefix pairs (credit ↔ loan, deposit ↔ savings), so one pair survives every case ending the noun can take.

// three walks of the same trie, merged — not three indexes
const searchTerms = [queries];                      // as typed

const translated = this._getTranslation(queries);   // sesxi → სესხი
if (translated) searchTerms.push(translated);

const alt = queries.map(q => this._getSynonym(q) || q);
if (alt.some((term, i) => term !== queries[i])) searchTerms.push(alt);

Expanding at read time keeps a single representation of the corpus: editing synonyms is a config change, not a reindex, and a bad synonym is reverted with a deploy instead of a crawl. The cost is at most three walks per query, each proportional to query length, and queries under three characters don't walk at all.

Ranking narrows the phrase

A multi-word query is matched whole first; if nothing matches, the last term is dropped and the search retried, down to the first term. The score is matchedWords × 1000 + matchCount — lexicographic on purpose, so a longer phrase match always beats a more frequent shorter one. Scoring lives in one class behind a fixed interface, so it can be replaced.

Indexed text and displayed text are kept apart

Matching wants normalized text — no punctuation or tags, collapsed whitespace, folded case — but snippets cut from it read like a ransom note. So each field keeps its raw form alongside the indexed one: match on the normalized text, preview from the raw. Snippet style (character-based, or word-based with sentence punctuation and an ellipsis) is set per channel, because prose and product pages need different previews.

Ingestion

Crawling is a separate program from serving

Crawling is slow and unreliable — timeouts, redirects, internal self-signed certificates, sites that are simply down. Queries have to be fast and always answerable. So the HTTP layer never crawls, never blocks on the network and never writes to the index. Indexing runs at startup, on a daily cron and via /refresh, with a guard that makes a concurrent second run a no-op. /ready returns 503 until at least one index exists, and reports per-channel job status in the same payload.

Worker threads that warm the service incrementally

An indexing worker splits each channel's URLs into chunks for chunk workers that pull from a shared cursor rather than a fixed partition — fetch times vary by orders of magnitude, and a static split leaves most threads idle behind one straggler. Each finished channel posts its entries back as a partial message and its index goes live immediately, so the service warms channel by channel instead of waiting for the slowest crawl. Data crossing the worker boundary is serialized explicitly, with non-cloneable fields stripped rather than failing the whole run.

Merge, never replace

Indexes are keyed CHANNEL-LANGUAGE, and a completed run swaps in only the keys it actually rebuilt:

const merged = Object.keys(next).length
    ? { ...SearchStorage.getAll(), ...next }  // fresh keys win, untouched keys survive
    : SearchStorage.getAll();

if (Object.keys(merged).length > 0) SearchStorage.replaceAll(merged);

Partial success is the normal outcome for a crawler. Swapping the whole map would let one unreachable site empty the search box for all of them; instead, a failing channel keeps serving its previous index.

Crawl as a bot, refetch only what changed

The indexed sites are SPAs whose HTML is empty until scripts run. Rather than put a headless browser in the ingestion path, the crawler sends a bot user-agent and receives the same pre-rendered HTML search engines get, from the prerendering middleware. Ingestion stays a plain HTTP fetch, and a page invisible to search engines is also invisible to site search — the right coupling, not a coincidence.

Parsed pages are cached by URL and reused when the sitemap's lastmod hasn't changed, so a normal daily run refetches only what moved. The cache carries a version number, and bumping it invalidates everything in one line for the day the extraction rules change.

Boilerplate opt-out lives in the markup

Navigation, footers and cookie banners would pollute every result with the same text. Besides a default selector list and per-channel additions, any element can carry a [data-search-ignore] attribute. A central selector list describes components owned by other repos and rots on the first rename; the attribute lets the owning team exclude content at the source.

Built for other people to extend

Adding a channel is a config entry plus a <CHANNEL>Parser method — one line for sitemap-based sites, delegating to the shared parser. Languages, indexed fields, ignored selectors and preview style are all config. The JSON-API channel needed no change to the indexing or search core, which is the real test of whether that boundary was in the right place.

A paginated endpoint dumps exactly what the parser extracted per channel and language. “Why doesn't my page come up in search?” goes from a log-reading exercise for the service owner to a one-minute check for whoever asked — usually the content sits inside a stripped component, or pre-rendering failed for that page.

Impact

• Search for three properties and two languages runs as one container, with no search infrastructure to provision, tune or pay for per query.
• Query cost scales with what the user typed, not with corpus size, and never touches the network.
• Georgian typed in Georgian or phonetically in Latin finds the same pages, as do inflected forms and domain synonyms like credit/loan.
• A channel that fails to crawl keeps serving its previous index; the others are unaffected.
• New channels are added by engineers who never touch the indexing or search core.