SeaLion Technical Reference Manual

SeaLion at a glance

SeaLion is a distributed full-text search engine built from first principles in Rust — BM25 ranking over immutable segments, exact skipping, typo tolerance, a polite crawler, and a search page served over HTTP.

SeaLion demo — search page with BM25-ranked hits

Figure 1. Demo — the search page answering a query

Try Live Search GitHub Repository

About this manual

This is the detailed technical reference for the project. It is the companion to the concise, GitHub-facing README.md:

README.md — project identity, status, and quick start.
docs/ (this manual) — architecture, interfaces, verification, and implementation detail in engineering-manual style.

Conventions used throughout:

monospace marks commands, file paths, identifiers, and literals.
Section references such as (§26) point at the full requirements text where applicable to this project.
Unmeasured values are written as TBD (unmeasured) — never silently estimated.
Normative byte layouts and decision records live alongside this manual as Markdown (docs/*.md, docs/adr/) and are linked, not duplicated.

Start with Introduction for scope and reading order, then Architecture for the system overview.

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.

The fastest way to see what the system is: the demo recording and live links at the top of this manual.

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

Normal cross-reference and link usage

Internal references look like this: Verification.
External links look like this: NEORV32 documentation, the visual reference for this manual’s style.
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.

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

The sidebar on the left is collapsible. Select a chapter title to navigate; select its arrow control to expand or collapse its subsections without leaving the page.

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.

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.2. Indexing path

corpus files (.txt/.md today)
  -> collect (stable DocIds)
  -> analyzer (tokenizer, case folding, stop words, stemmer)
  -> MemIndex (fielded positional postings)
  -> segment writer (delta+varint, per-term CRCs)
  -> immutable .seal segments + manifest.json

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

sealion search 'query'
  -> parse + normalize (same analysis as indexing)
  -> Boolean execution / ranked retrieval
  -> snippets + per-term explanation
  -> ranked hits (score, title, url, snippet)

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

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

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

raw text
  -> Unicode-alphanumeric tokenizer
  -> case folding
  -> stop-word handling (with position gaps)
  -> Porter stemming (per-field configurable)
  -> terms + positions

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.

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

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

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

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

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

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.

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

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

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

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

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

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

+-------------------------------+
| header                  60 B  |  magic SEALION1, version, flags, counts, offsets, CRC
+-------------------------------+
| postings + positions blocks   |  delta+varint DocIDs + gapped positions, per-term CRCs
+-------------------------------+
| dictionary  (count + entries) |  sorted by (field, term): offsets, df, bounds, CRCs
+-------------------------------+
| document metadata (stored)    |  DocID + JSON Document per doc
+-------------------------------+
| statistics                    |  per-field token totals (BM25 avgdl inputs)
+-------------------------------+
| footer                  16 B  |  magic + file CRC32
+-------------------------------+

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

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

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

Table 5. Measured compression (demo segment, from ADRs)
Metric	Compressed	Raw
bytes/posting	1.0–1.6	`TBD (unmeasured)`
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.

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