Frédéric Meyer

Posted on Jul 13 Originally published at github.com

ArborDb: a Rust document store where reading one field doesn't get slower as the record grows

#rust #database #performance #showdev

Most embedded document stores make you pay the same price to read one field as to read the whole record: they deserialize the entire value, then hand you the field you asked for. That cost grows with the record. Read one number out of a 128-field document, or one element out of a 10 000-element list, and you've just decoded all of it.

ArborDb is a pure-Rust, typed, transactional, indexed document store built around the opposite idea: store each value as one zero-copy blob and read a field in place, without touching the rest.

It's the 1.0 successor to StratoDb — same typed model and derive surface, a completely different storage strategy.

The core idea: one blob per value, navigated in place

A value in ArborDb is a tree of objects, lists, and scalar leaves. Instead of shredding each scalar into its own keyed row (StratoDb's old approach), ArborDb serializes the whole tree into a single blob in a single engine entry, laid out with offset tables:

a leaf is its scalar's byte encoding;
a list is a count plus a u32 offset table — O(1) jump to element i;
an object is a count plus a name-sorted (name, offset) table — O(log n) field lookup.

A bespoke codec — think "rkyv, but hand-written for this layout" — reads scalars straight out of the engine's page bytes. No decode into an owned tree, no alignment requirement (every read is an explicit from_be_bytes over an unaligned slice). It's layered over the redb key-value engine, which is kept fully opaque: no engine type ever appears in ArborDb's public API.

The payoff is the headline benchmark below. But first, what it feels like to use.

Quick start

use std::collections::BTreeMap;
use arbordb::{data::Scalar, ArborDb, Value};

fn main() -> arbordb::AdbResult<()> {
    let db = ArborDb::create_in_memory()?;      // or ArborDb::create(path) for a file
    let users = db.open_table("users")?;

    // Writes are transactional: stage, then commit.
    let w = users.write()?;
    w.store_value(
        "alice",
        &Value::Node(BTreeMap::from([
            (String::from("age"), Value::Leaf(Scalar::I64(30))),
        ])),
    )?;
    w.commit()?;

    // Reads see committed data; a field is reached by its intra-value path.
    let r = users.read()?;
    assert_eq!(r.get_as::<i64>("alice", "age")?, Some(30));
    Ok(())
}

Typed access with `#[derive(AData)]`

The dynamic Value API is always there, but with the derive feature you get typed storage with a Serde-style attribute set (rename, skip, default, with, from/into/try_from, enum representations, generics, flatten):

use arbordb::{AData, ArborDb};

#[derive(AData, Debug, PartialEq)]
struct User {
    name: String,
    age:  u32,
}

fn main() -> arbordb::AdbResult<()> {
    let db = ArborDb::create_in_memory()?;
    let users = db.open_table("users")?;

    let w = users.write()?;
    w.store::<User>("alice", &User { name: String::from("Alice"), age: 30 })?;
    w.commit()?;

    let r = users.read()?;
    assert_eq!(
        r.load::<User>("alice")?,
        Some(User { name: String::from("Alice"), age: 30 }),
    );
    Ok(())
}

The derive also generates lazy accessors — ArborUser<'_> / ArborUserMut<'_> — that navigate into the one blob without a full decode, so you can read (or patch) a single nested field of a large typed value.

A table is a virtual filesystem

This is the part that makes ArborDb feel different. A table isn't a flat keyspace — it's a tree of directories and files, and the filesystem operations sit right next to the value operations:

let w = table.write()?;
w.store_value("users/alice", &user("Alice", 30))?;
w.store_value("users/bob",   &user("Bob", 40))?;
w.mv("users/bob", "users/robert")?;      // relink a name: O(1), identity preserved
w.cp("users/alice", "archive/alice")?;   // deep copy under fresh keys
w.commit()?;

let r = table.read()?;
for entry in r.ls("users")? {
    println!("{}", entry.name());
}

Every node carries an opaque 16-byte AKey that survives renames and moves — mv relinks a name in O(1) and the key doesn't change. That's the reason for the two distinct path kinds:

an APath (users/alice) addresses a whole value in the filesystem — resolved by walking directories from the root, amortized by a per-table cache;
a VPath (home/city, tags[2]) navigates inside a value down to a scalar leaf, read zero-copy over the blob.

Access paths are never persisted, so a value's identity follows its key, not its location.

Secondary indexes

Declare them on the type, register with one call, and they're back-filled and maintained on write:

#[derive(AData)]
#[arbor(index(name = "by_age", columns(age)))]
struct User {
    name: String,
    age:  i64,
}

users.create_indexes::<User>("users/*")?;   // create + back-fill, scoped to a path pattern

// Query in index order; an empty prefix matches all.
let r = users.read()?;
let ages: Vec<i64> = r.find::<User>("by_age", &[])?.into_iter().map(|u| u.age).collect();

Indexes are named, composite (ordered columns), per-column ASC/DESC, optionally unique, and scoped to a path pattern. The key encoding is order-preserving across types, byte lengths and sign, so a prefix on a composite index returns every match ordered by the trailing columns, and reversing a query walks the index backward.

The headline: partial reads don't scale with the value

This is the whole point of the design. Because a value is one blob with offset tables, reaching one field or one list element is a jump straight to it — so ArborDb stays flat as the value grows, while a decode-the-whole-blob store grows linearly.

Read one field of an N-field record (on-disk):

Fields in record	ArborDb	redb + bincode	StratoDb
8	375 ns	826 ns	1.63 µs
32	1.43 µs	3.55 µs	2.96 µs
128	1.40 µs	12.1 µs	3.22 µs

Read one element of an N-element list (on-disk):

List length	ArborDb	StratoDb	redb + bincode
256	374 ns	1.91 µs	9.56 µs
1 024	1.36 µs	4.11 µs	74.0 µs
10 240	1.38 µs	9.82 µs	714 µs

ArborDb's cost is essentially constant across a 40× range of data: 8.6× ahead at 128 fields, and over 500× ahead at 10 240 list elements.

And on the "read + full decode" path — where nothing is skipped — ArborDb rides within ~4 % of the raw engine it's built on (693 ns vs redb+bincode's 665 ns), while beating native_db by 1.9× and StratoDb by 1.7×.

Being honest about the tradeoffs

Fast partial reads aren't a free lunch, and the benchmarks page says so:

Partial writes are conditional. Overwriting a scalar with one of the same byte width patches the blob in place — no decode, no re-encode (that's what puts update_score ahead of every other typed store). But a variable-width or structural edit re-encodes the one blob. Updating one element of a huge packed list trades write cost for the read speed above. A deliberate tradeoff, not magic.
Bulk insert under one directory is ~O(N²) by design. Inserting N files into one directory re-links each into that directory's (growing) blob. It's a real property of the filesystem model — measured, not hidden.

Numbers are indicative medians from a single machine; treat the ratios and the scaling shape (flat vs linear) as the durable signal.

What else is in the box

All opt-in via cargo features, nothing on by default:

JSON / YAML export — a hand-written, dependency-free, read-only renderer (no serde_json/serde_yaml), for a stored value or an in-memory subtree.
Entry timestamps — POSIX-style created/modified/accessed per node, stored out-of-band so the data format is unchanged and access times are buffered (a read burst never becomes a write burst).
Permissions & integrity — user/password auth (Argon2id + XChaCha20-Poly1305; passwords are never stored), per-node graded ACLs (None ⊂ Access ⊂ Modify ⊂ Delete), and dual tamper detection — a keyed BLAKE3 MAC for authenticated users plus an Ed25519 signature a keyless guest can verify — so an edit that bypasses ArborDb to touch the raw file is caught.
Rooted views — make every path relative to a fixed root and scope index queries to that subtree.
Big numbers — arbitrary-precision int / fixed-precision float / rational, each as a native scalar or as composite data, with correct index ordering.
serde and parallel (rayon) features too.

Status & trying it

ArborDb is at its 1.0 milestone: feature-complete, with a stable public API and on-disk format, runnable examples, a criterion benchmark suite, and CI. It's not yet on crates.io, so depend on it by git for now:

[dependencies]
arbordb = { version = "1.0.0", features = ["derive"] }

Builds on a recent stable toolchain (edition 2024).

👉 Repo: https://github.com/corebreaker/arbordb

If the "one blob, read in place" model is interesting to you — or if you have a workload where partial reads dominate — I'd love feedback, issues, and stars. What would you want to see before it lands on crates.io?

Top comments (4)

Mads Hansen • Jul 14

This is a good reminder that document stores are not one performance shape.

A lot of teams treat “document database” as if the unit of access is always the whole object. That is fine for some workloads, but it gets expensive when records grow and callers only need one field.

The interesting design question is not just storage layout. It is whether the database can keep these properties obvious to the user:

what is cheap to read
what gets rewritten on update
where indexes duplicate data
how partial reads behave under compression
whether schema drift changes the access pattern

That last point matters because document models usually evolve quietly. A design that keeps single-field reads predictable as documents grow solves a very real operational problem.

Frédéric Meyer • Oct 4

Thanks Mads, and sorry for the slow reply. That's the right question, and part of the answer lives in the API itself. Taking your list in order:

What's cheap to read. You can tell from the call. get_as("users/alice", "home/city") and the derived lazy accessors jump to one leaf through the offset tables (an O(1) jump per list index, a binary search over the sorted field names per object) and decode nothing else, while load::<T>() is the explicit "decode the whole value" call. Resolving the access path walks the directory tree, amortized by a per-table cache.
What gets rewritten on update. Always the whole value, since it's one engine entry. A same-width scalar overwrite skips the decode/re-encode (it's a byte splice), but the full blob still goes back to redb, which is copy-on-write: the saving is CPU, not I/O. Any other edit re-encodes the blob. Creating, removing or renaming a file also rewrites its parent directory's blob (a sorted name → key map), never its siblings, and mv doesn't touch the value at all.
Where indexes duplicate data. Only the indexed columns: an entry is index id · order-preserving encoded columns · 16-byte key (a unique index moves the key into the entry's value). There are no covering indexes, so a query is a range scan plus one value load per hit. On the write side, every mutation of a value within an index's scope deletes and re-inserts that value's entries, without diffing, even when the indexed column didn't change.
Compression. None today, and whole-value compression would work against the design: it's because the blob is stored as-is that a read can navigate its bytes without decoding anything, and compressing it would bring back exactly the "decode everything to read one field" cost. Compression that keeps partial reads would have to be granular, e.g. per leaf (a large string or byte leaf compressed on its own), so the offset tables stay navigable.
Schema drift. It doesn't change the access pattern. Fields are found by name, never by position, so adding, removing or reordering fields leaves every lookup the same; the price is that each blob carries its own field names, like BSON. A missing field reads as None through get. On the typed side, an Option<T> field loads as None, #[arbor(default)] fills the gap, #[arbor(alias = "old_name")] keeps a renamed field readable, and a required field with none of these fails with PathNotFound rather than quietly inventing a value. In an index, a missing column is indexed as Null (the lowest value), so older records stay in the index instead of silently dropping out.

Your list would make a good "cost model" section for the README. I may well borrow it.

Comment deleted