Maryk + FoundationDB: Storage Layout

This document explains how Maryk stores data in FoundationDB (FDB): what subspaces are used, how keys and values are encoded, and how versioning, soft deletes, uniques, and indexes work. It is meant to be approachable for contributors and readers new to both Maryk and FDB.

TL;DR

• Every DataModel gets its own FDB directory (subspace) tree under a configurable root.
• We keep small, well‑known subspaces per model: keys, table, unique, index. If history is enabled, we also have *_versioned variants. If update-history indexing is enabled, we also have update_history.
• “Latest” values live in table and are encoded as (version || value). History (if enabled) lives in separate subspaces keyed by an inverted version suffix to keep “latest first” ordering.
• Soft deletes are object‑level flags stored as a special qualifier. Hard deletes clear all records (and history) for a key.
• Uniques and Indexes are first‑class citizens with current and (optionally) historic representations.

---

Store metadata directory

In addition to the per-model directories, the store reserves a shared directory at ['__meta__', 'models_by_id']. It keeps a simple map from model id to model name so the datastore can verify that the configured dataModelsById matches what was previously persisted before touching any model data. Entries are stored as:

• Key: directory prefix + 4-byte big-endian model id.
• Value: UTF-8 encoded model name.

The dedicated directory already isolates this metadata, so no extra prefix byte is required.

Directory (Subspace) Layout

Per DataModel (e.g. Log, Person) we create these subspaces:

• meta – stored schema and migration state for the DataModel.
• keys – existence + creation version per object key.
• table – latest property values per object key, plus a small “latest version” marker per key.
• unique – latest unique constraints (per unique property or composite).
• index – latest secondary indexes.

If keepAllVersions = true, we also create historic subspaces:

• table_versioned – all historical values per object key.
• unique_versioned – historic unique entries (tombstones and key snapshots).
• index_versioned – historic index entries (tombstones and value snapshots).

If keepUpdateHistoryIndex = true, we also create:

• update_history – engine-level update history entries ordered by change version.

All of the above are regular FDB subspaces created via the DirectoryLayer. They give us prefix isolation so we can read/write/scan per model efficiently.

Keys and Qualifiers

Maryk uses a “row/column” style: the full FDB key is the subspace prefix + the Maryk key + a “qualifier” representing a property (or property+collection item).

Examples (pseudocode):

• Latest value for property: tablePrefix + key + propertyQualifier → (version || value)
• Object soft‑delete flag: tablePrefix + key + [0x00] → (version || [0x01])
• Creation timestamp: keysPrefix + key → version (no value payload)
• Latest version marker: tablePrefix + key → version (no qualifier; used to derive lastVersion)

The “qualifier” is generated from Maryk’s property references. Collections (list/set/map) qualify by index or element key. Embedded/object markers use small type markers.

Value Encoding

• Latest values in table: stored as (version || value)
  • version is Maryk’s HLC timestamp (8 bytes, big‑endian). We use it for concurrency control, “last write wins”, and to expose firstVersion/lastVersion to clients.
• Historic values in table_versioned: stored on a separate key with inverted version bytes in the key suffix:
  • Key: historicTablePrefix + key + encodeZeroFree(qualifier) + 0x00 + inverted(version)
  • Value: just value (no version prefix, since it is already in the key)
  • Inverting bytes for the version makes newer versions sort before older versions lexicographically, so a forward range scan gives “latest first”.

Property deletion uses an empty historic payload. Retained current tombstones use an exact two-byte 00 00 payload, distinct from the canonical one-byte zero count of a present empty collection. Incrementing-map tombstones retain allocated keys; allocation advances only the numeric key bytes, excluding anonymous collection markers and child qualifiers.

Maryk’s value serialization is reused across storage engines. Simple types are written directly, and for wrappers (e.g. enums, typed values) the inner type bytes are composed accordingly.

Active-case checks and parent replacement follow the shared multi-type rules.

Versioning

FoundationDB write transactions always write a new version (HLC timestamp) for any changed value(s). For keepAllVersions = true we mirror the write into the historic subspace using the inverted version in the key. Readers can then:

• Read the latest value from table.
• Read to a toVersion by scanning the historic subspace only up to the inverted toVersion (first match = latest ≤ toVersion).

On the historic/versioned tables the version is encoded in the key suffix with inverted bytes, so forward range scans yield latest‑first. Qualifiers are encoded to contain no 0x00 bytes. A single 0x00 separator is inserted between the (encoded) qualifier and the inverted version. This guarantees the separator is the first zero byte and preserves correct lexicographic ordering without extra buffering during scans.

Soft Delete vs Hard Delete

• Soft delete sets the special “object delete” qualifier on the table (and historic if enabled), recording (version || true).
• Hard delete clears:
  • keysPrefix + key
  • All tablePrefix + key + ...
  • All table_versioned + key + ... (if present)
  • And prunes related unique/index entries.

Consumers can request filterSoftDeleted = true and Maryk will transparently hide soft‑deleted objects.

Uniques

Uniques are stored in unique as:

• Key: uniquePrefix + (uniqueRef || valueBytes)
• Value: (version || keyBytes)

On insertion, we first read to check if a value already exists, and fail if the unique is taken. On update/delete we remove the unique entry (and, if historic is enabled, write a historic “tombstone” or snapshot into unique_versioned).

Mutation cleanup reads the stored unique-property descriptors in its own native transaction. This includes dynamic map/list/typed references introduced by other open writers, so hard deletion purges their retained ownership history while preserving claims belonging to other records.

Indexes

Indexes are stored in index as:

• Key: indexPrefix + indexRef + (indexValueBytes || keyBytes)
• Value (latest): version
• Historic: index_versioned + encodeZeroFree(indexRef || (indexValueBytes || keyBytes)) + 0x00 + inverted(version) → entries record index changes. Historic index scans read these entries within the computed range and map back to keys for ordering and filtering at a given toVersion.

This design enables:

• Efficient scans in index order with or without a starting key.
• Partial prefix scans (e.g. “all rows for this severity”).
• Historic scans (if enabled) to see which keys matched an index at a given time. Historic index scanning is supported and used when toVersion is provided.

Get, Scan, and Changes

• Get by key: check keys for existence and creation version, apply filters (including soft delete), then read values out of table or table_versioned depending on toVersion.
• Scan by key: compute key ranges from the model and filters, walk keys in ASC or DESC, apply filters, and collect up to limit.
• Scan by index: build index ranges from the filter and order, scan index (value+key) and map back to primary keys. When toVersion is provided, perform a historic index scan by computing the index value at that version per key and applying the same ordering and range filters.
• Scan updates with no explicit order: if keepUpdateHistoryIndex = true, scan update_history newest-first and map entries back to current records.
• Changes APIs (GetChanges/ScanChanges): instead of returning full values, we stream VersionedChanges (creation + field changes) between fromVersion..toVersion, with maxVersions limiting per field.

Filtering

Maryk’s filter DSL (Exists, Equals, Range, Regex, etc.) is evaluated by matching qualifiers to property references:

• For exact property references we do a direct get on table or scan table_versioned up to toVersion.
• For “fuzzy” references (like any element in a list/map) we scan the qualifier space under the property prefix.

Soft delete filtering is layered in: if filterSoftDeleted is true, we check the soft delete indicator and hide those rows.

Error Handling & Validations

Outside an explicit atomic request or transaction scope, each add, change, or delete object is committed in its own FDB transaction. Read-for-write validation (uniques and parent existence for nested values) runs inside that object’s transaction to avoid races. FDB retries conflicting transactions, and Maryk returns validation errors (for example, a unique violation) as structured per-object statuses. A multi-object request is therefore not atomic: objects committed before a later failure remain committed.

Explicit AtomicRequest execution uses one transaction across every participating model instead. Conditions and schema fences are read inside that transaction; values, indexes, history, cluster-log entries, and the successful retry receipt commit together. Transaction retries discard attempt-local notifications. See Atomic requests for the bounded contract.

Interactive transaction scopes use the same commit boundary for an ordered read/write journal. A revision fence protects point reads and range decisions, while durable responses receive ordered mutation versions at commit. Preview never publishes its staged bytes. See Serializable transactions.

Why use separate historic subspaces?

Keeping current data in table and history in table_versioned gives us:

• small and fast lookups for “latest” queries;
• predictable scans for “as of” queries without mixing current and historic writes;
• forward‑only streaming (because of inverted version suffix) for time windows.

This maps neatly to FoundationDB’s range read strengths, while preserving Maryk’s model semantics.

Update History

When keepUpdateHistoryIndex = true, each add/change/delete also writes:

• Key: updateHistoryPrefix + inverted(version) + key
• Value: empty

This is used for scanUpdates(order = null) so a forward scan returns newest-first object updates.

Opening storage format 2

Read the storage upgrade guide for rollout, conversion and recovery requirements. The details below describe this engine’s persisted layout.

Temporary staging includes both old and new keys. When this envelope exceeds FoundationDB’s 100,000-byte value limit, the upgrade chunks it in a separate temporary metadata subspace. Chunks, their manifest and the checkpoint commit together; cleanup removes them before the format is published. This also permits conversion of floating collection qualifiers whose unchanged value is close to the native value limit.

Stored source model definitions and their dependencies use the legacy transport reader during upgrade, preserving NANOS DateTime collection defaults. Before publication each source definition pair is rewritten with its own current-format marker in one guarded transaction. A restart can therefore distinguish rewritten schemas from remaining legacy pairs while the global upgrade is unfinished. This preserves source schemas and versions, including models not registered by the opener; application schema migrations still run afterward. Read-only schema discovery used by the App and CLI selects the same legacy/current reader from the store format and each source-pair marker before opening the store.

Opening maintenance flags and clock/history backfills follow the shared opening contract.

FoundationDB cluster logs distinguish released and current transport payloads in an existing type bit, including packed floating value objects and NANOS DateTime collections. Released packed DateTime pairs are decoded using the recorded format, preserving every element even when their bytes also resemble one current framed value. Old queued payloads can be read without a queue rewrite or extra log-envelope bytes.

FoundationDB stores the released receipt tag in its manifest and reconstructs the tagged logical receipt from unchanged 80,000-byte chunks. Manifest conversion uses the same staged opening-upgrade checkpoints as other format-sensitive metadata. Receipt limits include the fingerprint and current envelope, and the released manifest adds its envelope only once during reconstruction.

Unique ownership and replication

See store behavior for deletion, final unique ownership, replication ordering and deleted-inclusive scans.

Removing an optional encrypted value decrypts its previous value for validation before clearing the stored cell.