45 Segment Utilisation Table (SUT)

The Segment Utilisation Table (SUT) describes the utilisation and availability of the segments in an LSS. The cleaner uses it to choose segments worth cleaning, and the Segment Writer uses it to allocate segments that may safely be overwritten.

Logical state

Logically, the SUT consists of the following state:

SegId zero is not a usable segment. If the number of segment entries is N, the allocated segments have SegIds in the range 1 through N - 1, and N is the next SegId that will be created if no existing segment can be reused. Each utilisation must be non-negative and less than the segment size. The total utilisation permits the amount of live packet data in the LSS to be obtained without scanning the utilisation map.

Utilisation

The utilisation of a segment is the total encoded size of all live data and RPM packets in that segment. The encoded size of a packet includes its 13-byte packet header, its payload, and the optional trailing 8-byte Seid identifying the next packet in the chain.

Utilisation does not include snapshot records, delete-packet records, flush unit headers, or padding added at the end of a flush unit to reach a disk-sector boundary. Snapshot and delete-packet records contain recovery information but are not live packets that must be retained or relocated by the cleaner.

Every segment containing packets has at least one 32-byte flush unit header. Consequently, for a 512 KiB segment, the utilisation is strictly less than the segment size and cannot exceed 512 KiB - 32 bytes = 524256 bytes.

Writing a new packet increases the utilisation of its destination segment. Removing or superseding a packet decreases the utilisation of its former segment. Recovery replays these changes so that the in-memory SUT is brought forward from the last valid checkpoint.

Segment availability and reservations

A utilisation of zero means that the segment contains no live data or RPM packet bytes. It does not by itself mean that the segment can be overwritten. Recovery may still need the segment, a reader may still be accessing an obsolete packet, the Segment Writer may be preparing the segment in memory, or the segment may hold an internal SUT section whose bytes are not counted as packet utilisation.

For each segment, the SUT therefore also maintains a reservation count. A reservation denotes a current use that prevents the segment from becoming free, independently of its utilisation. More than one user may reserve the same segment, so the count rather than a Boolean value is logically significant. A segment cannot become eligible for reuse until both its utilisation and reservation count are zero.

The SUT owns two sets of zero-utilisation, unreserved segments:

• The Free Segment Stack (FSS) contains segments that may be allocated and overwritten immediately.
• The delta-FSS contains segments that have become free since the last valid checkpoint. They cannot yet be overwritten because recovery from that checkpoint may still need their contents.

When a segment's utilisation falls to zero, it is added to the delta-FSS if its reservation count is also zero. If reservations remain, it is added when the final reservation is released, provided its utilisation is still zero. A successful checkpoint makes the segments accumulated in its delta-FSS safe to overwrite, so they are transferred to the FSS after the new checkpoint has been published.

Allocation removes a SegId from the FSS and immediately reserves it. If the FSS is empty, allocation extends the segment address space by creating a new SegId and reserves that instead. The reservation protects a newly allocated segment while its utilisation may still be zero. These rules are described further in Free Segment Stack (FSS) and Reservations.

In-memory and on-disk state

The SUT in memory represents the current logical state. Its utilisation values, total utilisation, segment address-space extent, FSS, delta-FSS and reservations change as the Segment Writer writes packets, packets become obsolete, segments are allocated, and users acquire or release reservations. The on-disk SUT remains the snapshot from the last valid checkpoint; these changes are not written to it individually.

Only part of the in-memory state is persistent. A checkpoint records the total utilisation, the number of segment entries and every segment's utilisation. The FSS is derived from this information at startup by finding zero-utilisation segments that are not occupied by persistent internal structures. The delta-FSS is empty at the state represented by a checkpoint, and reservations for ordinary runtime users are transient. Any reservations required for persistent internal structures are reconstructed when those structures are loaded.

During recovery, the SUT is first reconstructed from the last valid checkpoint. The recovery scan then applies the effects of subsequently committed packet writes, deletions and segment allocations. The resulting in-memory SUT again represents the current logical state, even though those later changes are not yet part of an on-disk SUT checkpoint.

Implementation structure

The SUT class owns the complete state described above and the mutex that protects it. It delegates storage of the segment count and individual utilisation values through the pure abstract interface ISUT. This permits it to select either SmallSUT or LargeSUT without changing the higher-level utilisation, allocation, reservation or checkpoint rules.

SmallSUT stores all utilisations directly in the root block. When that representation grows beyond its configured capacity, the SUT changes permanently to the two-level LargeSUT representation. LargeSUT writes dirty SUT sections using shadow paging and stores references to those sections in the root block. Until the new root-block division is committed, the representation belonging to the previous checkpoint remains valid.

Thread safety

The SUT class serializes access to utilisation, allocation, free-segment and reservation state with one mutex. SmallSUT and LargeSUT are used through that class and do not independently provide the complete concurrency policy.

Why utilisation is not stored at 16-bit resolution

It might appear worthwhile to store each utilisation as a 16-bit value. This would halve the storage required for the utilisation entries in both SmallSUT and LargeSUT, allowing approximately twice as many entries in a root-block division or SUT-section. A lower-resolution value would also seem adequate for comparing segments when selecting profitable candidates for cleaning.

Utilisation is not merely a cleaning estimate, however. It is exact accounting of the encoded bytes belonging to live data and RPM packets. When a packet is written, its exact encoded size is added; when that packet is superseded or deleted, the same exact size is subtracted. The exact result is needed to determine when a segment has no live packets and, subject to its reservation count, may be added to the delta-FSS.

Rounding utilisation to 16-bit resolution loses information needed by later subtractions. Two different exact byte counts can have the same rounded representation. Subtracting the same obsolete packet size can then leave one of those segments empty and the other nonempty, even though the stored values are indistinguishable. Rounding each individual packet contribution does not solve the problem: rounding errors accumulate across packets, small packets may receive inappropriate charges, and the sum of independently rounded contributions may exceed the available 16-bit range.

Segments commonly reach zero without being processed by the cleaner. A segment may contain only a few serial elements, or temporal clustering may place a related tree of objects together so that deleting the tree makes all its packets obsolete. Exact accounting allows these ordinary updates to recognize an empty segment immediately. With only a rounded value, the LSS would instead need an additional exact per-segment counter, a reverse index, or a scan of the segment combined with RPM lookups before it could safely release the segment. Those mechanisms remove the simplicity and much of the storage benefit of the proposed representation.

Consequently, a rounded 16-bit utilisation could serve as a separate cleaning heuristic, but it cannot replace the exact utilisation value while retaining the current zero-detection and free-segment safety guarantees. The SUT therefore stores exact 32-bit utilisations.

Code

class SUT
{
public:
    SUT(LSS& lss);
    ~SUT();
    void SetSegmentSize(int segmentSize);
    void Clear();
    int GetTotalNumSegments() const;
    int GetUtilisation(SegId segid) const;
    void OffsetUtilisation(SegId segid, int deltaUtilisation);
    SegId AllocateSegId();
    void AllocateGivenSegId(SegId segid);
    void DumpSUT(xostream& os) const;
    void WriteDirtySUTSections();
    void Serialise(Archive& ar) const;
    void Deserialise(InputArchive& ar);
    void RetrieveDeltaFss(SegIdStack& deltaFss);
    void AddToFss(const SegIdStack& fss);
    int GetLastUtilisedSegment() const;
    void ReserveSegment(SegId segid);
    void UnreserveSegment(SegId segid);

private:
    int PrivateGetTotalNumSegments() const { return current_->GetTotalNumSegments(); }
    int PrivateGetUtilisation(SegId segid) const { return current_->GetUtilisation(segid); }
    SegId PrivateAllocateSegId();
    void PrivateReserveSegment(SegId segid);
    void PrivateUnreserveSegment(SegId segid);
    void ValidateFSSDuringCheckPoint();
    void IncrementTotalNumSegments() { current_->IncrementTotalNumSegments(); }
    void SetUtilisation(SegId segid, int u) { current_->SetUtilisation(segid,u); }
    bool IsSegmentReserved(SegId segid) const { return reservations_.IsSegmentReserved(segid); }
    void InitialiseFSSAtStartup();

private:
    LSS& lss_;
    mutable std::mutex mutex_;
    int segmentSize_;
    int64 totalUtilisation_;
    ISUT* current_;
    SmallSUT small_;
    LargeSUT large_;
    Reservations reservations_;
    SegIdStack fss_;
    SegIdStack deltaFss_;
};