74 PartitionDirectory

Logically, the PartitionDirectory records a map from a 32-bit PartitionId to a LogRecordPosition which points at an Partition log record.

SmallPartitionDirectory

Many stores will contain only a handful of partitions. A SmallPartitionDirectory representation serialises the complete map directly into a root block division.

struct SmallPartitionDirectoryEntry
{
    PartitionId partitionId;
    LogRecordPosition position;
};

struct SmallPartitionDirectory
{
    std::vector<SmallPartitionDirectoryEntry> entries;
};

Radix-tree representation

The scalable PartitionDirectory representation is a four-level radix tree. It has its own log using its own segments. The root block divisions of the LSS record the root node of this tree.

Choice of representation

The choice follows the approach used by the SUT. During checkpoint preparation, the directory uses SmallPartitionDirectory while its serialised representation fits in a root block division. When it no longer fits, it changes to the radix-tree representation. The root block division identifies which representation is stored.

Alternative: a B+Tree stored in the primary partition

A different approach is to have a distinguished primary Partition and store the PartitionDirectory in it using serial elements. The directory can use a B+Tree mapping additional 32-bit PartitionId values to LogRecordPosition values.

This approach may be more powerful, more efficient and require less code. A B+Tree supports both small and large directories, and needs to be implemented for other important uses. Storing the directory as serial elements also gives it the logging, MVCC, checkpointing and recovery support of the primary partition rather than requiring separate implementations of those mechanisms.

It also allows the initial design and implementation to support only the primary partition and have no PartitionDirectory. Support for additional partitions and the directory can be introduced later.