73 Partition

Purpose

An LSS can be divided into a number of Partition objects. An Partition is a coarse-grained physical and logging division of the store. It is heavier than a Space and normally contains many Spaces.

The purpose of partitioning is to increase parallelism when writing segments and to improve data locality. Independent partitions can build and submit segment writes concurrently. Data belonging to different uses of the LSS can be written to different segments, allowing related data to remain physically clustered.

Owned and shared components

Each Partition has its own:

• log and current log position;
• segment writer and write-progress state;
• collection of Spaces and their four-level RPM roots; and
• Segment Utilisation Table (SUT) for the segments assigned to the partition.

All partitions in an LSS share:

• the Random Access Store (RAS); and
• the Segment Cache.

LSS
    RAS
    SegmentCache

    Partition
        Log
        SegmentWriter
        SUT
        Space ...

    Partition
        Log
        SegmentWriter
        SUT
        Space ...

The RAS remains responsible for asynchronous access to the underlying storage, while the shared segment cache provides one bounded pool of resident segments across the LSS. Partitioning does not create a separate physical file or cache for every partition.

Relationship to Spaces

A Space is a lightweight logical namespace containing 32-bit Seids and a four-level RPM. It does not have its own log, segment writer, SUT, RAS or segment cache. Every Space belongs to one Partition, and packets addressed through that Space are written to the log of that partition.

An Partition is deliberately more coarse-grained. Creating a Space should be cheap enough to support many thousands of independent namespaces. Creating a partition establishes substantial logging, utilisation and write-coordination state, so the number of partitions should be much smaller.

class Partition
{
    // Heavyweight physical/logging domain
    std::mutex mutex;
    SegmentWriter writer;
    SUT sut;
    SpaceDirectory spaces;
};

Mutative transactions

Each Partition has a mutex which ensures that at most one thread at a time writes the log records for a mutative transaction into the partition's segments being prepared in memory. Transactions never span Partition objects.

The mutex orders transaction log records in the in-memory log. A transaction writes its log records followed by its snapshot record before releasing the mutex. A snapshot record does not need to identify its transaction because no other transaction can write records to that partition while the mutex is held.

As in Version 1, a lazy writer writes prepared segments to the RAS. It is allowed to be many segments behind the segments being prepared in memory. Completion of a mutative transaction does not mean its log records or snapshot record have been written to disk or made durable.

Transactions in different partitions can concurrently prepare their respective in-memory segments. Each partition has its own log, segment writer and lazy writer.

Mutex protection boundary

In Version 1 the SegmentWriter owns the transaction mutex, while the RPM7 root node and the SUT each have their own mutex. In Version 2 the transaction mutex belongs to Partition, where it protects the SegmentWriter, SUT and the mutable RPMs belonging to its Spaces. This places the mutex on the object which owns the complete partition-level mutation boundary.

A Version 2 mutative transaction therefore locks fewer mutexes than a Version 1 transaction, reducing mutex-acquisition overhead.

The partition mutex does not protect traversal through published immutable RPM roots. Readers retain an immutable root and traverse it without holding the partition mutex. Lazy loading into such roots uses the atomic child pointers described in the RPM chapter.

The partition mutex is not held while the lazy writer performs RAS I/O. Prepared segments can be written after the mutative transaction has released the mutex.

Parallel segment writing

Within each partition, the partition mutex allows one thread at a time to construct transaction log records in its in-memory segments. Different partitions can prepare log segments in memory at the same time. Their lazy writers can write prepared segments to the shared RAS concurrently.

Parallelism does not require one thread per partition. The Version 2 event-driven implementation can advance each partition's writer when work or RAS completions are available. A bounded shared I/O service can service writes for many partitions without giving every partition dedicated threads.

The RAS or an LSS-level segment allocator must assign non-overlapping physical segment locations to the partitions. A partition owns the contents and utilisation state of its assigned segments, while the shared RAS performs the physical writes.

Data locality

Without partitions, unrelated applications or workloads can append packets to the same sequence of log segments even when the workloads are accessed and cleaned independently. Assigning related Seid spaces to one partition keeps their packets in that partition's segments and prevents unrelated partitions from writing packets into those segments.

Several independent divisions of the store may each perform many transactions per second. With one log, successive transactions from those divisions append their packets to the same sequence of segments.

With separate partition logs, transactions in different partitions can execute concurrently and append packets to different segments. Successive transactions for one division therefore write to that partition's segments.

This can improve locality when reading, prefetching, caching and cleaning. A segment is more likely to contain packets used by the same related group of Spaces. Cleaning decisions based on the partition's SUT also operate on a physically coherent set of segments rather than a mixture of unrelated workloads.

Partitioning is not the only source of locality. Spaces localise RPM traversal and allocation metadata, while Partition localises physical log placement. The two mechanisms operate at different scales and complement one another.

Shared segment cache

The segment cache is shared so its memory limit can be applied across the complete LSS. Idle partitions do not retain private caches while an active partition is under memory pressure. Cache entries must identify segments unambiguously across partitions, either because SegId is unique within the whole LSS or because a cache key contains both a partition identifier and a partition-local segment identifier.

An Partition does not make the segment cache perform I/O. As described in the Segment Cache chapter, cache lookup, RAS submission and completion handling remain separate responsibilities.

SUT and cleaning

Each partition's SUT describes utilisation of the segments belonging to that partition. Packet replacement and deletion update the SUT associated with the packet's partition, and cleaning selects segments using that same utilisation information.

Cleaning state is logically partition-specific because logs and SUTs are partition-specific. This does not require a dedicated cleaner thread for every partition. An LSS-level cleaning service can schedule work across partitions while preserving the ownership of segment-utilisation state and log placement within each partition.

Granularity and cost

An Partition is not created merely to obtain a new 32-bit Seid namespace. That is the role of a Space. A partition is justified when a group of data benefits from an independent log-writing and physical-locality domain.

The implementation should expect many more Spaces than partitions. Partition-level buffers, queues, log tails, SUT state and checkpoint metadata can consume significant memory and leave unused space in partially filled segments. The number and assignment of partitions should therefore be chosen at a coarse workload boundary rather than automatically creating one partition for every Space.

Failure domain

Partitions share one open LSS and its RAS; they are not independent failure domains. An I/O or integrity error in any partition puts the LSS into its zombie state. Other partitions do not continue logical processing after such a failure.