69 Seids

Local 32-bit Seids

Version 2 changes the way Seids are understood. A Seid is a 32-bit identifier which is local to a Space. An LSS supports approximately 2³² partitions, each partition supports approximately 2³² Spaces, and each Space supports approximately 2³² Seids. A globally meaningful packet identity within an LSS is therefore the triple:

(PartitionId, SpaceId, Seid)

Most client data structures do not need to store that pair with every reference. They operate within one address space and store only the local 32-bit Seid. The address-space identity is supplied once by the context in which the structure is accessed.

A limit of approximately 2³² Seids in one address space is workable in practice. A single allocation domain containing more objects than that would already be exceptionally large and should be divided into multiple Spaces.

References which cross an address-space boundary must explicitly carry or otherwise resolve the destination address-space identity. A bare 32-bit Seid has no meaning outside its associated address space. APIs and persistent types should distinguish local Seids from globally qualified identities so that a local Seid cannot accidentally be interpreted in the wrong space.

Locality and contention

Supporting many address spaces provides better locality between separate uses of one LSS. Each use can allocate Seids within its own address space, so its identifiers and RPM paths are clustered independently rather than mixed with unrelated data. Better locality is an additional benefit of the address-space design, independently of the reduction from 64-bit to 32-bit local identifiers.

Separate address spaces can also reduce contention. Independent uses of the LSS operate on different RPM roots, Seid-allocation state and lazily loaded RPM nodes instead of repeatedly touching the same upper levels of one global RPM. Concurrent readers working in different Spaces are less likely to contend on the same RPM cache state or cache lines.

using Seid = uint32;
using SpaceId = uint32;

struct PartitionSeid
{
    SpaceId spaceId;
    Seid seid;
};

A PartitionSeid is meaningful within one Partition. Qualifying it with an PartitionId produces an identity which is unambiguous within the LSS. The important distinction is between the small local Seid stored frequently inside a Space and the qualified identity used when the Space and partition are not already known.

Space views

After resolving a SpaceId in a partition snapshot, the LSS gives the client an ISpaceView which directly refers to that Space's immutable state. Operations which repeatedly access one Space use this interface with local Seids:

const ISpaceView* space = partitionView->FindSpace(spaceId);
ICloseableInputStream* input = space->ReadSerialElement(seid);

The interface remains opaque even if its implementation is pointer-like. It is owned by the partition view and must not outlive that view. This enforces the snapshot lifetime without adding a SpaceDirectory lookup to every Seid operation.

Variable-height RPMs

Each address space has its own variable-height Recoverable Packet Map with at most four levels. The bytes needed to represent a 32-bit Seid are used as successive indexes in a radix tree with fan-out 256. A sufficiently large map has a level-3 root, equivalent to starting at the old RPM3 node, while small maps omit unnecessary upper levels.

The LSS maintains a sparse directory from SpaceId to address-space RPM roots. This directory is consulted when a Space view is obtained, not on every local Seid lookup. It must not be represented by a dense array of 2³² entries.

Space and performance advantages

Using 32-bit local Seids substantially reduces the size of data structures containing many object references. For example, a B+Tree non-leaf node containing 1024 Seids uses 4 KiB less storage than it would with 64-bit Seids. The smaller representation improves cache density and allows more entries to fit in a node or memory page.

An RPM lookup traverses at most four radix levels rather than eight. This can substantially reduce the CPU cost of an in-memory lookup, although the overall improvement must be measured because cache misses, segment access and other work may also contribute to lookup time. Performance benchmarks should compare the complete lookup operation rather than assume that halving the radix depth exactly doubles throughput.

The tree also reduces the cost of RPM copy-on-write. Updating an RPM leaf requires copying a path of at most four levels, rather than copying ancestors through an eight-level global tree. Transactions which update nearby Seids may continue to reuse paths already copied into their working RPM.

MVCC and Space-view lifetime

An ISpaceView identifies the immutable RPM root for that Space in its owning partition view's snapshot. A writer may create a new root using copy-on-write, while an older reader continues to use its original Space view and root. The interface does not select the latest root again for each lookup.

An ISpaceView must not outlive the partition view which owns it. Removing a Space from a newer snapshot does not invalidate a Space view owned by an older reader; the MVCC retention mechanism keeps the old root and its reachable packets alive until that snapshot is released.

Persistent and external identities

Some parts of the LSS operate without an already selected Space. Log scanning, cleaning, checkpointing, diagnostic tools and messages crossing address-space boundaries must be able to identify the relevant address space. Records used in those contexts carry the composite PartitionId, SpaceId and 32-bit Seid, or another encoding which is unambiguously equivalent.

Keeping a composite identity where it is required does not negate the main saving. Frequently stored local references in B+Trees, object graphs and other data structures remain 32-bit, while the address-space identity is carried once by their surrounding context.