159 Persistent Object Store

A persistent object store is a database that maps an object identifier, or OID, to a byte sequence:

OID → byte sequence

This is the conceptual interface. The physical location of the byte sequence is not part of the model and is not observable by clients. The store may move, copy, compact, compress, or replicate bytes without changing the OID.

An OID is part of the serialised state and remains stable across database server restarts. Ordinary memory addresses are meaningful only within a running process and are never persistent references.

Stream access

A byte sequence need not be presented as a contiguous memory buffer. It may be available only through input and output streams. Conceptually, the POS provides operations such as:

InputStream read(Snapshot snapshot, OID oid);

OID create(Transaction transaction);
OutputStream write(Transaction transaction, OID oid);
void erase(Transaction transaction, OID oid);

read observes an immutable version of the byte sequence in a snapshot. write creates a replacement version associated with a transaction; it does not expose a mutable persistent memory address. A concrete API may use callbacks, buffered streams, asynchronous streams, or scatter/gather I/O while preserving this model.

The POS treats bytes as opaque

The POS does not know whether a byte sequence represents a person, a B-tree node, an image, or an application log. It does not interpret object fields, schema declarations, embedded OIDs, or application-level version tags. Its responsibilities are naming byte sequences, preserving committed versions, and returning the correct bytes for a snapshot.

In particular, the following are serialisation-layer concerns rather than POS concerns:

• the in-memory type of an object;
• the binary encoding of strings, vectors, optionals, and variants;
• which fields contain OIDs;
• the schema version of an encoded object; and
• how an older schema version is upgraded when it is read.

Serialisation and object granularity

Objects in the POS are normally coarser than objects or allocations in memory. One persistent byte sequence can encode a record containing scalar fields, several strings, optional values, and vectors. The strings and vectors do not need separate OIDs merely because they use separate allocations in an in-memory C++ representation.

struct Person
{
    PersonId id;
    string name;
    optional<BirthEvent> birth;
    vector<OID> marriage;
    vector<OID> child;
};

A serialisation function writes the complete persistent representation of this Person to an output stream. A deserialisation function reads the stream and constructs whatever in-memory strings, vectors, and optional values are useful to the running program.

void serialise(OutputStream& out, const Person& person);
Person deserialisePerson(InputStream& in);

The appropriate persistent granularity is a physical design choice. Very small values can be encoded together to reduce OID and I/O overhead. A large collection can instead use several persistent objects, such as a header and B-tree nodes, so that updating or reading one part does not require rewriting the entire collection.

Schema versions and evolution

The schema version is part of the application's serialised byte sequence. A deserialisation function reads that version before decoding the remaining fields:

Person deserialisePerson(InputStream& in)
{
    SchemaVersion version = readSchemaVersion(in);

    switch (version)
    {
        case 1: return readPersonV1AndUpgrade(in);
        case 2: return readPersonV2(in);
        default: throw UnsupportedSchemaVersion(version);
    }
}

This permits software using a newer in-memory layout to read an older serialised representation and supply defaults, rename fields, or perform other schema-evolution steps. Rewriting the upgraded object is optional and occurs through an ordinary POS transaction.

The POS neither interprets nor validates this schema version. Three distinct notions of version must not be confused:

One server owns the database

One database server process owns the POS files, caches, transaction state, and background maintenance. Other processes communicate with that server rather than opening the same persistent store directly.

Exclusive process ownership avoids competing caches and cross-process coordination of recovery, compaction, and garbage collection. Concurrency still exists among clients and transactions, but it is mediated by one storage runtime.

Partitions and single mutators

The POS is divided into partitions. An OID identifies, either directly or through an OID directory, the partition responsible for that byte sequence. Each partition owns its version index, cached state, and update queue.

A partition is associated with a mutex and an actor. Read requests can be served from immutable committed versions, while every mutation is submitted to the partition actor. The actor processes mutation messages serially, so there is at most one mutator of a partition's state at a time.

client mutations
       ↓
partition queue
       ↓
partition actor ── protected by partition mutex
       ↓
new committed versions

This avoids fine-grained locking within the partition's mutation logic. Different partition actors can make progress concurrently. Partitioning therefore provides both a concurrency boundary and a unit for caching, checkpointing, compaction, and recovery.

Log-structured renditions

A natural implementation writes new renditions of byte sequences to an append-only log. Rewriting an OID appends new bytes; it does not overwrite the bytes of the preceding rendition:

transaction 100: OID 42 → bytes A
transaction 130: OID 42 → bytes B
transaction 170: OID 42 → bytes C

The old renditions remain physically present until the cleaner determines that no retained snapshot or recovery operation can use them. Append-only writing is therefore a useful physical basis for MVCC, but retaining old bytes is not by itself sufficient. The POS also needs a snapshot-consistent way to select one rendition for every OID and must prevent cleaning of selected renditions.

The persistent OID map

The POS maintains a persistent mapping from each OID to its selected byte sequence rendition:

OID → rendition

The map can be implemented as a persistent radix tree, B-tree, or another copy-on-write structure. Updating a small number of OIDs creates new versions of the affected map nodes and shares every unchanged subtree with the preceding map. Modified map nodes are appended to the log just like object renditions.

old map root
    ├── unchanged subtree ─────────┐
    └── OID 42 → rendition A       │
                                   │ shared
new map root                       │
    ├── unchanged subtree ─────────┘
    └── OID 42 → rendition B

The map and its internal references are POS metadata. They do not alter the conceptual interface OID → byte sequence, and neither their structure nor their physical positions are visible to the object layer.

Versioned OID maps

A snapshot identifies an immutable version of the persistent OID map. A reader uses the same snapshot for every POS read in a logical operation, so every OID lookup is resolved through one consistent mapping even while partition actors publish newer map versions. The transaction-level model is described in Snapshot Isolation.

snapshot S100:
    OID 42 → rendition A
    OID 57 → rendition X

snapshot S130:
    OID 42 → rendition B
    OID 57 → rendition X

Writers append new renditions and construct a new map version without modifying the map visible to existing readers. Commit atomically publishes the new map state and its visibility sequence. A delete publishes a map containing a tombstone or no entry for that OID; older snapshots can continue to select the preceding rendition.

The POS detects the write conflicts required by snapshot isolation. For example, a transaction that attempts to replace an OID can fail if another transaction has committed a new rendition since the writer's snapshot.

Checkpoint roots and transaction deltas

Publishing a snapshot does not require rewriting a complete persistent map after every transaction. One implementation publishes a copy-on-write root at each commit. Another represents a transaction snapshot as a checkpoint root plus immutable committed deltas:

snapshot at transaction 145
    =
OID-map root at checkpoint 100
    +
committed deltas 101 ... 145

Recent deltas can be held in immutable maps, merged into levels, and consulted before the checkpoint map. A later checkpoint folds them into a new persistent root. Checkpointing is then a batching and recovery mechanism; it does not restrict readers to checkpoint-granularity snapshots.

Whether the implementation publishes roots, retains deltas, or combines both, a snapshot handle protects all map nodes, deltas, and byte-sequence renditions needed to resolve reads through that snapshot.

Snapshots across partitions

A partition actor is the sole publisher of new mapping states for its partition. Readers use immutable partition snapshots and therefore do not need to hold the mutation mutex while reading.

struct Snapshot
{
    CommitSequence sequence;
    vector<PartitionSnapshot> partition;
};

A transaction confined to one partition can commit through that partition's actor. A transaction spanning partitions requires database-level coordination so that the affected partition states acquire one atomic visibility outcome. The partition actors perform the local mutations; a transaction coordinator determines whether the collection of changes commits or aborts.

Persistent garbage collection

There are two distinct reachability problems.

Application-object reachability

Because the POS treats byte sequences as opaque, it cannot discover application object reachability by inspecting them. The serialisation layer knows which decoded fields are strong OID references and can trace from application-defined persistent roots. It supplies the resulting set of live OIDs, or equivalent incremental reachability information, to the storage runtime.

This separation permits tracing to handle cyclic object graphs without teaching the POS about application schemas. Indexes, caches, and other derived structures are normally weak: they help find an OID but do not make the corresponding application object reachable.

Storage-version reachability

The POS traces or otherwise accounts for map nodes, delta layers, and object renditions reachable from every retained snapshot:

storage-live data =
    reachable from the current map root
    ∪ reachable from active snapshot roots
    ∪ reachable from retained recovery roots

The cleaner may reclaim a rendition only when no retained mapping can select it. Likewise, it may reclaim an old map node only when no snapshot root or delta layer depends on it. A long-running reader can therefore delay reclamation without blocking writers.

An OID that is no longer live in the newest application state may still have a rendition selected by an older snapshot. Application deletion first publishes a new map state in which the OID is absent or tombstoned. Its earlier renditions become physically reclaimable only after the oldest relevant snapshot and recovery boundary have advanced beyond them.

Application retention rules remain above the POS. The reachability layer may continue to report an otherwise unreachable OID as retained for audit, historical queries, or another policy. From the POS perspective it is simply still live.

Division of responsibilities