The FoundationDB Record Layer — A Deep Dive

• 7.1 Why a Record Layer?
• 7.2 The Layered Architecture
• 7.3 Tuple Layer — Order-Preserving Encoding
  • Worked example
• 7.4 Subspaces and the Directory Layer
• 7.5 The Record Layer Core — FDBRecordStore
  • The schema is protobuf
  • Opening a store
  • saveRecord byte-by-byte
  • Reading a record
  • Queries and the planner
• 7.6 Index Types in Detail
  • Online index builds
• 7.7 Concurrency, Conflicts, and the 5-Second Rule
• 7.8 How This Maps to the Toy Go Implementation
  • Running the lab
• 7.9 When Should You Use the Record Layer?
• 7.10 Reading Order for the Source
• 7.11 Interview Questions

The previous chapter taught you that a layer is just an encoding of a data model onto FDB’s ordered byte-string KV interface. This chapter takes the most production-grade example of that idea — Apple’s open-source foundationdb/fdb-record-layer — and pulls it apart end-to-end.

By the time you finish you should be able to:

1. Explain, on a whiteboard, how a Record Layer saveRecord() call becomes a set of FDB key-value mutations.
2. Read the upstream Java source and recognize the major subsystems.
3. Decide when to use the Record Layer instead of writing your own layer.
4. Map every concept back to the toy Go reimplementation in this repo (option-c-record-layer) so you can experiment in 100 lines of Go before touching the 200k-line Java codebase.

Reference revisions. Code references in this chapter point at the main branch of FoundationDB/fdb-record-layer and FDB release-7.3. Specific class names and file paths are stable across recent versions.

7.1 Why a Record Layer?

FDB itself gives you six operations: get, set, clear, clearRange, getRange, and a transaction wrapper. That’s a beautifully small surface, but if you build an application directly on it you will, within a week, have written:

• A primary-key encoder.
• A secondary-index maintainer.
• A schema-evolution story for when you add a field.
• A query planner that picks between scanning by primary key and scanning by index.
• Pagination with cursors that survive transaction boundaries.
• Type-safe Java/Kotlin/Swift bindings instead of raw byte arrays.

Every team that builds on FDB writes the same eight thousand lines of plumbing. Apple wrote them once, hardened them with CloudKit (production since 2015, billions of users), open-sourced them in 2018, and called them the Record Layer.

So a Record Layer is a layer on top of FDB that gives you:

The price is a Java dependency and a sizable conceptual surface. The rest of this chapter is that surface.

7.2 The Layered Architecture

The Record Layer is itself a stack of three layers above FDB:

┌──────────────────────────────────────────────────┐
│  Your application                                │
├──────────────────────────────────────────────────┤
│  RecordStore  (schema + index + query API)       │  ← fdb-record-layer-core
├──────────────────────────────────────────────────┤
│  Subspace / Tuple / Directory layer              │  ← fdb-extensions, Java tuple layer
├──────────────────────────────────────────────────┤
│  FDB transactions  (get/set/clear/getRange)      │  ← libfdb_java → libfdb_c
├──────────────────────────────────────────────────┤
│  FoundationDB cluster                            │
└──────────────────────────────────────────────────┘

Each of the three layers above FDB has a distinct responsibility:

1. Tuple layer — order-preserving binary encoding of typed tuples. Source: com.apple.foundationdb.tuple.Tuple in the Java bindings.
2. Subspace / Directory layer — namespace prefixes that turn one giant keyspace into a hierarchy of sub-keyspaces. Source: com.apple.foundationdb.subspace.Subspace, com.apple.foundationdb.directory.DirectoryLayer.
3. Record Layer core — protobuf-typed records, indexes, queries. Source: com.apple.foundationdb.record.provider.foundationdb.FDBRecordStore.

We climb each in turn.

7.3 Tuple Layer — Order-Preserving Encoding

The tuple layer’s job is to convert a typed sequence like ("users", 42L, "alice") into a byte string whose lexicographic byte order matches the natural sort order of the original tuple. This is the hinge that everything else swings on, because FDB sorts keys by raw bytes.

The wire format uses a one-byte type tag per element, then the value:

The integer encoding is the cleverest bit. To make a 64-bit signed integer sort-correctly under byte comparison without using a fixed 8-byte width (which would waste space), the tuple layer uses 13 different type codes (0x0B through 0x1D) representing lengths from -8 bytes (very negative) to +8 bytes (very large positive), and the value bytes are written in big-endian with a complement for negatives. Decoding is just the inverse; encoding 42 takes 2 bytes total.

Read the source: com.apple.foundationdb.tuple.TupleUtil in bindings/java/src/main/com/apple/foundationdb/tuple/TupleUtil.java. The encoding rules are codified there and copied — bit for bit — in every official FDB binding so that a Go process and a Java process can interop.

Worked example

byte[] k = Tuple.from("users", 42L, "alice").pack();
// k = 02 75 73 65 72 73 00       ← "users"\0
//     15 2A                       ← int tag 0x15 = 1 byte positive, value 0x2A = 42
//     02 61 6C 69 63 65 00        ← "alice"\0

Now Tuple.from("users", 42L, "bob").pack() is byte-greater than the above because "bob" > "alice" lexicographically, and Tuple.from("users", 43L).pack() is byte-greater again because the integer prefix differs. Co-location and ordering come for free.

The Go toy version in this repo, encoding.go, sidesteps the full tuple encoding by using fixed 0x00 separators and assuming string fields don’t contain nulls. That’s fine for a demo, but the production tuple layer handles arbitrary bytes correctly.

7.4 Subspaces and the Directory Layer

A Subspace is just a tuple prefix plus convenience methods:

Subspace users = new Subspace(Tuple.from("app", "users"));
byte[] key  = users.pack(Tuple.from(42L, "alice"));
// equivalent to Tuple.from("app","users",42L,"alice").pack()
Range range = users.range();
// → from "app/users/\x00" to "app/users/\xFF"

This is com.apple.foundationdb.subspace.Subspace — a few hundred lines.

The Directory Layer is the next step up. Hard-coding "app/users" as a prefix in production is wasteful (it’s repeated millions of times in keys). The directory layer maps human-readable paths to short integer prefixes:

DirectoryLayer dir = DirectoryLayer.getDefault();
DirectorySubspace usersDir = dir.createOrOpen(tr, List.of("app", "users")).join();
// usersDir.getKey() might be \x15\x0C — a 2-byte allocated prefix

Underneath, the directory layer stores its mapping in a well-known subspace (\xFE) and allocates new short prefixes using a small high-contention allocator (HighContentionAllocator) that uses random partitioning to avoid hot-spotting. The allocator is itself an instructive chunk of source: com.apple.foundationdb.directory.HighContentionAllocator.

This matters because every Record Layer store lives in a directory. A multi-tenant Record-Layer-based service will typically have a KeySpacePath of the form /applications/{appId}/environments/{env}/recordStores/{storeId}, each piece resolved through the directory layer into a tiny integer prefix. Adding a tenant is one transaction; deleting one is one Transaction.clear(Range).

7.5 The Record Layer Core — FDBRecordStore

This is where it gets interesting. The central class is com.apple.foundationdb.record.provider.foundationdb.FDBRecordStore. A record store is bound to:

• a Subspace (its root prefix, usually from the directory layer),
• a RecordMetaData (the schemas of the records it can hold),
• an open FDB transaction (record stores are short-lived, one-per-transaction objects).

The schema is protobuf

Schemas are .proto files. The Record Layer ships a small Protobuf extension package that adds annotations:

import "record_metadata_options.proto";

message User {
  required int64  id    = 1 [(field).primary_key = true];
  required string name  = 2;
  optional string email = 3 [(field).index = { type: "value" }];
  optional int64  signup_ts = 4;
}

message RecordTypeUnion {
  optional User _User = 1;
}

The RecordTypeUnion message is a oneof-style container so a single record store can hold heterogeneous record types in a shared key range.

RecordMetaDataBuilder reads the .proto, extracts the primary_key annotation, finds the field.index annotations, and builds an in-memory RecordMetaData describing every type and index. Source: com.apple.foundationdb.record.metadata.RecordMetaDataBuilder.

Opening a store

try (FDBDatabase db = FDBDatabaseFactory.instance().getDatabase()) {
  db.run(ctx -> {
    KeySpacePath path = users.add("env", "prod").add("store", "main");
    FDBRecordStore store = FDBRecordStore.newBuilder()
        .setContext(ctx)
        .setKeySpacePath(path)
        .setMetaDataProvider(metaData)
        .createOrOpen();
    // ... use store ...
    return null;
  });
}

The createOrOpen path runs a small store header read at offset <prefix>/0/info to verify schema compatibility. The header records:

• the format version of the on-disk layout,
• the user-supplied metadata version,
• whether the store is in the middle of an online index build.

If any of these don’t match what the caller expects, createOrOpen will either upgrade the header in place or throw, depending on the StoreExistenceCheck you passed. This is the schema-evolution machinery — there is no ALTER TABLE, just an in-place metadata version bump plus (optionally) a background index build.

saveRecord byte-by-byte

store.saveRecord(User.newBuilder()
    .setId(42)
    .setName("Alice")
    .setEmail("alice@example.com")
    .setSignupTs(System.currentTimeMillis())
    .build());

This single line expands into roughly the following FDB mutations inside one transaction. Assume the store prefix has resolved to S (a few bytes), and the union type tag for User is 1:

(Sub-key prefixes 0 = store header, 1 = records, 2 = secondary indexes, 3 = record versions, 4 = record-type index, 5 = aggregate indexes — see FDBRecordStoreKeyspace.)

Two things are worth pausing on:

1. Every byte is written in one FDB transaction. Records and all their indexes commit atomically. There is no “index out of sync with table” failure mode.
2. Record splitting (rows 2–3) is how the Record Layer handles records larger than FDB’s per-value limit (100 kB). The split key uses a fixed subkey suffix so range-reads can reassemble.

Reading a record

FDBStoredRecord<Message> rec = store.loadRecord(Tuple.from(42L));
User user = User.newBuilder().mergeFrom(rec.getRecord()).build();

loadRecord does a getRange over S / 1 / 1 / 42 / * (to pick up split parts), concatenates the bytes, decodes the protobuf, and wraps it in an FDBStoredRecord carrying the primary key and the optional versionstamp.

Queries and the planner

RecordQuery query = RecordQuery.newBuilder()
    .setRecordType("User")
    .setFilter(Query.field("email").equalsValue("alice@example.com"))
    .build();
RecordCursor<FDBQueriedRecord<Message>> cursor = store.executeQuery(query);

RecordQueryPlanner (in com.apple.foundationdb.record.query.plan.RecordQueryPlanner) takes the RecordQuery, inspects the metadata’s indexes, and emits a tree of RecordQueryPlan nodes. For the example above the plan is one RecordQueryIndexPlan over the email value index, followed by a RecordQueryLoadByKeysPlan to fetch each matched record.

Execution is streaming: RecordCursor<T> returns a record plus a continuation — an opaque byte string that resumes the scan from where it stopped. Continuations are the answer to “how do I paginate across transaction boundaries”, because FDB transactions are limited to 5 seconds and 10 MB of writes. A long scan is just many transactions, each fed the previous one’s continuation.

Read: RecordCursorIterator, KeyValueCursor, RecordQueryPlanner. The planner is ~3000 lines; it’s a rules-based planner, not (yet) cost-based, but the rule set is sophisticated — it understands compound indexes, covering indexes, sorted unions, and intersection.

7.6 Index Types in Detail

The Record Layer ships eight production index types. Each is implemented as a subclass of IndexMaintainer, registered through an IndexMaintainerFactory. The maintainer is called by saveRecord / deleteRecord with the old and new records and updates its key space accordingly. Source: com.apple.foundationdb.record.provider.foundationdb.indexes.

The brilliant trick for count/sum/min/max is that they use FDB’s atomic mutations (ADD, MAX, MIN) so concurrent writers never conflict on the aggregate key. Update 10 000 records in parallel; the count is always exact and no transaction has to retry.

rank is implemented as a skip-list-like layered index, also visible in the source as RankedSet (com.apple.foundationdb.async.rankset). It’s a standalone library you can use without records.

Online index builds

You can add an index to a deployed store without taking it down. OnlineIndexer (com.apple.foundationdb.record.provider.foundationdb.OnlineIndexer) scans the records in chunks, indexing each in its own transaction, while new writes go through the freshly registered maintainer. The index is marked WRITE_ONLY until the back-fill completes, then promoted to READABLE. The promotion itself is a single transaction. This is exactly the trick MySQL ALTER TABLE … ALGORITHM=INPLACE does, only without the quirks, because the underlying transactional KV makes it straightforward.

7.7 Concurrency, Conflicts, and the 5-Second Rule

Record Layer transactions inherit FDB’s two hard limits:

• 5 seconds of wall-clock time between getReadVersion() and commit.
• 10 MB of writes per transaction.

So large workloads are decomposed into many small transactions, glued together by continuations. OnlineIndexer.IndexingPolicy is one example of this pattern; MultiTransactionalRunner is another.

Two patterns appear over and over in production code:

// Pattern A: chunked write
db.runAsync(ctx -> {
    FDBRecordStore store = openStore(ctx);
    return AsyncUtil.whileTrue(() -> store
        .scanRecords(continuation)
        .map(rec -> doSomething(rec))
        .onHasNext()
    ).thenApply(v -> store.getNextContinuation());
});

// Pattern B: read-modify-write with retry
db.run(ctx -> {
    FDBRecordStore store = openStore(ctx);
    User u = store.loadRecord(Tuple.from(id)).getRecord();
    User updated = u.toBuilder().setEmail(newEmail).build();
    store.saveRecord(updated);
    return null;
});  // db.run() retries on `not_committed` errors automatically

The cost-per-byte of those not_committed retries is precisely Chapter 5 §5.3’s conflict probability formula in action. If two transactions touch the same primary key and one commits, the other reads stale data and rolls back. If they touch only different primary keys, they commit without coordination.

7.8 How This Maps to the Toy Go Implementation

The option-c-record-layer lab in this repo is a deliberately minimal re-implementation of the same ideas — in Go, in roughly 400 lines, on top of the official Go FDB bindings. Use it as a Rosetta stone:

Look at option-c-record-layer/recordlayer/store.go. The PutRecord method does exactly steps 2–4 of the byte-by-byte table in §7.5 above:

1. Read the old record (to find its old index entries).
2. Clear those index entries.
3. Write the new record bytes.
4. Write the new index entries.

…all inside one fdb.Transact() call. That’s the whole shape; the production layer differs in features (rank, text, versioned indexes, splitting, planner, cursors, online builds) rather than in mechanism.

If you can read the Go file, you have the mental model for the Java one.

Running the lab

cd option-c-record-layer
go run ./demo
# Inserts a few users with a value index on `city`,
# then LookupByIndex("user", "city", "Paris") and prints the results.

Set a breakpoint inside PutRecord and watch the four FDB calls happen in order. That is the Record Layer in miniature.

7.9 When Should You Use the Record Layer?

Use it when you would otherwise build your own ORM-like layer on FDB: multi-tenant SaaS, document-style storage with secondary indexes, anything where a schema and indexes evolve over time. The Record Layer encapsulates five years of CloudKit production lessons; reinventing it is rarely the best use of your time.

Skip it when:

• You have a single, well-known access pattern and need maximum control over key layout (e.g., the LevelDB-API and SQLite-VFS labs in this repo).
• You don’t want a JVM dependency. (The Record Layer is Java-only today; community ports to other languages do not exist as of this writing.)
• You are doing low-level systems work where the Tuple + Directory + Subspace primitives are enough.

For comparison: Apple’s CloudKit is built on the Record Layer. Snowflake’s metadata store is built directly on the Java bindings, no Record Layer. Both choices are reasonable; they reflect different trade-offs about schema flexibility vs. layout control.

7.10 Reading Order for the Source

If you decide to learn the upstream source, read in this order. Each step is roughly one focused session.

1. bindings/java/src/main/com/apple/foundationdb/tuple/TupleUtil.java — the tuple encoding. Everything is downstream of this.
2. com.apple.foundationdb.subspace.Subspace and com.apple.foundationdb.directory.DirectoryLayer — namespacing.
3. com.apple.foundationdb.record.metadata.RecordMetaData and RecordMetaDataBuilder — how a .proto becomes runtime metadata.
4. com.apple.foundationdb.record.provider.foundationdb.FDBRecordStore — saveRecord, loadRecord, deleteRecord. The core. Skim, don’t memorize.
5. com.apple.foundationdb.record.provider.foundationdb.indexes.ValueIndexMaintainer — the simplest index maintainer; read top to bottom.
6. com.apple.foundationdb.record.query.plan.RecordQueryPlanner — the planner. Read just plan(RecordQuery) first, then drill into one rule.
7. com.apple.foundationdb.record.provider.foundationdb.OnlineIndexer — chunked index build with continuations. Beautiful, real example of the 5-second-rule pattern.
8. The integration tests under fdb-record-layer-core/src/test — they are the best documentation. FDBRecordStoreTestBase has the canonical setup.

After that, jump to the Contributing chapter for the PR workflow, which is essentially the same as FDB itself.

7.11 Interview Questions

Each of these is answered by something earlier in this chapter. If you can answer all five, you understand the Record Layer.

1. Why does the tuple layer use 13 different type codes for integers instead of always using 8 bytes?
2. How does the Record Layer keep a secondary index consistent with the record it points at, even under concurrent writes?
3. What is a continuation, and why does it exist? (Hint: 5-second transaction limit.)
4. A user wants to add a new index to a 1 TB record store without downtime. Walk through what OnlineIndexer does.
5. You have two record stores in different KeySpacePaths under the same FDB cluster. Can a single transaction span both? Why or why not? (Hint: yes — they share an FDB cluster — but you must be careful about the 5 s / 10 MB limits and conflict ranges.)