Inside Tachyon: the architecture of a search engine that refuses shortcuts

Tachyon is an open source, typo-tolerant full-text search engine I've been building in Rust: BM25 relevance, fuzzy matching, filters, facets, sorting, and autocomplete, all behind a single binary.

docker run -p 8108:8108 adikeshri/tachyon:latest

That's the whole install, and it's not really what this post is about. What I want to walk through is the actual shape of the system underneath it - the crate boundaries, the write path, the part of the query engine that got a 3.4x speedup, and the handful of small, deliberate decisions (an integer type, a hash function, a sort that gets skipped on purpose) that a demo would never surface but a production workload eventually would.

The shape of the system

Tachyon is six Rust crates, and the dependency graph only points one direction. tachyon-core sits at the bottom and touches no I/O and holds no state - it's just types. tachyon-storage builds on it and knows nothing about posting lists. tachyon-query builds on the index layer and never opens a file. Each layer is testable in isolation because it genuinely cannot reach into the layer above it.

The workspace is laid out so that cargo test -p tachyon-index never touches disk and cargo test -p tachyon-query never touches a socket - the crate boundary enforces it, not a convention someone has to remember.

A request enters through tachyon-server, which does auth, rate-relevant analytics, and Prometheus metrics, and then hands off to tachyon-engine, which owns collection lifecycle and the write path. Everything below that is read by tachyon-query through a single trait, which is the detail that makes the rest of this post possible to write.

A write either fully happened or it never did

Every write goes through four steps, in this order, and the order is the entire design:

Validate the document against the schema, outside every lock, because parsing is the expensive part and it needs nothing but the schema.
Append to the write-ahead log and fsync per the sync policy.
Apply to the memtable. This step is infallible by construction - every fallible check already happened in step 1, so a write that reached the log always reaches memory.
Acknowledge.

Batch writes are atomic per document, not per batch: PRD §7.2 requires that one malformed document in a batch of ten thousand doesn't reject its nine thousand nine hundred ninety-nine neighbors. Each document gets its own DocOutcome with a success flag and, on failure, an error code - the batch itself never rolls back.

The part worth actually diagramming is what happens when the process dies mid-write, because a search engine that loses acknowledged writes on a crash is not a database, it's a cache. state.json is the commit point: it records which segments are committed and the WAL sequence number already captured in them, and it's written temp-file-then-rename so a reader only ever sees the whole old file or the whole new one, never a partial write. On restart, every WAL record past that sequence number replays in order, and document ids are handed out sequentially from a counter stored in state.json itself - so replay reconstructs the exact ids the previous process had assigned, which is the only reason a tombstone bitmap still means anything after a crash.

The mid-append case is the interesting one: a crash that leaves a torn frame. Every WAL frame carries a length prefix and a CRC32 -

frame: u32 payload_len u32 crc32(payload) payload

and replay stops at the first frame that's short or fails its checksum, then truncates the file right there. The logic behind that is almost philosophical: a frame that was never fully written was also never acknowledged to any client, so there is nothing to recover. The write just never happened, and the log is allowed to say so cleanly rather than trying to salvage a fragment nobody was told to expect.

One more choice that looks wasteful until you think about what it's actually paying for: the WAL payload is JSON, not a compact binary format. That costs a few bytes per record. But the log is truncated at every flush, so its size is bounded by the memtable threshold regardless of encoding, the fsync it's queued behind dwarfs the serialization cost either way, and a log an operator can read with strings during a 3am incident is worth more than the bytes a binary format would save.

Concurrency, kept deliberately boring

Each collection is one RwLock over its mutable state - the memtable, the WAL handle, the tombstone bitmap. Searches take the read lock and run fully concurrently with each other; a write holds the write lock only for the WAL append and the memtable apply, not for validation. This is not a sophisticated design and it isn't meant to be: it's the obvious thing that's correct by construction, and it's also exactly the place I'd look first if write throughput under concurrent search ever became the bottleneck. The natural next step is an atomically swapped read snapshot so searches never block on a write at all - but that's a real design change with its own failure modes, and adding it before anything has demonstrated it's needed would be optimizing a number nobody has measured yet.

The accumulator is flat, and that ends up being the whole optimization

This is the part of the codebase I'd point at first if someone asked what "designing for the hot path" actually looks like in practice.

A search walks postings for every candidate term, and every matching document needs evidence tracked per field and per query token: a BM25 contribution, an edit distance, a set of token positions. The structure that suggests itself is a HashMap<DocId, MatchState>, where MatchState holds a Vec per field. It reads cleanly. It is also the wrong structure, and the reason is allocation traffic.

A broad query - one that matches a meaningful slice of the corpus - has to score every match. The nested-Vec layout allocates two to four separate heap blocks per matched document, scattered wherever the allocator happens to put them. At a hundred thousand matches, that allocation traffic isn't a cost of the query. It is the query.

So the evidence lives in flat arrays instead, addressed by simple arithmetic:

fn cell(&self, slot: usize, field: usize, token: usize) -> usize { (slot * self.num_fields + field) * self.num_tokens + token }

A newly matched document appends one contiguous block to scores, edits, and (only when it's needed) positions. Nothing else in the query allocates again for that document. Two smaller decisions live in the same place and compound with it: position lists are only collected when something will actually read them - a single-token query never needs proximity, since the proximity of one term to itself is 1.0 by definition, so that entire code path is skipped - and the accumulator's own document-id index doesn't hash with SipHash:

fn write_u64(&mut self, value: u64) { // Fibonacci hashing: multiply by 2^64 / phi and fold the high bits // down to where the map reads them. self.0 = (self.0 ^ value).wrapping_mul(0x9E37_79B9_7F4A_7C15); self.0 ^= self.0 >> 32; }

SipHash is the standard library's default, and it's the right default when a map's keys are attacker-chosen input - a JSON body parsed straight into a HashMap, say. These keys are internal document ids Tachyon assigned itself: sequential, dense, and trusted. Paying SipHash's DoS-resistance tax on your own counter, once per matched posting on a query that might match a hundred thousand of them, is a tax with no corresponding benefit.

Net effect, measured on a million-document corpus with a query matching 6% of it - a synthetic case chosen specifically because it's the expensive one, broader than almost any real query load: p95 search latency went from 229ms to 68ms. Same ranking algorithm, same result set, one data structure changed.

Ranking is five numbers on the same scale

The score itself is a weighted sum, and the weights only mean anything once every signal shares a scale:

score = 0.45 * BM25 + 0.25 * field_boost + 0.15 * proximity + 0.10 * typo_penalty + 0.05 * popularity

BM25 and popularity are naturally unbounded, so both get squashed through x / (x + half) before they're mixed in. That function is monotonic, has no ceiling to clip against, and - unlike the more obvious move of dividing by the best score in the result set - never makes one document's score depend on which other documents happened to match the same query. A single result for a rare query scores exactly like the same document would if it were competing against nine others.

A document is scored on its best field, never the sum across fields. Summing double-counts a phrase that happens to appear in both title and description, and it lets a long, repetitive field quietly outrank a precise title match just by having more surface area. Whichever field wins also supplies the proximity and typo signals for that document, so all five components describe one coherent match instead of an average of unrelated ones.

Proximity itself is a minimum-window problem: given the positions each query token occurs at within the winning field, find the smallest span containing at least one occurrence of every token, then score (n - 1) / span. It's a standard k-way pointer sweep - repeatedly advance whichever list currently holds the smallest position, since that's the only move that can shrink the window - and it naturally returns 1.0 for an exact adjacent phrase and decays smoothly as the terms spread apart.

Getting `i64` versus `f64` wrong is a bug that waits years to surface

Numeric columns back every range filter, and a range filter wants a sorted array so it can binary-search both ends and slice between them. But the memtable takes writes constantly, and re-sorting on every insert is quadratic. The actual structure is a large sorted region plus a small unsorted tail:

Inserts land in the pending tail. Once it reaches 4096 entries, it's sorted once and merged into the sorted region in a single linear pass. A read touches both halves - binary search the sorted region, scan the short tail directly. That's O(log n) lookups with O(1) amortized inserts, and the bound on the tail is what keeps the linear part from ever dominating.

The detail I actually want to highlight is smaller and much easier to miss: integers are stored as i64, never coerced into f64 for convenience. A single numeric representation for the whole column would be simpler to write. It would also silently round any integer past 2^53 - and that is precisely the kind of bug that never shows up in a demo. It shows up two years later, in production, in someone's id column, after everyone who remembers the column was ever internally a float has moved teams. There's a test that pins the boundary down directly:

#[test] fn integers_stay_exact_beyond_float_precision() { let big = 1i64 << 53; let c = column_of(&[(big, 0), (big + 1, 1)]); assert_eq!(ids(&c.range(Some(NumKey::Int(big)), Some(NumKey::Int(big)))), vec![0]); }

And a genuinely counter-intuitive footnote sitting right next to it in the codebase: elsewhere, in the query executor, matched result sets get sorted before being packed into a RoaringBitmap, because that measurably wins for the sparse sets a search result is. Inside the numeric column's own bitmap builder, the opposite call is made on purpose, and there's a comment explaining exactly why:

// Deliberately a plain `insert` per id rather than a sort followed by // `from_sorted_iter`. Sorting first is the obvious optimization and it is // a loss here, measurably: the selections these columns produce are dense // enough that roaring stores them as bitmap containers, where an // out-of-order insert is a single bit-set and the sort buys nothing but // its own n log n. Benchmarked at 200k documents, sorting made a range // filter ~17% slower.

Same library, opposite answer, because the shape of the data flipped the trade. Neither comment is trustworthy on its own - it's the two of them sitting near each other, each with a measured number attached, that makes the codebase legible instead of superstitious.

Typos, correctly, not approximately

Typo tolerance runs on unrestricted Damerau-Levenshtein distance: insertions, deletions, substitutions, and transpositions of characters that don't need to be adjacent in the original string. Most search implementations reach for the cheaper "optimal string alignment" variant instead, which refuses to edit the same region of the string twice. That shortcut is invisible almost all the time - except that it makes cadefghi -> abcdefghi cost 3 edits instead of the true 2, and at the two-edit budget Tachyon's typo table grants for a word that length, that's exactly the gap a real user would fall into and silently get worse search for. So the real algorithm is what's implemented, not the popular approximation of it.

Because matching one query token means running this against many dictionary candidates, FuzzyMatcher keeps its scratch buffers alive across calls instead of reallocating per candidate, and it rejects in cheapest-first order: a length gap bigger than the edit budget is rejected with zero allocation, and anything that survives runs the DP matrix but abandons the moment a row's minimum exceeds the budget. Most dictionary terms never get past the length check.

The detail I like best in this file is quiet and easy to walk past. The transposition rule needs "the last row this character occurred in," which naively means a hash lookup inside the innermost loop, once per matrix cell. Instead, every character is mapped once to a dense array index - query characters when the matcher is constructed, candidate characters once per candidate, never once per cell - and the lookup becomes a plain array read. The hottest loop in a typo-tolerant search engine doesn't hash anything.

The same tokenizer, twice, on purpose

One line in tokenizer.rs matters more than its length suggests: the identical function runs at index time and at query time. That symmetry is the entire reason a query ever matches the document it should - if indexing lowercased and stripped accents but querying didn't, "Cafe" and "café" would live in different universes of the term dictionary and nobody would know why search felt broken. There's a test, query_time_and_index_time_normalization_agree, whose entire job is making sure nobody breaks that symmetry by accident while optimizing one side of it.

And the tokenizer is optimized on one side, carefully: ASCII text - the overwhelming majority of real-world tokens - skips Unicode normalization and combining-mark stripping entirely, because ASCII is already its own normal form and lowercasing it is a one-byte-to-one-byte operation. Non-ASCII text falls through to the full Unicode path. Same output either way; only the road there is different, and a test enforces that the two roads always agree.

What it's honest about not doing yet

I'd rather write this section than let a benchmark table speak for itself.

The structural limitation is that the memtable never flushes to disk. Every write is durable the moment it's acknowledged - it's in the WAL, and it replays on restart - but nothing is ever compacted into an on-disk segment, so memory grows with the corpus (roughly 1.1 KiB per document) and a cold start replays the entire log from the beginning. At 5 million documents that's about 5 GiB resident, past the 2.5 GiB the design actually targets. What's already built, though, is everything around that missing piece: the commit protocol, WAL generations, tombstone bitmaps, and the IndexSource trait the query executor already reads through polymorphically, so a search doesn't know or care whether it's touching the live memtable or a committed segment on disk. The segment writer is next, and it plugs into scaffolding that's already tested end to end.

The other honest limitation: broad queries scale linearly, because every matching document gets scored, with no block-max WAND early termination yet to skip documents that provably can't reach the top-K. At a million documents, a query matching 6% of the corpus costs roughly 68ms at p95 - the number from earlier in this post. Real catalogues are far more selective than that synthetic worst case, and adding a single filter already roughly halves the cost, but the actual fix hasn't been written yet either.

100k docs 1M docs Target Search p95 3.6 ms 67.6 ms < 30 ms Search p99 4.5 ms 68.5 ms < 60 ms Autocomplete p95 0.09 ms 0.1 ms < 5 ms Indexing 210k/sec 161k/sec 10k/sec Memory 104 MiB 1.0 GiB -

Indexing throughput clears its target by more than an order of magnitude at both scales. Search meets its target at 100k documents and misses it at 1M, on a corpus deliberately built to be the worst realistic case. Both of those facts are true at once, and I'd rather publish the miss next to the win than round it off.

Tachyon is Apache 2.0, and the source is at github.com/adikeshri/tachyon. If anything above made you want to argue with a design decision, that's the actual point of writing it down - open an issue.