69.4 Recoverable Packet Map (RPM)

Logically, the RPM maps a 32-bit Seid to a LogRecordPosition, except that Seid 0x00000000 is reserved as the null Seid.

The RPM will no longer store an LSS& in every RPM node.

The RPM is a four-level radix map which supports MVCC using reference-counted nodes and copy-on-write (COW). Publishing produces immutable RPM root nodes which are used by readers.

RPM and its root node

Each Space has a level 3 RPM root. Level 3 nodes record the positions of level 2 nodes, and level 0 nodes record the positions of data packets.

The RPM is a map object which holds a reference to its root node. The root is an ordinary RpmInternalNode, no different in type from the other internal nodes. Version 2 does not use an RPM7 subclass for the root. 


class RPM
{
    RpmInternalNode* root;
};

Map-level operations such as lookup, copy-on-write mutation and publication belong to RPM. An RpmInternalNode only represents one node in the radix tree. The root is special only because the RPM owns a reference to it.

The writer starts with the current RPM root and shallow-copies only the nodes on paths modified by the transaction. Unchanged subtrees are shared. When the new root is published, the new nodes become immutable and own references to their shared children.

Only the writer changes logical RPM-node reference counts. Readers retain an immutable root and traverse it without changing reference counts within the RPM. Releasing a reader's root is deferred to the writer, as described in the MVCC chapter. The node reference counts therefore do not need to be atomic.

Persistent RPM roots

The RPM roots cannot all be stored directly in the fixed-size LSS root block because an LSS can contain many Spaces. The checkpoint state of each Partition must locate the RPM roots belonging to its Spaces. The exact representation remains to be specified.

Meaning of a read-only snapshot

A read-only snapshot is a logically immutable RPM mapping. It is not the set of RPM nodes which happen to be resident in memory when the snapshot is published. Some child nodes may be represented by their packet positions and loaded later when a reader traverses the RPM.

Readers may therefore grow the in-memory materialisation of a snapshot by loading RPM nodes. Changing a cache entry from an unloaded packet position to a loaded immutable node does not change the logical mapping represented by the snapshot.

Atomic publication of loaded child nodes

An internal RPM node uses separate arrays for the immutable child positions and the mutable atomic pointers to loaded children: 


struct RpmInternalNode
{
    uint32 refCount;
    std::array<LogRecordPosition, 256> positions;
    mutable std::array<std::atomic<const RPMNode*>, 256> children;
};

The LogRecordPosition array defines the logical child relationships, while the pointer array records their in-memory materialisation. Keeping the arrays separate gives denser pointer cache lines for resident traversal, where the positions are not needed. A null pointer means that the child has not been loaded. A reader loads and fully constructs the immutable child node, then atomically changes the pointer from null to the child pointer. Release ordering when publishing the pointer and acquire ordering when reading it ensure that another thread which obtains the pointer sees the fully constructed child node.

Publishing a loaded child node does not change any existing logical RPM-node reference count.

On x86/x64, the reader's acquire load normally compiles to an ordinary mov instruction and does not require a separate fence instruction. Reader traversal therefore has excellent performance on these processors. 


std::unique_ptr<const RPMNode> LoadChildNode(LogRecordPosition position);

const RPMNode* RpmInternalNode::GetChild(int index) const
{
    auto& childSlot = children[index];
    if (const RPMNode* child = childSlot.load(std::memory_order_acquire))
        return child;

    auto candidate = LoadChildNode(positions[index]);
    const RPMNode* expected = nullptr;

    if (childSlot.compare_exchange_strong(
            expected,
            candidate.get(),
            std::memory_order_release,
            std::memory_order_acquire))
        return candidate.release();

    return expected;
}

LoadChildNode() returns an owned reference using unique_ptr. If the compare-and-exchange succeeds, release() transfers ownership to the published snapshot. If another reader has already published the child, the losing reader's unique_ptr deletes its unpublished node. There is no memory leak.

The SegmentCache serialises access to a segment, so racing readers do not cause duplicate segment I/O. They can both allocate and deserialise a child node from the same RPM packet in the loaded segment before one wins the compare-and-exchange. The probability of this race and the amount of duplicate work are small, so no additional guard against it is required.

This approach does not allow readers to evict loaded nodes from a read-only snapshot. Clearing an atomic child pointer and deleting the node could race with a reader which has already obtained the pointer. Loaded nodes in a read-only snapshot therefore remain resident. Eviction is instead performed on the mutable RPM tree.

Strengths

  • Readers only perform atomic pointer publication.
  • Published RPM nodes remain logically immutable.
  • Release/acquire ordering safely publishes fully constructed child nodes.
  • Logical RPM-node reference counts remain non-atomic and writer-owned.
  • Reader traversal does not require a global RPM lock.

Weaknesses

  • Once a reader loads a node into an immutable snapshot, that node remains resident until the snapshot is released. A long-lived reader can therefore materialise and retain a substantial part of its RPM.
  • Eviction from the mutable RPM is limited to nodes and cache slots exclusively owned by that mutable tree. It cannot clear child pointers in an immutable node shared with a published snapshot.
  • Concurrent readers can both allocate and deserialise the same child before one wins the compare-and-exchange, although they do not perform duplicate segment I/O.

Optional later use of RCU for eviction

Status: possible later enhancement.

Read-copy-update (RCU) or epoch-based reclamation could allow loaded nodes to be evicted from read-only RPM snapshots. A reader would enter one read-side critical section for an RPM lookup and could then traverse raw child pointers without incrementing and decrementing a reference count at each radix level.

Eviction would atomically change a cached child pointer back to null and put the removed node on a retired list. The node would be deleted after all readers which could have obtained its pointer had left their read-side critical sections.

The additional overheads include:

  • entering and leaving an RCU read-side critical section for each RPM lookup;
  • accessing per-thread epoch state;
  • registering reader threads with the RCU domain;
  • maintaining retired-node lists and detecting completed grace periods; and
  • retaining retired nodes until all relevant readers have finished.

An RPM cache miss may block while a segment is loaded. The reader must not remain in an RCU critical section across that blocking I/O; it would leave the critical section before loading and then retry or publish the child safely.

The initial design does not require RCU. It favours the simpler atomic-publication approach in which nodes loaded into a read-only snapshot remain resident until the snapshot is released. RCU may be introduced later if measurements show that retained RPM nodes create significant memory pressure.

Validation

Deterministic randomised tests should compare the RPM with a simple reference map while retaining multiple older roots. After each generated update, every retained root must continue to produce the mapping that existed when that root was published.