A search engine written in Rust
SeaLion is a search engine. It indexes a set of documents, ranks the matches, and answers from the command line or from a page in the browser. It is written in Rust. It can run as one process, or split the index across machines.

Quick start
Install Rust and Cargo, clone the repository, and run these commands from its root directory.
cargo build --workspace
./target/debug/sealion index ./evaluation/corpus --data-dir ./sealion-data
./target/debug/sealion search "distributed systems" --data-dir ./sealion-data
./target/debug/sealion serve --bind 127.0.0.1:8080 --data-dir ./sealion-data
Open localhost:8080 to use the search interface. See Interfaces for command options and configuration.
Contents
| Chapter | Coverage |
|---|---|
Scope, conventions, and reading order. |
|
Components, indexing and search paths, and crate responsibilities. |
|
Documents, analysis, inverted indexes, and segment generations. |
|
Commands, data directory structure, and configuration. |
|
Query syntax, normalization, and explain output. |
|
Reference oracle, correctness properties, and test commands. |
|
Segment layout, publication protocol, and integrity checks. |
|
Ranking formulas, compression, and benchmarks. |
|
Implemented behavior and current boundaries. |
Conventions
-
monospaceidentifies commands, paths, and code identifiers. -
Paths are relative to the repository root unless stated otherwise.
-
Unmeasured results are marked
TBD (unmeasured). -
The normative storage specification and design decisions are maintained in
docs/index-format.mdanddocs/adr/.
The repository contains the source and supporting documents. Use the chapter sidebar to navigate this manual, or press Ctrl+K / ⌘+K to search.
1. Introduction
This chapter defines what the system is, what this manual covers, and how to navigate the rest of the document.
1.1. Purpose
SeaLion is a distributed full-text search engine built from first principles in Rust. Its analysis, inverted index, segments, compression, and ranking are implemented directly — not delegated to an existing engine.
This manual is the engineering reference for that system. It records design intent, interfaces, verification strategy, on-disk detail, and measured behaviour in one numbered document.
Start with the Quick start to build the project and run a local search.
1.2. Scope
The manual covers:
-
system architecture and build order (see Architecture)
-
core data structures and text analysis (see Design)
-
command-line and file interfaces (see Interfaces)
-
the query model (see Programming Model)
-
correctness strategy (see Verification)
-
persistent layout and integrity (see Implementation)
-
measured performance (see Performance)
-
honest limits (see Known Limitations)
It does not replace:
-
README.md— quick start and repository map -
docs/adr/— architecture decision records behind individual choices -
crate-level rustdoc — API detail for a single module
1.3. How to read this manual
Read chapters in order the first time. Chapters 1–2 give context; chapters 3–5 give the working model; chapters 6–8 give the evidence that the system behaves as claimed.
Each chapter is self-contained enough to be entered directly from the sidebar once the overview in Architecture is familiar.
1.4. Conventions
-
Internal references look like this: Verification.
-
External links look like this: Rust documentation.
-
Inline code uses monospace, e.g.
sealion index,manifest.json,DocId. -
File paths are repository-relative, e.g.
crates/sealion-index/src/merge.rs.
-
Unordered lists state properties or inventories.
-
Ordered lists state procedures where sequence matters:
-
Build the workspace.
-
Index a corpus.
-
Run a query and inspect the explanation.
-
|
Note
|
Honest status is a project rule.
Roadmap items stay labelled roadmap; unverified claims stay out of
this manual. Where a number has not been measured it is written
TBD (unmeasured).
|
|
Tip
|
Select a chapter in the left sidebar, then use “On this page” to jump to a subsection on wide screens. On smaller screens, open the menu to switch chapters. Press / or Ctrl+K / ⌘+K to search the manual. |
2. Architecture
System overview: what the pieces are, how documents flow in, how queries flow through, and where each piece lives in the tree.
2.1. System overview
All boxes run — indexing, storage, search, crawl, distribution, product.
The two paths are deliberately asymmetric: indexing is batch-oriented and crash-safe; search is latency-sensitive and verified against a reference engine (see Verification).
2.2. Indexing path
Key properties:
-
Segments are immutable once published.
-
There is exactly one mutable file:
<data-dir>/manifest.json. -
Publication is atomic: temp file, fsync, verify, rename.
-
A crash before the manifest rename leaves the old generation untouched.
2.3. Search path
Ranking is exhaustive field-weighted BM25 over the live set (see Performance). Future skipping optimizers must reproduce this ordering exactly unless documented as approximate.
2.4. Crate map
| Crate | Owns | Stage |
|---|---|---|
|
document model, field taxonomy, config, errors |
foundation |
|
analysis, mem-index, segments, codec, merge, views |
indexing |
|
parser, Boolean execution, reference oracle, ranking, snippets |
retrieval |
|
frontier, fetch, politeness, robots, dedup, HTML extraction |
ingestion |
|
judgments, nDCG/MRR/MAP, regression comparison |
evaluation |
|
hash sharding, coordinator, replicas, routing, rebalancing |
scale-out |
|
HTTP search/complete/admin API + static search page |
product |
|
query/index benchmark harnesses |
measurement |
|
|
interface |
|
Note
|
Every crate named above runs in this tree and is covered by the verification gates in Verification — see Known Limitations for honest boundaries. |
2.5. Further reading
-
docs/architecture.md— system design and build order -
docs/adr/— records 001–017 behind the choices above -
Design — data structures behind each box in the figure
3. Design
Core data structures and transformations. This is the conceptual companion to the byte-level detail in Implementation.
3.1. Document model
Each document carries at least an identity, source location, fielded text, and metadata. Document IDs are stable content-derived values, so re-indexing the same path yields the same ID.
pub struct Document {
pub id: DocId, // stable: fnv1a64(path)
pub url: String, // source path or URL
pub title: String,
pub headings: Vec<String>,
pub body: String,
pub anchor_text: Vec<String>,
}
Fields are first-class: title, heading, body, and anchor
are indexed and weighted separately.
3.2. Text analysis
Stop words leave gaps rather than collapsing positions, so the phrase
"distributed systems" never falsely matches across a removed word.
Stemming is configurable per field through validated TOML configuration.
|
Warning
|
Query text must pass through the same analysis as indexed text. Skipping normalization on either side silently breaks term agreement and phrase checks. The parser in Programming Model applies the index pipeline to every query term. |
3.3. Inverted index
The primary structure maps each fielded term to a posting list of
(docID, frequency, positions) entries:
("body", "compiler")
doc 17: freq 2, positions [41, 98]
doc 93: freq 1, positions [7]
Properties:
-
postings are sorted by document ID
-
positions are gapped per document and stored in order
-
the in-memory index (
MemIndex) and the on-disk segments expose the sameIndexViewtrait, so search logic is storage-agnostic
3.4. Term dictionary
The vocabulary is a sorted, field-scoped dictionary — ordered by
(field, term) — supporting exact lookup, prefix enumeration,
and fuzzy candidate generation.
| Candidate | Why it fits here |
|---|---|
sorted dictionary |
simple, cache-friendly, sufficient at current scale |
trie / FST-like structure |
future option for prefix and fuzzy traversal at larger scale |
The choice is justified by lookup speed, prefix enumeration cost, memory, and build complexity — not by fashion. Any future change requires a benchmark comparison (see Performance).
3.5. Generations and merging
Segments accumulate in generations ordered by manifest.json.
Merging rebuilds the live document set into fewer segments:
-
newest version of an updated document wins (shadowing)
-
deleted documents are recorded as tombstones, invisible to search
-
merge == clean rebuildis a tested invariant -
obsolete versions and tombstones are dropped by the merge
|
Tip
|
Think of the mem-index as the write buffer, segments as immutable runs, and the manifest as the commit point. Readers only ever observe committed generations. |
4. Interfaces
How operators and programs touch the system: the CLI, the data directory, and the configuration file.
4.1. Command-line interface
# Index a local corpus (.txt/.md; others are counted and skipped)
sealion index ./evaluation/corpus --data-dir ./sealion-data
# Search: BM25-ranked hits with snippets
sealion search "distributed systems" --data-dir ./sealion-data
# Phrase + per-term BM25 explanation
sealion search '"distributed systems"' --explain --data-dir ./sealion-data
# Introspect the index
sealion index stats --data-dir ./sealion-data
sealion index verify --data-dir ./sealion-data
# Incremental updates without a rebuild
sealion index delete 12345 --data-dir ./sealion-data
sealion index merge --data-dir ./sealion-data
| Command | Effect |
|---|---|
|
build segments from local files and publish a new generation |
|
parse, execute, rank, and render hits with snippets |
|
additionally print parsed query, normalized terms, and BM25 components |
|
report segment, document, and term counts for the data directory |
|
re-verify checksums and publication invariants, reporting corruption as errors |
|
record a tombstone; the document becomes invisible immediately |
|
consolidate live documents, dropping tombstones and shadowed versions |
The rest of the working surface:
# Typo tolerance + autocomplete
sealion search "distribted databse" --data-dir ./sealion-data
sealion complete comp --data-dir ./sealion-data
# Crawl the web (robots, delays, dedup) straight into the index
sealion crawl https://example.org --depth 2 --pages 100 --data-dir ./sealion-data
# Cluster, relevance gate, benchmarks, serve
sealion cluster init --shards 4 --replicas 2 --data-dir ./cluster-data
sealion eval relevance --save new.json --baseline old.json
sealion bench query --rounds 3 --cache --data-dir ./sealion-data
sealion serve --bind 127.0.0.1:8080 --data-dir ./sealion-data
4.2. Data directory
sealion-data/
manifest.json # sole mutable file: { generation, segments, deleted }
seg-000001.seal # immutable segment
seg-000002.seal # immutable segment
{
"generation": 3,
"segments": ["seg-000001.seal", "seg-000002.seal"],
"deleted": [12345]
}
|
Note
|
A document is searchable if and only if its segment is listed in
manifest.json. Orphan temp files from a crashed publication are ignored.
|
4.3. Configuration
Validated TOML; unknown or inconsistent values are rejected at load, not silently defaulted.
[analysis]
stop_words = true
stemmer = "porter"
[analysis.fields.title]
stemmer = "porter"
weight = 4.0
[query]
max_query_terms = 64
|
Caution
|
Ranking weights live in configuration, but any weight change is a ranking change: it requires a relevance regression check (see Verification) before it is accepted. |
5. Programming Model
How to talk to the system: the query language, normalization rules, and the explanation output used for debugging ranking.
5.1. Query syntax
Queries are text plus a small set of operators.
All terms pass through the same analysis pipeline as indexed text
(see Design), so Databases and database agree when
stemming is enabled.
| Form | Example | Meaning |
|---|---|---|
bare terms (implicit AND) |
|
documents containing both terms |
explicit |
|
Boolean combination; precedence |
quoted phrase, bare or fielded |
|
positional adjacency required |
field filter |
|
term must occur in the named field |
site filter |
|
document source host must match |
prefix |
|
vocabulary prefix expansion |
fuzzy |
|
within edit distance 1 of the term |
sealion search 'title:compiler AND optimization NOT javascript' --data-dir ./sealion-data
sealion search '"index merge"~5' --data-dir ./sealion-data
sealion search 'storag~1' --data-dir ./sealion-data
|
Note
|
The parser rejects over-complex input with a typed error instead
of silently truncating. max_query_terms bounds prefix and fuzzy
expansion before execution.
|
5.2. Normalization and planning
-
Parse raw text into a query AST (
Term,Phrase,Prefix,Fuzzy,Site,And/Or/Not). -
Normalize every term through the index analysis pipeline.
-
Plan evaluation order from document frequency and posting size — never blindly left-to-right.
|
Tip
|
When a query surprises you, re-run it with --explain before
assuming the index is wrong. Most surprises are normalization
(case, stop words, stemming) rather than missing postings.
|
5.3. Explain output
query : "distributed systems"
parsed : Phrase(["distribut", "system"])
doc 17 : tf=2/1 df=3/9 idf=1.62/0.94 len=120 avg=98.4
field w: title 4.0, body 1.0 -> contrib 4.31 + 1.02
total : 5.33 (score desc, DocId asc)
The breakdown exposes parsed shape, per-term tf / df / idf,
field lengths and averages, field-weight contributions, and the final
score — the same components defined in Performance.
6. Verification
How the project proves search is correct — and how to re-run that proof locally.
6.1. Reference oracle
An intentionally slow engine scans every document and computes the exact answer for any query shape. Every optimized path must agree with it:
-
Boolean identities and spec examples
-
prefix, fuzzy, and site evaluation
-
phrase position checks
-
ranked ordering (score desc,
DocIdasc) -
incremental indexing equals clean rebuild
-
deleted documents never appear
|
Important
|
No search optimization lands without oracle agreement. Optimized top-k must equal exhaustive top-k unless the strategy is explicitly documented as approximate. |
6.2. Correctness properties
| Property | Where it is checked |
|---|---|
|
codec unit + roundtrip tests |
|
generations tests |
incremental indexing |
reference agreement tests |
optimized top-k |
phrase/rank + segment search tests |
phrase results truly contain the phrase |
phrase oracle tests |
deleted docs never appear |
Boolean reference + generations tests |
Corruption handling is also tested: bit flips, truncation, unknown versions, and unknown flag bits are rejected as errors — never misread (see Implementation).
6.3. Running the gates
cargo fmt --all -- --check
cargo clippy --workspace --all-targets -- -D warnings
cargo test --workspace
This is the same gate CI runs on every push
(.github/workflows/ci.yml).
Unit tests live next to the code in src/ files; integration gates
live in tests/ (boolean_reference, segment_roundtrip,
generations, phrase_rank, segment_search, and others).
|
Tip
|
When adding a query feature, add the oracle comparison first. A failing oracle test is the specification; a passing one is the proof. |
7. Implementation
Persistent layout and integrity rules.
docs/index-format.md is normative for the byte layout;
this chapter summarizes it and states the invariants the code enforces.
7.1. Segment layout
| Offset | Size | Field |
|---|---|---|
0 |
8 |
magic |
8 |
4 |
version |
12 |
4 |
flags — bit 0: compressed postings, bit 1: compressed positions |
16 |
8 |
doc_count |
24 |
8 |
dict_count (fielded terms) |
32 |
8 |
dict_offset |
40 |
8 |
meta_offset |
48 |
8 |
stats_offset |
56 |
4 |
header_crc (CRC32 of bytes 0..56) |
Dictionary entries are sorted by (field, term) and carry
postings_offset/len, positions_offset/len, first_doc/last_doc
(block-skip inputs), and per-block CRCs.
Statistics store per-field token totals in canonical field order;
average length is total / doc_count.
7.1.1. Dictionary entry fields
| Field | Notes |
|---|---|
field id |
|
term bytes |
|
doc_freq |
documents containing this fielded term in this segment |
offsets / lengths |
absolute file positions of the postings and positions blocks |
first_doc / last_doc |
DocID bounds feeding future block-skip retrieval |
CRCs |
per-block checksums verified on every open |
7.2. Publication protocol
-
Write the segment to a temp file in the data directory.
-
Flush and fsync the temp file.
-
Re-read and verify the temp file (checksums, ordering, counts).
-
Atomically rename the temp file into place.
-
Publish the new generation with an atomic manifest rename.
A crash before the final rename leaves the previous generation intact; orphan temp files are ignored on open.
7.3. Integrity policy
-
Every header, postings block, dictionary entry, and file carries a CRC32.
-
Readers reject unknown versions and unknown flag bits loudly rather than guessing.
-
Truncation and single-bit corruption are errors, not degraded reads.
-
Document IDs in metadata must match the stored document’s own ID.
|
Warning
|
Never hand-edit manifest.json or a .seal file.
Use sealion index stats, sealion index verify, sealion index merge,
and sealion index delete — the only writers that preserve the
atomicity and checksum invariants above.
|
8. Performance
Measured behaviour only. Unmeasured values are TBD (unmeasured).
Every optimization follows profile → hypothesize → implement →
benchmark → document.
8.1. Ranking model
Primary lexical score is field-weighted BM25 with positive IDF:
with k1 = 1.2, b = 0.75, and per-field weights applied on top:
score = 4.0 * title_BM25 + 2.0 * heading_BM25
+ 1.0 * body_BM25 + 1.5 * anchor_BM25
N, df, and length statistics are computed over the live set only —
tombstones and shadowed versions are excluded.
Ties break by ascending DocId, giving a total order that skipping
optimizers must reproduce exactly.
8.2. Compression
Postings use sorted DocIDs → delta encoding → variable-byte encoding; positions use deltas plus compact integer encoding. A raw (uncompressed) layout exists for benchmark comparison only.
| Metric | Compressed | Raw |
|---|---|---|
bytes/posting |
1.0–1.6 |
|
demo segment size |
46.8% of raw |
100% (baseline) |
Report bytes/posting, decode throughput, and query-latency effect together — size alone never justifies a codec change.
8.3. Benchmarks
# Codec + segment sizes (compressed must beat raw)
cargo test -p sealion-index --test compression_bench -- --nocapture
# Query + indexing harnesses (WAND ablation, cache, scaling runs)
cargo run -p sealion-bench -- --help
Benchmark sets should cover rare terms, common terms, multi-term AND, OR, phrases, typos, fuzzy, autocomplete, and a realistic mixed distribution. Scaling claims require 1/2/4/8-shard runs — never claim linear scaling without measuring it.
|
Note
|
kgCO₂ or latency numbers copied from another project do not
belong here. If it was not measured in this tree, it is
TBD (unmeasured).
|
9. Known Limitations
Honest boundaries: what the system is, and what it is not. This chapter overrides any optimistic reading of earlier chapters.
9.1. What is real today
-
Analysis, mem-index, query AST/parser, Boolean execution, and the reference oracle.
-
Persistent
.sealsegments with crash-safe publication and verified reads. -
Delta+varint postings compression with measured benchmarks.
-
Generations, tombstones, shadowing,
index merge/index delete. -
Exhaustive field-weighted BM25 with phrases, snippets,
--explain. -
Exact Block-Max WAND top-k verified
==exhaustive. -
Typo tolerance (BK-tree) and autocomplete with did-you-mean.
-
Crawler: frontier, politeness, robots, SSRF defense, canonicalization, SimHash dedup, HTML + img-alt extraction.
-
Relevance science: graded judgments, nDCG/MRR/MAP, regression gate (seed nDCG@10 = 0.9314).
-
Distribution: hash sharding, global-stats coordinator, replicas
failover routing, partial semantics, atomic moves. -
Caches + benches with measured before/after.
-
HTTP API (
/api/search,/api/complete, admin status/metrics) plus a dependency-free search page viasealion serve. -
CLI:
index,search,complete,crawl,cluster/shard/node,eval,bench,serve,index stats|verify|merge|delete|authority.
9.2. What is explicitly not here
-
Hybrid vector retrieval: evaluated and explicitly deferred (ADR-018) — no embedding runtime, lexical only.
-
Corpus formats are
.txt/.md/.html(alt text kept); binaries are counted and skipped. -
The product UI is a dependency-free search page — that is the UI.
9.3. Limits to design around
-
Ranking is lexical field-weighted BM25 (+ PageRank authority and freshness decay where configured) — no semantic signals.
-
A document is searchable if and only if its segment is listed in
manifest.json; readers reject corruption as errors rather than misreading. -
Published numbers are measured in this tree (release: 5114 docs/s indexing, 271 qps exact WAND search; seed nDCG@10 = 0.9314). Unmeasured values are
TBD (unmeasured).
About me
I’m Tyrone Marhguy, a Computer Engineering student at the University of Pennsylvania, class of 2028. SeaLion is the full-text search engine I am building in Rust.
I grew up between Kumasi and Accra. In 2021, Achimota School denied me admission because I wear dreadlocks as an expression of my Rastafarian faith. Ghana’s High Court ordered the school to admit me; I finished secondary school there, then came to Penn on a full scholarship. BBC Pidgin and Deutsche Welle covered the case.
I design the architecture, build the boards, and write the software. Tomato is a 32-bit computer with a running FPGA implementation and discrete boards in progress. I also build systems software, including a search engine, a compiler, and a database, and I contribute fixes to open-source EDA tools such as LibreLane, OpenROAD, Verilator, and OpenFPGA. That work has included production software at Aragorn AI and battery-management hardware at Vero Electric.
Hardware
-
Tomato, a 32-bit computer (repository)
-
Pineapple GPU, a programmable 3D GPU on a Nexys A7
-
riscv64xO3, a 2-wide out-of-order RV64IMAC
-
MAC, a BFloat16 multiply-accumulate for SkyWater 130 nm
-
UDP/IP stack, a 100 Mbps datapath on a Nexys A7
-
ITCH parser, NASDAQ ITCH 5.0 on a Nexys A7
-
6T SRAM, a full-custom SRAM study
Open source
See open-source work for contributions to LibreLane, OpenROAD, Verilator, and OpenFPGA.