69.5 Recoverable Packet Map (RPM)

Purpose and scope

An RPM is a variable-height radix map from a 32-bit key to a LogRecordPosition. The RPM module does not reserve key zero or interpret the mapped packets. A Space uses an RPM to map Seids to data packets, while a SpaceDirectory uses the same implementation to map SpaceIds to Space packets. The containing abstraction decides whether a key is valid and what its value means.

Version 2 treats RPM nodes as passive mapping data. They do not contain an LSS& or initiate work in other LSS modules. Operations which need the node loader, SegmentWriter or SUT receive those dependencies explicitly. Nodes do not cache a parent pointer, child index, level or key prefix; traversal functions carry that context. Omitting a parent pointer is also necessary because copy-on-write sharing produces a DAG across RPM roots.

Seid and SpaceId allocation are not RPM responsibilities. A Space records its next Seid and a SpaceDirectory records its next SpaceId. The partition mutex protects mutable RPM state; there is no separate root-node mutex.

Height and key ranges

An RPM has between zero and four levels. Leaf nodes are at level 0. An empty RPM has height zero and no root. A height-one RPM has a leaf root. Each additional byte required to represent the greatest mapped key adds one internal level, up to a level-3 root at height four.

When a key lies beyond the current range, the writer creates internal roots until the key is representable and installs the previous root at child index zero. Height is determined by the greatest mapped key, not by the number of mappings. The initial implementation does not reduce height after deletions; monotonic allocation makes repeated shrinking and regrowth unnecessary.

The height is the height of the current logical mapping, including changes made in memory since the last checkpoint. It is not necessarily the height recorded on disk. For example, inserting a key may grow a persisted height-two RPM to height three by creating a new dirty root in memory. Until the next checkpoint is published, the recoverable RPM on disk still has height two.

When the current height is nonzero, its root is resident at level height - 1. Descendants may be dirty resident nodes, clean resident nodes, or unloaded persistent nodes represented only by positions. A current height-four RPM may therefore consist in memory of a dirty level-3 root above a mixture of resident and persistent descendants.

The diagram shows the maximum-height case. Shorter RPMs use the corresponding lower suffix of the same radix structure.

Map and node representation

Internal and leaf nodes share mapping and ownership metadata. Internal nodes additionally cache pointers to materialised child RPM nodes. Leaf positions refer to data packets; internal positions refer to persistent RPM-node packets.

using LogRecordPosition = uint64;

struct RpmNodeCommon
{
    uint32 refCount;
    LogRecordPosition persistedPosition;       // Zero if never persisted
    uint32 persistedTotalPacketSize;
    bool isDirty;
    uint16 numEntries;
    std::array<uint64, 4> occupancy;
    std::array<LogRecordPosition, 256> positions;
};

struct RPMNode;

struct RpmInternalExtra
{
    mutable std::array<std::atomic<const RPMNode*>, 256> children;
};

struct RpmLeafExtra
{
    mutable std::atomic<uint64> timeLastAccessed;
};

struct RPMNode
{
    RpmNodeCommon common;
    union
    {
        RpmInternalExtra internal;
        RpmLeafExtra leaf;
    };
};

struct RPM
{
    uint8 height;                       // Between 0 and 4 inclusive
    RPMNode* root;                       // Null iff height is zero
};

struct PersistentRpmRoot
{
    uint8 height;
    LogRecordPosition rootPosition;             // Zero iff height is zero
};

The active union member is determined by traversal level: level zero uses leaf and higher levels use internal. Construction and destruction functions receive that level and manage the union explicitly. This C-like representation avoids virtual dispatch. Root height supplies its level, and recursive operations pass the decremented level to children.

The 256-bit occupancy bitmap says which positions are present and permits sparse serialization as a bitmap followed by the positions whose bits are set. numEntries is the population count of the bitmap and allows serialized size to be calculated without rescanning it. The values must agree when a node is validated. Although zero is also the null LogRecordPosition, the bitmap remains useful because it compactly identifies the indexes included in the serialized node.

Atomic child pointers are materialisation caches, not part of the persistent logical mapping. The occupancy bitmap and positions define that mapping. Publishing or evicting a resident child does not make its parent dirty.

Use by Spaces and the SpaceDirectory

struct Space
{
    SpaceId id;
    Seid nextSeid;
    RPM rpm;
};

struct SpaceDirectory
{
    SpaceId nextSpaceId;
    RPM rpm;
};

A Space packet records its allocation state and enough RPM state to locate its root. The partition's top-level checkpoint state similarly records its SUT and SpaceDirectory state. During checkpoint preparation, dirty RPM nodes are written bottom-up before the state which records their root positions.

PersistentRpmRoot is the checkpoint representation used to open an RPM. Its height and root position describe the recoverable mapping on disk and may lag behind the current in-memory RPM while mutations are uncheckpointed. Opening loads the referenced root and constructs a resident RPM; the persistent root position then also appears in that root node's persisted metadata. Keeping the checkpoint reference separate avoids requiring a dirty in-memory root to have a corresponding position on disk.

The initial implementation supports only the primary Partition and does not implement a PartitionDirectory. Partition identifiers and the persistent format do not preclude adding more partitions later.

Lookup and lazy materialisation

Lookup receives a loader explicitly. It synchronously loads persistent RPM nodes as required. The containing abstraction, rather than the RPM module, decides how an absent mapping is reported.

LogRecordPosition LookupRpm(const RPM& rpm, RpmNodeLoader& loader, uint32 key);

A published RPM root is a logically immutable mapping, not the set of descendants which happened to be resident when it was published. Readers may materialise persistent descendants without changing the mapping.

To materialise a child, a reader fully constructs a candidate and then publishes it with compare-and-exchange. Release ordering on successful publication and acquire ordering when reading the slot ensure that another reader sees the fully constructed node. A losing candidate remains private and can be deleted immediately.

RpmNodeOwner LoadRpmNode(LogRecordPosition position, int level);

const RPMNode* GetChild(
    const RPMNode& parent,
    int index,
    int childLevel)
{
    auto& slot = parent.internal.children[index];
    if (const RPMNode* child = slot.load(std::memory_order_acquire))
        return child;

    auto candidate = LoadRpmNode(parent.common.positions[index], childLevel);
    const RPMNode* expected = nullptr;
    if (slot.compare_exchange_strong(
            expected,
            candidate.get(),
            std::memory_order_release,
            std::memory_order_acquire))
        return candidate.release();

    return expected;
}

The SegmentCache coalesces access to the containing segment, although racing readers may still deserialize separate candidate nodes before one wins publication. This duplicate work is acceptable unless measurement shows otherwise.

RpmNodeOwner is a move-only owner which remembers the node level and invokes the corresponding union destructor. Its get() and release() operations have the same ownership meaning as those on std::unique_ptr.

MVCC and copy-on-write

The partition mutex protects mutable RPMs. A writer shallow-copies only nodes on modified paths; unchanged subtrees are shared with published roots. Publishing makes the new logical root immutable. Readers retain an immutable partition view and traverse it without the partition mutex.

The intrusive refCount records owning in-memory references from RPM roots and resident child slots. Reference-count changes associated with copy-on-write and root retirement occur under the partition mutex. A reader which publishes a newly loaded node transfers the candidate's initial owning reference into the child slot and therefore does not increment an existing shared count. A losing unpublished candidate can be destroyed directly.

Copying an internal node for mutation copies its logical positions and may share already resident children by acquiring references under the partition mutex. The new logical node is dirty. Loading a node from disk produces a clean node, and changing only a materialisation-cache pointer does not change dirty state.

Deserialization and validation

void Deserialise(InputArchive& archive, RPMNode& node, int level);

The traversal level determines whether the packet represents a leaf or internal node. Deserialization reads the occupancy bitmap and populated positions, verifies that numEntries matches the bitmap population, initializes resident child pointers to null, and records the packet position and total size.

An unsafe cxSerialise archive may use unchecked pointer advancement after the enclosing segment and packet boundaries, sizes and checksum have been validated. A 64-bit checksum makes accidental corruption extremely unlikely, but it does not replace structural validation of counts, sizes and levels. Version 2 does not attempt to parse an LSS file safely after malicious modification.

Writing dirty nodes

uint32 GetSerialisedSize(const RPMNode& node, int level);
void Serialise(OutputArchive& archive, const RPMNode& node, int level);
void WriteDirtyRpmNodesToLog(SegmentWriter& writer, SUT& sut, RPM& rpm);

Dirty nodes are visited depth-first and written bottom-up. Once a dirty child has been written, its new position is available when its parent is serialized. The occupancy bitmap and numEntries determine serialized size before space is reserved in the SegmentWriter, allowing serialization directly into the destination segment.

Writing a new RPM packet increases utilization of its destination segment. It does not necessarily make the node's previous packet obsolete. An older MVCC snapshot may still need to load that packet, and a previous recoverable checkpoint may still refer to it. Previous RPM packets enter a deferred-retirement set and reduce SUT utilization only after both conditions are true:

1. no retained in-memory snapshot can reach the old logical node; and
2. no checkpoint which may be selected during recovery refers to the old packet.

The persisted position and total packet size recorded on a node identify the packet to retire. In-memory refCount alone is not a persistent-packet reference count and must not be the sole test for SUT obsolescence. Snapshot and checkpoint retirement jointly release deferred packets when they are no longer reachable.

After serialization, the new position and total packet size become the node's persisted metadata and its logical dirty flag is cleared. The operation runs with the partition mutex held, serializing mutation of the SegmentWriter, SUT and mutable RPM.

Resident-node eviction

Persistent positions remain when resident child pointers are cleared, so eviction changes neither the logical mapping nor its height. A non-root internal node with no resident child pointers should itself be removed from its parent. Evicting a leaf can therefore permit resident ancestors to be pruned up to, but not including, the root. This invariant concerns resident pointers; an evicted internal node may still describe many persistent children.

Leaf nodes record approximate last-access time using a relaxed atomic logical clock. Approximate values suffice because eviction only needs to prefer colder nodes; reader traversal must not acquire a global LRU mutex.

The evictor may scan immutable roots retained by partition views, build a histogram of leaf access times, choose a threshold, and clear suitably cold child slots with compare-and-exchange. Shared node objects must be selected by identity so traversal through several roots does not treat one allocation as several independent candidates.

Safe reclamation after eviction

Clearing a child pointer cannot immediately release its owning reference because a reader may already hold the raw pointer. RPM traversal therefore occurs inside an epoch or RCU read-side critical section. Evicted slot references are placed on a retired list and released only after every reader which could have observed the old pointer has left its critical section.

The critical section is scoped to RPM traversal, normally one lookup. It is not held for the lifetime of an IPartitionView, an input stream or a public API call after the required LogRecordPosition has been obtained. If a cache miss requires blocking I/O, lookup leaves the critical section, loads the candidate, re-enters and retries publication. Long I/O waits must not delay an epoch grace period.

Reader registration, epoch publication, nesting, memory ordering, thread termination and grace-period detection must be provided by a proven epoch/RCU implementation or specified as a separate concurrent algorithm. The approximate logical clock used to choose eviction candidates is not the reclamation epoch and cannot prove that deletion is safe.

After a grace period, releasing a retired slot reference is handed to the partition's serialized ownership path. If other roots or slots still reference the node, its count remains nonzero. Destruction recursively releases resident children using the known traversal level.

Validation

Deterministic randomized tests should compare the RPM with a simple reference map while retaining older roots. Tests must cover height growth, sparse keys, deletion, checkpoint replacement, lazy loading and eviction. Every retained root must continue to produce the mapping that existed when it was published.

Concurrent tests should repeatedly publish and evict children while readers traverse retained roots. Instrumented builds should verify occupancy counts, reference counts, deferred persistent-packet retirement and the rule that no retired node is destroyed before its read-side grace period.