An In-Memory Autocomplete Library for Go

One of the APIs I run has a type-ahead box over a few tens of thousands of titles. People type without diacritics, they often start with the second word instead of the first, and they expect something useful to pop up on every keystroke. Sure, Elasticsearch can do that. But running a whole cluster for a list that fits in a few MiB felt like overkill. Hitting the database on every keystroke wasn’t any better: that’s a round trip per letter, and a LIKE pattern doesn’t care about word order and has no clue that padu should find Pădurea.

What I actually wanted was an index living inside the Go process. It should match word prefixes in any order, ignore case and diacritics, rank the results in a sane way and tell the frontend what to highlight. It turned into a small library, github.com/replsv/autocomplete, and since I kept changing the data structures underneath it, I benchmarked every change along the way.

Tagging a struct

The index is generic over your own type. You tag the fields you want searched, and it stores and hands back your items as they are:

1
2
3
4
5
6
7

type Movie struct {
	ID       string  `searchindex:"id"`
	Title    string  `searchindex:"true,boost=25"`
	AltTitle *string `searchindex:"true"`
	Year     int
	Votes    int
}

searchindex:"true" indexes a field (it has to be a string or a *string). boost=25 adds 25 to the score when that field is the item’s best match, so a hit on the main title beats the same hit on the alternative one. searchindex:"id" marks the id. New reads the tags once, and a malformed tag fails right there instead of somewhere down the line.

Creating, filling and searching the index takes three calls:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

ix, err := autocomplete.New[Movie]()
if err != nil {
	log.Fatal(err)
}
if err := ix.Build(movies); err != nil {
	log.Fatal(err)
}

for _, r := range ix.Search("thrones game") {
	fmt.Println(r.ID, r.Item.Title, r.Tier, r.Score, r.Ranges("AltTitle"))
}
// tt0944947 Urzeala tronurilor 1 -8 [{0 4} {8 15}]

Each Result[T] carries the item, its id, the tier and score of its best field, plus the highlight ranges for every field that matched. r.Ranges("AltTitle") gets you one field by its Go name. The ranges are half-open rune offsets into the original text, so in Game of Thrones, {0 4} is Game and {8 15} is Thrones. The result types come with lowercase JSON tags, which means a handler can just encode them as they are.

Feeding it from the outside

Build swaps out the whole index. Upsert inserts items, or replaces the ones that share an id, and Remove deletes by id and tells you how many it actually found:

1
2
3
4

if err := ix.Upsert(Movie{ID: "tt15239678", Title: "Dune: Partea a doua", Year: 2024, Votes: 600000}); err != nil {
	log.Fatal(err)
}
removed := ix.Remove("tt0133093", "tt-unknown") // 1

A write either goes through completely or not at all. An empty id, or a write that would go past WithMaxItems, returns an error, and the index keeps serving whatever it had before.

Each of these methods has a named func type: BuildFunc[T], UpsertFunc[T] and RemoveFunc. In practice the code that feeds the index lives somewhere else (a ticker reloading from the database, a queue consumer, an admin route) and none of it needs the index itself. Hand it a func and you’re done:

1
2
3
4

go rebuildEvery(ctx, 5*time.Minute, loadMovies, ix.Build)

mux.Handle("PUT /movies", upsertHandler(ix.Upsert))
mux.Handle("DELETE /movies/{id}", removeHandler(ix.Remove))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func rebuildEvery(ctx context.Context, every time.Duration,
	load func(context.Context) ([]Movie, error), build autocomplete.BuildFunc[Movie]) {
	t := time.NewTicker(every)
	defer t.Stop()
	for {
		select {
		case <-ctx.Done():
			return
		case <-t.C:
			movies, err := load(ctx)
			if err == nil {
				err = build(movies)
			}
			if err != nil {
				log.Printf("rebuild: %v", err)
			}
		}
	}
}

func removeHandler(remove autocomplete.RemoveFunc) http.Handler {
	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
		if remove(r.PathValue("id")) == 0 {
			http.NotFound(w, r)
			return
		}
		w.WriteHeader(http.StatusNoContent)
	})
}

If a load fails, the current index stays in place. The full version, with a JSON search endpoint and a graceful shutdown, is under examples/httpapi in the repo.

Popularity and recency

With no score, two equally good matches are sorted by id, which is rarely what you want. I’d rather see popular and recent titles first, so WithScore takes a func of your item type, and it gets called once per item at indexing time:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func popularity(m Movie) float64 {
	votes := 60 * math.Log10(1+float64(max(m.Votes, 0)))
	recent := 4 * float64(min(10, max(0, 10-(time.Now().Year()-m.Year))))
	return votes + recent
}

ix, err := autocomplete.New[Movie](
	autocomplete.WithScore(popularity),
	autocomplete.WithArticles("the", "a", "an", "o", "un"),
	autocomplete.WithLimit(10),
)

The logarithm is there so a title with two million votes doesn’t bury everything else. Recency adds up to 40 points for anything under ten years old. WithArticles lists the leading articles a match is allowed to skip, so matrix counts as an exact match for The Matrix. By default that’s the, a and an; I throw in the Romanian ones as well.

Bounding memory

The index lives in your process, so how big it gets is on you. WithMaxItems rejects writes beyond a given number of items, which helps when a feed suddenly sends ten times more than usual. WithMaxFieldBytes caps each normalized field (255 bytes by default). WithCapacity presizes the id map and the chunk list for Build.

1
2
3
4
5
6

ix, err := autocomplete.New[Movie](
	autocomplete.WithScore(popularity),
	autocomplete.WithCapacity(60_000),
	autocomplete.WithMaxItems(1_000_000),
	autocomplete.WithMaxFieldBytes(200),
)

Keep in mind that a Build keeps the old snapshot around until the new one is ready, so briefly you have two of them. Set GOMEMLIMIT with room for that plus the rest of the process. At roughly 60k items, 150 MiB is more than enough.

What’s inside

Before getting into the details, here’s what an index actually holds. Everything a search reads is immutable and hangs off a single atomic pointer, and almost all of it is flat slices of integers:

Searches load the snapshot pointer and never take a lock. Writes serialize on a mutex, and the word index gets rebuilt by a single background goroutine. In the benchmarks further down, the whole thing adds up to about 270 bytes per item, not counting the items’ own strings.

How matching and ranking work

Queries and fields go through the same normalization: lowercase, diacritics stripped, a handful of letters with no decomposition folded by hand (ß to ss, ł to l), and anything that isn’t a letter or a digit splits words. So Țara Șoimilor turns into tara soimilor. The function is exported as autocomplete.Normalize, in case you need your own keys normalized the same way. Each query word has to be a prefix of some word in the field.

A match lands in one of five tiers, best first. Take the field The Dark Knight:

The tier always wins. Inside a tier, the score is the field boost plus the item score, minus 8 points for each extra word the field has compared to the query, capped at 80. That’s where the -8 in the first example comes from: Game of Thrones has one word more than thrones game. Ties fall back to the item score and then the id, so the order is always the same.

Highlights only get computed for the results that are actually returned. The index stores a normalized copy of each field, not the original text, so it normalizes the field from the item again, keeps track of which rune every byte came from, and maps the matched bytes back to it.

The first version: a scan over packed chunks

My first version didn’t have an inverted index at all. Items sit in chunks of 256 entries. A chunk holds the items by value, their ids and scores, and the normalized fields packed one after another in a single string, with a span per field. On top of that, every field gets a 16-byte bloom-style filter: a 64-bit set of the first letters of its words and a 64-bit set of their first letter pairs. A field can only match if it has every bit the query’s tokens need.

A search was just a linear pass over the filters, which live in a small contiguous slice, and string matching ran only on the fields that got through. Simple, and fast enough for a few thousand items. At 60k items, though, a two-letter prefix took 613 µs, and a query matching nothing still took 105 µs. A scan pays for the whole index no matter what you ask it. With a search on every keystroke, I wanted the cost to depend on the candidates instead.

A word index ordered by score

The current version keeps the chunks and adds a word index next to them. Each distinct normalized word is stored once, sorted, in one string with uint32 offsets, so finding the range of words a query token prefixes is a binary search. Every word gets two posting lists: the entries that contain it, and the entries where it leads a field (first, or right after an article).

The postings store ranks rather than positions. Entries are numbered by descending item score, with a rank-to-position table, so when you walk a posting list you meet the most popular items first. Once the results are full and the next candidate’s score plus the highest boost can’t beat the worst result, the walk stops. For st, which matches about a quarter of the benchmark index, that happens after a few dozen candidates.

The order in which candidates get tried follows the tiers. First come the fields equal to the query, looked up in a sorted table of field hashes. For a multi-word query, next are the entries led by the first token as a whole word, since those are the only ones that can match at the prefix tier. After that, the entries led by the first token as a prefix, which covers the aligned tier. Last, the entries holding the rarest token, for the two lower tiers. A step gets skipped once the only way to beat the current results is a tier that’s already fully covered.

A token like st prefixes a lot of words, so its candidates are the union of many posting lists. The cursor merges them lazily through a small heap of list heads, which means a walk that stops early never pays for the tens of thousands of postings it didn’t read. Past 1024 candidates it switches to a bitset of the union: one bit per posting instead of a heap update per candidate. Every walk is also driven by the smaller of two sets and filtered through a bitset of the other one, so night xq walks the few entries with a word starting with xq and checks each of them for night.

Copy-on-write and a snapshot for readers

All of this lives in an immutable snapshot behind an atomic.Pointer. Search loads the pointer and never locks. Writers serialize on a mutex, build a new snapshot on the side and swap it in, so a search sees the index either before or after a write, never something in between. This part hasn’t changed since the first version.

A snapshot is a list of chunk pointers, and that’s what keeps a small write cheap. A write copies the list (8 bytes per 256 items) plus each chunk it touches, once per call. Everything else is shared with the previous snapshot. A removal moves the last item into the hole, so every chunk except the last one stays full.

Dirty positions and the background rebuild

The word index is the expensive bit, so writes leave it alone. A write marks the positions it changed in a copy-on-write bitset and a list. Searches skip those positions in the word index and scan them through their filters instead, together with any items appended since the index was built. With 500 upserts pending at 60k items, st takes 15.5 µs instead of 7.7 µs, and zzqx 3.5 µs instead of 0.28 µs.

When more than max(1024, n/16) positions are pending, the word index gets rebuilt. Initially, the write that crossed the threshold did the rebuild synchronously, and a benchmark of 5000 single upserts at 60k items made the problem obvious: the median upsert took 35 µs, the slowest one 28 ms. I really didn’t want a queue consumer freezing for 28 ms every few thousand writes.

These days the write that crosses the line kicks off the rebuild in a goroutine and returns right away. The rebuild reads the immutable chunks of that snapshot, builds a new word index, then grabs the writer mutex for a moment to install it into the current snapshot, marking the positions written in the meantime as dirty again. Only one rebuild runs at a time, and if the writes that came in during it already make the result stale, it just starts another one. A Build during a rebuild wins.

The p50 and p99 went up a few percent, since the rebuild now competes with the writes for CPU. The p99.9 difference isn’t statistically significant (p=0.180). The maximum, which is what I cared about, dropped by 93%.

Flat integer slices instead of a trie

The textbook answer for prefix search is a trie: a node per letter, with pointers to its children. I stayed away from it on purpose. The word index is flat slices of uint32 offsets and ranks and uint64 hashes, plus one string with all the words. The garbage collector doesn’t bother scanning memory that has no pointers in it, whereas a trie would be a huge pile of small, long-lived objects for it to walk on every cycle.

A forced runtime.GC() with a 200k item index live took 3.86 ms with the linear version and 3.98 ms with the word index, so roughly 3% apart. The rest of that time goes to the items, whose strings the collector has to scan either way.

Benchmarks

All numbers come from go test -bench . -benchmem -count=6, compared with benchstat, which reports medians. I ran them on my laptop, an AMD Ryzen 7 PRO 7840U, with Go 1.27.3 on linux/amd64, GOMAXPROCS=4, GOMEMLIMIT=1GiB and GOFLAGS=-p=2, inside a 2 GiB systemd-run scope. My desktop session was running alongside, so take small differences with a grain of salt.

The data is synthetic, generated with a seeded math/rand/v2. Titles have one to five words, drawn with a Zipf distribution from 56 real words (with and without diacritics) plus 6000 pseudo-words. A quarter of the titles start with an article, and half have an alternative title. The item score is the votes and recency formula from earlier. st matches about a quarter of the index, which makes it a worst case for a two-letter prefix.

“Before” is the linear scan over the filters, “after” is the word index:

I only added the last three queries together with the word index, then ran them against the old code afterwards with the same settings. At 10k items, st went from 174 µs to 12.8 µs and zzqx from 16.1 µs to 0.29 µs.

The cost doesn’t grow with the index anymore. What it depends on is how many candidates a search has to walk before its results are settled: a few binary searches for a query with no match or a single rare word, a few dozen candidates for a broad prefix.

Writes cost about the same as before. A single upsert at 60k items took 41.1 µs with the linear version and 44.0 µs now; a batch of 100 random ids, 4.07 ms against 4.16 ms, counting the CPU of the background rebuilds they trigger. A word index rebuild on its own takes 21.8 to 23.6 ms at 60k items, depending on the run, and around 85 ms at 200k.

Memory

The Build benchmark also reports the live heap the index keeps per item, on top of the items’ own strings:

With two indexed fields, the word index costs 45 to 53 bytes per item. At 60k items that puts the index at around 15 MiB plus the items.

The number you should size for is the peak, though. A Build allocates about 1.3 times what it retains (20.1 MiB at 60k items) and holds onto the old snapshot until the swap. A background word index rebuild allocates 7.2 MiB at 60k and 22.6 MiB at 200k, and keeps the old index until the new one is in place. A search allocates 0.5 to 10 KiB, mostly the normalized query and the results with their highlight ranges.

Weak spots

Build is 1.8 to 1.9 times slower than the linear version, because it builds the word index too: 57 ms instead of 31 ms at 60k items. For a rebuild every few minutes I don’t mind; for individual changes, use Upsert.

Queries made of several common short prefixes gain a lot less. lo ri ta is only about twice as fast at 60k and 200k items, and night dark star at 10k doesn’t gain anything, since no item has those words first. When the best results are in-order or any-order matches of common prefixes, the search ends up walking every candidate of its rarest token, which isn’t far from a scan.

The highlight offsets are in runes, not UTF-16 code units. JavaScript indexes strings in UTF-16, so for characters outside the Basic Multilingual Plane (emoji, for instance) the frontend has to convert them. For Latin text with diacritics they line up just fine.

Every rebuild, whether it’s a full one or just the word index, holds the old and the new structure at the same time. If your memory limit is too tight, that’s exactly where the GC starts sweating.

Getting it

1

go get github.com/replsv/autocomplete

You’ll need Go 1.27 or later, and the only dependency is golang.org/x/text. The source, the examples and the raw benchmark output are all on GitHub. It does type-ahead over a list that fits in memory and nothing more, and for that job I no longer need a search cluster or a query per keystroke.