58 Proposed MVCC support in cxPersistStore

Status: proposal. This chapter describes intended behaviour, not the current cxPersistStore implementation.

This proposal builds on the proposed MVCC support in the LSS. The LSS provides stable snapshots of persisted serial elements; cxPersistStore composes each of those bases with an immutable per-PSpace object delta so application readers can observe stable states that have not yet been written to the LSS.

Layered overview

cxPersistStore partitions the objects in one LSS into PSpaces. Each PSpace has its own mutex, mutable Resident Object Table (ROT), dirty-object state, and immutable ROT snapshots. A user transaction is declared on a PSpace, not on the whole PersistStore. The PSpace is therefore the unit of logical mutation and snapshot isolation above the LSS.

cxPersistStore
    ├── PSpace A: mutex + mutable ROT + immutable ROT snapshots
    ├── PSpace B: mutex + mutable ROT + immutable ROT snapshots
    └── PSpace C: mutex + mutable ROT + immutable ROT snapshots
             │
             └── one shared LSS: concurrent readers + one serial writer

The LSS and a PSpace require snapshots for different reasons and at very different rates. An LSS snapshot preserves a map from Seids to serial elements already applied to the LSS. A PSpace snapshot preserves the object state visible to an application operation, including edits that have not yet been applied to the LSS. Consequently, an immutable ROT root does not always correspond to a newly published RPM root.

A PSpace snapshot is composed of an immutable ROT root and a retained LSS base snapshot. The ROT embodies an in-memory delta for that PSpace relative to the base:

PSpace snapshot S = LSS base snapshot B + immutable PSpace ROT delta D

Several successive snapshots of one PSpace can share the same LSS base while representing different in-memory deltas. Different PSpaces can publish independently. This is necessary for interactive applications. Moving an object with a mouse may produce updates at approximately 50 Hz, and asynchronous calculations need frequent stable inputs so that readers do not block writers and independent calculations can run in parallel. Writing each of those application states to the LSS would be wasteful. A PSpace can instead publish cheap copy-on-write ROT snapshots at the required interactive rate, while cxPersistStore applies accumulated deltas from one or more PSpaces to the shared LSS every few seconds.

Where concurrency comes from

The mutex of PSpace A does not prevent a transaction from mutating PSpace B. Writers in well partitioned PSpaces can therefore run concurrently in memory. Immutable ROT snapshots allow readers and asynchronous calculations to continue without taking the PSpace writer mutex. On a ROT cache miss, the LSS already permits different threads to read different serial elements concurrently. The single LSS writer serialises only the eventual physical application of PSpace deltas; it does not serialise ordinary PSpace mutation or immutable reads.

This means the database can support considerably more concurrency than the single LSS writer might initially suggest. Its scalability depends on placing independently updated object graphs in separate PSpaces and avoiding unnecessary shared mutable state. The design must preserve concurrent LSS reads: an immutable snapshot read must not acquire the LSS writer lock or a PersistStore-wide lock.

Three independent cadences

The design separates three events which must not be conflated:

Publishing a PSpace snapshot. That PSpace's mutable ROT root is frozen and a new mutable root is created by copy-on-write. Each PSpace can do this independently and frequently enough to feed its user-interface readers and asynchronous calculations.
Applying PSpace deltas to the LSS. At a lower rate, normally every few seconds, cxPersistStore selects stable deltas from one or more dirty PSpaces and serialises them through one LSS write transaction. CloseAndPublishSnapshot() turns the resulting global RPM state into a new retained LSS base snapshot.
Flushing completed LSS transactions to durable storage. This is independent of both snapshot cadences. A transaction can request a synchronous flush on close through FlushWhenClose(); the same force-flush facility is available to user transactions declared on a PSpace through cxPersistStore. Without a forced flush, the LSS LazyFlusher periodically flushes completed work according to LssSettings::flushTimeMilliSec, which defaults to 1000 milliseconds.

The first cadence controls how quickly readers and calculated results observe a stable application state. The second controls how much in-memory change can accumulate before it is represented in the LSS. The third controls the amount of completed LSS work that can be lost in a process or machine failure. Relaxed durability permits the common editing case to avoid a disk flush for every mouse movement, while an operation with an external durability requirement can explicitly force a flush.

The writer-to-reader transition is especially appropriate when MVCC is exposed by layers above the LSS. When cxPersistStore applies selected immutable PSpace deltas to the LSS, it uses the read transaction returned by CloseAndPublishSnapshot() as the new persisted base for subsequent PSpace snapshots. This pins exactly the LSS state produced from that persistence batch. A call to OpenReadTransaction(false) would instead publish whichever writer state happened to be current, independently of the selected PSpace cutoffs. It is therefore the wrong composition mechanism. The Boolean API is not part of this design; it can be reconsidered separately if direct LSS clients establish a concrete requirement for it.

PSpace snapshots over an LSS base

Each immutable ROT root represents one snapshot of one PSpace. It retains an LSS base snapshot and records that PSpace's object-level delta relative to the base. Many immutable ROT roots, belonging to one or several PSpaces, can share one base. The retained base owns the ILssReadTransaction that pins its global RPM root; an individual ROT root retains the base rather than necessarily owning a distinct LSS read transaction.

When cxPersistStore opens, it obtains the initial base with OpenReadTransaction(). A later persistence batch obtains its replacement base from CloseAndPublishSnapshot(). Replacing a PSpace's current base does not alter its existing ROT snapshots: an old base remains pinned until the last ROT root, reader, or calculation in any PSpace that depends on it is released.

                         ┌── PSpace A snapshot A101 with delta DA101
LSS base snapshot B100 ──├── PSpace A snapshot A102 with delta DA102
                         ├── PSpace B snapshot B51  with delta DB51
                         └── PSpace C snapshot C7   with delta DC7

Partition independence and global LSS bases

An RPM root is global to the LSS file, whereas a ROT root concerns one PSpace. PSpaces can therefore retain global LSS roots with different transaction sequence numbers. This is safe for ordinary object access because each PSpace reads and writes its own OID/Seid domain. A persistence batch that changes PSpace A need not force unchanged PSpace B to publish a new ROT snapshot merely because the global RPM root advanced.

PersistStore-wide metadata, including the PSpace map and any serial elements not owned by one PSpace, requires an explicit base-selection policy. Such metadata must not be interpreted through an arbitrary PSpace snapshot. Similarly, an operation that reads several PSpaces holds a collection of PSpace snapshots. Ordinary PSpace transactions do not imply that this collection is one atomic PersistStore-wide snapshot; a requirement for cross-PSpace consistency needs explicit coordination.

A lookup first consults the immutable ROT snapshot. A resident object entry supplies the object rendition and a tombstone reports that the object does not exist. If there is no entry, the object is loaded through the LSS read transaction retained by the base. Every lazy load therefore uses the same base as that PSpace's ROT delta and cannot accidentally advance to a newer RPM snapshot. The dirty state of the ROT path and entry records whether the object is part of the delta or is merely a clean cached object loaded from the base.


Read(snapshot, oid)
{
    if (auto entry = snapshot.rot.Find(oid))
    {
        if (entry.IsTombstone())
            return DoesNotExist;
        return entry.Object();
    }

    return snapshot.lssBase->Read(oid);
}

Delta lifetime and eviction

Dirty ROT nodes and the dirty object renditions or tombstones reachable through them embody the delta pending application to the LSS. The delta contains objects created since the base, rewritten renditions of existing objects, and tombstones for deleted objects. Freezing a mutable ROT does not make those entries clean; it makes that particular delta immutable. An absent ROT entry means "consult the LSS base" and therefore cannot also represent deletion. A tombstone must remain in the delta for as long as the snapshot exists.

An object rendition that forms part of the delta cannot be evicted if eviction would leave only the older rendition in the LSS base. Reloading it from that base would make the snapshot revert. The initial implementation therefore strongly retains every new or rewritten object rendition and every deletion tombstone required by a live snapshot. Clean objects whose values come entirely from the LSS base can be evicted and reloaded through the retained LSS read transaction.

Later implementations can replace a retained C++ object with another snapshot-stable representation, such as an immutable serialised byte sequence, a compact delta record, or a record in a spill file. The invariant is not that every delta object must remain materialised as a C++ object; it is that the snapshot must retain enough information to reproduce exactly the same Seid-to-serial-element and OID-to-object mappings without consulting a newer state or falling back to an older base rendition.

Cheap high-frequency ROT snapshots

Publishing a PSpace snapshot freezes that PSpace's current mutable ROT root and publishes it as immutable. A new mutable root initially shares the frozen nodes and object renditions. The next write under that PSpace's mutex copies only the changed object and affected ROT path. Snapshot creation must not scan the complete ROT or serialise every dirty object; delta membership is maintained incrementally as objects are created, rewritten, and deleted.

Publishing a new latest snapshot releases the latest-reference held on the preceding snapshot. If no reader or calculation retained the old root, it is destroyed immediately and its unshared ROT paths and delta objects are reclaimed. A high publication rate therefore does not by itself retain a long history. Memory grows only for snapshots still used by readers or asynchronous work, plus COW nodes and object renditions shared with those snapshots.

Asynchronous calculations retain the immutable PSpace ROT root that defines their input. Calculations for different snapshots or different PSpaces can run concurrently without blocking PSpace writers and without observing changing inputs. Each result records the identity of its input PSpace snapshot. When it completes, cxPersistStore installs it only where it is valid; a slow result for an older snapshot must not overwrite a result for a newer snapshot. Work scheduling can cancel obsolete calculations or coalesce pending requests so that a 50 Hz edit stream does not require every intermediate calculation to run to completion.

Periodically applying PSpace deltas to the LSS

At the persistence cadence, cxPersistStore selects an immutable ROT snapshot as the cutoff for each dirty PSpace included in a batch. Because each cutoff is immutable, serialization can proceed without allowing later edits to change what is being written. The selected deltas are applied through one serialized LSS write transaction. Calling CloseAndPublishSnapshot() at the end of that transaction publishes the resulting global RPM root and returns the already-pinned LSS read transaction for the new shared base.

Selecting a cutoff requires the PSpace mutex only long enough to retain the immutable root and record its generation. Serialization and LSS writing occur after releasing that mutex, while new user transactions continue against the PSpace's newer mutable ROT root. The persistence worker can collect cutoffs from several PSpaces without holding all of their mutexes throughout object serialization or LSS I/O.

selected cutoffs:  PSpace A snapshot A104, PSpace C snapshot C28

before applying A104:  current A = B100 + DA104 + changes after A104
before applying C28:   current C = B100 + DC28  + changes after C28

apply DA104 and DC28 in one LSS transaction; call CloseAndPublishSnapshot()
                                      ↓
new global LSS base B105:             B100 + DA104 + DC28
current A after rebasing:              B105 + changes after A104
current C after rebasing:              B105 + changes after C28

Earlier PSpace snapshots remain unchanged as their old base plus their own delta. New snapshots of A and C use B105 as their base. A PSpace not included in the batch can retain B100. Rebasing mutable state must not simply clear dirty flags: an object written from a cutoff may have been edited again while serialization was in progress. Generation-tagged delta entries or comparison with the immutable cutoff identifies which changes were included in B105 and which later changes must remain dirty.

If PSpace B later persists a delta still based on B100, its LSS write transaction nevertheless starts from the latest global LSS state, B105, and applies only B's own Seid changes. It must not reconstruct and publish the whole older B100 map, which would erase the persisted changes from A and C. Disjoint PSpace Seid domains make this merge straightforward; updates to PersistStore-wide metadata require the explicit coordination described above.

Visibility and durability remain separate. CloseAndPublishSnapshot() makes B105 available as an LSS base but does not by itself require a synchronous disk flush. If the declaring PSpace transaction requests forced durability through cxPersistStore, that request propagates to FlushWhenClose() on the LSS transaction. Otherwise the LazyFlusher flushes according to LssSettings::flushTimeMilliSec, whose default is 1000 milliseconds.

A PSpace transaction that requests forced durability cannot merely leave its delta for the normal multi-second persistence cadence. Closing that transaction waits until a persistence batch containing at least its cutoff has completed and the corresponding LSS flush has returned. Other dirty PSpaces can be included in the same batch, and the flush also makes all preceding completed LSS transactions durable.

After the LSS API is changed, each PSpace must maintain immutable ROT deltas and retain their LSS bases. cxPersistStore must batch selected PSpace deltas into LSS transactions and rebase each participating PSpace's later mutable state without losing edits made after its cutoff.

Preparing objects in a temporary PSpace

cxPersistStore can create and populate objects in a temporary PSpace and later transfer them into a parent PSpace. Most construction then occurs while holding only the temporary PSpace's mutex. The parent mutex is needed only for the transfer, reducing contention on a heavily used parent and preventing readers of the parent from observing partially prepared objects.

The transfer acquires write access to both PSpaces in the defined lock order and transfers object ownership, dirty-object state, deletion state, and resident ROT entries as one operation. The parent snapshot immediately before the transfer contains none of the transferred objects; the first parent snapshot published afterward contains the complete transferred state. An already-retained snapshot of the temporary PSpace remains immutable and readable for its lifetime even though the mutable temporary PSpace has transferred its objects.

The current transfer machinery must be audited for in-place changes to object or CSpace ownership metadata. It must not mutate an object rendition reachable from an older immutable temporary-PSpace snapshot. Where ownership metadata is observable through the snapshot, transfer creates the parent rendition by copy-on-write and leaves the old rendition intact. ROT and dirty-set transfer likewise updates only the new mutable roots, not retained snapshot roots.

Transferred dirty objects remain pending application to the LSS under the parent PSpace. A later persistence batch serialises them with the parent's selected cutoff. Transfer therefore shortens the parent's logical critical section without requiring construction-time mouse movements, imports, or derived work to become separate LSS transactions.

Snapshot identity and diagnostics

A PSpace snapshot identity is distinct from the LSS transaction sequence number and is scoped to its PSpace. Several ROT snapshots in one or more PSpaces can share one LSS base sequence while carrying different deltas. Asynchronous results and ROT-version comparisons therefore use the identity of the relevant PSpace snapshot, not merely the sequence number of the retained LSS base.

Resource limits and operational policy

cxPersistStore must report these values per PSpace: the number and age of retained ROT snapshots, the LSS base shared by each snapshot, bytes retained in immutable deltas, and asynchronous calculations holding old roots. Aggregate statistics must show which PSpaces and LSS bases account for retention. A rapid publication rate is harmless when superseded roots are unused and released immediately. Sustained growth indicates real outstanding readers or calculations. The scheduler can apply backpressure, cancellation, or latest-value coalescing to calculations without invalidating a snapshot already in use.

Validation and tests

Required cxPersistStore tests include:

Many immutable ROT snapshots from one or several PSpaces share one LSS base while returning their distinct new, rewritten, and deleted object states.
Evicting clean ROT cache entries reloads through the retained base, while delta renditions and tombstones cannot revert to that base.
Replacing the latest ROT snapshot immediately reclaims its predecessor when no reader or calculation retained it.
A slow calculation over an old ROT snapshot observes stable inputs and cannot overwrite a result belonging to a newer snapshot.
Transactions mutate different PSpaces concurrently while mutation within each PSpace remains serialised by its mutex.
Readers in different PSpaces concurrently load different serial elements without acquiring the LSS writer lock.
Applying immutable cutoffs from several PSpaces in one LSS batch does not clear later edits from any participating mutable delta.
A PSpace omitted from a persistence batch continues using its existing base and snapshots correctly.
A multi-PSpace reader observes the explicitly selected component snapshots and is not accidentally presented as a globally atomic snapshot.
Objects constructed in a temporary PSpace become visible in the parent as one complete transfer while older retained snapshots remain unchanged.
Forced durability flushes the selected cutoff synchronously, while ordinary updates remain eligible for periodic lazy flushing.

Suggested implementation sequence

Represent each PSpace snapshot as an immutable ROT delta over a retained LSS base, allowing snapshots from several PSpaces to share that base.
Strongly retain delta renditions and tombstones until another snapshot-stable representation exists.
Publish and reclaim high-frequency COW ROT snapshots independently in each PSpace and independently of the lower-frequency LSS persistence cadence.
Batch immutable cutoffs from several dirty PSpaces into one LSS transaction and rebase each participating mutable state without clearing later changes.
Associate asynchronous calculated results with their input PSpace snapshots and prevent obsolete results from replacing newer results.
Preserve temporary-to-parent PSpace transfer as a short, atomic parent update under ordered PSpace locks.
Propagate forced durability from PSpace transactions declared through cxPersistStore while retaining LazyFlusher as the default durability path.

The resulting design separates logical publication from physical persistence. A PSpace can cheaply publish immutable application snapshots as often as its readers and calculations require, while cxPersistStore periodically batches stable deltas through the single LSS writer. Retained LSS bases, ROT deltas, and tombstones together preserve each PSpace snapshot until its final user releases it.

Previous57 Proposed MVCC support in the LSS Next59 Backup enhancements