VLSM — an LSM-Tree with Vector Segments

What You Are Building

Agents read and write the same store in the same breath: an upsert of a tool result is followed, milliseconds later, by a semantic search over everything written so far. Classical vector databases assume a mostly-static corpus and rebuild indexes offline; classical LSM-trees ingest fast but cannot answer “what is near this embedding?” In this lab you build VLSM, an LSM engine in which every SSTable carries a vector segment: a block of scalar-quantized embeddings plus a serialized HNSW graph over them. Searches fan out across the memtable and every level’s graphs; compaction merges graphs instead of throwing them away.

The lab has four milestones. Milestone 1 is a file format. Milestone 2 is an index. Milestone 3 is the heart of the lab — compaction that preserves index work. Milestone 4 turns your engine into evidence: a harness, a frontier, and an ablation table. Each milestone has an acceptance test in the grading suite (cargo test --features grading, distributed at the end of Week 2); passing it is necessary but not sufficient for full credit.

Fix these workload parameters unless a milestone says otherwise: vector dimension D = 768 (f32 source vectors), cosine distance over L2-normalized inputs (so you may implement it as negative dot product), k = 10 for all recall figures, and the synthetic agent trace produced by the provided generator with seed 2027. “Recall@10” always means recall against exact f32 brute-force search over the live (non-deleted, latest-version) rows.

The Skeleton

Clone data2027/vlsm-skeleton. It is a small but real engine — roughly 1,000 lines — and it already passes its own key–value test suite. You get:

• Core types & Engine trait (lib.rs): Key/Value/DocId/Vector, EngineConfig/HnswParams, the error enum, and ParetoRow.
• Memtable (memtable.rs): a BTreeMap mapping keys to values, with vectors in a DocId-keyed side-table and brute-force knn. Flush threshold 64 MiB.
• SSTable writer & format spec (sstable.rs): the normative byte layout in its doc comments, a working SstWriter (codec 0 = raw f32), and a reference crc32c; SstReader is todo!() — Milestone 1.
• Workload generator (workload.rs): emits the Milestone 4 trace, with brute-force ground truth per query.
• Smoke harness (src/bin/bench.rs): replays the trace against the memtable; the seed of your Milestone 4 harness.

The public surface you extend, abridged:

// src/lib.rs — provided; the memtable implements it, your Db must too
pub trait Engine {
    fn put(&mut self, key: Key, value: Value, vector: Option<Vector>)
        -> Result<Option<DocId>>;
    fn get(&self, key: &[u8]) -> Result<Option<Value>>;
    fn scan(&self, start: &[u8], end: &[u8]) -> Result<Vec<(Key, Value)>>;
    fn knn(&self, query: &Vector, k: usize, ef: usize)
        -> Result<Vec<(DocId, f32)>>;
}

// src/sstable.rs — writer provided (codec 0)
impl SstWriter {
    pub fn new(path: impl Into<PathBuf>, dim: usize) -> SstWriter;
    pub fn add(&mut self, key: &[u8], value: &[u8],
               vector: Option<(DocId, &Vector)>) -> Result<()>;
    pub fn add_tombstone(&mut self, key: &[u8]) -> Result<()>;
    pub fn finish(self) -> Result<SstMeta>;
}

// src/sstable.rs — YOU WRITE (Milestones 1–2): the todo!() stubs
impl SstReader {
    pub fn open(path: &Path) -> Result<SstReader>;
    pub fn get(&self, key: &[u8]) -> Result<Option<Value>>;
    pub fn scan(&self, start: &[u8], end: &[u8]) -> Result<Vec<(Key, Option<Value>)>>;
    pub fn vector(&self, ordinal: u32) -> Result<Vector>;
    pub fn knn(&self, query: &Vector, k: usize, ef: usize)
        -> Result<Vec<(DocId, f32)>>;                   // Milestone 2
}

// new modules — YOU WRITE (Milestones 2–3): HNSW build/search/serialize,
// a Db (memtable + levels) implementing Engine, and graph-merging
// compaction, e.g.
pub fn merge_graphs(srcs: &[&SstReader], live: &DocIdFilter,
                    params: HnswParams) -> (SstWriter, MergeStats);

DocId is a u64, assigned sequentially in put order, one per vectored version; each segment’s row-id map takes a graph ordinal to its DocId. The workload generator pre-assigns the same sequence in Op::Upsert::doc_id — replay the trace in order, exactly once, and ground-truth ids match engine ids with no translation table.

The Vector Segment Format

Every .sst file holds six sections — header, key block, vector codes, codebook, row-id map, HNSW adjacency — followed by a 64-byte footer at EOF that points backward at all of them. All integers are little-endian. Every section starts at a 64-byte-aligned offset (pad with zeros), so the reader can hand out aligned zero-copy slices from the mmap. The layout:

Acceptance: round-trip property tests pass (write → read → decode within quantization error); the reader returns Err(Corrupt), never panics or UB, on the provided corpus of 200 mutated files; brute-force search over decoded i8 codes achieves recall@10 ≥ 0.95 against f32 brute force on the 100k-vector sample set.

Per-Level HNSW: Build and Search

Implement HNSW (Malkov & Yashunin, 2018 — assigned in Week 2) from scratch. Construction runs at flush and at the end of compaction, over the quantized codes; drive it from the provided HnswParams { m, ef_construction, ef_search } and serialize the result into the segment’s HNSW section as per-layer CSR adjacency (Fig. 1). Distances during build and search are computed directly on i8 codes using the segment’s scale/bias — do not decode whole vectors to f32 buffers.

Db::knn must consult every live source: brute-force over the memtable, then beam search (width ef) in each level’s segment graphs, merging candidates in a single global heap. A candidate whose DocId is shadowed by a newer version or a tombstone above it must be filtered before it can occupy one of the k result slots. Optionally re-rank the final 4k candidates with f32 vectors — keep this behind a flag; it is one of your ablations.

Acceptance: on a 1M-vector single-segment fixture with m = 16, ef = 64: recall@10 ≥ 0.90 with mean query latency ≤ 2 ms on the grading machine (8 cores, AVX2); construction ≤ 8 minutes; the serialized graph reloads byte-identically.

Graph-Merging Compaction

This is where VLSM differs from “LSM plus a vector index bolted on.” When compaction merges SSTables S₁…Sₙ into new output tables, the naive move is to rebuild each output graph from scratch — O(N log N) distance computations you already paid for once. Implement merge_graphs instead:

• Remap, don’t rebuild. Surviving nodes keep their neighbor lists, with ordinals rewritten through the compaction remap table.
• Repair, locally. Edges pointing at dropped rows (tombstoned or shadowed) are repaired by promoting neighbors-of-neighbors of the dropped node, re-selected with the standard HNSW heuristic; cap repair fan-out at 2m distance evaluations per dropped node.
• Insert the minority. Nodes from all source graphs but the largest are inserted into the largest graph’s structure via normal HNSW insertion (over quantized codes). Layer assignments may be preserved or redrawn — measure both and report.
• Requantize when forced. If the merged value range moves any dimension’s scale by more than 25%, recompute scale/bias and re-encode; otherwise keep the dominant segment’s parameters. Record which case occurred in MergeStats.

Acceptance: after the scripted compaction storm in tests/m3_storm.rs (50 compactions, 30% deletes), recall@10 of merged graphs is within 0.02 of rebuilt-from-scratch graphs at equal ef, and total compaction CPU time is at least 3× lower than the rebuild baseline — which you must also implement, behind --features rebuild-baseline, because it is the control arm of your ablation.

Benchmark Harness and Pareto Report

The provided generator (workload.rs) emits a synthetic agent trace: sessions that interleave upserts (tool results, ~20% of ops), range scans (~10%), and vector searches (~70%) with Zipfian skew over both keys and query templates. Build a harness that replays it at a fixed arrival rate while sampling four axes: search latency p99, sustained update throughput, resident memory (RSS, plus your own accounting of graph bytes), and recall@10 (sampled: every 50th search is also answered by the brute-force oracle).

Sweep at least three knobs — m ∈ {8, 16, 32}, ef ∈ {16, 64, 256}, and re-ranking on/off at minimum; codec and level fan-out are encouraged — and plot the Pareto frontier in the recall–latency plane with memory encoded as mark size, plus one ablation table isolating each knob’s marginal effect with the others held at defaults. The report (≤ 6 pages, PDF) must state the hardware, the seed, and the exact commit; every figure must be regenerable by make report.

Rubric

Late policy: 10% per day, 3 days maximum. One milestone may be designated “best effort” in your report for a 5-point cap reduction instead of failing its tests silently — honesty is cheaper than hope.

Where Last Year’s Cohorts Bled

What You May Not Do

• No off-the-shelf vector or ANN libraries. faiss, hnswlib, usearch, instant-distance, qdrant-anything — including “just for the baseline” or via FFI. The brute-force oracle, the quantizer, and the graph are the lab.
• No serde-derived on-disk formats. The vector segment is written and parsed by your own code against the byte-level spec above. (Serde for the report’s JSON output is fine.)
• No single-number results. Every performance claim in the report carries a distribution (p50/p99) or a frontier; “1.7× faster” with no operating point is graded as unsupported.
• Allowed: crossbeam, rayon, memmap2, crc32c, hand-written SIMD via std::arch, and anything already in the skeleton’s lockfile. When in doubt, ask on the course forum before the due date, not in the regrade request.

Checkpoint Questions

Answer in ≤ 1 page each, in CHECKPOINTS.md, before the milestone they accompany. They are graded inside the report component.

Starter files