This Repository — Five Implementations

This repo contains five working implementations of FDB layers, ordered from conceptually simple to architecturally sophisticated. Each folder is self-contained: it has its own go.mod, source code, and docs/GUIDE.md with a deep dive into how and why that layer is built the way it is.

foundationdb-labs/
├── option-a-leveldb/     LevelDB API above FDB        → docs/GUIDE.md
├── option-a-sqlite/      SQL engine above FDB         → docs/GUIDE.md
├── option-c-record-layer/ Records + secondary indexes → docs/GUIDE.md
├── option-b-leveldb/     LevelDB on FDB storage       → docs/GUIDE.md
└── option-b-sqlite/      SQLite VFS substrate         → docs/GUIDE.md

5.1 Recommended Reading Order

Start with option-a-leveldb regardless of your background. It introduces all the core patterns — subspaces, range scans, snapshot reads, transaction retry loops — in the simplest possible context.

5.2 Layer-by-Layer Architecture Map

option-a-leveldb (API Layer above FDB)

LevelDB API (Get/Put/Delete/Batch/Iterator/Snapshot)
                        ↕
         FDB KV store (subspace-encoded keys)

The layer sits above FDB. User code calls db.Put(key, value). The layer encodes the key as ns + 0x00 + key and calls tr.Set(encodedKey, value). All LevelDB semantics (iterators, snapshots, batches) are implemented using FDB primitives.

Why this layer: LevelDB’s API is the lingua franca of embedded KV stores. By implementing it on FDB, existing code that uses LevelDB can be dropped into a distributed, replicated context without changing its API usage.

option-c-record-layer (Record + Index Layer)

Application (PutRecord / GetRecord / LookupByIndex)
                        ↕
   FDB (two subspaces: records and indexes)

The layer sits above FDB. A record is stored at a fixed key. Every indexed field also has an index key in a separate subspace. Both are written in the same transaction to keep records and indexes consistent.

Why this layer: This is the fundamental pattern for any “database” feature. Tables, collections, documents — all of them are “records with indexes.” Understanding how to keep a record and its indexes consistent under concurrent writes is the core of database internals.

option-a-sqlite (SQL Engine Layer)

SQL (CREATE TABLE / INSERT / SELECT / UPDATE / DELETE)
                        ↕
     Table catalog (FDB) + Row store (FDB)

A minimal SQL parser and query engine above FDB. Tables are defined in a catalog (a separate subspace). Rows are encoded as msgpack values keyed by primary key. SELECT * is a range scan over the table’s key range.

Why this layer: Shows that a full (if minimal) relational database is ~300 lines of Go above FDB. The interesting parts are the catalog encoding and the primary key sort-order problem.

option-b-sqlite (SQLite VFS Substrate)

SQLite (full SQL engine)
           ↕
   SQLite VFS API (xRead / xWrite / xSync / xLock)
           ↕
   FDB (page-keyed store: pageNum → 4096 bytes)

SQLite provides its own SQL engine, query planner, and transaction management. The VFS is just a storage substrate: given a logical page number, read or write 4096 bytes. FDB stores those pages.

Why this layer: Shows how to extend an existing system by replacing its storage interface rather than reimplementing its logic. The interesting parts are partial-page writes (SQLite calls xWrite with sub-page ranges, requiring read-modify-write) and locking (translating SQLite’s POSIX lock semantics to FDB key operations).

option-b-leveldb (LevelDB Storage Substrate)

LevelDB (full KV engine)
           ↕
   storage.Storage interface (Create / Open / Rename / List)
           ↕
   FDB (file metadata keys + chunked file data keys)

LevelDB provides its own full KV engine. The storage layer is just a filesystem abstraction: create/open/read/write/rename/delete files. FDB stores those files as key ranges.

Why this layer: Shows that even complex storage engines like LevelDB (which manage their own B-trees, compaction, and WAL) can be decoupled from the filesystem. The interesting parts are chunk encoding (64KB chunks to stay under FDB’s value limit), atomic rename (LevelDB uses rename to commit new SSTables), and why WAL redundancy is a non-issue (FDB’s own log subsystem replaces the LevelDB WAL’s durability purpose).

5.3 Running the Labs

Each lab has a demo/main.go that exercises the layer. To run any lab:

# Start FDB (requires Docker)
docker-compose up -d

# Run a specific demo
cd option-a-leveldb && go run demo/main.go
cd option-c-record-layer && go run demo/main.go
# ... etc.

Prerequisites:

• Docker + Docker Compose (for the FDB cluster)
• Go 1.21+
• The FDB C client library (installed by the bootstrap script: bash scripts/bootstrap-fdb.sh)

FDB API version: All labs use API version 710 (FDB 7.1.x). This is set at process start:

fdb.MustAPIVersion(710)

5.4 Extending the Labs — Suggested Exercises

Each docs/GUIDE.md has exercises specific to that lab. Here are cross-cutting improvements that apply to multiple labs:

1. Continuations (all labs): Add a ScanWithCursor(cursor []byte, limit int) function that returns at most limit results and a cursor byte string. The cursor encodes the last key seen. Next call resumes from cursor. This makes full-table scans safe under FDB’s 5-second transaction limit.

2. Transactions exposed to the caller (option-a-leveldb, option-a-sqlite): Wrap multiple operations in a user-visible transaction: db.Begin() → Tx, tx.Put(k, v), tx.Get(k), tx.Commit(). Internally, this is just db.Transact(func(tr) { ... }) — all operations share one FDB transaction.

3. Versionstamp-based change feed (option-c-record-layer): When writing a record, also write to a change log subspace: changelogKey = ns + changelogSubspace + versionstamp. A background consumer can do GetRange(lastCheckpoint, MAX) to efficiently read all changes since the last poll. This is how fdb-record-layer implements change feeds.

4. Range index queries (option-c-record-layer): Current index lookup finds exact matches (field = value). Add LookupByRange(schema, field, minValue, maxValue) that does GetRange(indexPrefix(field, minValue), indexPrefix(field, maxValue)). This requires your index value to be sort-preserving encoded (integers via encodeInt64, strings lexicographically).

5. Multi-file SQLite (option-b-sqlite): Support ATTACH DATABASE by mapping SQLite filenames to separate FDB subspaces. Two “attached” databases are just two different ns prefixes in FDB — no code duplication needed.