69.1 Multiple Address Spaces in a Working Set

This subchapter discusses PSpaces and working sets only to explain the higher-layer motivation for the LSS Space design. They are not part of the LSS Version 2 specification. This material will probably move to the PersistStore document.

Operational transformation and independent object creation

Higher layers of CEDA use operational transformation (OT) to support conflict-free branching and merging of working sets in PSpaces. A working set is a tree of objects together with operations on that tree. Different sites or users can work independently, exchange operations and objects, and merge their changes without requiring a central allocator for every object identifier.

It is important that several sites can create objects in the same logical working set while they are disconnected. Object creation must not allocate the same identity at two sites, and reconnecting the sites must not require either site to rewrite every identifier it has already stored.

Allocation spaces in Version 1

In Version 1, independent sites allocate different SeidHigh values. Each allocation space is also assigned a 128-bit UUID. The UUID is the stable identity of the allocation space across sites; the numerical SeidHigh is only its local representation in one store.

When two sites connect over TCP and exchange operations or objects, they use the UUIDs to establish a translation between their local SeidHigh values. If a sender transmits a 64-bit Seid, the receiver retains its low 32 bits and translates its high 32 bits to the possibly different SeidHigh used locally for the same UUID. Once a connection has established this mapping, many identifiers can be translated without repeatedly sending their UUIDs.

Distinguished private address space

Every PSpace has a distinguished private address space for its internal persistent structures. This address space has no UUID because it does not represent an allocation domain shared between sites. Its Seids are local implementation identifiers and are never sent over the wire.

The PSpace uses 32-bit Seids from this private address space for structures such as B+Tree nodes and links between those nodes. For example, the child references in a B+Tree non-leaf node can be stored as 32-bit Seids:


struct BTreeInternalEntry
{
    Key separator;
    Seid childNode;       // PSpace private address space
};

This is the common path for internal PSpace data structures and obtains the storage, cache-locality and four-level RPM benefits of 32-bit Seids. A B+Tree leaf may still contain 64-bit OIDs when its payload refers to objects in a distributed working-set tree, but the B+Tree's own structure does not need 64-bit identifiers.

The private address space is stored separately from the vector of UUID-bearing object allocation spaces. Keeping it out of that vector prevents a private Seid from accidentally being interpreted as a transmissible working-set OID.


struct PSpaceAddressSpaces
{
    AddressSpaceId privateAddressSpaceId;
    LssAddressSpaceHandle privateAddressSpaceHandle;
};

Object address-space table

Version 2 retains the distributed object-allocation concept while composing a working set from the LSS's 32-bit Seid address spaces. Each working set records its own vector of object allocation spaces whose entries associate:

a local LSS AddressSpaceId;
the 128-bit UUID which globally identifies that allocation space; and
an LssAddressSpaceHandle bound for efficient access.


struct WorkingSetAddressSpaceEntry
{
    AddressSpaceId addressSpaceId;
    UUID uuid;
    LssAddressSpaceHandle handle;
};

std::vector<WorkingSetAddressSpaceEntry> addressSpaces;

This representation is illustrative. In particular, the persistent fields and transient handle may be stored separately. Logically, however, a working-set entry associates all three identities.

OID representation within the working set

Within the tree of objects in a multi-site working set, object references remain 64-bit OIDs. The high 32 bits are an index into the working set's object-address-space vector and the low 32 bits are a Seid local to the selected LSS address space:


struct Oid
{
    uint32 addressSpaceIndex;   // OIDHigh
    uint32 seid;                // OIDLow
};

An OID is therefore not itself a global 64-bit LSS Seid. It is a working-set object reference composed at the working-set layer:

    working-set-local address-space index + address-space-local LSS Seid

Resolving an OID first indexes the working set's object-address-space vector. The resulting handle gives direct access to the four-level RPM for that allocation space, and the low 32-bit Seid is looked up in that RPM. This requires only a vector indexing operation before the local RPM lookup; it does not traverse the upper four levels of a global eight-level RPM.

The three forms of address-space identity

The design deliberately uses three related but distinct forms of identity:

UUID: The globally stable identity of an allocation space. It is used to recognise the same allocation space at different sites and establish translation mappings.
AddressSpaceId: The persistent identity assigned to the address space by one local LSS. Different LSS files may use different values for the same UUID.
Working-set vector index: The compact value stored as OIDHigh in one replica of a working set. Different sites may assign different vector indexes to the same UUID.

The LssAddressSpaceHandle is not another persistent identity. It is a runtime capability giving efficient access to the address space selected by the other identities.

The working set is the identity boundary

A working set has its own persistent identity, vector time and OT history. All replicas of that working set share the same working-set identity, and every operation is tied to it. The meaning of an OID is therefore scoped by the working set:

    WorkingSetId + OID

A bare OID must not be resolved through a PSpace-wide object-address-space table. Two working sets in the same PSpace can use the same numerical OID for unrelated objects. Incoming operations first identify and validate their target working set, and only then interpret OIDHigh through that working set's vector.


struct WorkingSet
{
    WorkingSetId id;
    VectorTime vectorTime;
    std::vector<WorkingSetAddressSpaceEntry> addressSpaces;
};

The PSpace hosts and persists working sets, but it does not combine their UUID-to-address-space mappings. Even if two working sets mention the same allocation-space UUID, their mappings remain logically separate because their object identities and OT histories are separate.

Translation when sites connect

A connection establishes a mapping from the sender's address-space indexes for a particular working set to the corresponding indexes in the receiver's replica of that same working set. For each sender index encountered, the sender communicates the corresponding UUID. The receiver looks up that UUID in the local vector belonging to the identified working set. If it is already present, the receiver uses the existing vector index. Otherwise it creates a local LSS address space and appends a corresponding entry to that working set's vector.

    sender OID
        (sender vector index, Seid)
                    |
                    v
             allocation UUID
                    |
                    v
    receiver OID
        (receiver vector index, Seid)

The low 32-bit Seid does not change. Only the working-set-local high part is translated. The connection can cache the resulting index-to-index mapping, so UUID resolution is required when an allocation space is introduced to the session rather than for every OID sent over the wire.

Each working-set vector and its indexes are local storage metadata, not replicated global numbering. Two replicas can independently assign different vector indexes and different LSS AddressSpaceId values to the same UUID. This is expected and is the reason UUID-based translation is required.

Creating objects at independent sites

Each site which independently creates objects uses an allocation space identified by its own UUID. It allocates 32-bit Seids from the corresponding local LSS address space. Because independently created allocation spaces have different UUIDs, two disconnected sites cannot create the same composite object identity even if they allocate identical 32-bit Seid values.

After operations are exchanged, an object created remotely is represented locally using the vector index assigned to the remote allocation-space UUID together with the unchanged 32-bit Seid. OT can therefore merge operations and object trees without a central Seid allocator and without renumbering the objects created by either site.

Objects do not retain identity when transferred between working sets

An object must not be moved to another working set while retaining its OID. A delayed operation for the source working set could otherwise resolve to the transferred object and be applied outside the OT history and vector-time domain in which the operation was created. That would violate the assumption that every operation targets an object in one identified working set.

Transferring data between distinct working sets is instead an export and import, analogous to moving content between distinct Git repositories. The destination allocates new OIDs, copies the selected object tree and rewrites its internal object references. Later operations in the source working set continue to address only the source objects; they are not redirected to the imported copies.

Branches and replicas of the same working set are different: they share the working-set identity and OT history and use UUID translation to preserve object identities while changes are exchanged.

Persistent and transient state

The PSpace persists the AddressSpaceId of its distinguished private address space. Each working set persists its own identity, vector time and enough information to reconstruct its object-address-space vector, including each entry's UUID and local LSS AddressSpaceId. The pointer-like LssAddressSpaceHandle is transient. It is recreated by binding the persistent entry to the appropriate LSS transaction or snapshot when the PSpace is opened.


struct PersistentWorkingSetAddressSpaceEntry
{
    AddressSpaceId addressSpaceId;
    UUID uuid;
};

struct BoundWorkingSetAddressSpaceEntry
{
    const PersistentWorkingSetAddressSpaceEntry* persistent;
    LssAddressSpaceHandle handle;
};

Separating these representations prevents a process pointer or snapshot-specific capability from being mistaken for durable state while retaining a direct handle on the lookup path.

MVCC snapshot binding

An address-space handle used by a partition view refers to the immutable four-level RPM root for that address space in the view's snapshot. Every bound working-set vector for that view must therefore use snapshot-specific handles. It must not contain a process-wide handle which silently changes to mean the latest RPM root.

A writer can use copy-on-write to create a new RPM root for one address space while readers continue to use older handles. Removing an address-space entry from a newer working-set snapshot cannot invalidate the entry, root or packets retained by an older reader. Their lifetime follows the same deferred release rules as other immutable RPM roots.

Vector-index invariants

The object-address-space vector index is stored in every local OID using that allocation space, so an entry must not be reordered while such OIDs exist. Reusing an index for a different UUID would cause old OIDs to resolve through the wrong RPM. The simplest rule is that entries are append-only and indexes are never reused within the lifetime of a working set.

There can be at most one vector entry for a given UUID in one working set. When a connection introduces a UUID, lookup by UUID must occur before an entry is appended. Each working set therefore needs both indexed access for normal OID resolution and an efficient UUID-to-index map for session establishment.

Relationship to Predica PSpace boundaries

Multiple object allocation spaces within one working set do not permit OID-based references into a different working set or Seid-based references between different PSpaces. The 64-bit OID described here is peculiar to the tree of objects in one working set and supports independent sites creating objects in that same tree. It is not the universal identifier for internal PSpace structures. Predica relationships which cross a PSpace boundary must still use keys defined in the Predica schema. The OIDs and Seids remain hidden persistence identifiers which are not exposed as schema-defined application keys.

Resulting layering

The responsibilities are divided as follows:

The LSS provides many independent 32-bit Seid address spaces and efficient handles to their four-level RPM roots.
Every PSpace has a distinguished UUID-less address space containing internal structures such as B+Trees, whose internal links use 32-bit Seids.
Each working set owns its identity, vector time, OT history and mapping from compact local OIDHigh indexes to UUID-bearing LSS object address spaces.
The PSpace hosts the working sets and provides persistence services without combining their object identity domains.
The OT and messaging layers validate the working-set identity and use UUIDs to translate address-space indexes between replicas of that working set.
Predica uses schema-defined keys, rather than persistence identifiers, for relationships crossing PSpace boundaries.

This retains the distributed-allocation property of 64-bit OIDs where it is needed, while allowing the LSS and local data structures to benefit from compact 32-bit Seids and four-level RPMs.

Previous69 Seids Next69.2 Space