63 Other Proposals

This chapter collects smaller proposals that do not warrant a separate chapter. The proposals describe possible future changes and are not descriptions of the current implementation.

Avoid references from LSS modules back to `LSS`

The LSS object should be the composition root and coordinator of the storage engine. A module owned by it should not normally retain an LSS& through which it can reach the entire implementation. Such upward references reverse the desired dependency direction: the parent knows its children, but each child can also know and call any other child through the parent.

The current implementation uses this pattern extensively. Examples include SegmentCache, SegmentBase, SegmentWriter, SUT, LargeSUT, RPMNode, RootBlock, LazyWriter, LazyCleaner and LazyCheckPointer. The reference is convenient, but it gives each class an effectively unbounded private API and conceals its real dependencies.

Problems caused by the upward reference

The header or implementation usually needs visibility of LSS, increasing compile-time coupling and making dependency cycles easy to introduce.
A class declaration does not reveal which services it requires. A constructor taking LSS& could use the RAS, SUT, RPM, SegmentCache, error state, settings, checkpointing or any combination of them.
The class can bypass the intended API of a neighbouring module and manipulate a lower-level mechanism directly. This makes module invariants and locking responsibilities harder to identify.
The class is difficult to instantiate and test independently because a complete or heavily mocked LSS must be provided even when only one narrow service is required.
Changes to the internal organization of LSS propagate into modules which should depend only on stable lower-level contracts.

This is principally an architectural problem, not an objection to storing references or using dependency injection. A module should retain references to the specific lower-level services it needs. It should not use its owning aggregate as a service locator.

Replace `LSS&` with narrow capabilities

For each module, list every operation currently invoked through lss_ and group those operations into coherent lower-level capabilities. Constructor parameters should then state those requirements explicitly. The capabilities need not use virtual dispatch: references to concrete module APIs or small value/context objects can preserve the present performance characteristics.

For example, SegmentBase currently uses LSS& to obtain the RAS, segment size and file position of a segment. These constitute a segment-I/O capability rather than a need for the whole LSS:


class SegmentStorage
{
public:
    int GetSegmentSize() const;
    int GetDiskSectorSize() const;
    octet_t* AllocateBuffer();
    void FreeBuffer(octet_t* buffer);
    void ReadSegment(SegId segid, octet_t* buffer);
    void WriteSegment(SegId segid, const octet_t* buffer);
    void WriteSegmentSection(SegId segid, int begin, int end, const octet_t* buffer);
};

class SegmentBase
{
public:
    SegmentBase(SegmentStorage& storage, SegId segid);

private:
    SegmentStorage& storage_;
};

Similarly, SegmentCache needs segment storage plus a place to report file errors. A Segment needs segment storage and a way to release itself to its owning cache; it does not need to navigate through LSS::GetSegmentCache(). The cache can pass itself or a narrow release callback when constructing the segment.

Background scheduling helpers are particularly simple cases. LazyCheckPointer needs an operation which performs a synchronous checkpoint, while LazyFlusher needs an operation which flushes the log. They can receive those operations or the corresponding narrow module references without retaining the entire LSS.

Desired dependency direction

The intended shape is downward and explicit:

LSS coordinator
    - constructs modules
    - supplies their declared dependencies
    - coordinates operations spanning modules

high-level protocols
    checkpoint, recovery, cleaning, transactions
        |
        v
storage mechanisms
    RPM, SUT, SegmentWriter, SegmentCache
        |
        v
physical storage
    segment I/O, RootBlock I/O, IRAS

An operation which genuinely spans sibling modules should normally be coordinated above them rather than implemented by one sibling reaching through LSS into another. This keeps the sibling contracts independently understandable and makes the cross-module ordering visible in the coordinator.

Avoid replacing one service locator with many trivial interfaces

The proposal is not to create an interface for every method or to divide the implementation into arbitrarily small classes. A useful capability should correspond to a coherent service with a stable invariant, such as segment storage or pinned segment access. If every class receives a large bundle of unrelated one-method interfaces, the original coupling has merely been made more verbose.

Nor must every short-lived algorithm object be treated as an architectural module. A visitor local to recovery or dumping may reasonably receive an operation context containing the resources for that operation. The important rule is that long-lived owned modules should expose their required dependencies and should not gain unrestricted access to their parent aggregate.

Migration

Inventory every class storing LSS& and every method it calls through that reference.
Identify the existing module which should own each required operation. Where no clear owner exists, treat that as evidence of an unresolved module boundary rather than immediately creating an interface.
Start with relatively independent lower-level cases such as SegmentBase and SegmentCache. Replace their upward references with explicit storage, error-reporting and ownership capabilities.
Move cross-module workflows into an LSS-level coordinator or an explicit operation object. Preserve the current lock scopes and ordering while doing so.
Add focused tests which instantiate each extracted module with its direct dependencies. The ability to do this without constructing an LSS is one test of whether the new boundary is useful.
Once a module has been migrated, prevent its source subtree from including LSS.h or calling back into LSS, except through an explicitly documented transitional adapter.

Unresolved boundaries

Some dependencies cannot yet be removed mechanically because they expose real architectural questions:

RPM updates also change SUT utilisation and acquire SUT reservations. It must be decided whether that coordination belongs in a higher-level packet-placement operation or in a narrow utilisation capability supplied to the RPM.
LargeSUT stores its own sections in segments allocated and cached by the same storage engine whose allocation state it represents. The self-hosting and checkpoint protocol must remain atomic while its dependencies are made explicit.
SegmentWriter jointly uses the SUT allocator, SegmentCache, log/checkpoint thresholds and checkpoint notification. Separating these dependencies must not split the invariant governing the current and next log segments.
RootBlock publication serializes state belonging to several modules. The correct boundary between root-block I/O and checkpoint coordination needs to be established before removing its LSS&.
The common file-error state is currently reached through LSS. It remains to be decided whether failures should be returned directly, recorded through a narrow error sink, or place the whole store into an explicit failed state.

These points should remain recorded as unresolved design work. Removing LSS& is successful only when it reveals a coherent dependency structure; replacing the reference while preserving the same hidden cycles would be a cosmetic change.

Rename the Free Segment Stack as the Free Segment Set

The FSS should be renamed from Free Segment Stack to Free Segment Set in the implementation and documentation. The acronym can remain FSS, so the new name is more accurate without introducing a second abbreviation for the same concept.

The FSS is conceptually the set of SegIds that are currently safe to allocate and overwrite. Stack semantics are not part of its contract. In particular, the current SegIdStack type does not implement LIFO behaviour: Push() appends at the back of its underlying std::deque, while Pop() removes from the front. Furthermore, when entries from the delta-FSS become reusable, the implementation sorts the combined FSS by SegId. Allocation therefore normally selects the lowest available SegId rather than the most recently freed SegId.

The ordering is an allocation policy layered on top of set membership. Preferring low SegIds helps cluster consecutive writes in nearby parts of the file and favours reuse near the front, making it more likely that unused segments accumulate at the end where the file could eventually be truncated. Calling the structure a stack obscures both its membership semantics and this deliberate ordering policy. Calling it a queue would also be inaccurate because checkpoint transfer can reorder all its entries.

The code change should rename terminology such as SegIdStack, comments, trace output and identifiers where they imply stack semantics. The replacement container name should avoid promising a particular implementation strategy: for example, a name such as FreeSegmentSet can expose insertion, removal and membership operations while keeping lowest-SegId-first allocation as an explicit policy. The delta-FSS should use correspondingly neutral terminology because it too is a collection of segment identifiers rather than a LIFO stack.

The documentation should consistently expand FSS as Free Segment Set while continuing to explain the ordered allocation policy separately. This is principally a source and documentation rename; the words and C++ type names are not part of the persistent LSS representation, so the proposal should not require an on-disk format change. Any externally visible diagnostic text or source-level API names should nevertheless be reviewed for compatibility before completing the rename.

Support a raw disk partition

The persistent LSS implementations currently store the LSS in a file on Windows or Linux. A future implementation could also use a raw disk partition as the linear storage medium behind the IRAS abstraction.

IRAS would be implemented on a partition in the same manner as on a fixed-size file.

Represent a log-record position as a linear offset

The current LogRecordPosition stores a segment identifier and an offset within that segment:


struct LogRecordPosition
{
    SegId segid_;
    int32 offset_;
};

It could instead store a single uint64 offset measured from the start of the first segment in the LSS file:


struct LogRecordPosition
{
    uint64 offset_;
};

Because the segment size is a power of two, the segment identifier and the offset within the segment can be recovered efficiently. If segmentSize == 1 << segmentSizeLog2, the segment identifier is offset_ >> segmentSizeLog2 and the offset within the segment is offset_ & (segmentSize - 1). Converting the value to an absolute file offset additionally requires adding the file position of the first segment.

This would give a log-record position a simple linear representation while retaining constant-time access to its two logical components. Its principal advantage is that a log-record position would no longer be limited by a 32-bit segment identifier. A 64-bit byte offset can address up to 16 EB, whereas the current documentation quotes a maximum store size of about 500 TB.

The 500 TB figure assumes 512 kB segments and arises from the current two-level Segment Utilisation Table (SUT). One 512 kB SUT-section contains 128k four-byte utilisation entries and therefore covers 64 GB of the store. The SUT-root is an array of four-byte segment identifiers stored in one division of the 64 kB root block. Approximately 8,000 such references can fit in the division, allowing the SUT to describe roughly 500 TB.

Changing LogRecordPosition alone would not raise the store-size limit. The SUT, free segment stack, segment cache, file-address calculations, and other structures also use the 32-bit SegId. They would need to be changed as part of the larger-store design. Because log-record positions are stored in persistent LSS structures, adopting the representation also requires an on-disk format change or a compatibility mechanism for existing stores.

Ensure that `FlushWhenClose()` provides durability

Ordinary LSS transaction processing deliberately does not flush the log on every close. This is central to its serial transaction throughput. FlushWhenClose() is an exceptional operation for cases that must coordinate with an external durability protocol, such as two-phase commit. Two-phase commit is a blocking protocol whose coordination and durability barriers make it expensive and impractical and are contrary to the normal LSS fast path; supporting it is not an endorsement of using it.

When that exceptional operation is requested, it is intended to make the transaction, and every transaction preceding it, durable before ILssTransaction::Close() returns. The current implementation closes the current flush unit and calls LSS::Flush() while retaining the transaction's log-record sequence lock. This drains the relevant work from the lazy writer and writes it through the RAS. It waits for the RAS writes to complete, but the RAS interface has no operation that asks the operating system and device to make those writes durable. Data may therefore remain in an operating-system or volatile device cache after Close() returns.

The RAS should provide an explicit durability operation. Its name should make the stronger semantics clear; for example:

struct IRAS
{
    // Write data without requiring an immediate durability barrier.
    virtual void Write(const void* buffer, RASAddress offset, int numBytes) = 0;

    // Make every preceding write durable on non-volatile storage.
    // Return only after the storage stack reports completion; throw on failure.
    virtual void FlushToNonVolatileStorage() = 0;
};

Durability should be separate from Write(). Requiring every write to be durable would prevent the lazy writer from batching sequential writes and would impose a storage barrier for every flush unit. An explicit operation allows many writes and transactions to be covered by one barrier. Opening a file in a mode that forces every write to stable storage can remain an optional configuration, but it should not be required for correct implementation of FlushWhenClose().

Required ordering

When a transaction marked with FlushWhenClose() is closed, the LSS should perform the following operations in order:

Finish adding the transaction's log records and close its current flush unit while retaining transaction serialisation.
Drain the lazy-writer queue through that transaction, waiting for all preceding RAS writes to complete.
Call IRAS::FlushToNonVolatileStorage().
Release the transaction's log-record sequence and return from ILssTransaction::Close() only after the durability operation succeeds.

Retaining transaction serialisation through the barrier prevents a later transaction from entering the log before the required durability point has been established. The barrier may cover more data than strictly required, but it must never cover less. Any error while writing or flushing must be reported to the caller; a failed durability operation must not be presented as a successful durable close.

Check pointing requires the same primitive. Before a new root-block division publishes a check point, all log and snapshot data referenced by that division must be made durable. After writing the new division, a second durability barrier is required before the check point can be considered durable. The required order is therefore:

write referenced log data
flush to non-volatile storage
write the new root-block division
flush to non-volatile storage

Linux mapping

For a file-backed RAS on Linux, the conservative implementation is fsync(fd). It flushes modified file data and the metadata needed to make the file state persistent. fdatasync(fd) may be sufficient when only file data and metadata required for subsequent retrieval need to be durable, but that choice must be checked against file growth, truncation, preallocation, and every supported filesystem. Using O_DIRECT does not remove the need for a durability operation, and using O_SYNC or O_DSYNC for every write is not required by this design.

If creating, renaming, or replacing the LSS file is part of the durability promise, the containing directory may also need to be opened and passed to fsync(). That is a file-lifecycle concern and need not be repeated for every transaction in an already established file.

Windows mapping

For a file-backed RAS on Windows, the explicit operation should call FlushFileBuffers(hFile) and report failure using the existing file exception mechanism. This supports batching when the file is opened without FILE_FLAG_WRITE_THROUGH. Write-through may remain available as an optional setting, but enabling it should not be necessary for FlushWhenClose() to request a durability barrier.

Neither operating system can compensate for a storage device or virtualisation layer that falsely reports completion before data is safe. The contract is therefore that the LSS issues the correct platform durability request, waits for it, and propagates errors—not that it can overcome dishonest or faulty hardware.

Verification

The change should be tested using an instrumented RAS that distinguishes completed writes from durable writes. Simulated power failure should discard completed but non-durable writes. Tests should verify that:

a transaction closed with FlushWhenClose() survives the simulated failure;
all preceding transactions survive the same failure;
transactions not covered by a completed barrier are allowed to disappear;
several transactions can be covered by one barrier;
write and durability failures are propagated by Close(); and
check point data is durable before the root-block division that references it is made durable.

Delay root-block division publication until its dependencies are durable

The check point protocol must be reviewed specifically for failures in which writes reach non-volatile storage out of order. A new root-block division can be internally valid—its sequence values and CRC may all be correct—while some log, snapshot, SUT, or RPM data referenced by that division has not yet become persistent. After a power failure, recovery may then select the new division but be unable to validate or reconstruct the state it describes.

The primary fix is to delay writing the new root-block division. The division is the publication record for the check point and must be the last check point state written. It must not be issued until all data it will reference has been written and an explicit durability barrier for that data has completed. Once the division is written, a second durability barrier is needed before the check point can be reported as complete.

This is a dependency-based delay, not a time delay. Sleeping, waiting for a periodic flusher, or merely waiting for preceding IRAS::Write() calls to return does not establish persistence or prevent reordering. The first IRAS::FlushToNonVolatileStorage() call is the event that permits the delayed root-block write.

The alternating root-block divisions protect against a torn write of a division itself. They do not, by themselves, order that write after writes to other parts of the LSS file. The recovery algorithm does, however, validate the segment containing the newest division's check point through the recorded position. If that validation fails, it rejects the newest division and reverts to the other division. This makes the current LSS more robust than a design that selects a root-block division solely from its sequence values and CRC.

The investigation should establish and document the check point publication invariant:

A root-block division must not be written until every item of persistent state needed to recover from it has been made durable. It must not be accepted as a completed check point until the division itself has subsequently been made durable.

The current implementation should be traced from creation of the check point records through SegmentWriter, LazyWriter, IRAS::Write(), and RootBlock::WriteNextDivisionToDisk(). The analysis must identify:

every log, snapshot, SUT, RPM, and file-size write on which the new division depends;
which writes have merely completed at the API boundary and which have reached non-volatile storage;
whether the operating system, filesystem, controller, or device may persist the new division first;
when the previous root-block division and the segments needed by it cease to be a valid fallback; and
whether segment recycling can overwrite data still needed to recover from the previous division.

Delayed publication protocol

The current implementation already places RootBlock::WriteNextDivisionToDisk() after SegmentWriter::FlushLastFlushableLRSForCheckPoint(). This is the right high-level order, but the latter operation waits only for RAS writes to complete; it does not establish that they are durable. If the explicit RAS durability operation proposed above is adopted, the delayed publication protocol should be:

Write all log, snapshot, allocation, and other persistent state that the new check point will reference.
Drain those writes and call IRAS::FlushToNonVolatileStorage().
Only after that barrier succeeds, write the next root-block division.
Call IRAS::FlushToNonVolatileStorage() again.
Only then report the check point as durable and permit retirement or reuse of state needed solely by the previous check point.

The first barrier prevents the root-block division from overtaking the data it references. The second barrier establishes that the division itself is durable before later operations rely on its publication. This protocol deliberately batches the dependent writes; it does not require every RAS write to be synchronously durable.

Recovery fallback

Recovery already rejects the newest root-block division and retries the previous division when the segment containing the new check point fails validation. This is an important existing defence against out-of-order persistence. The investigation should verify its scope: in particular, which other referenced structures are validated before the new division is accepted, and that all data needed by the previous division remains intact until the new check point is safely established.

Correct publication ordering remains desirable even with this fallback. It avoids reverting to an older check point unnecessarily, reduces the correctness burden placed on retention and validation of the previous state, and protects dependencies that may not be covered by validation of the check-point segment alone.

Failure testing

An instrumented RAS should model completed writes, durable writes, torn writes, and arbitrary persistence order. Tests should introduce a simulated power failure before and after every write and durability barrier in the check point sequence. For every reachable persisted state, reopening the store must produce one of the explicitly permitted outcomes:

recover from the newly published check point;
recover from the preceding check point when publication of the new one was incomplete; or
report an underlying I/O failure that made neither state recoverable.

A valid root-block division that refers to non-durable data must not cause silent loss, acceptance of inconsistent state, or an avoidable corrupt-store result. The tests should cover Windows and Linux file-RAS behaviour, buffered and direct I/O where supported, device write caching, repeated failure during recovery, and segment cleaning around the check point boundary.

Replace `GetDiskSectorSize()` with explicit I/O requirements

IRAS::GetDiskSectorSize() is poorly named. An RAS may be backed by a file, raw partition, virtual device, memory store, HDD, SSD, or NVMe device, so it is not necessarily a disk. The term sector size is also ambiguous: it can refer to a logical block, physical block, atomic-write unit, or direct-I/O alignment. The LSS does not assume that a write of this size is atomic.

The current value is principally used to constrain RAS file offsets, transfer lengths, and allocated buffer addresses. A minimal improvement would therefore be:

virtual int GetIoAlignment() const = 0;

Related source names such as diskSectorSize_ should become ioAlignment_, and the documentation should describe flush units as I/O-aligned rather than sector-aligned. This would clarify the present intent without suggesting sector atomicity.

A single alignment value may nevertheless be insufficient. Depending on the operating system, filesystem, and device, the required alignment of a file offset, transfer length, and memory-buffer address can differ. A more robust interface would return the requirements separately:

struct IoRequirements
{
    int offsetAlignment;
    int lengthAlignment;
    int bufferAlignment;
};

virtual IoRequirements GetIoRequirements() const = 0;

The file RAS should query these requirements using the facilities of the host operating system rather than returning the current hard-coded 512-byte value. The memory RAS can report the natural requirements of its implementation. Buffer allocation, segment sizing, root-block layout validation, flush-unit padding, and every RAS read and write should use the appropriate member rather than a single assumed sector size.

Logical block size, physical block size, and atomic-write size should not be folded into IoRequirements. They are different device properties and should be exposed separately only if an LSS algorithm has a defined use for them. In particular, an alignment value must never be interpreted as an atomicity guarantee.

The current root-block header stores the value under the historical meaning of disk sector size. Renaming the source-level field and clarifying its interpretation need not change the binary file format if it remains the same integer. Supporting alignments incompatible with the current 1 kB root-block boundaries is a separate format issue: the implementation must either reject such a store with a clear diagnostic or introduce a new root-block layout and compatibility mechanism.

Investigate a more efficient checksum

Investigate checksum algorithms that are significantly faster than CRC32 while still providing appropriate protection against corrupted or partially written data. The selected checksum would be used both for the divisions of the root block and for log flush units.

One possibility is to retain the existing CRC32 but calculate it using carry-less multiplication. Implementations can fold multiple blocks of input in parallel using instructions such as x86 PCLMULQDQ or VPCLMULQDQ, or Arm PMULL. If the implementation uses exactly the same polynomial and initial and final processing, this could improve performance without changing the on-disk format. A proven optimized implementation, such as one provided by a storage-oriented library, should be considered before writing a new implementation.

Another candidate is CRC32C. Modern x86 and Arm processors commonly provide dedicated CRC32C instructions. These are checksum instructions rather than SIMD instructions, but can nevertheless be very fast. CRC32C uses a different polynomial from the conventional IEEE CRC32, so adopting it would normally require an on-disk format change or a compatibility mechanism for existing stores.

XXH3 is also worth investigating. It is a fast non-cryptographic hash with implementations using SSE2, AVX2, AVX-512, NEON and VSX, and provides 64-bit and 128-bit results. A 64-bit result would provide a much lower probability of an accidental collision than a 32-bit result, but would enlarge the checksum fields in the root block and flush unit headers and therefore change the on-disk format. Truncating it to 32 bits would avoid enlarging the fields but would discard that advantage.

XXH3 does not provide the formally defined burst-error detection properties of a CRC. Those properties may not be essential for the LSS because the checksum is primarily intended to reject partially written flush units, stale data in recycled segments, and inconsistent writes rather than to protect a communication channel. This should be decided explicitly from the required failure model rather than inferred from throughput measurements alone.

The investigation should:

Implement or obtain an optimized calculation of the existing CRC32 and determine whether it preserves the current on-disk format.
Benchmark hardware-accelerated CRC32C.
Benchmark XXH3-64 as a possible checksum for a new on-disk format.
Measure small and large flush units separately, because setup and final-reduction costs may be significant for small inputs.
Assess the corruption patterns detected by each candidate, as well as its throughput.

Any implementation using processor-specific instructions would need runtime dispatch and a portable fallback unless the supported processor baseline already guarantees those instructions. This is a proposal to replace CRC32 with a more efficient checksum, not to allow the LSS to operate without checksums.

Previous62 Arena allocation for RPM nodes NextPart VIII: History