69.1 Seid Allocations

Local Seid allocations in a PSpace

A PSpace may support a million (non-durable) transactions per second, yet only write its dirty objects to the LSS every few seconds. The PSpace does not access the LSS during its transient transactions to allocate Seids. Instead, the PSpace owns the Spaces it creates for its objects. It can therefore allocate Seids itself by recording the next available Seid as part of its own state. Creating objects and assigning Seids does not require an LSS transaction. This permits large ranges of Seids to be allocated efficiently while objects are created or modified in memory.

struct PSpace
{
    SpaceId spaceId;
    Lss::IPartition* partition = nullptr;
    const Lss::ISpaceView* space = nullptr;
    Seid publishedNextSeid;
    Seid nextSeid;
    IPartitionView* lastMvccSnapshot = nullptr;
    std::mutex mutex;
    ...
};

When dirty objects in a PSpace are written to the LSS, ReserveSeidsBefore() is called if nextSeid exceeds publishedNextSeid.

void PSpace::OnOpen()
{
    lastMvccSnapshot = partition->OpenView();
    space = lastMvccSnapshot->FindSpace(spaceId);
    nextSeid = publishedNextSeid = space->PeekNextSeid();
}

void PSpace::TxnOnLss()
{
    LockGuard lock(mutex);
    if (lastMvccSnapshot)
    {
        lastMvccSnapshot->Close();
        lastMvccSnapshot = nullptr;
        space = nullptr;
    }
    {
        IPartitionTransaction* txn = partition->OpenTransaction();
        IMutableSpace* mutableSpace = txn->FindSpace(spaceId);
        // Write dirty objects with calls to mutableSpace->WriteSerialElement()
        // Delete objects with calls to mutableSpace->DeleteSerialElement()
        if (nextSeid > publishedNextSeid)
            mutableSpace->ReserveSeidsBefore(nextSeid);
        lastMvccSnapshot = txn->CloseAndPublishSnapshot();
        space = lastMvccSnapshot->FindSpace(spaceId);
    }
    publishedNextSeid = nextSeid;
}

void PSpace::OnClose()
{
    if (lastMvccSnapshot)
        lastMvccSnapshot->Close();
    partition->Close();
}

Seid allocations in a working set

Consider two sites which independently create objects in replicas of the same working set. Each site allocates Seids in its own Space. A Space is never shared between sites for the purpose of Seid allocation, so each Space has exactly one allocator and its allocation frontier advances in a single order.

The working set identifies each object-allocation Space with a UUID. Within one replica, an OID contains an index into the working set's object-address-space vector and a 32-bit Seid. When sites connect, the UUID is used to translate the sender's vector index to the receiver's vector index. The low 32-bit Seid is retained unchanged.

    sender OID                         receiver OID
    (sender index, Seid)               (receiver index, Seid)
             \                           /
              allocation-Space UUID

CEDA OT respects causal order, so operations which allocate objects in a particular Space are applied in their original order at every other site. A receiver therefore reproduces the allocation sequence for that Space while applying the ordinary working-set operations. It does not allocate Seids in the remote site's Space, merge competing allocation frontiers, or require separate Seid reservation messages.

For example, an operation which creates an object or a contiguous range of objects contains the Seids needed to identify them. Applying the operation advances the receiver's transient allocation frontier for the corresponding working-set Space. Gaps are harmless, so allocations which are never referenced by a received operation do not need to be reproduced at the receiver.

When the receiver later writes its dirty working-set state to the LSS, it translates the working-set vector entry to the corresponding local SpaceId, obtains its IMutableSpace from the partition transaction, and calls ReserveSeidsBefore() with the resulting exclusive frontier. The reservation, any newly introduced UUID-to-Space mapping, and the dirty objects are published in the same LSS transaction. Consequently, an object cannot be published in an LSS snapshot without the local Space mapping and Seid reservation required to resolve it.

Example: allocating Seids for a tiled image

Consider creating a tiled image containing one million tiles. Each tile is stored as a separate serial element, and the image records the first Seid in the contiguous range assigned to its tiles:

struct TiledImage
{
    int numTilesX;
    int numTilesY;
    Seid baseSeid;  // Tile Seids are in [baseSeid, baseSeid + numTilesX * numTilesY)
};

The PSpace allocates the entire range by advancing its local exclusive allocation frontier. No LSS transaction is required at this point.

uint32 numTiles = image.numTilesX * image.numTilesY;
image.baseSeid = workingSet.nextSeid;
workingSet.nextSeid += numTiles;

This local allocation gives the image the range [baseSeid, baseSeid + numTiles), but does not yet make the allocation durable in the LSS. When an LSS transaction is opened to write the dirty image, it advances the durable frontier to workingSet.nextSeid, the first Seid after the allocated range. The reservation and the write of the image object must commit atomically. Otherwise the image could become durable while the LSS allocation frontier still permits the tile Seids to be allocated again after recovery.

mutableSpace->ReserveSeidsBefore(workingSet.nextSeid);
// Write image using the same transaction, then commit it.

The LSS reservation is a monotonically advancing durable frontier; it does not create serial elements for the reserved Seids. Gaps are allowed, and deleting a serial element does not make its Seid available for reuse. After recovery, the working set initializes its local nextSeid from the durable frontier returned by ISpaceView::PeekNextSeid().