Raqueeb

Systems · 2026

ferret

Local full-text search engine in Rust: hand-built inverted index and BM25

Complete · source available

Overview

  • What: a local file search engine that indexes text, code and PDFs and answers ranked queries in well under a millisecond.
  • Hardest problem: merging 21 million postings with bounded memory while staying crash-safe.
  • How it is validated: 58 tests, a PDF extractor checked token-for-token against poppler, and measurements on a 100,300-file corpus.

The inverted index is built from scratch: tokenizer, postings codec, BM25 scoring, LSM-style segment merging and crash recovery. SQLite is used only as a B-tree and page cache; there is no Lucene, Tantivy or FTS5. It ships a CLI, a watch mode and a dependency-free local web UI.

Architecture

 files / PDFs --> tokenizer --> memtable --> flush --> segments (delta + varint postings)
                                                           |
                                    k-way merge (one B-tree walk, no sort buffer)
                                                           |
 query --> BM25 ranking over segments --> ranked results (CLI / web UI)
 durability watermark per flush: re-index anything the catalogue claims but the index lacks
fig. 01 — ferret architecture

Highlights

  • Measured on 100,300 files (456 MB): the index is 168.2 MB (36.9% of the corpus) with positions included, at 6.00 bytes per posting via delta + varint encoding; single-term p50 0.15 ms, phrase p50 0.16 ms.
  • Against grep on the same corpus: 6.3 ms vs 510 ms for a term in 49,708 files; 0.32 ms vs 400 ms for a rare term. ferret also finds text inside compressed PDF streams that grep cannot read.
  • Memory-bounded merge: a (term, seg) clustered WITHOUT ROWID table lets a k-way merge stream through one B-tree walk with no sort buffer, with a 4.8 MB peak working set while merging 21 million postings.
  • From-scratch PDF text extractor (FlateDecode streams, Tj/TJ operators, hex/octal strings, UTF-16BE) validated token-for-token against poppler's pdftotext.
  • Crash recovery born from a real crash: a per-flush durability watermark tombstones and re-indexes documents the catalogue claimed but the index never received.
  • 58 tests; three real bugs documented (inverted ranking, uncompactable tombstones, memtable budget undercounting 3x); dependencies limited to rusqlite, notify, walkdir, flate2.

What I learned

Three real bugs, documented in the repo, taught the most: ranking that came out inverted, tombstones that could not be compacted, and a memtable budget that undercounted by 3x. The crash-recovery watermark exists because a real crash left the catalogue ahead of the index.