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 four-level 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;
};

An 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.

Address-space handles

The LSS hands a client an opaque handle to a Seid address space. Internally the handle is essentially a pointer to the root of that address space's RPM. Operations which repeatedly access one Space retain this handle and use it with local Seids:

class SeidAddressSpace;

LogRecordPosition GetPacketPosition(
    const SeidAddressSpace& addressSpace,
    Seid seid);

The public handle should remain opaque even if its implementation is pointer-like. This permits the LSS to enforce its lifetime and snapshot rules without adding an address-space lookup to every Seid operation.

Four-level RPMs

Each address space has its own four-level Recoverable Packet Map. The four bytes of a 32-bit Seid are used as successive indexes in a radix tree with fan-out 256. The handle gives direct access to the root of this tree, which is equivalent to starting at the old RPM3 node rather than traversing the upper four levels of one global eight-level RPM.

The LSS maintains a sparse directory from SpaceId to address-space RPM roots. This directory is consulted when an address-space handle 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 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 four-level tree also reduces the cost of RPM copy-on-write. Updating an RPM leaf requires copying at most the path through its four-level address-space RPM, 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 handle lifetime

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

An address-space handle must not outlive the partition view or transaction which supplies it. Removing an address space from a newer snapshot does not invalidate a handle retained 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.