45.2 SmallSUT

SmallSUT is an implementation of the pure abstract interface ISUT when the entire SUT can be stored in the root block.

Representation

SmallSUT stores one 32-bit utilisation for every segment in a contiguous in-memory vector. The vector is serialized directly into each new root-block division during a checkpoint, so no separately allocated SUT-section segments are required. Lookups and updates are constant-time array operations.

Transition to LargeSUT

The transition is governed by the space required to serialize the SmallSUT into a root-block division. It is not triggered directly by allocating a segment and there is no separately maintained maximum segment count. Instead, the SUT facade tests the serialized size when SUT::WriteDirtySUTSections() is called during preparation for a checkpoint. It tests the size of the complete SUT representation that would be written to the root block:

sizeof(int) + sizeof(int64) + sizeof(bool) + small_.GetSerialisationSize()

The first three terms account for the SUT schema, total utilisation and the flag identifying which implementation is active. SmallSUT::GetSerialisationSize() adds the SmallSUT schema, the serialized vector length, and one int utilisation value for every vector entry:

sizeof(int) + sizeof(int) + numSegments * sizeof(int)

Conversion takes place when the resulting size is greater than MAX_SUT_SIZE_IN_ROOT_BLOCK. The current default for this limit is 20 KiB. This is a deliberately conservative limit: the implementation notes that more root-block space is reserved, but uses 20 KiB so that it changes to separately stored SUT sections earlier. The limit can also be reduced by the stress-test program to exercise the transition more frequently. Thus the effective maximum size of a SmallSUT follows from its serialized representation and this configured byte limit; it is not an independent architectural limit on the number of segments.

With the current data types, the expression has a fixed overhead of 21 bytes and requires four bytes for each entry in the utilisation vector. The first vector size for which the expression exceeds 20 KiB is therefore 5,115 entries:

21 + 4 * 5115 = 20481 > 20 * 1024

Vector entry zero does not represent a store segment, so 5,115 entries correspond to 5,114 segments. The following table gives the resulting file size at the earliest checkpoint which can cause the transition. It includes the 64 KiB root block in addition to the segments.

Because the test occurs during checkpoint preparation, allocating the segment that takes the SmallSUT over the limit does not itself perform the conversion. The in-memory SmallSUT may exceed the limit temporarily. Consequently, if multiple segments are allocated before the next checkpoint, the actual store can be larger than the values in the table when conversion occurs. At the subsequent call to WriteDirtySUTSections(), the facade initializes LargeSUT from all the entries in SmallSUT, clears the SmallSUT vector, and changes its current implementation to LargeSUT. It then writes any dirty LargeSUT sections required by that checkpoint.

The transition is one way. Once LargeSUT has been selected, the size test is no longer performed and the store does not revert to SmallSUT, even if high-numbered segments later become free. This avoids changing representations merely because current utilisation falls, and ensures that a store whose segment address space has grown beyond the root-block representation continues to use the scalable on-disk representation.

Code

class SmallSUT : public ISUT
{
public:
    SmallSUT() {}
    void Clear();
    virtual void Serialise(Archive& ar) const;
    virtual void Deserialise(InputArchive& ar);
    virtual int GetUtilisation(SegId segid) const;
    virtual void SetUtilisation(SegId segid, int u);
    virtual int GetTotalNumSegments() const;
    virtual void IncrementTotalNumSegments();
    int GetSerialisationSize() const;

private:
    xvector<int> utilisations_;
};