74.2 Log Records

Record classes

An LFU payload is a sequence of log records. Each record begins with a one-octet ELogRecordType. Version 2 defines exactly sixteen valid values; every other octet value is invalid. The type determines the representation and how a scanner finds the following record. There is no common size field. A fixed-size record has a size implied by its type, while a variable-size record contains only the length or structural information required by that particular representation.

using LogRecordType = uint8;

enum class ELogRecordType : uint8
{
    HeadDataPacket                         = 0,
    HeadDataPacketWithNext                 = 1,
    OverflowDataPacket                     = 2,
    OverflowDataPacketWithNext             = 3,
    RelocatedHeadDataPacket                = 4,
    RelocatedHeadDataPacketWithNext        = 5,
    RelocatedOverflowDataPacket            = 6,
    RelocatedOverflowDataPacketWithNext    = 7,

    SpaceRpmNode                           = 8,
    SpaceDirectoryRpmNode                  = 9,
    Space                                  = 10,

    DeleteSerialElement                    = 11,
    AdvanceNextSeid                        = 12,
    CreateSpace                            = 13,
    DeleteSpace                            = 14,
    Snapshot                               = 15
};

The two RPM owners are different record types, so an extra owner flag is not needed to distinguish a Space RPM node from a SpaceDirectory RPM node.

The Snapshot boundary applies uniformly to all sixteen types. Recovery processes every record in log order through the last complete valid Snapshot record and ignores every record after it.

The declarations in this chapter define the information represented by each record. The binary-format chapter must additionally specify how each record type determines its extent, as well as field widths, byte order, alignment and padding. C++ structure padding must not implicitly become part of the file format. A field must not be added merely to make records uniform when the same information can be derived from the record type or payload encoding.

Data packets

There are eight data-packet types because a data packet has three independent binary properties: it either terminates the chain or carries the next packet's Seid; it is either the head or an overflow packet; and it is either a logical packet write or the physical relocation of an existing packet. All eight combinations are meaningful and are named explicitly in ELogRecordType.

The values zero through seven correspond to a three-bit word. Within that range the bits have these meanings:

constexpr LogRecordType DATA_PACKET_WITH_NEXT_MASK = 0b001;
constexpr LogRecordType DATA_PACKET_OVERFLOW_MASK  = 0b010;
constexpr LogRecordType DATA_PACKET_RELOCATED_MASK = 0b100;

These masks support efficient predicates after the type has been established to be one of the eight data-packet types. They are not flags which may be applied to other record types. In particular, IsDataPacket(type) must be established before testing any of these masks.

A data-packet record contains bytes belonging to a serial element. Its PartitionSeid selects the Space RPM and leaf entry which map the packet to its current LogRecordPosition. An overflow packet has its own Seid and may identify the next packet in the chain.

struct DataPacketRecord
{
    PartitionSeid packetId;
    uint32 payloadSize;
    // Payload bytes follow.
    // A next-packet Seid follows the payload for a WithNext record type.
};

The payload size is required because data packets are variable-sized; it is not a generic log-record size. The record type states whether a next-packet Seid is present and whether this is the head packet, avoiding separate fields for those values. A type without WithNext terminates the packet chain.

Relocation records

Data packets have explicitly named relocated types because the recovery log contains both logical data-packet writes and physical copies of existing data packets. The cleaner changes an ordinary data-packet type to its corresponding relocated type; a data packet which already has a relocated type retains it when moved again.

It is not strictly necessary to distinguish OverflowDataPacket from RelocatedOverflowDataPacket. Because overflow Seids are not reused, recovery could infer a new overflow packet from an absent RPM mapping and a relocation from an existing mapping. The explicit distinction makes the log self-describing, permits stronger self-consistency checking, lets logical-change consumers reject relocation records without an RPM lookup, and may therefore improve performance. The Recovery Scan and Cleaner chapters use the explicit relocated types.

The stored PartitionSeid consists of a SpaceId and Seid. When the cleaner copies a live data packet, it updates this Seid's position in the corresponding Space RPM leaf and marks the modified path dirty. The path is written later during a checkpoint.

Structural addresses of RPM nodes

An RPM node needs a stable structural identity so the cleaner can update its parent after relocation. That identity is separate from the data Seid namespace:

struct RpmNodeAddress
{
    uint8 level;       // 0 is a leaf; the maximum is 3
    uint32 keyPrefix;
};

For a node at level L, the low 8 * (L + 1) bits of keyPrefix are zero. The remaining high bits identify the key range covered by the node. Its address and serialized representation are stable when the RPM grows in height: the old root retains its level and prefix when it becomes child zero of a new root.

For a non-root node at level L, its parent is at level L + 1, and its child index within that parent is:

(keyPrefix >> (8 * (level + 1))) & 0xff

The address identifies a logical node, not a particular version or physical packet. Different versions written by checkpoints or cleaning may have the same structural address and different log-record positions.

Space RPM-node packets

A Space RPM-node packet records one node of the RPM which maps Seids to data packets. It carries both the SpaceId and the node's structural address:

struct SpaceRpmNodeRecord
{
    SpaceId spaceId;
    RpmNodeAddress nodeAddress;
    // Serialized RPM node follows.
};

The serialized RPM node determines this record's extent from its occupancy bitmap and entry count; the log record does not repeat that size in a common header.

When the cleaner moves a non-root Space RPM node, it uses this identity to find the Space and update the node's position in its parent. The parent and its ancestors are marked dirty; they are not written immediately. If the moved node is the current root, its new position is recorded in the dirty Space state which will be written as a Space packet during the checkpoint.

Space packets

A Space packet is the persistent top-level state of one Space. It records allocation state and the recoverable root of the Space RPM:

struct SpaceRecord
{
    SpaceId spaceId;
    Seid nextSeid;
    PersistentRpmRoot rpmRoot;
};

This record is fixed-sized once the binary representation of PersistentRpmRoot is selected, so its type implies its size.

The containing partition's SpaceDirectory RPM maps spaceId to the current Space packet. During a checkpoint, dirty Space RPM nodes are written bottom-up, then the Space packet is written with the resulting root position, and finally the corresponding SpaceDirectory leaf entry is updated.

When the cleaner moves a live Space packet, it updates the packet position in the SpaceDirectory RPM leaf and marks that path dirty. As with other RPM updates, the dirty SpaceDirectory nodes are written only during a checkpoint.

SpaceDirectory RPM-node packets

A SpaceDirectory RPM-node packet records one node of the partition's RPM from SpaceId to Space-packet position. Its record type identifies the owner, so it needs only the structural node address:

struct SpaceDirectoryRpmNodeRecord
{
    RpmNodeAddress nodeAddress;
    // Serialized RPM node follows.
};

As with a Space RPM-node record, the node encoding determines the end of the record without a generic record-size field.

Moving a non-root directory node updates its parent and marks the path dirty. Moving the current root updates the dirty SpaceDirectory root state which the partition checkpoint will record.

Relocation chain

The record identities allow the cleaner to relocate every kind of live packet and reduce the source segment's utilization to zero:

DataPacket
    mapped by a Space RPM leaf

SpaceRpmNode
    mapped by its parent, or by a Space packet when it is the root

Space
    mapped by the SpaceDirectory RPM leaf

SpaceDirectoryRpmNode
    mapped by its parent, or by partition checkpoint state when it is the root

Space RPM-node, SpaceDirectory RPM-node and Space records do not need corresponding relocated types. Their ordinary persistent form is written while constructing a checkpoint, outside the recovery-log sequence belonging to the preceding checkpoint. If one of these structural record types occurs in that preceding checkpoint's post-checkpoint recovery log, it was written by the cleaner and therefore unambiguously represents relocation. Checkpoint context and recovery-log context distinguish the two uses of the same type.

In both cases, the stable identity already carried by the record tells recovery which current mapping is being relocated, and the record's position tells recovery the destination. The previous position is obtained from that mapping. No size, old position or separate relocation header is added.

Relocation records participate in transaction framing and become recoverable only when followed by a complete Snapshot record. A logical-change stream, delta file or replication consumer must omit the explicit relocated data-packet types and the contextual structural relocation records, because relocation does not change the logical contents of the LSS. Recovery must process them to reconstruct the physical mappings and SUT accounting needed to reuse the source segment safely.

Relocation writes a byte-for-byte equivalent logical packet at a new position, updates the relevant in-memory position, marks the ancestor path dirty and transfers SUT utilization from the old record to the new record. It does not synchronously serialize the dirty ancestor path. Checkpointing later writes RPM nodes bottom-up and publishes the new roots. The Cleaner chapter defines ordering, commit, reservation and segment-reuse requirements for this operation.

Snapshot record

Version 2 has exactly one Snapshot record kind. It always records both a transaction sequence number and the time at which the transaction was committed. Version 1's older Snapshot record containing only the type octet is deprecated and has no Version 2 equivalent.

struct SnapshotRecord
{
    LogRecordType type;                 // ELogRecordType::Snapshot
    TxnSequenceNumber txnSequenceNumber;
    LssTime timeStamp;
};

The serialized record is exactly 17 octets:

<SnapshotRecord> =
    <LogRecordType     : uint8>
    <TxnSequenceNumber : uint64>
    <LssTime           : int64>

The two 64-bit values use the Version 2 file format's byte order and are serialized field by field; the in-memory structure is not copied directly because the record can begin at an unaligned position and a C++ compiler may insert padding after the type octet. Its type octet is exactly ELogRecordType::Snapshot.

A Snapshot record stores the TxnSequenceNumber, defined by the Partition chapter, of the mutative transaction it commits. It commits every preceding record since the previous Snapshot. During recovery, changes are applied only through the last complete valid Snapshot record; every record following it is an uncommitted tail and is ignored. The timestamp records the commit time associated with that transaction boundary and is available to recovery, diagnostics and consumers of transaction history.

DeleteSerialElement record

A DeleteSerialElement record deletes a complete serial element. Its identity must be the Seid of the head packet, not the Seid of an arbitrary data or overflow packet:

struct DeleteSerialElementRecord
{
    LogRecordType type;             // ELogRecordType::DeleteSerialElement
    PartitionSeid headPacketId;
};

The record is fixed-sized. The stored SpaceId and Seid select the head packet.

Deleting the head implicitly deletes every packet in its chain. The LSS follows the chain beginning at headPacketId, removes the RPM mapping for the head and every overflow packet, and decreases SUT utilization for all of those packets. No separate delete record is written for each overflow packet.

Using an overflow-packet Seid in this record is invalid. It would leave the preceding part of the serial element referring to a deleted suffix and is treated as an integrity error. The name DeleteSerialElement makes the whole-chain semantics explicit and does not suggest that callers may delete individual data packets.

AdvanceNextSeid record

Motivation

In the common case, a layer allocates a Seid and writes the corresponding serial element in the same transaction. Recovery sees the data-packet record and advances the Space's nextSeid beyond that packet's Seid. No separate allocation record is needed.

A layer can instead preallocate a large range of Seids for serial elements which will be written in later transactions. For example, one transaction can reserve Seids for all the tiles of a large image, after which separate transactions write the data for individual tiles. The allocation transaction has no packet records for tiles which have not yet been written. Packet records therefore cannot protect the unwritten part of the range. Without another record, recovery after a crash could allocate the same Seids to different serial elements.

Solution

AdvanceNextSeid records the resulting allocation frontier only when it cannot be inferred from data-packet records. At commit, the transaction determines the value recovery will obtain from the preceding state and its ordinary data-packet records. If the Space's actual nextSeid is greater, the transaction writes one AdvanceNextSeid record for that Space. Multiple allocations in one transaction are therefore coalesced, and allocate-and-write transactions normally add no record.

struct AdvanceNextSeidRecord
{
    LogRecordType type;             // ELogRecordType::AdvanceNextSeid
    SpaceId spaceId;
    Seid nextSeid;
};

The identified Space must exist and nextSeid must be greater than its current allocation frontier; the record can only advance that frontier. A zero-count allocation or any allocation already implied by packet records needs no record.

CreateSpace record

A CreateSpace record adds a newly allocated SpaceId to the partition's SpaceDirectory:

struct CreateSpaceRecord
{
    LogRecordType type;             // ELogRecordType::CreateSpace
    SpaceId spaceId;
};

The new Space is empty, has a height-zero RPM and has nextSeid == 0. Those values are implied by the record type and are not repeated in its payload. The SpaceId must not already identify a live Space. Processing the record creates the in-memory Space and adds its entry to the SpaceDirectory; checkpointing later writes its persistent Space packet.

DeleteSpace record

A DeleteSpace record removes an entire Space from the containing partition:

struct DeleteSpaceRecord
{
    LogRecordType type;             // ELogRecordType::DeleteSpace
    SpaceId spaceId;
};

The Space must exist and contain no serial elements in the state immediately preceding the record. Processing the record removes its SpaceDirectory mapping and retires the Space packet and any persistent empty-RPM state belonging to it, updating SUT utilisation for each retired record. A SpaceId is not made available for reuse by deleting its Space; SpaceId allocation policy must prevent a later Space from being confused with retained snapshots or log records referring to the deleted one.