68 LSS API

This chapter defines the Version 2 LSS API. Value types are structs or aliases, operations which do not belong to an object are free functions, and runtime polymorphism is expressed using pure abstract interfaces. The API does not expose implementation classes.

An LSS is a persistent heap of variable-length serial elements organised into a flat set of Partitions. A Partition neither contains nor records the existence of other Partitions.

The logical data hierarchy is:

Lss
    (PartitionId, Partition)
        Space
            SerialElement

• Lss is associated with one LSS file and its lifetime.
• Partition is the transaction, MVCC snapshot and mutation-concurrency boundary. At most one mutative transaction is active on a partition, while different partitions may mutate concurrently.
• Space is a 32-bit Seid address space containing serial elements.
• SerialElement is a variable-length binary value identified by a Seid (pronounced “see-id”), a contraction of serial element identifier.

An LSS can have up to approximately four billion partitions, each partition can have up to approximately four billion spaces, and each space can have up to approximately four billion serial elements.

Identifiers

using PartitionId = uint32;
using SpaceId = uint32;
using Seid = uint32;
using TxnSequenceNumber = uint64;

inline constexpr PartitionId PRIMARY_PARTITION_ID = 0;
inline constexpr PartitionId NULL_PARTITION_ID = 0xffffffff;
inline constexpr SpaceId NULL_SPACE_ID = 0xffffffff;
inline constexpr Seid NULL_SEID = 0xffffffff;

struct PartitionSeid
{
    SpaceId spaceId;
    Seid seid;
};

A Partition is logically a set of Spaces indexed by 32-bit SpaceId. A Space is logically a set of serial elements indexed by 32-bit Seid. For each of PartitionId, SpaceId and Seid, the value 0xffffffff is null and does not identify an object. Zero is a valid identifier value for all three types; values intended to begin null must be initialized to the corresponding null constant explicitly. For Seids, the null value is also used as the exhausted allocation frontier. A PartitionSeid is null when its seid member equals NULL_SEID; its spaceId is then irrelevant. A nonnull PartitionSeid must not have spaceId == NULL_SPACE_ID.

TxnSequenceNumber is the 64-bit identifier exposed by partition transactions and views. Each Partition has its own independent sequence of transaction sequence numbers. A newly created Partition's initial empty snapshot is assigned zero, and later mutative transactions are assigned successive numbers in commit order.

Logical model

The following model defines the logical meaning of an LSS, its Partitions and its Spaces independently of their storage representation.

An LSS is a set of (PartitionId, Partition) pairs where:

    • the PartitionIds are unique integers in [0, 232 - 1)

A Partition is a set of (SpaceId, Space) pairs where:

    • the SpaceIds are unique integers in [0, 232 - 1)

The number of partitions in an LSS and the number of spaces in a Partition are each between 0 and 2³² - 1 inclusive.

A Space is:

A Space is a pair (nextSeid, serialElements) where:

    • nextSeid is an integer in [0, 232), and

    • serialElements is a set of (seid, serialElement) pairs where:

        • the seids are unique integers in [0, nextSeid)

        • each serialElement is a finite sequence of zero or more octets
          (with no upper bound specified)

For any space (nextSeid, serialElements) the number of serial elements is between 0 and nextSeid.

The allocated Seids of a Space are the integers in [0, nextSeid). Therefore, nextSeid is both the next Seid to allocate and the number of allocated Seids in the Space.

Because nextSeid is at most 0xffffffff and serial-element Seids are less than nextSeid, 0xffffffff never identifies a serial element and is used as NULL_SEID.

Serial-element input

struct ReadOnlyBuffer
{
    const octet_t* data;
    std::size_t size;
};

struct IContiguousSerialElement
{
    virtual ReadOnlyBuffer GetBuffer() const = 0;
    virtual void Close() = 0;
};

An IContiguousSerialElement pins the storage containing its buffer until Close() is called. It is not deleted by the caller.

Partition views

struct ISpaceView
{
    virtual SpaceId GetSpaceId() const = 0;
    virtual Seid PeekNextSeid() const = 0;
    virtual bool SerialElementExists(Seid seid) const = 0;
    virtual ICloseableInputStream* ReadSerialElement(Seid seid) const = 0;
    virtual IContiguousSerialElement* ReadContiguousSerialElement(Seid seid) const = 0;
};

An ISpaceView represents one Space in one immutable partition snapshot. Its SpaceId is immutable. The allocation frontier and serial-element state accessed through it belong to that snapshot.

An ISpaceView is owned by its IPartitionView and becomes invalid when that partition view is closed.

struct IPartitionView
{
    virtual PartitionId GetPartitionId() const = 0;
    virtual TxnSequenceNumber GetTxnSequenceNumber() const = 0;
    virtual const ISpaceView* FindSpace(SpaceId spaceId) const = 0;
    virtual void Close() = 0;
};

FindSpace() returns null when the selected partition snapshot does not contain a Space with the given SpaceId. Passing NULL_SPACE_ID is illegal; null is not treated as a valid but absent SpaceId.

The returned ISpaceView supplies the immutable MVCC state used by PeekNextSeid() and the serial-element read operations.

IPartitionView::GetTxnSequenceNumber() returns the sequence number of the mutative transaction which published the immutable partition snapshot pinned by that view. The view returned by CloseAndPublishSnapshot() returns the same value as the closing IPartitionTransaction.

An IPartitionView pins one immutable MVCC snapshot of the Partition and every Space it contains. Every read through the view therefore observes the same completed partition transaction boundary.

Every input stream and contiguous serial element obtained from a partition view must be closed before the view is closed. A partition view may be used concurrently by multiple reader threads, but an individual returned stream is not shared between threads.

Partition transactions

IMutableSpace

struct IMutableSpace : ISpaceView
{
    virtual Seid AllocateSeids(uint32 count) = 0;
    virtual bool ReserveSeidsBefore(Seid nextSeid) = 0;
    virtual ICloseableOutputStream* WriteSerialElement(Seid seid) = 0;
    virtual bool DeleteSerialElement(Seid seid) = 0;
};

An IMutableSpace is owned by its partition transaction and becomes invalid when that transaction is closed. Its reads and mutations belong to that transaction. A returned output stream must be closed before another mutative operation is performed through the transaction.

It is illegal to pass NULL_SEID as the seid argument to SerialElementExists(), ReadSerialElement(), ReadContiguousSerialElement(), WriteSerialElement() or DeleteSerialElement(). In particular, null is not treated as a valid but nonexistent serial-element identifier.

Allocating Seids

Seid allocation information is part of a Partition's persistent state. It is updated atomically by partition transactions and is available to readers through MVCC snapshots. It can only be updated through an IMutableSpace owned by an IPartitionTransaction. It can only be read through either an ISpaceView owned by an IPartitionView or an IMutableSpace owned by an IPartitionTransaction.

The allocation state of a Space is represented by an exclusive frontier called its next Seid. Allocatable Seids are in the range [0, 0xffffffff). All allocatable Seids less than the next Seid are reserved, while the next Seid itself is available for allocation unless it equals 0xffffffff. A next Seid of 0xffffffff indicates that the Space is exhausted. The frontier never moves backwards, and Seids cannot be unallocated or reused.

Seid allocation and serial-element existence are distinct. Allocating or reserving a Seid does not create a serial element. A serial element exists in the resulting partition state only after a partition transaction successfully writes it. Deleting a serial element removes the element but does not release its Seid.

AllocateSeids(count) returns the first Seid in a newly allocated contiguous range [first, first + count). The count may be zero. In that case no Seids are allocated and the function returns the next Seid, allowing the caller to determine how many Seids remain available in the Space. The operation fails without changing the allocation frontier if the requested range would extend beyond 0xffffffff. The limit check is performed without unsigned integer wraparound. For a nonzero count, the returned Seid is never NULL_SEID. A zero-count allocation returns NULL_SEID when the Space is exhausted.

ReserveSeidsBefore(nextSeid) ensures that every valid Seid less than nextSeid is reserved. It advances the Space's allocation frontier when necessary and returns true if the frontier was advanced. It returns false if the requested range was already reserved. The greatest frontier which may be requested is 0xffffffff.

Writing and deleting serial elements

WriteSerialElement(seid) does not fail merely because the given Seid has not previously been allocated or reserved. When necessary, writing the serial element implicitly advances the Space's allocation frontier sufficiently to cover the Seid. The frontier advancement and serial-element write are part of the same partition transaction. Consequently, AllocateSeids() is an optional convenience for obtaining fresh Seid values, not a prerequisite for writing serial elements. Because 0xffffffff is both NULL_SEID and the exhausted-frontier value, it is not an allocatable Seid.

IPartitionTransaction

struct IPartitionTransaction
{
    virtual PartitionId GetPartitionId() const = 0;
    virtual TxnSequenceNumber GetTxnSequenceNumber() const = 0;
    virtual IMutableSpace* FindSpace(SpaceId spaceId) = 0;
    virtual IMutableSpace* CreateSpace() = 0;
    virtual void DeleteSpace(IMutableSpace* space) = 0;

    virtual void FlushWhenClose() = 0;
    virtual void Close() = 0;
    virtual IPartitionView* CloseAndPublishSnapshot() = 0;
};

An IPartitionTransaction holds the mutex of its containing Partition. At most one such transaction is open on a partition. Transactions on different partitions are independent and may be open concurrently. A transaction never spans partitions.

Transaction sequence numbers

Each Partition has its own independent sequence of transaction sequence numbers. Creating a Partition establishes an initial immutable snapshot containing no Spaces and assigns that snapshot transaction sequence number zero. The first mutative transaction opened on the Partition is assigned one, and each subsequently opened transaction is assigned the next number in that Partition's sequence. Opening and closing a transaction consumes its assigned number even when the transaction makes no changes.

GetTxnSequenceNumber() returns the partition-local sequence number assigned when the mutative transaction is opened. The value is stable for the lifetime of the transaction and is the value subsequently written in its Snapshot record. During crash recovery, each Partition recovers its transaction sequence independently. The first transaction opened after recovery is assigned one greater than the sequence number of the last recovered transaction. Every valid recovered Partition has at least its initial transaction-zero snapshot.

The store may internally perform atomic writes on a Partition while cleaning or checkpointing. These maintenance writes are not partition transactions, are not assigned transaction sequence numbers and do not increment the Partition's transaction sequence number.

Managing Spaces

CreateSpace() allocates a new, unused SpaceId and returns the transaction's mutable interface for that Space. It fails without changing the transaction if the SpaceId domain is exhausted; it never allocates NULL_SPACE_ID.

FindSpace() returns null when the transaction does not contain a Space with the given SpaceId. Passing NULL_SPACE_ID is illegal.

DeleteSpace() removes a Space from the transaction. The Space must contain no serial elements, and the supplied IMutableSpace must not be used after the call. A deleted SpaceId is never reused. Older partition views continue to contain the Space, while views published from the deleting transaction do not. Physical reclamation is deferred while an older retained snapshot can still access the deleted Space.

Closing a transaction

Closing a partition transaction commits its allocation-frontier changes atomically with its other changes. Once an allocation or reservation is durable, it is permanent. Calling FlushWhenClose() before closing requests that this transaction and preceding transactions on the same Partition be flushed before the close returns. Without that request, a completed transaction may be published to readers before it is guaranteed to survive a storage failure; recovery nevertheless observes either the transaction's frontier changes and serial-element changes together or neither of them.

There is no transaction abort. Close() completes the transaction without publishing a reader snapshot. CloseAndPublishSnapshot() completes the transaction, publishes its immutable partition snapshot and returns a partition view pinned to that exact snapshot. Both functions consume the mutative transaction.

Affiliate Seids

Version 1 provided a concept of affiliate Seids, in which allocation attempted to place a new Seid near an existing related Seid. Affiliate Seid allocation is not currently planned for Version 2. Before it is added to the Version 2 API, it must be shown to provide a useful benefit that justifies the additional allocation policy and implementation complexity.

GetSeidsInSeidSpace()

Version 1 provided GetSeidsInSeidSpace() for enumerating the Seids of serial elements in a Seid space. This operation is not currently planned for Version 2. Before an equivalent operation is added to the Version 2 API, it must be shown to provide a useful benefit that justifies the additional API and implementation complexity.

Open modes

Version 2 defines EOpenMode directly and has no dependency on the cxUtils definition:

enum class EOpenMode
{
    CreateNew,
    CreateAlways,
    OpenExisting,
    OpenExistingReadOnly,
    OpenExistingSharedRead,
    OpenAlways,
    DeleteExisting,
};

An operation fails rather than returning a null resource when the selected mode requires existence or nonexistence and that precondition is not met. A resource opened with either read-only mode does not permit a mutative transaction.

Partitions

struct IPartition
{
    virtual PartitionId GetPartitionId() const = 0;
    virtual IPartitionView* OpenView() const = 0;
    virtual IPartitionTransaction* OpenTransaction() = 0;
    virtual void Close() = 0;
};

IPartition::OpenView() returns a view pinned to the Partition's last published immutable snapshot. It does not create a snapshot of the latest completed transaction. The returned view can therefore be very stale if mutative transactions have been completed with Close() rather than CloseAndPublishSnapshot().

OpenView() exists so that a client which obtains a Partition in order to read it does not first have to open a mutative transaction merely to publish a view. When CreateOrOpenPartition() opens or creates a Partition, the implementation publishes its recovered or initial snapshot. The client can then call OpenView() immediately.

An IPartition may be used concurrently by multiple threads. Partition state is read through immutable IPartitionView snapshots and changed through IPartitionTransaction. At most one mutative transaction is open on a Partition, while any number of views may be used concurrently.

Stores

Managing Partitions

struct ILss
{
    virtual ~ILss() = default;
    virtual IPartition* CreateOrOpenPartition(
        PartitionId partitionId,
        EOpenMode openMode) = 0;
    virtual void DeletePartition(PartitionId partitionId) = 0;
    virtual void Close() = 0;
};

Repeated calls to CreateOrOpenPartition() for the same PartitionId are permitted. The LSS maintains at most one live in-memory IPartition instance for each PartitionId, so successful calls made while an instance is live return references to that instance. Each successful call acquires one reference, and its caller must release that reference with exactly one call to IPartition::Close(). Closing one reference does not invalidate other references. After the final reference is closed, a later call may create a new interface instance for the same persistent Partition; pointer identity is not persistent.

Partition ID zero is valid and is PRIMARY_PARTITION_ID. CreateOrOpenPartition() returns an open Partition or fails according to the supplied EOpenMode; it never reports absence by returning null. Passing NULL_PARTITION_ID to CreateOrOpenPartition() or DeletePartition() is illegal.

Calls to CreateOrOpenPartition() and DeletePartition() are serialized by a mutex on the LSS. Each operation is atomic and durable. When a call which creates a Partition returns successfully, the Partition and its transaction-zero initial snapshot, containing no Spaces, will exist after recovery from a subsequent failure. When a deletion returns successfully, the Partition will not exist after recovery.

Creating a Partition atomically adds it to the LSS's persistent set of Partitions. Replacing an existing Partition with EOpenMode::CreateAlways or EOpenMode::DeleteExisting, and deleting one with DeletePartition(), requires that it have no open IPartition references and therefore no open transactions, views, streams or buffers. Replacement first deletes the persistent Partition and then creates a new empty Partition having the same PartitionId as one atomic durable operation.

Opening a store

using RASAddress = int64;
using RASSize = RASAddress;

struct IRAS
{
    virtual bool IsReadOnly() const = 0;
    virtual RASSize GetSize() const = 0;
    virtual void Read(void* buffer, RASAddress offset, int numBytes) = 0;
    virtual void Write(const void* buffer, RASAddress offset, int numBytes) = 0;
};

struct LssSettings;

std::unique_ptr<ILss> CreateOrOpenLss(
    std::unique_ptr<IRAS> ras,
    bool openReadOnly,
    const LssSettings& settings);

The listed IRAS operations are those relevant to opening an LSS; the complete interface provides additional storage operations. The RAS has already been opened as a storage object. IRAS::IsReadOnly() reports whether that storage object permits writes.

CreateOrOpenLss() opens an existing LSS or creates one when the RAS is new. It uses GetSize() to distinguish a new RAS from one which can contain an LSS root block. If a root block can be present, the function reads and validates it, including its format markers and checksums. A root block which cannot be read, is corrupt, has an unsupported format or does not identify an LSS causes the operation to fail; it is not treated as a new store and is not overwritten.

Creating an LSS requires a mutable RAS. Opening an existing LSS permits a read-only or mutable RAS. Passing openReadOnly == true requests a read-only LSS even when IRAS::IsReadOnly() is false. The resulting LSS is read-only when either the RAS is read-only or openReadOnly is true.

A read-only LSS permits immutable views but does not permit operations which would modify its persistent state, including creating, replacing or deleting Partitions and opening mutative partition transactions. An attempt to perform such an operation reports an error. Read-only access violations, I/O failures, invalid arguments, unsupported formats and detected corruption are all reported through the API's error mechanism; they are not represented by null interface pointers or silently ignored.

The store owns the RAS passed to CreateOrOpenLss(). The returned unique_ptr owns the LSS interface. All Partitions, transactions, views, streams and contiguous serial elements must be closed before the LSS is closed.

Errors

The Version 2 error model has not yet been selected. The following issues must be resolved before the interfaces in this chapter form a complete public API contract:

• Whether failures are reported using C++ exceptions, explicit result values or another mechanism. If exceptions are used, their public types, meanings and inheritance hierarchy are part of the API and must be specified.
• Which failures are distinguished, including invalid arguments, read-only access violations, allocation exhaustion, unsupported formats, I/O failures and detected corruption.
• What happens when an opened LSS appears to be corrupt, including which observations are sufficient to classify it as corrupt and whether any operation may continue afterward.
• Whether an I/O failure or detected corruption puts the LSS, its underlying RAS, or both into a zombie state. Such a state would prevent further reads and writes from accessing the file while still allowing resources to be released.
• Whether a failed operation leaves its interface usable, leaves its transaction usable, consumes the operation, or changes the LSS to a zombie state.
• How errors interact with every Close() operation. The API must specify whether closing can fail or throw, whether it must still release resources after an earlier failure or in the zombie state, and how a failure while committing, flushing or publishing a transaction is reported.
• Which cleanup operations remain valid after an error and the order in which streams, views, transactions, Partitions, the LSS and its owned RAS must then be closed.