Storage Engines: From SQLite to Redwood to Sharded RocksDB

• 3.1 The Storage Server Interface
• 3.2 Era One: KeyValueStoreSQLite (2013 – 2021)
  • What “ssd-1” actually does on a write
  • Why two flavors, ssd-1 and ssd-2?
  • Why it had to be replaced
• 3.3 Era Two: Redwood (2020 – present)
  • Why “versioned”?
  • Page layout
  • Copy-on-write writes
  • Concurrency
  • What to read in the source
  • How to know if you’re running Redwood
• 3.4 Era Three: Sharded RocksDB (2022 – present)
  • What “sharded” means here
  • What you give up
  • Where the gains are
  • When to pick which
• 3.5 The Memory Engine — Not Just for Testing
• 3.6 The “Outer MVCC” — How All Three Engines Look the Same to FDB
• 3.7 Putting It Together: A Worked Example
• 3.8 What This Means for the Labs
• Interview Questions

“FoundationDB’s storage engine is the part most outsiders get wrong. They picture a thin shim over RocksDB. The reality is three engines, fifteen years of evolution, and a bytecode interpreter that runs inside a B+tree.”

The previous chapter covered FoundationDB’s distributed plane: proxies, resolvers, transaction logs, and the cluster controller. This chapter zooms into the box labeled “Storage Server” and asks what is actually written to disk.

The answer has changed three times since FoundationDB became public in 2013:

If your fdbserver was compiled in the last year and you typed configure ssd, you got Redwood. If you typed configure ssd-rocksdb-v1 you got Sharded RocksDB. If you typed configure memory you got the in-memory engine. The original SQLite-based engine is still in the tree (ssd-1/ssd-2) and still used for catalog data; it is the engine the rest of the world used in production for the better part of a decade.

Why three engines? Because the abstract interface that a Storage Server needs is very narrow, but the physics underneath it are very picky.

3.1 The Storage Server Interface

A Storage Server is just an IKeyValueStore. The interface is defined in fdbserver/IKeyValueStore.h:

class IKeyValueStore : public IClosable {
public:
    virtual KeyValueStoreType getType() const = 0;

    virtual void  set(KeyValueRef keyValue, const Arena* arena = nullptr) = 0;
    virtual void  clear(KeyRangeRef range,  const Arena* arena = nullptr) = 0;
    virtual Future<Void> commit(bool sequential = false) = 0;

    virtual Future<Optional<Value>>      readValue(KeyRef key, ...) = 0;
    virtual Future<Standalone<RangeResultRef>>
        readRange(KeyRangeRef keys, int rowLimit, int byteLimit, ...) = 0;

    virtual StorageBytes getStorageBytes() const = 0;
};

Five operations: set, clear, commit, readValue, readRange. That’s it. Every storage engine in FDB implements those five and a handful of introspection methods. Everything you have ever heard about FDB — MVCC, sharding, replication, MVCC GC — lives above this interface.

That narrowness is what made it possible to swap SQLite for Redwood for RocksDB without changing the Resolver, the Transaction Log, the Data Distributor, the client library, or any layer.

The Storage Server itself (the role, as opposed to the engine) is implemented in fdbserver/storageserver.actor.cpp. That file is ~10,000 lines of Flow actors that:

1. Subscribe to the Transaction Log for mutations.
2. Buffer them in an in-memory MVCC structure called the VersionedMap (a persistent — i.e., immutable-snapshot — radix tree, see fdbserver/VersionedMap.h).
3. Periodically write a “durable version” of the VersionedMap into the underlying IKeyValueStore.
4. Serve reads by composing the durable engine’s data with anything newer in the VersionedMap.

So when you read a key from FDB, you are reading from two layers: a recent in-memory MVCC overlay, plus the durable on-disk B-tree (or LSM). The MVCC overlay is what gives you the 5-second window of historical reads; the durable engine is what gives you petabytes of capacity.

3.2 Era One: KeyValueStoreSQLite (2013 – 2021)

When FoundationDB Inc. was founded in 2009, the team made a deliberate decision: don’t write a new B-tree. B-trees are notoriously hard to get right — crash recovery, concurrency, page-level corruption — and SQLite’s B-tree had already been deployed on a couple billion devices and tested by Richard Hipp’s TH3 test suite, which famously exercises 100% MC/DC branch coverage.

So they took SQLite’s B-tree (btree.c, pager.c, os_unix.c), forked it, stripped out everything above it (the SQL parser, virtual machine, VFS layer), and wired the resulting key-value primitive into Flow as KeyValueStoreSQLite. The fork still lives in the repo at fdbserver/sqlite/ — the file names will look very familiar to anyone who has read SQLite source.

What “ssd-1” actually does on a write

Storage Server receives mutation: set("apple", "1") at version v100
   │
   ▼
KeyValueStoreSQLite::set()                            ← in-memory, just a queue
   │
   ▼  (commit called by storageserver.actor.cpp every "MUTATION_BATCH_INTERVAL"
   │   — typically 5 ms, configured by KNOB STORAGE_COMMIT_INTERVAL)
   │
KeyValueStoreSQLite::commit()
   │
   ├──► sqlite3BtreeBeginTrans(WRITE)
   ├──► for each mutation:  sqlite3BtreeInsert() / sqlite3BtreeDelete()
   ├──► sqlite3BtreeCommitPhaseOne()    ← writes WAL frame
   ├──► sqlite3BtreeCommitPhaseTwo()    ← fsync, then page move
   ▼
returns Future<Void> that fires when on disk

The SQLite engine runs in rollback-journal mode, not WAL mode (counter- intuitively — SQLite’s “WAL” is unrelated to FDB’s distributed Transaction Log). The rollback journal works like this:

1. Before modifying page X, copy X’s current contents to a side file (*.fdb-rj).
2. Modify page X in memory.
3. fsync the rollback journal.
4. Overwrite page X in the main file.
5. On crash recovery, if a rollback journal exists, restore each page from it.

This is the same algorithm as PostgreSQL’s older “physical log” approach. It gives crash atomicity at the page level. The cost: every page modification incurs two writes — one to the journal, one to the main file — plus an fsync.

Why two flavors, ssd-1 and ssd-2?

ssd-1 was the original. ssd-2 is the same engine with a btree corruption check and a tweaked page size (introduced in FDB 6.1). In practice you should not be choosing between them; both are legacy.

Why it had to be replaced

Three problems compounded as FDB went to multi-terabyte Storage Servers:

1. Page locking. SQLite serializes all access to its pager. Reads and writes contend on a single mutex. With Flow actors generating thousands of concurrent reads, the mutex became a bottleneck around 2016.
2. No MVCC. SQLite is a single-writer engine. Every commit has to wait for the previous one to finish. FDB worked around this by batching mutations, but the batch wall-time directly became commit tail latency.
3. Write amplification. With 4 KB pages and the rollback journal, write amplification was ≈ 6× even before SSD wear leveling.

By 2018 a Storage Server saturating a single NVMe at sustained write throughput was a known hardware-limited operation. The team decided to write a purpose-built engine that knew it was running inside an MVCC system.

3.3 Era Two: Redwood (2020 – present)

Redwood is a versioned, copy-on-write, prefix-compressed B+tree with delta encoding inside each page. It is implemented in a single ~10,000-line file: fdbserver/VersionedBTree.actor.cpp. The lead designer is Steve Atherton; his FDB Summit 2018 talk (“Redwood Storage Engine”) is required viewing.

Why “versioned”?

Recall from §3.1 that the Storage Server maintains an in-memory VersionedMap and periodically flushes a “durable version” to disk. With SQLite, “flush” meant replace — the on-disk state always represented one version, and older versions only existed in memory.

Redwood is fundamentally different: the B+tree itself is multi-versioned. Each page has a version. When you read at version V, the tree exposes the view that was current at version V — even if newer versions exist on disk.

Concretely:

Page #42  versions:  v100  →  [apple=1, banana=2]
                     v150  →  [apple=1, banana=2, cherry=3]
                     v200  →  [apple=9, banana=2, cherry=3]

Read at v160 returns:  [apple=1, banana=2, cherry=3]   ← uses v150
Read at v250 returns:  [apple=9, banana=2, cherry=3]   ← uses v200

This collapses three things into one structure:

1. The in-memory MVCC overlay (no longer needed for the 5-s window).
2. The durable on-disk tree.
3. The “checkpoint” / snapshot mechanism (a checkpoint is just a frozen version).

The win: a single commit writes new versions of touched pages once, with no journal copy and no rewrite. Write amplification drops from ≈6× to ≈1.5×.

Page layout

Each Redwood page is laid out (see BTreePage in the source, around line 2200 of VersionedBTree.actor.cpp):

┌──────────────────────────────────────────────────────────────┐
│ Header: page type (leaf|internal), height, version, flags    │ 16 B
├──────────────────────────────────────────────────────────────┤
│ DeltaTree: prefix-compressed sorted entries                  │
│                                                              │
│   anchor key: "user:1024:profile"                            │
│   delta 1   : +3 "_v1"           value=...                   │
│   delta 2   : +3 "_v2"           value=...                   │
│   delta 3   : skip 4 "_pic"      value=...                   │
│   ...                                                        │
│                                                              │
│   Each delta:  { prefix_len, suffix_bytes, value_or_ptr }    │
└──────────────────────────────────────────────────────────────┘

The DeltaTree2 structure (fdbserver/DeltaTree.h) is the cleverest part: it stores keys as deltas from the previous key in sorted order, then arranges those deltas in a balanced binary search tree inside the page so you can binary-search without decompressing the whole page. A typical FDB workload has 60–80% prefix overlap inside a page (keys like user:1024:posts:001, user:1024:posts:002, …); DeltaTree2 routinely compresses pages 3–5×.

Copy-on-write writes

Writes never modify a page in place. Instead:

1. The mutation logically applies to page #42.
2. A new physical page (say #9817) is allocated containing the new content.
3. Page #42’s parent in the B+tree is rewritten to point to #9817 (this recurses to the root — O(log N) new pages per commit).
4. The old page #42 is not freed immediately. It is kept alive until the oldest reader’s version is past it.
5. A background actor periodically scans the page allocator’s free queue and reclaims pages whose oldest_reader_version constraint is satisfied.

The free-page allocator is itself a B+tree (a “queue of free pages”), making allocation transactional. See FIFOQueue in fdbserver/FIFOQueue.h.

Concurrency

Redwood uses lock-free reads: a reader takes a snapshot of the root pointer for its version, then walks down. Because pages are copy-on-write, no other writer can mutate the pages the reader is walking — they will allocate new pages instead. This is the same trick used by LMDB and CouchDB.

There is exactly one writer thread per Redwood instance. With one writer, write serialization is implicit; no page locks needed.

What to read in the source

The DWALPager (“Direct-Write-Ahead-Log Pager”) is Redwood’s WAL. Like the distributed Transaction Log, it lets the engine acknowledge commits before the B+tree itself has been fully updated, then flushes lazily.

How to know if you’re running Redwood

fdbcli> status details

Look at each Storage Server line:

10.0.0.5:4500 (...)     class=storage      storage_engine=ssd-redwood-1

In Go-binding clients there is no API for this — it is configured at the cluster level via fdbcli> configure ssd-redwood-1-experimental (the suffix was dropped in 7.3, but the keyword survives for backward compat).

3.4 Era Three: Sharded RocksDB (2022 – present)

The third engine is a deliberate move toward leveraging a battle-tested LSM implementation. The motivation is not technical envy; it is operational reality:

• RocksDB has decades of investment in compaction tuning, write throttling, rate limiters, and observability hooks.
• Many FDB consumers (Snowflake, Apple) already run RocksDB elsewhere in their stack and have on-call expertise.
• LSMs match write-heavy workloads better than B+trees, and a meaningful fraction of FDB deployments are write-dominated (event logs, time series).

What “sharded” means here

This is not LevelDB-style. A single Storage Server in modern FDB hosts many shards (key ranges, typically ~250 MB each). In ssd-rocksdb-v1 each shard is its own RocksDB instance:

Storage Server process
  ├── shard "user:0000..." → /data/shards/abc123/  (one RocksDB tree)
  ├── shard "user:0001..." → /data/shards/def456/  (another RocksDB tree)
  ├── shard "user:0002..." → /data/shards/ghi789/  (another RocksDB tree)
  └── ...

Why per-shard instances? Because when Data Distribution moves a shard, the Storage Server can physically move the RocksDB directory instead of copying key by key. The destination server just opens the directory in place. This makes data movement nearly instantaneous, and bypasses the compactor entirely.

This trick was prototyped in Tigris’s FDB fork and brought upstream by the Snowflake team. The implementation lives in fdbserver/KeyValueStoreShardedRocksDB.actor.cpp.

What you give up

• Read amplification. LSM lookups must consult multiple SSTs. For point lookups bloom filters help; for range scans they don’t. Redwood beats RocksDB on read-heavy workloads by a non-trivial margin.
• MVCC native to the engine. The MVCC overlay must come back; Sharded RocksDB cannot serve historical reads natively, so the VersionedMap in storageserver.actor.cpp is doing real work again.
• Snapshot semantics. Cheap with copy-on-write, harder with LSMs.

Where the gains are

• Bulk ingestion. SST file ingestion (IngestExternalFile) lets backup restore at near-disk-bandwidth rates.
• Mature tuning knobs. Rate-limited compaction, prioritized flushes, block cache observability — all features of the engine itself.

When to pick which

3.5 The Memory Engine — Not Just for Testing

KeyValueStoreMemory (source) is sometimes dismissed as a test fixture. It is actually used in production for workloads where the entire dataset fits comfortably in RAM and ultra-low latency matters — Snowflake uses it for some metadata services.

Its design is straightforward:

• An in-memory radix tree holds all keys.
• A disk WAL records every mutation, fsynced before commit ack.
• On restart, the WAL is replayed to reconstruct the tree.
• Periodic compaction rewrites the WAL as a snapshot to bound restart time.

The latency win is real: a set is O(log N) pointer manipulations plus an append to an open log file. A 64-core Storage Server running the memory engine can sustain ~500,000 set/sec on a single NVMe, vs ~120,000 for Redwood on the same hardware. The cost is obvious — capacity is bounded by RAM.

3.6 The “Outer MVCC” — How All Three Engines Look the Same to FDB

Regardless of engine, the rest of FDB only ever sees:

struct StorageServerState {
    VersionedMap<KeyRef, ValueOrClearToRef> versionedData;   // in-memory MVCC overlay
    IKeyValueStore*                          storage;         // SQLite | Redwood | RocksDB
    Version                                  storageVersion;  // last durable version
    Version                                  oldestVersion;   // GC horizon (~5 s old)
    Version                                  latestVersion;   // most recent applied mutation
};

A read at version v:

1. Walk versionedData for the key at version v. If found, return.
2. Otherwise, read from storage (which holds the snapshot as of storageVersion).
3. If v < oldestVersion, return transaction_too_old (error 1007).

A mutation:

1. Update versionedData at the new version.
2. Update latestVersion.
3. Periodically (every ~5 ms or 5 MB, configurable via STORAGE_COMMIT_INTERVAL and STORAGE_COMMIT_BYTES knobs), flush the versionedData entries with version ≤ some cutoff into storage, then advance storageVersion.

The flush itself is the engine-specific part — Redwood writes copy-on-write pages, Sharded RocksDB writes to a memtable, SQLite writes to its journal.

This separation explains why FDB can “upgrade” your storage engine via a rolling restart: stop one Storage Server, change its config to use the new engine, start it back up, and the Data Distributor will gradually move shards to it. No data migration script — just shard relocation, which FDB does anyway.

3.7 Putting It Together: A Worked Example

A client commits a transaction at commitVersion = v100 that sets apple = 1 and clears banana. The Storage Server holding both keys is running Redwood. Here is the byte-by-byte journey:

Notice: one fsync per commit batch, not per mutation. With a 5 ms batch window and ~5,000 mutations per batch at peak load, this gives Redwood its characteristic ≈250,000 mutations/sec/disk throughput on commodity NVMe.

3.8 What This Means for the Labs

The five labs in this repo treat FDB as a black-box ordered KV store. But the performance of each lab is shaped by which engine is underneath:

• Option B labs (SQLite/LevelDB on FDB). They store pages (4–32 KB) as values. Redwood’s prefix compression buys you nothing here — pages don’t share prefixes. RocksDB sharded engine, with native block compression, is usually faster for this workload.
• Option A labs (KV API / SQL above FDB). They store many small keys with shared prefixes (table/pk/..., index/col/val/pk/...). Redwood’s DeltaTree2 will compress these aggressively. Redwood is the better default.
• Option C (Record Layer). Same prefix-heavy story as Option A. Redwood wins.

Try this experiment with the labs:

# Default cluster: Redwood
docker compose up -d
./scripts/bootstrap-fdb.sh
cd option-c-record-layer && go run ./demo

# Re-configure to memory engine and re-run
docker exec -it $(docker ps -qf name=fdb) fdbcli --exec "configure memory"
cd option-c-record-layer && go run ./demo
# Notice the latency drop on commits, but capacity is now RAM-bounded

Interview Questions

Q: Why did FoundationDB build Redwood instead of using RocksDB or LMDB?

Three reasons. First, RocksDB at the time of Redwood’s design (2017–2019) did not have efficient native MVCC; FDB already maintained an in-memory MVCC overlay and wanted to push that down into the engine. Second, FDB’s workload has heavy prefix overlap (long encoded keys like \x15\x01user\x00\x15\x01...) and RocksDB had no prefix compression inside a block. Third, FDB’s copy-on-write semantics are a poor match for LSM compaction overhead. Redwood was designed to fit FDB’s existing MVCC model rather than fight it.

Q: How does Redwood reclaim free pages without breaking historical reads?

Each page has a version when freed. The free-page queue stores tuples (pageID, versionFreed). The pager only re-allocates a page when versionFreed < oldestReaderVersion across all live transactions. Because FDB’s MVCC window is ~5 seconds, free pages typically take 5–10 s to become re-allocatable. The free queue is itself a B+tree, so the bookkeeping is transactional.

Q: What is the difference between FDB’s Transaction Log and an engine’s WAL?

FDB’s Transaction Log is the distributed WAL — f+1 copies of every commit written across machines before client ack. The engine’s WAL (e.g., Redwood’s DWALPager, SQLite’s rollback journal, RocksDB’s MANIFEST/WAL) is the local WAL for that one Storage Server, used to recover that server’s on-disk state if it crashes before its in-memory pages were flushed. The durability guarantee comes from the Transaction Log; the engine’s WAL is purely for local crash recovery.

Q: Why does the Memory engine still need a disk WAL?

So that commits survive a process crash. The in-memory radix tree is rebuilt from the WAL on startup. Without the WAL, a restart would lose data even if FDB’s distributed Transaction Log retained the commits — the engine couldn’t re-derive its state quickly. The WAL turns recovery into an O(WAL size) sequential read instead of an O(dataset) cross-cluster re-replication.

Q: A Storage Server is being moved to a new machine. Compare what happens under SQLite vs. Sharded RocksDB.

Under SQLite: the source Storage Server streams every key in the shard’s range to the destination over the network, which then writes each key into its own SQLite B-tree. Cost: O(shard size) bytes over network, O(shard size) random writes on the destination disk. Under Sharded RocksDB: the source copies the SST files of that shard’s RocksDB directory to the destination, which opens the directory directly. Cost: O(shard size) bytes over network, but writes on the destination are sequential SST file writes — no key-by-key insertion overhead. The latter is typically 5–10× faster wall-time.