Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Typeahead & autocomplete

Suggestions that keep up with typing, about 100 ms per request: a precomputed top-N list per prefix, a client that debounces and cancels, hot prefixes cached at the edge, and lists rebuilt from the query log and swapped in whole.

One request per letter

Type lond into a travel site's destination box, and the box asks the server four questions:

  1. l returns London, Lisbon, Los Angeles, Lyon, Lagos.
  2. lo returns London, Los Angeles, Lombok, Lofoten.
  3. lon returns London, Long Beach, Londonderry, Long Island.
  4. lond returns London, Londonderry, London Gatwick.

Each list should arrive before the next letter does, a goal for the rhythm of typing rather than a promise for every keystroke. A user types five characters in about a second, roughly 200 ms between keys, so a request that spends ~100 ms on the lookup and the network leaves the client time to draw the list before the next key, and autocomplete is a latency budget first and a data structure second. And without a pause on the client, every keystroke from every user is a request, so a popular box takes thousands a second, each returning a handful of strings.

The query that spends the whole budget

The first version asks the table of past searches: SELECT query FROM query_counts WHERE query LIKE 'lon%' ORDER BY hits DESC LIMIT 10. A suitable index on query finds the rows that start with lon, but the sort needs all of them before it can return ten, and for a one-letter prefix that is a large share of the table. A prefix scan and a sort on every keystroke spend the budget before the response leaves the data centre.

But there are few different questions. Everyone who types lon asks the same one, and its answer changes when search habits change, over hours, not between keystrokes.

The answer is stored under the question

Do not search at query time. Precompute the top 5–10 completions for every prefix and store them under the prefix as the key. Two shapes do this: a prefix trie where each node carries its own top-N list (walking "lo" → "lon" reads the list off the node, no subtree scan), or a flat sorted set per prefix in Redis (ZREVRANGE ac:lon 0 9), which is the same idea with the trie flattened into keys. Either way a lookup walks the prefix or reads one key and returns at most ten entries, and the ranking, by query frequency, recency and click-through, happened offline. Each query's count goes to every prefix of it, so London's searches weigh in the lists for l, lo, lon and lond. Keeping only the best ten per prefix out of a stream of counts is a Top-K & leaderboards problem. Store prefixes up to a length, say 8 characters; longer input has no list of its own and goes straight to real search.

Personalisation stays a thin layer: keep the global list generic and cheap, then re-rank its 10 candidates with the user's own history at request time. Never precompute per user per prefix: the key space explodes.

Keystroke → prefix lookup, rebuilt from the query log

The hot path (top) reads precomputed lists; the builder (bottom) writes a new version of the prefix lists on a schedule.

The client's half of the work

A fast server does not stop the box showing the wrong list, because responses can come back out of order:

  1. The box sends lon.
  2. The user types d, and the box sends lond.
  3. The answer for lond arrives, and the box shows it.
  4. The answer for lon, held up on a slow server, arrives and replaces it: the list jumps back to Long Beach.

Debounce briefly (~50–150 ms): wait for a short pause before sending, which collapses fast bursts but adds the pause to the delay the user feels, on top of the request's ~100 ms, so the pause stays short. Cancel superseded requests, and show a response only if it answers the current input: once lond is in flight, the answer for lon is dropped. With the edge cache below, this removes much of the load and every out-of-order flicker. Without them, sending on every keystroke multiplies load during fast typing and lets stale responses overwrite fresh ones.

Most people type the same few letters

Prefix traffic is skewed: a small share of prefixes, mostly short ones, carries most of the requests, and l alone is asked far more often than a typical 6-character prefix. A CDN or edge cache in front of GET /suggest?q=lon serves those without touching the service at all. That only works while the response is the same for everyone, so the personal re-ranking happens on the device or after the shared lookup. Caching layers and CDN & static delivery cover the layers and their staleness.

Rebuilding while people type

A periodic rebuild, hourly or daily, from the query log is simple and good enough for most catalogues; a breaking-news or trending term needs an incremental path where hot new queries are merged into the affected prefixes within minutes.

Rewriting the live keys one by one leaves users reading a half-built set, some prefixes new and some old. Build the new version aside and swap in one step:

  1. The builder aggregates the query log and writes every prefix list under a new version, ac:v43:lon beside the live ac:v42:lon.
  2. The builder checks the new set, then changes the pointer the Suggest API reads, ac:current, from v42 to v43 in one write; v42 is kept until no read can still use it (a fixed grace period works only if it outlasts the longest read), then deleted.

Offensive or expired suggestions are removed at build time; a block-list check on every request adds work to every keystroke, and in this design, behind the edge cache, it never sees the lists the edge answers by itself. One that cannot wait for the next build goes into the persistent block list the builder applies, so later builds leave it out, and is deleted from the lists being served and purged from the edge cache. Making that removal stick against a build or a read already under way takes coordination of its own, which is worth designing before the first urgent request arrives.

Splitting the prefix space

When the lists outgrow one Redis node, split them by a hash of the whole prefix rather than by alphabet ranges, since s, c and p carry many times the traffic of x and z (Sharding & partitioning, Consistent hashing). No split helps the hottest single keys: l is one key on one shard however you divide the space, so the edge cache and read replicas carry the short prefixes.

Where the lists stop

The lists answer exact prefixes of popular queries. A traveller who types rekyjavik finds nothing useful once it passes re, and neither does a rare query longer than the stored prefixes; the first needs matching by edit distance, the second an index over every document rather than only popular queries, and both are Full-text search. A common split is to read the prefix list first and send the request on to a search index only when the list returns too few suggestions, so the expensive path runs on a small share of keystrokes.

Two paths that never meet

Typeahead Autocomplete asks for each suggestion "before the user types the next character". The test of a good Grid is that the two paths never meet: the Suggest API reads one precomputed list per prefix and has no edge to a database sort, while a builder fed by the query log writes the lists, its schedule in its title and the version swap on its edge. For the typo requirement, put a search index beside the API and say in a note when the API falls through to it.

Practice this