Demetrius Albuquerque

Posted on Jul 20

NyaruDB2: an embedded document database for Swift, built on Codable and actors

#swift #ios #database #opensource

Every iOS developer who has shipped a Core Data app knows the ritual. You open the visual model editor. You define an entity. You generate a class. You inherit from NSManagedObject. You learn about contexts, and then about the difference between the view context and a private context, and then about the merge policy you have to set because two contexts disagreed. You write a lightweight migration. It fails on a device you don't have.

Meanwhile, the thing you actually wanted to persist was this:

struct User: Codable {
    let id: String
    let name: String
    let city: String
    let age: Int
}

NyaruDB2 is an embedded document database that lets you persist exactly that. No base class, no schema file, no code generation, no migration ceremony. Your Codable structs go in, your Codable structs come out, and everything in between is async/await.

let db = try NyaruDB(path: url)

let users = try await db.collection(
    "users",
    of: User.self,
    options: CollectionOptions(
        idField: "id",
        partitionKey: "city",
        indexedFields: ["city", "age"]
    )
)

try await users.insert(User(id: "u1", name: "Ana", city: "São Paulo", age: 32))

let adults = try await users.find()
    .where("city", isEqualTo: "São Paulo")
    .where("age", isGreaterThanOrEqualTo: 18)
    .sort(by: "age")
    .limit(50)
    .execute()   // → [User]

That's the whole API surface for the common case. What I want to talk about in this post is what's underneath it — because "just use Codable" is easy to say and considerably harder to make fast and safe.

Status: NyaruDB2 is experimental. It works, it's tested, and it is not yet running in anyone's production app — including mine. I'm publishing the architecture because the design decisions are the interesting part, and because I'd rather have them torn apart in public than defend them alone.

The layers

The stack is four pieces, each with one job:

NyaruDB — the database handle. An actor that owns your collections.
NyaruCollection<T> — the only layer that knows what T is. It encodes your struct to bytes going in, and decodes bytes back into your struct coming out.
QueryBuilder<T> — fluent predicates, sort, limit.
CollectionCore — the engine underneath all three: an actor that owns the indexes, routes documents to shard files, and gates compaction.

There's one invariant here that shapes everything else: type erasure happens at the collection boundary. Below NyaruCollection<T>, nothing knows about User. The engine works on Data, and when it needs a single field out of a document — an id, an index key — it pulls that one field out of the encoded bytes without decoding the whole document.

That's why there's no base class. The engine doesn't need one.

Storage: slots, not an append log

A collection's data lives in shard files. Each shard is a flat sequence of slots, and each slot holds one record: a 16-byte header plus a payload.

Field	Size	Purpose
`capacity`	`u32`	Bytes reserved for the payload — rounded up to a multiple of 32
`payloadLength`	`u32`	Bytes actually used (`≤ capacity`)
`flags`	`u8`	Bit 0 = tombstone; bits 1–3 = compression method
reserved	3 B	keeps the header 16-byte aligned
`crc`	`u32`	CRC32 of the payload as stored

The gap between payloadLength and capacity is slack, and the slack is the entire trick.

An update is usually a single pwrite at the same offset. If the new version of the document fits the capacity already reserved — which the 32-byte padding is designed to make likely — the record doesn't move. The index pointer doesn't change. Nothing else has to be touched.

A delete is one byte. Set the tombstone bit in the flags, in place. The slot's (offset, capacity) then joins an in-memory free list kept sorted by capacity, so the next insert can binary-search it for a best fit and reuse the space.

Before reusing a free slot, the engine re-reads the header from disk and verifies that the capacity matches and the tombstone bit is genuinely set. If the disk disagrees with the free list, the slot is forgotten rather than overwritten. A stale entry in an in-memory structure can never clobber a live record on disk. This pattern — when in doubt, do nothing dangerous — shows up all over the engine, and I'll come back to it.

Reads are direct: a point read is one speculative pread of up to 4 KiB from the record's offset, so the header and (for typical documents) the entire payload arrive in a single syscall. Full scans stream the file through a 4 MiB sliding window, which means scanning a 2 GB collection uses 4 MB of memory, not 2 GB.

Partitioning: your data's natural shape becomes the file layout

Declare a partitionKey, and documents route to shard files by that field's value. A document with city: "São Paulo" and no encryption configured lands in SaoPaulo.nyaru. With an encryption key set, the filename is instead HMAC-SHA256(value, key) — something like a3f9…c1.nyaru.

Two things fall out of this.

First, a query filtered on the partition key reads exactly one file and ignores every other. Partitioning isn't a logical grouping — it's physical.

Second, notice the encryption branch. If your partition key is something like customer name or user id, then unencrypted shard filenames would leak those values through the filesystem even though the record contents are sealed. So when encryption is on, the filename is an HMAC of the partition value. The directory listing tells an attacker nothing.

(The corollary: partition on something with tens or hundreds of distinct values, not on the document id. One file per document is a misuse, and the engine won't stop you.)

Indexes: sorted arrays, and a trick for deletes

Every indexed field gets an OrderedIndex, held entirely in memory and persisted as a snapshot. It's two parallel sorted arrays:

keys:     [ "Belo Horizonte", "Curitiba",  "Rio",  "São Paulo" ]
postings: [ [p1, p7],         [],          [p3],   [p2, p4, p9] ]
                              ↑ dead slot

Lookups binary-search keys; the matching postings entry gives you the record pointers.

The interesting part is that empty slot. Removing a key from a sorted array shifts every element behind it — O(n) per removal. And it's worse than it sounds: deleting documents one by one tends to empty the corresponding key in the id index every time, and a FIFO deletion pattern empties position 0 repeatedly. That's the pathological case, hit over and over.

So when a posting list becomes empty, the key stays in the array as a dead slot — semantically absent, physically present — and the arrays get rebuilt in a single O(n) sweep only once dead slots exceed a quarter of the keys. Removal becomes amortised O(1).

The invariant every reader honours: postings[i].isEmpty means the key is absent. search and range are naturally correct (an empty list contributes nothing). contains and allKeys check explicitly. Bulk rebuilds drop dead slots for free, since they're rebuilding the arrays anyway.

Queries: the index answers, or it narrows

The planner runs once per execution. It flattens the top-level AND conjuncts, asks the engine in a single actor hop which of the referenced fields are indexed, and picks a strategy — in priority order: an index lookup on an indexed field (equality beats a set-membership check beats a range), then a single-file partition scan if the partition key has an equality predicate, then a full scan as the fallback.

Covered queries are the fast lane. A query counts as covered when exactly one top-level predicate exists and the index alone can answer it — no sort, or a sort on that same indexed field, ascending. Because the index alone answers the predicate, limit and offset are pushed into the index range scan — a .limit(10) over a range matching 100,000 documents stops collecting pointers after 10. It never reads the other 99,990.

Two more paths never touch the disk at all:

count() on a covered query counts pointers.
distinctValues(on:) over an indexed field enumerates the index keys directly.

And when records are read, the pointers get sorted by offset first. Index order is key order, which is random file order; sorting turns random seeks into a forward walk of the file. Sorted-and-limited queries run through a bounded top-K heap, so .sort(...).limit(10) over a huge candidate set keeps 10 items in memory, not all of them.

Concurrency: actors, not locks

There's one ShardActor per shard file, so writes to different partitions proceed genuinely in parallel and never contend. CollectionCore is a single actor because the indexes are shared mutable state — it's the serialization point for index maintenance, and the compiler enforces that, not a code review comment.

Crucially, CPU-bound work is pushed outside the actors. Encoding, CRC, compression, encryption, and decoding are pure functions over Data. They run across all cores through a parallel map while no actor is held. The actor protects the state; it doesn't get to hog the CPU.

The compaction gate

Compaction rewrites a shard file — which invalidates every offset stored in it — and then remaps the index pointers to the new offsets. The actor suspends at each await inside that operation, and that's a window. A concurrent get could read a stale offset against the already-rewritten file. A concurrent insert could register a pointer into the new file that the subsequent remap then discards as "stale."

Both are silent-wrong-answer bugs, which are the worst kind.

So every pointer-based operation brackets itself with beginPointerOp() / endPointerOp(), and compaction drains them all before touching a file. Scans don't take the gate — they walk the file for live records rather than following stored pointers, so a rewrite can't strand them.

Durability: the dirty flag, and what happens after a crash

Each shard file carries a dirty bit in its header.

The ordering is the whole design:

Setting the flag is fsynced before the first write lands. A crash therefore can't produce modified data behind a clean flag.
Clearing it writes a state sidecar first (the free list and live count, so the next clean open can skip a full scan), then clears the flag. A crash in between leaves the flag set — which forces a full recovery scan. Expensive, but never wrong.

That sidecar, by the way, is validated on load against a magic number, a version, the actual file size, and a CRC of its own contents. Any mismatch and it's ignored in favour of a scan. It's a cache, never an authority.

On recovery, the engine verifies everything: every live record's CRC is recomputed, and a record that fails is tombstoned (a corrupt record that is readable is more dangerous than one that's gone). An invalid header mid-file means a torn append, and the file is truncated there. Index snapshots from before the crash are discarded wholesale and rebuilt from the surviving data — offsets recorded before a crash can't be trusted.

fsync itself is a policy, not a hardcoded rule: .off by default (fsync on explicit sync() and close()), or .afterWrites(n), or .interval(seconds). On mobile, "always fsync" is a battery decision as much as a safety one, and it should be yours to make.

Atomic batches, and a bias against losing data

writeBatch runs mixed inserts/updates/upserts/deletes in four phases, strictly in order:

Validate & resolve — reads only: duplicate checks, resolving existing pointers, extracting old index keys. Any throw here leaves the collection completely untouched.
Append new versions — one batched write per shard. Old versions are still intact on disk.
Tombstone old versions — updates, upserts, deletes.
Update indexes — pure in-memory. Cannot fail.

The hard case is a failure during phase 3, where some old versions got tombstoned and others didn't. You can't roll that back — the tombstone already landed on disk. So, per operation:

Old version already tombstoned? The newly appended version is now the only copy of that document. Rolling it back would destroy data. Keep it, and make it visible in the indexes.
Old version still live, or it was a plain insert? Tombstone the new append. The pre-batch state stays authoritative.

And if probing the old record fails, the engine assumes it was tombstoned — because preferring the new version risks a duplicate after an index rebuild, while wrongly assuming "still live" would tombstone the only surviving copy.

Duplicates are recoverable. Data loss is not. That asymmetry is why the phases are ordered the way they are, and it's the same instinct as the free-slot check earlier: when the engine can't prove which of two states it's in, it picks the one you can come back from.

What NyaruDB2 deliberately doesn't do

I think a design is best judged by what it refuses.

Not doing	Why
A full LSM-tree (SSTables, leveled compaction, bloom filters)	The engine already has the useful subset: batched sequential appends, an in-memory sorted index, tombstones, streaming compaction. The rest of the LSM machinery buys sustained write throughput at the price of background write amplification — which on a phone is battery drain and flash wear.
Faulting / lazy proxy objects (the Core Data trick)	It requires intercepting property access, which the Obj-C runtime gives `NSManagedObject` and Swift does not give a `Codable` struct. Doing it means giving up the plain-struct API — the one thing this project won't trade. A projection API gets most of the benefit without it.
`mmap` on the read path	Point reads are already a single `pread`. `mmap` fights iOS file protection (page faults after the device locks), needs remapping when the file grows, and needs a fence around compaction's file swap or a live pointer becomes a use-after-unmap crash. And it can't help at all when payloads are compressed or encrypted, because the bytes on disk aren't the bytes you want.
A background compaction thread	Predictability. `needsCompaction()` tells you when it's worth doing; `compact()` does it when you say so. Nothing spends your users' battery behind your back.
SQL	It's a document store. The query builder is typed, composable, and survives a rename refactor. A SQL string is none of those.

Where it stands

It's real code: encryption at rest (AES-GCM per record, sealed manifests, sealed index snapshots), compression (gzip/lzfse/lz4), file protection, crash recovery, atomic batches, streaming cursors. It has a test suite. It runs on macOS and iOS.

It is also experimental, pre-1.0, and has no production users. I'm still working on performance — the query path in particular has a real gap against Core Data that I'm chasing, and I'll write about that separately, along with the story of how I discovered that most of my other apparent gaps were bugs in my own benchmark harness rather than in the engine.

Issues, disagreements, and "you're wrong about mmap and here's why" are all welcome.

github.com/maltzsama/nyarudb2