# Rust database architecture: one key per value in RushDB 3

> Inside the Rust database architecture of RushDB 3: one ordered key per property value, a catalog derived on every commit, a WAL-first write path, and its costs.

Canonical URL: https://rushdb.com/blog/lmpg-rust-architecture-deep-dive

Updated: 2026-11-11T20:44:28.469Z
Author: RushDB
Category: Engineering

RushDB 3 is a single-process Rust database, and its architecture rests on one idea: every property value of every record is its own ordered key in an embedded B-tree (redb). A pure function derives counters, value dictionaries and presence rows from each commit, in the same batch, so the schema catalog is exact at every snapshot. Writes are WAL-first with group commit through one logical writer, which caps single-record commits but keeps the catalog and the data in lockstep.

The reasons for building it instead of staying on Neo4j are in [Time to move on: why RushDB took the hard path off Neo4j](https://rushdb.com/blog/time-to-move-on-from-neo4j).

## TL;DR

- The Labeled Meta-Property Graph (LMPG) layout stores one key per property value, called an occurrence, so a record is a contiguous key range.
- Counts and value dictionaries are derived rows from a pure `Deriver`; they are never logged and never enter a conflict set.
- Writes pass one admission lock and a sequencer overlay, so commit N+1 plans before N is durable, and each group shares one fsync.
- Reads run on pinned MVCC snapshots, and the planner intersects ordinal bitmaps most-selective-first.
- The price is about 1,015 single-record commits/s in one tenant with 32 writers, ~2.5 KB/record on disk, and slow candidate-heavy reads at 30M records.

## Why store one key per property value?

A document store keeps each record as a blob. LMPG goes the other way: every property value of every record or relationship is its own key, and keys are ordered so that related keys sit next to each other ([LMPG layout](https://docs.rushdb.com/engine/architecture/lmpg-layout)).

| Concern | Document layout | Occurrence layout |
|---|---|---|
| Update one property | Rewrite the whole document | Write one key |
| Find owners of a property | Scan, or keep a separate index | Scan the presence rows of that label and property |
| Mixed types under one name | Discovered at read time | Each value typed when written; types live side by side |
| Counts and statistics | Scan, or maintain by hand | Derived on every commit |
| Read a whole record | One read | One ordered prefix scan |

The manual states the trade as a larger key fan-out per record, in exchange for property-grained writes, exact counts, and planner statistics that come from the data. In our 10-field fixture that fan-out is about 28 rows and ~700 bytes of live layout per record (storage format 5).

In LMPG, properties are first-class: each one is a typed definition shared by every record that uses it, so schema discovery, value ranges and facets fall out of the storage layout instead of a separate system that drifts.

## What does the keyspace look like?

Every key starts with a namespace byte: `0x00` for system rows, `0x01` plus a 4-byte big-endian tenant ordinal for tenant rows. Tenant isolation comes from that 5-byte prefix. A tenant is one contiguous range, a scan cannot cross tenants, and purging one is a range delete.

Inside a tenant, hot rows use typed families: one family byte, then fixed fields. Integers inside keys (record ordinals, property ids) use an order-preserving varint, one length byte plus minimal big-endian bytes, so byte order equals numeric order and small numbers take 1–4 bytes instead of 8.

| Family | Key after the tenant prefix | Value | Kind |
|---|---|---|---|
| Record id | `0x03 ‖ public id (16 B)` | ordinal | base |
| Record header | `0x04 ‖ ordinal` | `public id ‖ label` | base |
| Label membership | `0x05 ‖ label ‖ ordinal` | empty | base |
| Counter | `0x09 ‖ sub-family ‖ fields` | count | derived |
| Value dictionary | `0x0A ‖ kind ‖ label ‖ pid ‖ type tag ‖ value` | refcount | derived |
| Occurrence | `0x12 ‖ kind ‖ owner ordinal ‖ pid ‖ element` | `flags ‖ state/type ‖ value` | base |
| Presence | `0x13 ‖ kind ‖ label ‖ pid ‖ nullness ‖ owner ordinal` | empty | derived |

`kind` is `r` for a record owner and `e` for a relationship owner. Colder rows (property catalog, relationship headers, adjacency `adj/out/<node>/<type>/<other>/<rel>` and `adj/in/…`, embeddings) use `/`-separated segment families.

A record has a 16-byte UUID public id and a dense per-tenant ordinal that every other row refers to. Dense ordinals are what make bitmap intersection cheap in the planner.

```mermaid
flowchart TD
  J["One PERSON record<br/>name, born"] --> base
  subgraph base["Base rows, written"]
    ID["0x03 record id"]
    H["0x04 record header"]
    LM["0x05 label membership"]
    O["0x12 occurrences: name, born"]
  end
  subgraph derived["Derived rows, same commit"]
    PR["0x13 presence"]
    VD["0x0A value dictionary"]
    C["0x09 counters"]
  end
  base -.->|"derived on commit"| derived
```

### Families, definitions, occurrences

A **family** is one normalized name per owner kind: ASCII lower-cased, other non-alphanumerics mapped to `_`, so `FirstName` and `firstname` share one.

A **definition** is a family at one type (`boolean`, `int64`, `float64`, `utf8`, `datetime` as UTC milliseconds), with its own property id, the pid. If one service writes `amount` as a number and another as text, the family gets two definitions. No write is rejected for a type mismatch, and the catalog shows both.

An **occurrence** is `(owner kind, owner ordinal, pid, element)`, one per array element. Values use an order-preserving encoding (integers with a sign flip, floats with a total-order transform), so a range predicate is a byte-range read.

Because the key is `owner ‖ pid ‖ element`, one record is one contiguous range. Reconstruction reads the header by ordinal, prefix-scans `0x12 ‖ r ‖ ordinal`, resolves each pid through a per-session cache and folds elements into scalars or arrays.

The read boundary is a fallible trait, and the infallible version was deliberately never written.

```rust
/// Fallible storage boundary for admission and reads. Txn deliberately does
/// not implement an infallible counterpart, so a disk error cannot become a
/// missing record.
pub trait TryRead {
    fn get(&self, k: &[u8]) -> Result<Option<Vec<u8>>, rushdb_storage::StorageError>;
    // …
}
```

Source: [`crates/rushdb-lmpg/src/reader.rs`](https://github.com/rush-db/rushdb/blob/v3.0.8/crates/rushdb-lmpg/src/reader.rs), abridged. When one record is many keys, "not found" and "unreadable" must never collapse into the same `None`. The graph-language adapter follows the same rule, so a storage error rejects the statement instead of returning an empty result.

## How is the catalog maintained on write?

RushDB splits rows into **base** rows (headers, label membership, occurrences, adjacency, the property catalog, index definitions, pending text changes) and **derived** rows (presence, value dictionary, counters, array markers, declared-index entries). Base rows are what commits write and the WAL logs. Derived rows are a function of base rows ([derived state](https://docs.rushdb.com/engine/architecture/derived-state)).

That function is a trait with an unusually strict contract:

```rust
/// Implementations must be pure functions of `(ci, base_ops, before)`: no
/// clock, randomness, or global state, because replay and replicas call the
/// same function and must reach byte-identical state.
pub trait Deriver: Send + Sync {
    fn derive(
        &self,
        ci: u64,
        base_ops: &[Op],
        before: &dyn DeriveRead,
    ) -> Result<Vec<Op>, StorageError>;
    // …
}
```

Source: [`crates/rushdb-storage/src/derive.rs`](https://github.com/rush-db/rushdb/blob/v3.0.8/crates/rushdb-storage/src/derive.rs), abridged. The deriver returns final values, not deltas, and its output is written in the same backend batch and at the same commit index as the base rows. A reader can never see a record without its counter bump.

**Derived rows are never logged.** Live publication, crash recovery, point-in-time restore, replication followers and transaction overlays all run the same deriver over the same base log.

**Derived rows never enter a write set.** Two transactions that both increment the `Person` record counter do not conflict. Without that rule, every record created in a label would conflict with every other one.

**Counts are exact, not eventually consistent.** "How many `Person` records carry `email`" is a counter read at the reader's snapshot. Estimates exist only to choose plans.

Counters are rewritten on almost every commit, which collides with MVCC history. The storage op set has a dedicated variant for that.

```rust
pub enum Op {
    Put(Vec<u8>, Vec<u8>),
    Del(Vec<u8>),
    /// Overwrite a key **without** retaining a superseded version […]
    /// Without this, every overwrite of a hot counter rewrites its whole
    /// history vector, which is quadratic in the number of writes.
    Set(Vec<u8>, Vec<u8>),
    Purge(Vec<u8>),
}
```

Source: [`crates/rushdb-storage/src/lib.rs`](https://github.com/rush-db/rushdb/blob/v3.0.8/crates/rushdb-storage/src/lib.rs), abridged.

The value dictionary maps `(kind, label, pid, value)` to a refcount, so `propertyValues` and distinct counts read the dictionary, not records. Values whose encoding exceeds 96 bytes (`DICT_MAX_VALUE_BYTES`) stay out of it. For those, storage format 6 keeps a refcount per value digest (16 bytes of SHA-256) and a distinct-long-values counter, so a column of long text still has an exact distinct count at no scan cost.

Planner statistics are not maintained per write. On a miss, the planner walks the value dictionary under a budget and caches the distribution (LRU, 32 MiB default).

Since derived state is a pure function, it is checkable. `rushdb serve --data-dir <dir> --verify` runs a scrubber that recomputes every derived row from scratch and diffs it against what is stored. In our benchmark harness, a churn test ran 3 seeds × 20,000 randomized operations (creates, merges, type changes, deletes, links, committed and rolled-back transactions) and compared the catalog with an in-memory model and a full recount at 60 checkpoints. It found zero mismatches.

## What happens on a write?

One constraint shapes the write path. Planning commit N+1 must observe everything commit N wrote, including new property definitions. So planning is serialized, and the job is to keep that from serializing fsyncs too ([write path](https://docs.rushdb.com/engine/architecture/write-path)).

```mermaid
sequenceDiagram
    participant W as Writer thread
    participant A as Admission lock
    participant S as Sequencer overlay
    participant P as Publisher
    participant L as WAL
    participant R as redb
    W->>A: FIFO ticket, then lock
    W->>S: plan against committed state + in-flight commits
    W->>W: expand to Put/Del/Set/Purge, reserve index (CAS)
    W->>A: release before waiting for durability
    W->>P: try to become publisher
    P->>P: derive each commit against the state before it
    P->>L: append group, one fsync
    P->>R: apply base + derived rows, durability None
    P-->>W: advance watermark, acknowledge group
```

**Admission.** One mutex per node, with a FIFO ticket gate in front (`FairGate`), because a plain mutex doesn't hand off in arrival order. Admission first checks the commit key's retry receipt (kept 24 hours), so a retried commit returns its recorded outcome without running again.

**The sequencer overlay.** Waiting for each predecessor's fsync would cap throughput at one commit per fsync. Instead the planner reads a fresh snapshot layered with the net key effects of every commit that has an index but isn't published yet. The overlay holds only distinct in-flight keys and opens no long-lived read pin, so it never blocks garbage collection.

**Dense indexes.** The commit index is reserved by compare-and-swap only after expansion succeeds and passes the size check. A failed or oversized expansion never burns an index, so the sequence has no holes and the WAL LSN equals the commit index.

**Group commit.** The writer releases admission before waiting for durability, then tries to become the publisher. The publisher drains contiguous commits from `published + 1`, derives each, appends the group to the WAL with one fsync, and applies it to redb in one write transaction per shard with durability `None`. It publishes only up to its own commit, then hands off.

**WAL format.** Records carry a 32-byte header with a CRC32C in 64 MiB segments. Each record holds both the expanded ops (for replay and PITR without planning) and the originating command batch, so a follower can re-expand it.

**Fencing.** If a WAL append, fsync or apply fails, the outcome on disk is uncertain. The publisher fails the group and every queued commit and refuses all writes until restart; `/ready` reports `durable publisher failed`.

Why not one redb transaction per commit? Every commit would pay a copy-on-write B-tree commit plus its fsync. Splitting durability (sequential WAL append) from materialization (buffered apply, flushed at the 5-second checkpoint) gives one recovery story, because whatever redb lost is in the WAL past the last checkpoint.

## How does MVCC work on top of redb?

MVCC in RushDB pins one redb read transaction per shard at a commit index, and keeps older row versions in a history table only while a reader can still see them, so readers never block writers.

A read view is a pinned snapshot at commit index S. It holds one native redb read transaction per shard (which pins redb's physical pages), a registered pin with a lease, a cancellation handle and the deriver ([MVCC and snapshots](https://docs.rushdb.com/engine/architecture/mvcc-and-snapshots)).

Each current row carries the commit index that wrote it. Older versions are `VersionEntry { from_ci, to_ci, value }` covering half-open ranges in a `history` table. In the common case of a single shard and a view at the latest commit, redb's own snapshot already is the state at S and the engine reads the current table directly.

History is kept only while someone can read it. The GC floor is `max(previous floor, min(committed, oldest pinned))`, and an abandoned reader is cancelled after its 65 s lease. There is no "as of commit N" query.

Interactive transactions get snapshot isolation, equivalent to PostgreSQL `REPEATABLE READ`. First committer wins against write sets kept in a 64 MiB conflict window, with no lock manager and no deadlock detection. Write skew is permitted. Record and relationship ids are reserved at staging from one store-wide allocator (since 3.0.5), so transactions that only create records don't conflict with each other. Native autocommit mutations plan under admission against the latest state, so they never see `write_conflict` at all.

## How does the planner pick candidates?

The planner answers the conditions it can from maintained structures (counters, value dictionaries, presence rows, declared indexes), most selective first, as compressed bitmaps of record ordinals. Conditions it cannot answer that way run only on the candidates that survive the intersection.

The native planner flattens the top-level `$and` into conjuncts and sorts them into two bins ([query execution](https://docs.rushdb.com/engine/architecture/query-execution)):

- **Eligible** leaves can be answered from maintained structures: equality and `$in`, `$exists: true`, null checks, numeric ranges, `$id`.
- **Residual** leaves can't: `$ne`, string matching, `$type`, nested logic, relationship predicates. They run on whatever candidates survive.

Each eligible leaf gets an estimate from counters and the value dictionary and is materialized most-selective-first into a set of owner ordinals:

```rust
/// A set of owner ordinals. Ordinals are allocated densely per tenant, so a
/// compressed bitmap holds a million owners in ~128 KiB and intersects them
/// word by word.
pub(crate) type OwnerSet = roaring::RoaringTreemap;
```

Source: [`crates/rushdb-query/src/planner.rs`](https://github.com/rush-db/rushdb/blob/v3.0.8/crates/rushdb-query/src/planner.rs). The access path per leaf is a `Ready` declared ordered index if one exists, else presence narrowing (walk the owners of label × property and check values), else a full scan in bounded batches when nothing is eligible or the best unindexed leaf would materialize more than 2 million owners (`PLANNER_MATERIALIZE_CAP`, see [query execution](https://docs.rushdb.com/engine/architecture/query-execution)). Index-answered leaves are never capped.

Every index candidate is re-checked, and index-assisted results are differentially tested against forced full scans, so a query returns the same rows with or without an index. Pages are reconstructed only after ordering and pagination, so a `limit 20` query decodes 20 records.

There are no automatic value indexes. An ordered index is one label plus one property, declared by you and built online in 250 ms slices. Composite indexes don't exist yet.

SQL runs on Apache DataFusion with labels as tables, relationship types as tables in `rushdb_edges`, and streaming scan providers. GQL, openCypher, Gremlin and SQL/PGQ run on Grafeo through a read-only adapter over the pinned view; their writes go to a copy-on-write overlay holding only touched records, refused above 100,000 of them or 64 MiB.

## Which Rust crates make up the database?

RushDB 3 is a Cargo workspace. Its main crates split the database into types, storage, the LMPG layer, query planning, SQL, graph languages, vectors, the protocol and the server binary. Only `rushdb-server` is a product crate; the rest are internal ("No stable API; install rushdb-server instead").

| Crate | Role |
|---|---|
| `rushdb-types` | ids, value types, order-preserving encoding, commit batches, key constructors |
| `rushdb-storage` | admission, sequencer, group commit, WAL, redb backend, MVCC views, retention, receipts |
| `rushdb-lmpg` | mutation planning, expansion, derivation, index maintenance, reconstruction, scrubber |
| `rushdb-query` | native query parsing, access-path planning, traversal, aggregation, planner stats |
| `rushdb-sql` | SQL over DataFusion 54.1.0 |
| `rushdb-language` | GQL, openCypher, Gremlin, SQL/PGQ over Grafeo 0.5.42 |
| `rushdb-vector` | embedding spaces, exact search, segmented ANN cache over usearch |
| `rushdb-protocol` | versioned envelope and error taxonomy |
| `rushdb-server` | the `rushdb` binary: config, transports, executor, workers, replication, backup |

The LMPG layout, expansion, derivation, planner, tenancy and authorization are RushDB's own code. Storage ([redb](https://github.com/cberner/redb)), SQL ([DataFusion](https://github.com/apache/datafusion)), graph languages ([Grafeo](https://github.com/GrafeoDB/grafeo)), BM25 ([Tantivy](https://github.com/quickwit-oss/tantivy)) and ANN ([USearch](https://github.com/unum-cloud/USearch)) are adopted.

The backend sits behind a `pub(crate) trait StorageBackend`, so redb could be replaced without touching LMPG, query or search. Today redb and an in-memory backend are the only implementations.

Thin LTO with one codegen unit shrank the binary from 204 to 130 MB and made 32-client filtered reads ~11% faster (measured 2026-10-19).

Async stops at the transport. Tokio accepts and authenticates HTTP requests, then hands them to a bounded pool of plain `std::thread` workers (2–256 threads, 32 queued per worker); a full queue answers HTTP 503 instead of waiting. Graph statements run on a dedicated thread with a 256 MiB stack, because Grafeo plans recursively and a 500-clause `CREATE` script once overflowed an ordinary worker stack.

## What does this design cost?

The design costs write throughput, disk space and broad-read latency at scale. One logical writer caps single-record commits at about 1,015 per second in one tenant with 32 writers (114 with one writer), records take about 2.5 KB on disk, and candidate-heavy reads at 30M records take seconds ([capacity planning](https://docs.rushdb.com/engine/operations/capacity-planning)).

Every number here: one `rushdb serve` node, i9-12900H (20 threads), LUKS NVMe, Linux, warm page cache, 10-field records, October 2026, storage format 5; 3.0 writes format 6 ([capacity planning](https://docs.rushdb.com/engine/operations/capacity-planning)). None is a cross-vendor comparison.

| Cost | Measured |
|---|---|
| One publisher for the whole node | ~1,015 single-record commits/s in one tenant at 32 writers; 820–890/s over 50 tenants |
| Per publish group (~10 commits) | 6.6 ms WAL append + fsync, 2.7–5.0 ms apply, ~0.5 ms derive, serially |
| Bulk ingest | 12,600 records/s at 200K (8 writers, 500-doc batches); 4,760 records/s at 30M |
| Per 500-doc commit at 30M | 169 ms durable: 49 ms apply, 32 ms expand, 32 ms derive, 13 ms WAL sync |
| Disk | 2.47 KB/record at 200K including WAL; 3.44 KiB/record at 30M; redb pages ~40–50% full, no compression |
| Value dictionary | 12% of ingest throughput on a near-unique-property fixture |
| Filters without an index | ~5.6× slower than with one at 4K records per label |
| Reads at 30M (32 clients, `status ∧ city`) | p50 15.0 s, p99 23.2 s; CPU-bound, 0 bytes read from storage once warm |
| Broad filtered facets at 30M | 457 s (properties), 483 s (schema) |
| Offline compaction at 10M | 27.6 min for 28.5 GB, holding writes the whole time |

**The single logical writer is an accepted ceiling.** Batching is the answer (bulk ingest gets ~12× the single-record commit rate), and why we chose one writer is the subject of Single writer by design .

**Derivation cost grows with the store.** It takes half a millisecond per group at 200K; at 30M, deriving a 500-document commit costs as much as expanding it.

**The fan-out shows up on disk.** ~700 B of live layout per record becomes ~2.5 KB allocated ([disk sizing](https://docs.rushdb.com/engine/operations/capacity-planning)), mostly half-empty B-tree pages, because tenants growing side by side in key order meet redb's 50/50 page split. RocksDB was shortlisted to fix that. A RocksDB backend used less disk, but it was slower on ingest and reads, so we kept redb (the FAQ has why).

**Exact counts under a filter are linear in the match set.** Unfiltered catalog reads come from counters (labels at 1M records: 0.4 ms). A filtered facet visits every match, and at 30M a broad one takes minutes. Candidate-heavy reads cost 5–20× more for 3× the records in those pre-release runs; 3.0.1 removed a cost quadratic in tenant size from building an indexed filter's match set, and the 30M scenario has not been re-measured since. The engine is not qualified past 30M records per node ([measured envelope](https://docs.rushdb.com/engine/operations/capacity-planning)).

**Some things 3.0 doesn't do yet.** A record has one primary label (multi-label `CREATE` fails), there are no client-chosen snapshots and no composite indexes, and Raft is only an in-process preview. Native `records` queries page with cursors (pages up to 10,000), but statement languages (SQL, Cypher, GQL, Gremlin) return fully materialized results with no server-side cursors.

## Would we make the same trade again?

For a database whose job is to tell an agent or an application exactly which fields, types and values exist under the current filter, yes. The occurrence layout plus a pure deriver makes the catalog a by-product of committing. The costs are measured, and most of them sit on the write and disk side.

For a stable schema at hundreds of millions of rows, a relational engine or a warehouse fits better. The [release notes](https://rushdb.com/blog/rushdb-3-0-release-notes) list what 3.0 doesn't do yet, the [2.x vs 3.0 guide](https://rushdb.com/blog/rushdb-3-vs-2-upgrade-guide) covers the move off Neo4j, and the [features page](https://rushdb.com/features) shows these layers from the user's side.

## FAQ

### How is a graph stored on disk in RushDB 3?

As ordered keys in an embedded redb B-tree. Each property value of each record or relationship is one key, `owner ordinal ‖ property id ‖ element`, so a record is a contiguous range. Adjacency is stored in both directions as `adj/out/…` and `adj/in/…` rows, so traversal either way is a prefix scan.

### What happens to the catalog after a crash?

Recovery replays the WAL past the last checkpoint through the same deriver, so counters and dictionaries are recomputed from base rows and come back exact. Nothing is rebuilt from scratch at boot: in our capacity runs `/ready` answered 0.07 s after a `kill -9` at 1M records.

### Why redb and not RocksDB?

Because of the access pattern. RocksDB was on the shortlist to fix disk usage, but LMPG issues many short prefix scans per query and many seeks and point gets per ingested record. Each of those is one B-tree descent in redb but a multi-source LSM seek in RocksDB, so the RocksDB backend saved disk and lost on ingest and read speed.

## Sources

- [LMPG layout (engine manual)](https://docs.rushdb.com/engine/architecture/lmpg-layout)
- [Derived state](https://docs.rushdb.com/engine/architecture/derived-state)
- [Write path](https://docs.rushdb.com/engine/architecture/write-path)
- [MVCC and snapshots](https://docs.rushdb.com/engine/architecture/mvcc-and-snapshots)
- [Query execution](https://docs.rushdb.com/engine/architecture/query-execution)
- [Architecture overview and crate map](https://docs.rushdb.com/engine/architecture/overview)
- [Capacity planning](https://docs.rushdb.com/engine/operations/capacity-planning)
- [redb](https://github.com/cberner/redb)
- [Apache DataFusion](https://github.com/apache/datafusion)
- [Grafeo](https://github.com/GrafeoDB/grafeo)
- [Tantivy](https://github.com/quickwit-oss/tantivy)
- [USearch](https://github.com/unum-cloud/USearch)
- [RushDB on GitHub](https://github.com/rush-db/rushdb)