161 CEDA MVCC Storage

CEDA implements multiversion concurrency control across two layers. The Log-Structured Store (LSS) stores opaque serial elements and provides stable read snapshots. The Persistent Object Store (POS), implemented by cxPersistStore, interprets those serial elements as persistent C++ objects and provides snapshot-consistent resident objects.

The log is the store

The LSS is log structured: the log is the store, not merely a recovery journal. One writer serialises transactions into a total order. Each transaction appends its serial elements followed by a snapshot record marking the completed transaction. An unfinished transaction at the end of the log has no such record and is ignored during recovery.

The single writer removes the need for writer conflict detection, strict two-phase locking, deadlock recovery, or transaction rollback. Only one process opens an LSS file. Writes can be accumulated into complete segments, so committing a transaction need not imply flushing a partially filled segment.

Segments, serial elements, and packets

The log is a daisy chain of fixed-size segments, commonly around 1 MB. A single-threaded SegmentWriter appends serial elements one after another. A serial element begins with a 13-byte header containing its 64-bit OID. A later serial element with the same OID is a new rendition of that element.

A serial element may cross segment boundaries and is therefore represented by a chain of data packets. Serial elements can be very large, although that is not the common case. The LSS also writes RPM packets containing nodes of the recoverable packet map.

A packet's physical location consists of a segment index and an offset within that segment.

The recoverable packet map

The recoverable packet map (RPM) maps each 64-bit OID to the physical location of its latest visible serial element. It is an eight-level radix map whose levels correspond to the eight bytes of an OID. An RPM node has up to 256 children.

Nodes at levels 1 through 7 contain physical locations of child RPM nodes. Level-0 nodes contain physical locations of serial elements. The level-7 root also records the next available OIDhigh, while level-3 nodes record the next available OIDlow for their corresponding OIDhigh.

OID allocation is structured rather than random. The high 32 bits identify a private allocation space containing up to 2³² low OIDs. Operations allocate new OIDhigh values and allocate OIDlow values within a selected high space.

Checkpoints and recovery

During an LSS checkpoint, dirty RPM nodes are appended to the log from the lowest dirty nodes upwards. Once their descendants are durable, the new root location is written to a distinguished area at the beginning of the file. A graceful close performs a checkpoint.

After an ungraceful close, recovery begins with the last checkpointed RPM root and replays the later log. Transaction snapshot records identify the complete transactions to apply and allow an incomplete tail transaction to be ignored.

Checkpoint frequency balances write amplification against recovery time. Writing checkpoints too frequently appends many dirty RPM nodes; delaying them leaves a longer log tail to scan during recovery.

Cleaning and segment reuse

A cleaner selects segments with low utilisation and copies their live packets to the end of the log. The relocated packets supersede their old physical copies, causing the source segment's utilisation eventually to reach zero.

Packets selected by any reader-pinned RPM root remain live even when a newer RPM root selects a later rendition of the same serial element. A source segment cannot be reclaimed while an active snapshot still resolves a packet to its old physical location.

Reusable segment identifiers are held in the Free Segment Stack (FSS). A segment after the last checkpoint cannot return to the FSS even when it has no live packets, because recovery may still need to scan that part of the log. Checkpointing advances this reclamation boundary and allows eligible segment identifiers to return to the FSS.

Published RPM snapshots

The in-memory RPM uses copy-on-write nodes. Published roots and their shared unchanged descendants form a DAG. A reader pins one published root and uses it for every serial-element read, while the writer continues changing a separate working view.

Publishing an RPM root for every writer transaction would impose unnecessary cost at transaction rates approaching one million per second. Roots are therefore published in batches or epochs. A reader begins with the latest valid published root; it does not force publication of a newer root. Allowing new readers to begin slightly stale lets many readers share the same snapshot and substantially reduces the number of retained RPM nodes.

Any number of readers may use a published root concurrently. Roots and nodes are reference counted. Starting a reader retains its root; ending the reader releases it. When a stale root's count reaches zero it is deleted, recursively decrementing its children. Nodes shared with another root remain alive, while unreachable stale nodes are automatically reclaimed from memory.

LSS read and write transactions

The LSS exposes the snapshot lifetime explicitly:

auto txn = lss.BeginReadTxn();
auto serialElement = lss.Read(txn, oid);
lss.EndReadTxn(txn);

BeginReadTxn() returns a handle that pins the selected RPM root. Every call that reads a serial element takes that handle and resolves the OID through the same root. EndReadTxn() releases the handle and may consequently release a stale root and RPM nodes no longer reachable from any reader.

BeginWriteTxn() likewise returns a transaction handle that may be passed to serial-element reads as well as writes. It gives the single writer a consistent view containing the latest committed renditions together with the transaction's own writes. The writer can therefore load an existing serial element before replacing it without opening a separate read transaction.

Persistent spaces

The POS divides persistent objects into persistent spaces, or PSpaces. A PSpace owns an OIDhigh and allocates its objects from the corresponding low OID space. It is both an allocation domain and a concurrency domain.

One mutex protects all objects and POS metadata within a PSpace. POS operations normally lock only one PSpace at a time. An operation that exceptionally locks several PSpaces acquires them in a total order, making deadlock impossible without strict two-phase locking.

A transaction updates exactly one PSpace. Inter-PSpace OID references are not permitted, and constraints cannot span PSpaces. There is consequently no transactional invariant that requires an atomic commit over several PSpaces and no need for a multi-PSpace transaction protocol.

The mutex protects the mutable frontier of the PSpace. Immutable ROT nodes and immutable resident object renditions may be read without holding it. This keeps mutation simple without preventing concurrent access to published snapshots.

Ownership within a PSpace

This design proposes a corresponding restriction on Predica's logical model: each persistent object has exactly one owning location within its PSpace. Other relationships do not become additional owners merely because they provide another way to reach the object. For example, a supplier may own its shipments while a part has a non-owning relationship to the shipments in which it occurs.

One possible surface syntax is an owns annotation on the owning relationship:

entity Shipment
{
    Supplier supplier;
    Part part;
}

entity Supplier
{
    owns object Shipment shipment* where shipment.supplier = this;
}

entity Part
{
    Shipment shipment* where shipment.part = this;
}

The two shipment attributes retain the same predicate and navigation semantics, but only Supplier.shipment owns its members. Deleting a supplier therefore deletes its shipments, whereas the relationship from a part does not give the part ownership of them. Changing a shipment's supplier transfers its ownership.

Updates within the PSpace must preserve referential integrity. Deleting an owner deletes its owned objects, and every non-owning relationship to those objects is derived or removed by the same transaction. It cannot be left dangling. Because OID references do not cross PSpace boundaries, this rule can be enforced under the one PSpace mutex and checked at its transaction boundary.

Deleting a shipment likewise removes it from both relationship extensions. The shipment identifies the supplier and part that refer to it, so the compiler can update any physical inverse indexes directly rather than searching the PSpace. These changes form part of the same transaction as the deletion.

Unique physical ownership avoids persistent reference counts for ordinary object lifetime. The proposed logical restriction concerns ownership, not reachability: several logical paths may still reach the same entity, but only one of them is owning. Reference counting used by the MVCC ROT and RPM DAGs is a separate, in-memory mechanism for retaining shared immutable versions while readers use them. The proposal is recorded here without yet imposing the restriction on the rest of this specification.

The mutable writer ROT

Each PSpace has one mutable ROT root used by writers holding the PSpace mutex. That root owns the LSS transaction handle returned by BeginWriteTxn(). A cache miss is resolved through that handle, so objects loaded for reading or writing belong to the writer's consistent LSS view and are the latest versions available to the PSpace.

ROT nodes private to the mutable writer view are marked dirty and may be changed in place while the mutex is held. A clean node may also be reachable from a published reader root and is immutable. On the first update beneath such a node, the writer copies the node and changes the private copy. Only the path affected by the update is copied; all unchanged subtrees remain shared.

Snapshot resident-object tables

Each PSpace has a Resident Object Table (ROT) mapping an OID to the resident C++ object rendition for that snapshot. Within one snapshot it supplies the canonical C++ object for an OID. The ROT is an in-memory copy-on-write radix structure with published snapshot roots, analogous to the RPM.

Readers pin snapshot ROT roots. Shared ROT nodes remain alive across snapshots, and reference counting recursively deletes stale nodes and releases resident object renditions after their last reader completes.

Each snapshot ROT root owns an LSS read-transaction handle. That handle pins the corresponding RPM root. A ROT cache hit therefore returns an object from the correct object snapshot, while a cache miss or lazy load resolves the persistent object through the same LSS snapshot. Releasing the last reference to the ROT root releases its LSS transaction handle and allows the two snapshot structures to be reclaimed coherently.

Publishing a PSpace snapshot

Creating a new PSpace snapshot requires the PSpace mutex. While holding it, the implementation freezes the mutable ROT root and the resident C++ object renditions reachable from that view. They become immutable and can be published to readers. The implementation then creates a fresh mutable writer root that initially shares the frozen nodes and objects.

Subsequent writers use copy-on-write for resident objects as well as ROT nodes. Reading an immutable object does not copy it. The first attempt to mutate it clones that object rendition and changes the writer ROT path to refer to the clone. Consequently, a writer may read millions of resident objects and change one while cloning only the changed object and the affected ROT path.

Freezing stable object renditions allows their serialisation and the writing of dirty objects to proceed after the PSpace mutex has been released. Physical I/O therefore need not extend the critical section. Buffered serialisation into the LSS segment cache may further separate snapshot publication from device writes.

Snapshot publication has a tunable cadence. Publishing too often increases copy-on-write work, reference-count traffic, and the number of simultaneously retained roots and object versions. Publishing too infrequently means that a new reader begins from an older view. Readers take the most recently published snapshot rather than forcing the writer to create one, so many readers can share a root.