44 Recoverable Packet Map (RPM)

Logical contents

The Recoverable Packet Map (RPM) is a persistent map from Seid to LogRecordPosition. It records every data packet in a packet chain, not only the head packet. The head and each overflow packet have their own Seid and their own entry in the RPM. The RPM also records the locations of RPM packets. For each entry, the LogRecordPosition identifies the physical location in the log of the latest version of that packet. There is one RPM for the LSS.

The RPM also maintains the state used to allocate Seids. It records the next available SeidHigh and, for each SeidHigh, the next available SeidLow.

Structure

The RPM is implemented as an eight-level radix tree keyed by the eight bytes of a 64-bit Seid.

Each RPM node in the radix tree stores an array of 256 LogRecordPosition values, using an index in the range [0,255]. The storage space required is at most 256 x 8 = 2 KiB. The levels are labelled from 0 to 7 where 0 is at the "bottom" and 7 is at the "top" of the radix tree. There is exactly one RPM-node at level 7. This node is stored in the root block of the LSS. All the other RPM-nodes are stored in the log as indivisible (packet) log records (indivisible means that the RPM-node can't be broken up into a chain of packets, as done for serial elements).

The level 7 RPM-node in the root block stores the current locations of the RPM-nodes at level 6. The RPM-nodes at level 6 store the current locations of the RPM-nodes at level 5. This continues until we get to the RPM-nodes at level 0. These store the current locations of the packets that contain actual data.

Seid allocations increment the next SeidLow or SeidHigh as ordinary unsigned integers. This fills RPM-nodes in index order at level 0 (for SeidLow) or level 4 (for SeidHigh). When a level 0 RPM-node is filled, we create a new level 0 RPM-node under the parent (level 1) RPM-node. If this level 1 RPM-node is full then we create a new level 1 RPM-node under the parent (level 2) RPM-node. This "create RPM-node on overflow" concept continues up through the levels, corresponding to normal base-256 integer counting. Therefore the fan-out at a given node will often be much less than 256. When an RPM-node is serialised to disk, only the portion of the array of LogRecordPosition that is in use is written to the archive.

In-memory and on-disk state

The on-disk RPM is a snapshot taken at the last checkpoint. It is updated only by a checkpoint and does not change as individual transactions write serial elements. The SUT follows the same model: its in-memory state is current, while its on-disk state is updated at checkpoints.

The in-memory RPM represents the current logical state, but only a subset of its nodes need to be resident. Nodes from the checkpointed RPM are faulted into memory on demand. A clean resident node contains no changes relative to its on-disk representation and may be evicted and loaded again later.

As the Segment Writer writes serial elements as packet chains into segments in memory, it updates the in-memory RPM with the locations of the new data packets. The affected RPM nodes are marked as dirty. Collectively, the dirty nodes record the delta between the current in-memory RPM and the checkpointed RPM on disk. A dirty node cannot be evicted because its changes do not yet exist in the on-disk RPM.

Dirtiness is propagated eagerly up through the ancestors all the way to the root node at level 7. This traversal up through the ancestors can terminate as soon as a node is encountered that has already been marked as dirty.

Checkpoints

When a checkpoint is performed, the dirty RPM nodes at level 0 are written to the log as packet records. This updates the positions of those level 0 nodes recorded in their dirty level 1 parents. The dirty level 1 nodes are then written, followed by each successive dirty level through level 6. The RPM must therefore be written in bottom-up order, beginning with level 0 and ending with level 6.

Finally the level 7 RPM node, which has also been marked as dirty, is written to the root block.

Recovery

The on-disk RPM and SUT are brought up to date at checkpoints rather than being rewritten for every transaction. A checkpoint writes the dirty RPM nodes in bottom-up order, writes the level 7 node to the root block, and records the corresponding SUT state. Together these structures describe the store at the checkpoint.

Recovery begins from the last valid checkpoint and scans the subsequent log records. Data-packet records are self-describing: they identify the Seid and physical packet location and provide the information needed to reconstruct subsequent changes to both the RPM and SUT. Delete records and other recovery-relevant records are handled in the same scan. These changes are not applied merely because their records were encountered; they become part of the recovered state only when the scan reaches the snapshot log record that commits their transaction. Records after the final valid snapshot are ignored.

The recovery scan therefore starts with the checkpointed RPM and SUT and deduces every committed change made since that checkpoint. Transactions do not need to contain explicit records for each corresponding RPM or SUT update. This permits checkpoints to be relatively infrequent while still allowing the current state to be recovered.

Packet relocation and SUT accounting

RPM-nodes that are written to the log have a Seid. Like any other packets they can be copied to the end of the log as a segment is cleaned.

During a check point, dirty RPM-nodes are written to the log. This renders previous versions of the RPM-nodes obsolete - in fact an obsolete packet will no longer be referenced by the RPM. It is necessary to subtract the total size of the obsolete RPM packet from the utilisation in the SUT.

Level 0 RPM nodes do not store data-packet sizes. Updating the SUT for an existing serial element requires processing its packet chain through the Segment Read Cache to obtain each packet's size and next Seid. Caching only the head packet's size in the RPM would therefore provide little benefit, while caching the complete chain metadata would increase the size and complexity of the RPM.

Seid encoding

The 64-bit space of valid Seid values is partitioned into four mutually exclusive sets:

A Seid used for a data packet has the byte representation c6.c5.c4.c3 c2.c1.c0.p, ordered from most significant to least significant. The four-byte SeidHigh value c6.c5.c4.c3 is in the range 0x00000001 through 0xfeffffff, while the four-byte SeidLow value c2.c1.c0.p may have any value from 0x00000000 through 0xffffffff. Consequently, c6 is less than 0xff; when c6 is zero, at least one of c5, c4 and c3 is nonzero. The range used for data packets is contiguous across both SeidHigh and SeidLow.

        SeidHigh :  00000001 to feffffff
        SeidLow  :  00000000 to ffffffff for each SeidHigh

This provides approximately 1.837 x 10¹⁹ data Seids. More importantly, SeidLow is an ordinary contiguous 32-bit allocation space. Allocating the next Seid normally requires only an integer increment, and ranges of related Seids remain numerically contiguous. This makes allocation, range storage, Seid compression and affiliation substantially simpler.

RPM nodes occupy the separate region whose most significant byte is 0xff. For levels 0 through 6, one or more leading 0xff bytes identify an RPM packet, and the number of leading 0xff bytes identifies its level. The prefix is unambiguous because a Seid used for a data packet cannot begin with 0xff.

        Level 6 RPM packet          ff.ff.ff.ff. ff.ff.ff.c6
        Level 5 RPM packet          ff.ff.ff.ff. ff.ff.c6.c5
        Level 4 RPM packet          ff.ff.ff.ff. ff.c6.c5.c4
        Level 3 RPM packet          ff.ff.ff.ff. c6.c5.c4.c3
        Level 2 RPM packet          ff.ff.ff.c6. c5.c4.c3.c2
        Level 1 RPM packet          ff.ff.c6.c5. c4.c3.c2.c1
        Level 0 RPM packet          ff.c6.c5.c4. c3.c2.c1.c0
        Data packet                 c6.c5.c4.c3  c2.c1.c0.p
                                    <-----------------------  increasing significance

The all-ones value 0xffffffffffffffff identifies the single level 7 RPM node. That node is stored in the root block and is not written as an RPM packet.

Testing the most significant byte distinguishes Seids used for data packets from RPM-node identifiers. Testing the complete Seid against zero detects the null Seid. No reserved values or gaps need to be skipped while allocating within a SeidLow range.

Traversing the RPM

The eight bytes of a data Seid are consumed from most significant to least significant while traversing the RPM. The byte c6 indexes the level 7 root to select a level 6 node, c5 selects a level 5 node, and so on. The final byte p indexes a level 0 node to select the data packet's LogRecordPosition.

Masking and shifting expresses the traversal independently of the host machine's byte order:

uint64 value = seid.value_;
for (int level = 7; level >= 0; --level)
{
    int index = (value >> (level * 8)) & 0xff;
    // Use index at this level of the RPM.
}

Every index is in [0,255], so each RPM node has a uniform fan-out of 256. For an RPM-packet Seid, the leading 0xff bytes identify the node level and the remaining bytes identify its path.

Eviction policy for RPM nodes

RPM nodes are faulted into memory from disk on demand. For a very large store the memory footprint of the RPM nodes can become excessive. Therefore an eviction policy is required.

Navigation to an RPM node always proceeds downwards from the root node. This suggests that parent nodes are evicted if and only if there are no descendants resident in memory.

As a result we only worry about an LRU eviction policy on the level 0 nodes.

Eviction of RPM nodes is performed occasionally by the lazy cleaner thread (only when it is not cleaning). This involves a depth first traversal of the entire RPM tree currently resident in memory. This traversal can automatically evict level 1-6 nodes that have no child nodes resident in memory.

Note that it is important to only evict clean RPM nodes.

Seids must be allocated independently of writing serial elements

Otherwise it would be impossible to create two objects that referenced each other by Seid! This means that Seid allocation must be able to run in a separate phase from writing the serial elements.

Unfortunately this means that we must support creation of whole trees of RPM nodes that don't actually have any descendent data packets. Therefore lifetime management of RPM nodes can't simply depend on whether there exist descendent data packets.

The RPM should be marked as dirty from Seid allocations

It is conceivable that the implementation would only mark the RPM as dirty when the mapping from Seid to LogRecordPosition changes, but not when Seid allocation information changes. However there are two good reasons to additionally mark the RPM as dirty when allocation information changes.

• This avoids the chance that eviction of RPM nodes leads to recycled seid allocations
• Closing and opening the store (gracefully) won't cause recycled seid allocations - which could surprise the application programmer.

Seid allocations

In order to support independent creation of objects at different sites, each process has its own independent "Seid space", uniquely identified by a 128 bit GUID called an OidSpaceGuid. Each process independently maps OidSpaceGuids to local 32 bit SeidHigh values. This mapping is 1-1.

When a Seid is sent over the wire, it is necessary to map the remote SeidHigh to a local SeidHigh. The OidSpaceGuids are used to initialise the SeidHigh conversion map correctly. This can be done on demand during the course of a session - the sender simply sends (OidSpaceGuid,SeidHigh) pairs before sending new SeidHighs for that session.

Each site will still want to cluster related Seids. Note that inevitably Seids created by different sites can't be clustered because they will always use a different SeidHigh.

Within a Seid space (i.e. for a given SeidHigh), the LSS supports allocation of affiliate Seids. This is based on trying to use the largest possible prefix in the Seidlow. Note that the SeidHigh is disregarded! Related Seids will naturally cluster even though they may have been affiliated via Seids generated on a different site!

We require a map from SeidHigh to OidSpaceGuid and vice versa. The former could be achieved by storing OidSpaceGuids directly in the RPM. The latter would required a separate data structure. However we choose to put this is a layer above the LSS, to keep the LSS simple.

Consider that in a single CedaLock many thousands of objects are created. We want these to affiliate correctly. An autoincrement approach may be reasonably good, but perhaps not as good as using the affiliation hints provided by the process. It is possible to imagine pathological cases where the time order of creating objects doesn't relate very well to their affiliation.

When a Seid is allocated we *expect* that in the near future it will really be used. Therefore there seems little disadvantage in eagerly allocating the RPM nodes.

The only remaining issue is to correctly clip RPM nodes from the tree.

Consider the following scenario :

1. Create objects
2. Check into repository.
3. Delete all objects
4. Create more objects.
5. Check into repository.

It would be bad to recycle Seids in step 4. Note that there was no non-graceful shutdown so we can't assume a new Seid space will prevent recycled Seids. The conclusion is that it is not reasonable to recycle Seids.

Non-affiliated Seid Allocations

An individual non-affiliated SeidLow allocation does not append an explicit allocation record to the log. The checkpointed RPM records nextSeidLow_ in each RPM3, while every committed data-packet record written after the checkpoint contains the Seid that was allocated for that packet. The log also has an LR_NEXT_SEID_HIGH record for changes to the SeidHigh allocator.

During recovery, replaying a data-packet record is therefore also evidence that its Seid has already been allocated. If its SeidLow is greater than or equal to the checkpointed nextSeidLow_, the RPM advances nextSeidLow_ to the value immediately after the recovered SeidLow. The same high-water-mark rule is applied to nextSeidHigh_ when required, in addition to replaying LR_NEXT_SEID_HIGH records. Because non-affiliated allocation is sequential and the counters only move forwards, advancing each counter beyond every recovered Seid is sufficient to prevent a recovered Seid from being allocated again.

To support recovery correctly, the RPM needs to be able to create nodes on demand as requests are made to add entries.

For an RPM3 that uses only non-affiliated allocation, nextSeidLow_ records the complete allocation history. Empty descendant RPM nodes therefore contain no allocation state and can be removed without allowing Seids to be reused. When affiliated allocation is used, descendant nodes may contain allocation counters and overflow links that must be retained even when they contain no live data-packet positions. The RPM3 itself must be retained in either case because it stores nextSeidLow_.

Writing dirty RPM nodes

Dirty RPM nodes must be written to the log during a check point.

RPMNode defines a virtual WriteDirtyRPMNodes() method. This base class implementation is suitable for RPM0. If the node is dirty it serialises the RPM packet to the given writer.

WriteDirtyRPMNodes() is overridden by RPMi to *first* recurse into the (dirty) child nodes, before processing that node. Note that dirty nodes are always resident in memory - there is no need to load child nodes into memory. By processing child nodes first, we ensure that dirty nodes are written to the log in bottom up order.

WriteDirtyRPMNodesToLogAndRPM7ToArchive() is implemented by RPM7. This needs to lock the RPM mutex. Also, only the descendent nodes are written to the log. The RPM7 node itself is written to a separate archive that will end up being written to the root block as part of the check point.

Note that RPM dirty does not imply there are nodes to write to the log!

Consider that only a Seid space has been allocated. This only marks the RPM7 as dirty, and therefore there are no dirty nodes to be written to the log.

Bad idea : Using the RPM to track which data packets have been loaded

RPM-nodes for levels 1 to 7 keep track of what RPM-nodes at the next (lower) level have been brought into memory. In fact they directly cache an array of 256 memory pointers to RPM-nodes. By analogy, it would seem reasonable for the level 0 RPM-nodes to keep track of what data packets have been brought into memory.

Instead, the Segment Read Cache (SRC) keeps track of the segments that have been faulted into memory, and there is no concept of eagerly breaking up a segment into independent packets. For that reason we don’t have a C++ class that represents a single packet, and the level 0 RPM-nodes have no idea of what data packets have already been loaded into memory by the SRC.

Interestingly, if packets were indeed represented as C++ objects, and the RPM was used to track which packets have been brought into memory, we would have a significant problem : Segment loading would be unbounded. When a segment is loaded we may read a packet with an OID that requires other segments to be loaded in order to retrieve the relevant RPM nodes (in order to indicate the fact that the packet has been loaded in the RPM in memory). These segments can in turn read packets that require yet more packets to be loaded. In the worst case, a chain reaction could end up loading the entire store into memory!

As a general rule, we favour a design that keeps the (complicated) RPM as simple as possible. This will hopefully reduce the amount of meta-data that needs to be written to the store. For example, the RPM won’t be able to tell us how big an existing packet is for the purposes of updating the segment utilisation in the SUT. Only the SRC can give us access to information stored in the packet, such as the total packet size or the next OID in the chain.

Indexing into the RPM

Given a Seid c6.c5.c4.c3 c2.c1.c0.p used for a data packet, the RPM consumes the bytes in that order. Each byte is used directly as an index in [0,255]. The first seven indexes select the path from the root to a level 0 node; p selects the data packet position stored in that node. No byte value acts as a terminator or requires special treatment.

RPM responsibilities

The RPM is responsible for the following:

• Provides a mapping from Seid ---> LogRecordPosition, for every packet in the system, i.e. for both data and RPM packets.
• Takes care of marking nodes as dirty, and ensure they are all written to the log in the right order during a check point.
• Provide functions for adding and removing entries, either by the LRSWriterForCheckPoint, or during recovery
• Provides functions for allocating Seids

Class inheritance hierarchy

Use of LSS& in RPM nodes

Every RPMNode stores an LSS&. The reference is accepted by the base-class constructor and is propagated into every node created at every level of the RPM:

class RPMNode
{
public:
    RPMNode(LSS& lss, RPMNode* parent, int index, int level, Seid seid);

protected:
    LSS& lss_;
};

The reference does not represent ownership of the LSS. The LSS owns the RPM, which in turn owns its resident nodes. It is an upward reference from each node to the aggregate which ultimately owns it, and is used as a route from a node to other LSS modules and store-wide state.

Faulting child RPM nodes into memory

Only some of the RPM tree is resident in memory. An internal RPM node records the LogRecordPosition of each non-resident child. When traversal needs such a child, the RPM uses the LSS reference to reach the segment-reading facilities, locate the packet containing the child RPM node, access its bytes and deserialise a new child node. The LSS reference is then passed to the child constructor so the same process can continue at lower levels.

Segment access and reservation

Resolving an RPM entry ultimately produces the physical position of a packet in a segment. RPM operations can use LSS& to reach the segment cache and, where requested by the operation, reserve or acquire access to the corresponding segment. RPM navigation is therefore coupled to both the logical Seid-to-position mapping and the mechanism used to make the containing segment accessible.

SUT utilisation accounting

RPM packets themselves occupy space in log segments. When an RPM packet is replaced, relocated or made obsolete, the utilisation recorded for the affected segments must be adjusted. The RPM uses its route through the LSS to reach the SUT and its reservation/accounting operations. This means an operation which appears to update an RPM node may also update store-wide segment utilisation.

Dirty-node and checkpoint coordination

Changing a packet position or Seid-allocation state marks an RPM node and its ancestors as dirty. Dirty nodes must remain resident and are later written in bottom-up order during a checkpoint. The implementation uses LSS-level RPM and checkpoint state when maintaining this bookkeeping, including store-wide dirty-node counts and the decision that enough RPM work has accumulated to require a checkpoint.

Consequences of the reference

The single LSS& therefore conceals several different dependencies: loading RPM packets, accessing or reserving segments, updating SUT utilisation, maintaining RPM-wide state and coordinating checkpoint work. A node constructor does not reveal which of these facilities a particular node operation can use. Because every descendant receives the reference, every node is also coupled to the lifetime and complete private interface of the LSS even when most node operations only manipulate the node's local arrays and metadata.

Code

class RPMNode
{
public:
    RPMNode(LSS& lss,RPMNode* parent,int index,int level,Seid seid);
    virtual ~RPMNode() {}
    virtual void Clear();
    virtual bool EvictUnusedDescendentNodes(int minSeqNum) = 0;
    int GetLevel() const { return level_; }
    virtual void Serialise(Archive& ar) const;
    virtual void Deserialise(InputArchive& ar);
    virtual void WriteDirtyRPMNodes(LRSWriterForCheckPoint& writer);
    virtual void DumpAllocatedSeids(xostream& os) const {}
    virtual bool RemovePacket(int index);
    virtual bool HaveChild(int index) const;
    virtual void WriteInfo(xostream& os) const;
    LogRecordPosition GetPacketPosition(int index) const { return positions_[index]; }
    void SetPacketPosition(int index, LogRecordPosition pos);
    void SetThisPacketPositionAndSize(LogRecordPosition pos,int totalPacketSize);
    Seid GetSeidOfChild(int index) const;
    void GetSeidsOfChildren(xvector<Seid>& children, bool enableOverflowPackets) const;
    Seid GetSeid() const { return seid_; }
    SeidLow GetSeidLow() const { return seid_.low_; }
    bool IsEmpty() const { return numChildren_ == 0; }
    bool IsFull() const { return numChildren_ == 256; }
protected:
    void MarkAsDirty();

protected:
    LSS& lss_;
    RPMNode* parent_;
    int index_;
    int level_;
    Seid seid_;
    mutable bool isDirty_;
    int totalPacketSize_;
    LogRecordPosition positions_[256];
    int numChildren_;
    SeidLow forward_;
    int numLocalAffiliateAllocs_;
};

class RPM0 : public RPMNode
{
public:
    RPM0(LSS& lss, RPMNode* parent, int index, Seid seid);
    virtual void Clear();
    virtual bool EvictUnusedDescendentNodes(int minSeqNum);
    SeidLow AllocateSeidLow();

    private:
    int lastUsedSeqNum_;
    friend class RPM7;
};

class RPMi : public RPMNode
{
public:
    RPMi(LSS& lss,RPMNode* parent,int index,int level, Seid seid);
    virtual ~RPMi();
    virtual void Clear();
    virtual bool EvictUnusedDescendentNodes(int minSeqNum);
    virtual void WriteDirtyRPMNodes(LRSWriterForCheckPoint& writer);
    virtual void DumpAllocatedSeids(xostream& os) const;
    virtual bool RemovePacket(int index);
    virtual bool HaveChild(int index) const;
    RPMNode* CreateChildNode(int index);
    RPMNode* AllocateChildNode();
    RPMNode* GetChildNode(int index);
    const RPMNode* GetChildNode(int index) const { return const_cast<RPMi*>(this)->GetChildNode(index); }
    RPMNode* AlwaysGetChildNode(int index);
    void WriteDirtyChildRPMNodes(LRSWriterForCheckPoint& writer);
    void CreateChildNodeAndDeserialiseFromPacket(int index, const void* buffer, int size, int totalPacketSize);
    RPM0* AllocateChildLevel0();
    RPMi* AllocateChildLevel1();
    RPMi* AllocateChildLevel2();

private:
    RPMNode* nodes_[256];
};

class RPM3 : public RPMi
{
public:
    RPM3(LSS& lss,RPMNode* parent,int index,Seid seid);
    virtual void Clear();
    virtual void DumpAllocatedSeids(xostream& os) const;
    virtual void Serialise(Archive& ar) const;
    virtual void Deserialise(InputArchive& ar);
    virtual void WriteInfo(xostream& os) const;
    bool AllowForSeidLow(SeidLow seidLow);
    SeidLow AllocateSeidLow();
    SeidLow PeekNextSeidLow() const;
    void GetSeidsInSeidSpace(xvector<SeidLow>& seidLows) const;
    RPM0* BindLevel0(SeidLow x);
    RPM1* BindLevel1(SeidLow x);
    RPM2* BindLevel2(SeidLow x);
    std::pair<SeidLow,bool> AllocateAffiliateSeidLow(SeidLow x);

private:
    SeidLow nextSeidLow_;
};

class RPM7 : private RPMi
{
public:
	RPM7(LSS& lss);
    virtual void Clear();
    virtual void Serialise(Archive& ar) const;
    virtual void Deserialise(InputArchive& ar);
    void WriteDirtyRPMNodesToLogAndRPM7ToArchive(LRSWriterForCheckPoint& writer, Archive& arRootNode);
    LogRecordPosition GetPacketPosition(Seid seid, bool reserveSegment);
    void SetPacketPosition(Seid seid, LogRecordPosition pos);
    bool RemoveDataPacket(Seid seid);
    Seid AllocateSeid(SeidHigh seidHigh);
    bool ReserveSeid(Seid seid);
    SeidLow PeekNextSeidLow(SeidHigh seidHigh);
    Seid AllocateOverflowPacketSeid(SeidHigh seidHigh);
    bool AllocateAffiliateSeid(Seid& seid);
    SeidHigh AllocateSeidHigh();
    void DumpSeidAllocationInfo(xostream& os) const;
    bool NeedCheckPoint() const;
    void GetSeidsInSeidSpace(xvector<SeidLow>& seidLows, SeidHigh seidHigh) const;
    void DeleteSeidSpace(SeidHigh seidHigh);
    void EvictUnusedNodes();
    bool RecurseSeidMap(xvector<Seid>& children, Seid seid, bool enableOverflowPackets) const;
    bool WriteInfoOnNodeForGivenSeid(Seid seid, xostream& os) const;
    bool IsDirty() const { return isDirty_; }
    void IncrementNumDirtyLevel0Nodes() { ++numDirtyLevel0Nodes_; }
    std::optional<SeidHigh> GetDirtyNextSeidHigh();
    void UpdateNextSeidHigh(SeidHigh nextSeidHigh);

private:
    void PrivateSerialise(Archive& ar) const;
    SeidHigh PrivateAllocateSeidHigh();
    void TouchRPM0(RPM0* node);
    virtual void WriteInfo(xostream& os) const;
    RPMNode* GetNodeForGivenSeid(Seid seid);
    const RPMNode* GetNodeForGivenSeid(Seid seid) const { return const_cast<RPM7*>(this)->GetNodeForGivenSeid(seid); }
    void PrivateAllowForSeidHigh(SeidHigh seidHigh);
    RPMNode* GetParentNodeAndChildIndex(Seid seid, int& index);
    RPMNode* AlwaysGetParentNodeAndChildIndex(Seid seid, int& index);
    RPM3* AlwaysGetLevel3Node(SeidHigh seidHigh);
    const RPM3* AlwaysGetLevel3Node(SeidHigh seidHigh) const { return const_cast<RPM7*>(this)->AlwaysGetLevel3Node(seidHigh); }
    RPM3* GetLevel3Node(SeidHigh seidHigh);

private:
    mutable std::mutex mutex_;
    SeidHigh nextSeidHigh_;
    bool nextSeidHighIsDirty_;
    int timeSeqNum_;
    mutable int numDirtyLevel0Nodes_;
};