Quiver is a Cargo workspace: a from-scratch storage engine, index structures, SIMD distance kernels, and a query planner, with a thin gRPC/REST shell and a TUI client. The C4 views — system context and container view — map the system at a glance; the crate map below and the index design that follows are the deep dive. Every significant decision is captured as an ADR.

Quiver — Architecture Overview

Quiver is a native-Rust vector database. It stores vectors and structured payloads, builds approximate-nearest-neighbour (ANN) indexes over them, and answers top-k similarity queries with optional metadata filtering — over gRPC, REST, an embeddable library API, and an MCP server, with a retro terminal cockpit for operators.

The wedge (and the non-goals)

Quiver competes on a narrow, defensible edge, not on raw scale or feature count:

1. Security-first, by default. Encryption-at-rest is on out of the box with secure defaults; payloads can be client-side-encrypted so the server never sees plaintext; strong authN/Z, audit, and crypto-shredding. Only audited cryptography (rustls, RustCrypto/ring) — never a primitive of our own.
2. Memory frugality. Disk-resident graph/inverted indexes plus quantization (product, scalar, binary) let large datasets serve from a laptop’s RAM budget. The headline benchmark metric is memory footprint at a fixed recall, not just QPS.
3. Developer experience. A single static binary; embeddable and server modes; a ratatui cockpit; idiomatic Python and TypeScript SDKs; an MCP server so agents can drive it.

Explicit non-goals for v1 (stated to keep the project honest): out-scaling Milvus/Pinecone; distributed clustering (single-node excellence first; replication is a clearly-labelled stretch); homomorphic-encrypted search in core (only a published distance-comparison-preserving scheme, behind an experimental flag, with honest leakage caveats). Embeddings are produced by the caller — Quiver stays model-agnostic.

Workspace map

The core (storage, indexes, kernels, query planner, on-disk format, wire protocol) is built from scratch. A minimal set of vetted crates is used only where reinventing would be reckless (async runtime, TLS, crypto, serialization, TUI). No embedded database engine is used (no RocksDB/LMDB/sqlite).

Dependency DAG (acyclic by construction)

flowchart TD
  simd[quiver-simd]
  crypto[quiver-crypto]
  proto[quiver-proto]
  core[quiver-core] --> crypto
  index[quiver-index] --> core
  index --> simd
  query[quiver-query] --> index
  query --> core
  embed[quiver-embed] --> query
  embed --> crypto
  providers[quiver-providers]
  server[quiver-server] --> embed
  server --> proto
  server --> crypto
  server --> providers
  tui[quiver-tui] --> proto
  mcp[quiver-mcp] --> embed
  mcp --> crypto
  mcp --> providers
  cli[quiver-cli] --> server
  cli --> tui
  cli --> mcp
  cli --> embed

Domain logic lives in the lower crates (core/index/query/crypto); framework code (HTTP, gRPC, TUI, MCP) stays at the edges. This keeps the engine testable in isolation and reusable in embedded mode.

Operating modes

• Embedded library — quiver_embed::Database::open(path, config)? gives an in-process handle: no network, no auth surface, encryption-at-rest still on. For tests, notebooks, and apps that want a local vector store.
• Server — quiver serve exposes gRPC + REST with auth, RBAC, multi-tenant namespaces, audit, query cost limits (ADR-0040), and observability. The TUI and MCP server are API clients of it.

Both ship in one static binary; quiver-server is a thin network/policy shell over quiver-embed.

Request lifecycles

Write (upsert): client → server (TLS terminate → authenticate → authorize scope → cost-limit check → idempotency check) → quiver-embed → quiver-core appends a WAL record (encrypted, checksummed) and stages the vector + payload into the active segment → quiver-index inserts the vector into the live index → ack after WAL fsync (durability boundary). Payload secondary indexes updated transactionally with the segment.

Query (top-k + filter): client → server (authn/z) → quiver-query plans the filter strategy (pre-filter via metadata bitmap when selective; post-filter otherwise) → quiver-index runs ANN search (HNSW/Vamana/IVF), using quiver-simd kernels on quantized vectors → candidate set re-ranked with exact distances against full-precision vectors fetched & decrypted from quiver-core → top-k assembled (payloads decrypted at rest; returned as-is if client-side-encrypted) → response with a cursor for pagination.

Cross-cutting concerns

• Security layers: TLS/mTLS in transit (quiver-crypto/rustls); envelope encryption at rest (per-collection DEK wrapped by a master key, AEAD on segment pages); optional client-side payload encryption (opaque ciphertext to the server); API-key scopes + RBAC + tenant isolation; append-only audit log; crypto-shredding by DEK destruction. See ../security/threat-model.md and ../security/crypto.md.
• Concurrency: single-writer, many-reader. The server guards the engine with a reader–writer lock (ADR-0057): searches take the shared lock and run in parallel, writes take the exclusive lock. A read that finds a collection’s index stale (a prior write deferred its rebuild) serves the prior snapshot and schedules an off-lock rebuild (ADR-0062) — the inputs are captured under the shared lock, the new index is built with no lock held, and it is swapped in under a brief write lock — so a rebuild never stalls concurrent readers (measured: a 100k-vector rebuild that blocked every read for ~77 s now keeps reads in the sub-millisecond tail). Reads are then snapshot-isolated and eventually consistent across a rebuild window; embedded &mut callers still rebuild synchronously for read-your-writes. Durability and the kill -9 crash gate are unchanged.
• Observability: OpenTelemetry-compatible tracing spans across server→query→index→core; Prometheus /metrics; structured logs; /healthz + /readyz.
• Configuration: typed, validated config with secure defaults; secrets via env + KMS pattern (see ADR-0013).

Where to read next

• C4 system context — c4-context.md; container view — c4-container.md.
• Per-subsystem diagrams (storage, indexing, retrieval, distributed, security, ops) — ../diagrams.md.
• Decisions — ../adr/. Roadmap & DoDs — ../roadmap.md. Risks — ../risk-register.md.
• The bridge to implementation — ../repo-scaffold-plan.md.

Index Design

The index engine (quiver-index) is the centerpiece. Indexes are pluggable per collection behind a common trait, so a collection picks the point on the recall / latency / memory surface it needs. The decisions are recorded in ADR-0007 (index roadmap) and ADR-0008 (quantization); the distance math is in distance-kernels.md.

The tradeoff surface

Memory frugality is the headline; the disk-resident path is risk R1 and is de-risked with the analytical budget below before any code is written.

HNSW — Phase 1, in-memory

Hierarchical Navigable Small World graphs (Malkov & Yashunin, IEEE TPAMI 2020; arXiv:1603.09320). A multi-layer proximity graph: greedy descent through sparse upper layers to an entry region, then an ef-bounded best-first search at the dense base layer.

• Parameters: M (neighbors/node/layer; base layer 2M), efConstruction, efSearch, level factor mL = 1/ln(M). Recall/latency tuned by efSearch at query time.
• Neighbor selection: the paper’s heuristic (keep diverse neighbors, not merely the nearest) — materially better recall on clustered data than naive top-M.
• Memory layout: base-layer adjacency in a flat arena of fixed 2M u32 slots per node for cache locality; upper-layer lists (held only by the few nodes promoted above L0) in a compact side structure. Vectors are referenced by row id into the columnar store — full-precision for exact distance, or quantized codes when compressed.
• Concurrency: built by the single writer; traversed lock-free by readers via atomic adjacency publication + EBR (see ../concurrency/model.md).

Vamana / DiskANN — Phase 2, disk-resident (the memory-frugal core)

DiskANN (Subramanya et al., NeurIPS 2019). A single flat Vamana graph (degree R, build list L, prune slack α≈1.2) laid out on SSD so each node co-locates its adjacency and its full-precision vector in one disk block — one random read per hop.

• RAM holds only PQ-compressed vectors (to navigate with approximate distances) plus a hot-node cache; the graph and full vectors stay on SSD. The candidate set returned by the beam search is re-ranked with exact distances by fetching full-precision vectors from SSD.
• Parameters: R (e.g. 64–128), L, α, beam width W (parallel SSD reads/hop).

IVF (+ PQ / SPANN) — Phase 2, the predictable-memory fallback

Inverted file: a coarse k-means quantizer partitions space into nlist Voronoi cells; a query probes the nprobe nearest cells. Combined with PQ (IVFADC; Jégou et al., IEEE TPAMI 2011) or with on-disk posting lists (SPANN; Chen et al., NeurIPS 2021, which keeps centroids in RAM and balanced posting lists on SSD). IVF gives a tighter, more predictable RAM profile (essentially just centroids) and fast builds, at somewhat lower recall-per-IO than a good graph — hence its role as the R1 fallback if a Vamana RAM budget slips.

Quantization (ADR-0008)

• Scalar (SQ): f32 → int8 per-dim min/max. 4× smaller, fast, good default for light compression.
• Product (PQ): split dim into m subspaces, k-means (256 centroids → 1 byte/subspace); asymmetric distance via precomputed lookup tables. The workhorse for RAM-resident codes.
• Binary (BQ): 1 bit/dim (sign); Hamming via SIMD popcount as a fast pre-filter, then exact re-rank. ~32× smaller; strong for high-dim normalized embeddings.
• Re-rank flow: approximate distance (SQ/PQ/BQ) → candidate set → exact full-precision distance → final top-k. The candidate multiplier is the recall ↔ latency/memory knob.

Analytical memory budget — de-risking R1 (768-dim f32 embeddings)

10M × 768-dim: full vectors = 30.7 GB (won’t fit a laptop). DiskANN keeps PQ codes (m=96) ≈ 0.96 GB in RAM + a node cache, with full vectors + graph (~32 GB) on SSD → serve 10M from ~1–2 GB RAM. 100M ⇒ ~9.6 GB PQ in RAM (a 32 GB workstation) + ~320 GB SSD. Honest scope: billion-scale DiskANN needs a server (~64 GB RAM); on a 16–32 GB laptop/workstation the disk path comfortably serves tens to a few hundred million vectors. SIFT1M (128-dim) full-precision HNSW is ~0.5 GB of vectors + ~0.13 GB adjacency — trivially in RAM.

De-risk plan: (1) this budget + a recall model from the cited papers (now); (2) a .scratch spike on a public 1–10M set measuring real recall vs RAM for chosen (R, m, W) before Phase 2 implementation; (3) prove at 10M+ in Phase 2 benchmarks. Fallback: IVF+PQ.

Filtered search

The planner (in quiver-embed) decomposes the Filter into the predicates the secondary indexes can answer (And intersects, Or unions, negation/existence/undeclared fields widen to unconstrained — always a sound superset) and resolves a candidate id set via Store::matching_ids. When that set is selective (at or below a full-scan threshold) it scans those rows exactly — perfect recall, and immune to the filtered-ANN recall cliff that bites when a selective predicate starves an over-fetched candidate list; an empty candidate set short-circuits to no results. When the filter is broad (or not indexable) it post-filters the ANN candidates instead. Both arms re-check the full Filter, so results are exact regardless of path. This is the selectivity-based strategy for v1; constraining graph traversal to an allowed-node bitmap, and specialized filtered-graph search (e.g. Filtered-DiskANN, Gollapudi et al. WWW 2023; ACORN, Patel et al. SIGMOD 2024), are later enhancements.

Incremental updates (Phase 4 — ADR-0023)

Through v0.3.0 the index is a derived artifact: HNSW absorbs a brand-new id in place, but an update, a delete, or any write to a batch index (Vamana / IVF / DiskVamana) marks the collection stale and the next search rebuilds it from the store — which is also how every index is reconstructed on open. This is simple and correct (the store is the single source of truth, ADR-0020/0021, so the index never has to be crash-consistent), but the update cost is O(N), which does not suit streaming workloads.

Phase 4 closes the gap with SpFresh’s LIRE protocol (Lightweight Incremental REbalancing; Xu et al., SOSP 2023), applied first to IVF — the inverted-list structure LIRE was designed for (SPANN; Chen et al., NeurIPS 2021). Inserts append to the nearest centroid’s posting list; deletes mark a per-index deletion set; and local split / merge / reassign rebalancing keeps posting lists balanced as the distribution drifts, maintaining the invariant that each vector sits in its nearest centroid’s list — which is what preserves recall — without a global rebuild. The first increment (v0.4.0) kept the index in memory and derived, so the kill -9 crash gate (ADR-0005) was untouched by construction. v0.6.0 then made the IVF index durable: it is snapshotted at checkpoint, referenced by the manifest under the same atomic swap as the segments, and recovered on open by loading the snapshot and replaying only the post-checkpoint WAL tail instead of rebuilding — with the crash gate extended to cover it (ADR-0025). v0.13.0 closes the last gap with FreshDiskANN’s StreamingMerge for the graph family (Vamana / DiskVamana; Singh et al., 2021 — a different algorithm than LIRE): the batch-built graph becomes a read-only base, recent inserts land in a small in-memory delta graph (Vamana::insert) searched alongside it, deletes are O(1) tombstones filtered with live-fraction beam widening, and consolidation is a derived rebuild from the store once pending work passes a churn threshold — so the index stays in memory and derived, the on-disk artifact keeps its write-once contract, and the crash gate is untouched by construction (ADR-0033). The decisions and full scope are in ADR-0023, ADR-0025, and ADR-0033.

Multi-vector / late interaction (Phase 4 — ADR-0028)

Single-vector retrieval pools a document into one embedding; late-interaction models (ColBERT) keep a document as a set of token embeddings and score a query — also a set — by MaxSim: each query token takes its best-matching document token, and the maxima are summed. It is stronger out of domain, at the cost of storing 100–200 vectors per document — the large, low-dimensional pool that Quiver’s PQ and disk-resident index were built to compress, so late interaction showcases the memory-frugality wedge rather than straining it.

Quiver models a multi-vector document as a group of ordinary rows — one row per token vector — over the existing row-addressed store (ADR-0020), with no on-disk format change, so the kill -9 crash gate stays untouched by construction. The token pool is the set the collection’s ANN index serves, so candidate generation is a normal nearest-neighbour search (the PLAID shape): for each query token, find its nearest token rows, union their parent documents, then re-rank those candidates by the full MaxSim and apply the document-level Filter. Document grouping (doc-id → token rows) is derived in memory on open, like the existing id maps; the store stays the single source of truth. Late interaction requires a similarity metric (Cosine or Dot); the token pool compresses under the same IVF+PQ / disk path as any collection, with exact vectors read for the re-rank. The decision and full scope are in ADR-0028.

v0.14.0 takes two of ADR-0028’s three deferred follow-ups (ADR-0034). Incremental maintenance: document upsert/delete now dispatch to the token-pool index incrementally through the same per-point insert/delete path single-vector collections use, instead of marking the collection stale for a full rebuild — so a document write is size-independent, closing the last write-then-rebuild path. ColBERTv2 / PLAID compression: an opt-in colbert index holds coarse kmeans centroids plus per-token (centroid id, PQ residual code) in RAM (residuals trained under L2 so reconstruction is faithful; the collection metric is applied only at scoring) and prunes candidate generation by scoring centroids first — the exact token vectors stay on the encrypted store for the MaxSim re-rank. Both stay in memory and derived (rebuilt from the store on open), so neither changes the on-disk format or the crash gate. The third follow-up — native variable-stride document rows — is deferred: its benefit is storage locality / id-space only (candidate generation still needs the token-pool index, so it removes no work), and ADR-0034 gates the on-disk change on a measured locality win that is owner-reference-hardware-only, so it is not shipped on faith.

References

1. Malkov, Yashunin. Efficient and robust ANN search using HNSW graphs. IEEE TPAMI, 2020.
2. Subramanya et al. DiskANN: Fast, accurate billion-point NN search on a single node. NeurIPS, 2019.
3. Chen et al. SPANN: Highly-efficient billion-scale ANN search. NeurIPS, 2021.
4. Jégou, Douze, Schmid. Product quantization for nearest neighbor search. IEEE TPAMI, 2011.
5. Xu et al. SpFresh: Incremental in-place update for billion-scale vector search. SOSP, 2023.
6. Gollapudi et al. Filtered-DiskANN. WWW, 2023. · Patel et al. ACORN. SIGMOD, 2024.
7. Singh et al. FreshDiskANN: A fast and accurate graph-based ANN index for streaming similarity search. 2021.
8. Khattab, Zaharia. ColBERT: Efficient and effective passage search via contextualized late interaction over BERT. SIGIR, 2020. · Santhanam et al. ColBERTv2 (NAACL 2022) · PLAID (CIKM 2022).