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.

SeaLion demo — search page with BM25-ranked hits (2x speed).

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

Introduction

Scope, conventions, and reading order.

Architecture

Components, indexing and search paths, and crate responsibilities.

Design

Documents, analysis, inverted indexes, and segment generations.

Interfaces

Commands, data directory structure, and configuration.

Programming model

Query syntax, normalization, and explain output.

Verification

Reference oracle, correctness properties, and test commands.

Implementation

Segment layout, publication protocol, and integrity checks.

Performance

Ranking formulas, compression, and benchmarks.

Known limitations

Implemented behavior and current boundaries.

Conventions

  • monospace identifies 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.md and docs/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:

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.4. Conventions

Normal cross-reference and link usage
  • 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.

List conventions
  • Unordered lists state properties or inventories.

  • Ordered lists state procedures where sequence matters:

    1. Build the workspace.

    2. Index a corpus.

    3. 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.

SeaLion system overviewIndexing: Corpus files → analysis → MemIndex → segment writer; Storage: Immutable .seal segments; manifest.json publishes the current generation.; Search: Query → normalization → ranked retrieval → snippets and explanations SeaLion system overview Ingestion, storage, and retrieval 01 Indexing Corpus files → analysis → MemIndex → segment writer 02 Storage Immutable .seal segments; manifest.json publishes the current generation. 03 Search Query → normalization → ranked retrieval → snippets and explanations
Figure 2. System paths at a glance

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.4. Crate map

Table 1. Crates and their responsibilities
Crate Owns Stage

sealion-core

document model, field taxonomy, config, errors

foundation

sealion-index

analysis, mem-index, segments, codec, merge, views

indexing

sealion-query

parser, Boolean execution, reference oracle, ranking, snippets

retrieval

sealion-crawler

frontier, fetch, politeness, robots, dedup, HTML extraction

ingestion

sealion-eval

judgments, nDCG/MRR/MAP, regression comparison

evaluation

sealion-distributed

hash sharding, coordinator, replicas, routing, rebalancing

scale-out

sealion-api

HTTP search/complete/admin API + static search page

product

sealion-bench

query/index benchmark harnesses

measurement

sealion-cli

sealion command-line interface

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 same IndexView trait, 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 rebuild is 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
Table 2. Subcommands
Command Effect

index <corpus>

build segments from local files and publish a new generation

search <query>

parse, execute, rank, and render hits with snippets

search --explain

additionally print parsed query, normalized terms, and BM25 components

index stats

report segment, document, and term counts for the data directory

index verify

re-verify checksums and publication invariants, reporting corruption as errors

index delete <id>

record a tombstone; the document becomes invisible immediately

index merge

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.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.

Table 3. Query operators
Form Example Meaning

bare terms (implicit AND)

distributed systems

documents containing both terms

explicit AND / OR / NOT with parens

compiler AND (optimization OR backend) NOT javascript

Boolean combination; precedence NOT > AND > OR

quoted phrase, bare or fielded

"distributed systems", title:"distributed systems"

positional adjacency required

field filter

title:compiler

term must occur in the named field

site filter

site:example.com

document source host must match

prefix

comp*

vocabulary prefix expansion

fuzzy

compiler~1

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

  1. Parse raw text into a query AST (Term, Phrase, Prefix, Fuzzy, Site, And / Or / Not).

  2. Normalize every term through the index analysis pipeline.

  3. 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, DocId asc)

  • 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

decode(encode(postings)) == postings

codec unit + roundtrip tests

merge(segments) preserves search results

generations tests

incremental indexing == clean rebuild

reference agreement tests

optimized top-k == exhaustive 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).

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

Table 4. Header (60 bytes, little-endian)
Offset Size Field

0

8

magic SEALION1

8

4

version 1 (readers reject anything else)

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

0=title 1=heading 2=body 3=anchor; unknown ids rejected

term bytes

u32 length + UTF-8 bytes; entries sorted by (field, term)

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.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:

\[\text{idf}(t) = \ln\left(1 + \frac{N - df(t) + 0.5}{df(t) + 0.5}\right)\]
\[\text{bm25}(t, d) = \text{idf}(t) \cdot \frac{tf(t,d)\,(k_1 + 1)}{tf(t,d) + k_1\left(1 - b + b\,\frac{|d|}{\text{avgdl}}\right)}\]

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.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 .seal segments 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 via sealion 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

Software and systems

Open source

See open-source work for contributions to LibreLane, OpenROAD, Verilator, and OpenFPGA.