39.1 Log Flush Units

Flush Unit Header

A Flush Unit Header is 32 bytes and contains the following fields:

Log Flush Unit

The RAS provides a method that returns the sector size. This will typically be 512 bytes. In that case there will be 1024 sectors per 512k segment.

Data is always written to the end of the log using a Log Flush Unit (LFU). An LFU always begins and ends on disk sector boundaries within a single segment. LFUs are written one after the other until the segment is full.

A flush of the log involves

1. Preparing the relevant sectors in memory (within the segment in memory to be flushed)
2. Writing all the sectors to disk.

An LFU begins with a FlushUnitHeader. This takes up the first 32 bytes of the first sector in the LFU. The header stores the CRC calculated on the header + payload, allowing for validity testing of the LFU. In particular it tests whether the LFU was written in its entirety to disk. This avoids many assumptions about the hard-disk such as atomicity of writing disk sectors, or the order in which sectors are written.

After the header is the binary payload. The payload is zero padded to fill up the last sector in the LFU.

Checksum

The first field in a flush unit header is a 32 bit CRC. When a flush unit is closed, the LSS calculates the CRC over the rest of the header, beginning with the check point Id, and the flush unit payload. The CRC field itself and the sector padding after the payload are not included. The recorded CRC is checked when a flush unit is read during recovery and other operations which scan flush units.

Calculating a CRC over every flush unit payload has proved to be a significant overhead to write performance. The source contains a faster additive 32 bit checksum named CalcChecksum32 as a commented alternative, but the current implementation uses CalculateCRC32.

The compile-time macro ENABLE_FLUSH_UNIT_CRC controls the CRC calculation. Setting it to zero causes the calculated value to be zero, effectively disabling validation of the flush unit contents. This option was only added to measure the performance cost of CRC calculation. The intention has never been to use an LSS without checksums.

Checksums are required because a process may fail after only part of a flush unit has been written. Segments are not cleared when they are recycled, so a partial write can leave a mixture of new data and data from the previous use of the segment. The old data may include log records and snapshot records. Recovering those records as though they belonged to the new flush unit could corrupt the recovered state of the store.

The LSS also makes no assumption about the order in which writes reach non-volatile storage. Storage devices are well known for reordering writes, particularly when they have large on-device memory caches. Such reordering is particularly problematic for Write Ahead Logging, which depends on log records reaching durable storage before the data pages they protect. In practice, reliable durability barriers may be unavailable, incorrectly implemented, or sufficiently expensive that they are disabled. The correctness of a WAL system then depends on assumptions that the storage stack does not satisfy. The LSS instead combines the checksum, check point Id and flush sequence number when validating flush units, making it extremely unlikely that a recovery scan will accept invalid data.

Check points should not be performed too frequently, because a check point updates the root block with a new recovery position and check point Id, exposing another boundary at which out-of-order writes must be considered. When the store is opened, the LSS reads the last valid root block division and validates every flush unit from the beginning of the segment containing the check point up to the recorded check point position. The flush units must have valid payload sizes and checksums, and the scan must end exactly at the recorded position. This is intended to detect errors caused by writes reaching non-volatile storage out of order around a check point.

During recovery, the system will find the last valid LFU. All the following must be true for a valid LFU.

• The checkPointId is correct
• The FSN corresponds to the next assigned sequence number to the LFU
• The size of the payload is reasonable (e.g. it must not overflow the segment)
• The NextSegId is a valid segment number
• The last sector is correctly padded with zeros
• The CRC is correct

Note that segments can be recycled without clearing away old data. The system must robustly identify the end of the log. It is assumed that the validity test defined above will have extremely low probability of making a mistake.

The checkPointId is a guid generated each time a check point is performed, and stored in the root block. This avoids one LSS file accidentally recovering LFUs that don't belong to the check point.

Recovery

Recovery begins by reading the root block and finding the last valid check point. The check point has an associated check point Id - a 128 bit guid. This is used to validate flush units in the recovery scan.

Now 2^128 = 3.4E38 is a very large number, so the probability of incorrectly validating a flush unit is very small. In fact, recovering flush units at the rate of 1GHz would take 10^22 years to give a reasonable chance of seeing randomly generated bytes look like the check point Id.

Between check points, it is not possible for segments to be recycled - because of the use of the delta-FSS. Therefore, all segments written with the checkPointId will comprise a single linear list of segments.

After recovery is completed, the store is immediately check pointed. This generates a new check point id, eliminating the chance that previously written flush units will be accidentally validated on a subsequent recovery.

Example scenario :

• Store is gracefully shut down. This always involves a check point, and therefore a new check point id will be generated. On startup no recovery scan of the store will be attempted. Also, there is no need to check point the store on startup. Flush units will be written using the last valid check point.
  [It will be safer to check point the store anyway - because when the file for the store is copied, we always continue writing flush units with independent GUIDs, avoiding any risk of one store recovering the other's store's flush units]
• Store is not gracefully shut down, a large number of segments have been written since the last valid check point. In the worst case, the sectors may have been written to disk out of order. On startup a recovery scan will be performed. This will validate flush units in turn. The recovery scan ends at the first flush unit with an invalid CRC or checkPointId. This may happen "early" if sectors have been written out of order. If the power fails then recovery will be repeated the next time. After recovery a check point is performed. Only when this is completed successfully will the next recovery start the scan from a different position and use a different check point Id. At that point we don't care about all the old flush units because they will have an out of date check point Id in the flush unit headers.
  Between check points segments may be cleaned. However they are only marked as free in the delta-FSS, so there is no chance they will be recycled. Therefore we will never write a segment that already contains flush units with the existing check point id.

Code

// Sequence number assigned to flush units in the log.  Starts at one for each check point
typedef int32 FlushSeqNumber;

// 32 bytes
const int FLUSH_UNIT_HEADER_SIZE = sizeof(CRC32) + sizeof(Guid) + sizeof(FlushSeqNumber) + sizeof(int32) + sizeof(SegId);

#pragma pack(push,1)
    struct FlushUnitHeader
    {
        void AssignCRC() { crc32_ = CalcCRC(); }
        bool IsValidCRC() const { return crc32_ == CalcCRC(); }

        enum EStatus
        {
            OK,
            BAD_CRC,
            BAD_CHECKPOINTID,
            BAD_FSN,
            BAD_PAYLOAD_SIZE,
            BAD_NEXT_SEGID,
        };

        // Validate this flush unit, where it is expected to have the given checkPointId and fsn.
        // positionOfFlushUnit is the zero based offset in bytes of the flush unit header from the
        // start of the segment.
        EStatus GetValidityStatus(const Guid& checkPointId, FlushSeqNumber fsn, int positionOfFlushUnit, int lssSegmentSize) const;

        bool IsPayloadSizeValid(int positionOfFlushUnit, int lssSegmentSize) const;

        void WriteToStream(xostream& os) const;

        // Assumes numBytesInPayload_ is initialised correctly
        CRC32 CalcCRC() const;

        //////////////// Member variables
        CRC32 crc32_;
        Guid checkPointId_;
        FlushSeqNumber fsn_;
        int32 numBytesInPayload_;
        SegId nextSegid_;
    };
#pragma pack(pop)

class FlushUnitIterator
{
public:
    FlushUnitIterator() : segment_(nullptr), pos_(0) { }
    FlushUnitIterator(Segment* segment, int pos) { Set(segment,pos); }
    int GetPos() const { return pos_; }
    int GetEndPos() const;
    Segment& GetSegment() const { cxAssert(segment_); return *segment_; }
    void Set(Segment* segment, int pos)
    {
        segment_ = segment;
        pos_ = pos;
        AssertValid();
    }
    FlushUnitHeader& operator*() const
    {
        AssertValid();
        cxAssert(pos_ < segment_->GetSegmentSize());
        return * (FlushUnitHeader*) segment_->GetRawBuffer(pos_);
    }
    FlushUnitHeader* operator->() const
    {
        return &operator*();
    }
    FlushUnitIterator& operator++()           // Prefix
    {
        pos_ = GetEndPos();
        AssertValid();
        return *this;
    }
    bool IsPayloadSizeValid() const
    {
        cxAssert(segment_);
        FlushUnitHeader& header = operator*();
        return header.IsPayloadSizeValid(pos_, segment_->GetSegmentSize());
    }
    int GetPayloadPos1() const
    {
        return pos_ + FLUSH_UNIT_HEADER_SIZE;
    }
    int GetPayloadPos2() const
    {
        FlushUnitHeader& header = operator*();
        return pos_ + FLUSH_UNIT_HEADER_SIZE + header.numBytesInPayload_;
    }
    void WriteToStream(xostream& os) const;

public:
    Segment* segment_;

    // The zero based offset in bytes of the flush unit header from the start of the segment.
    // Must be a multiple of the disk sector size.
    int pos_;
};

struct IFlushUnitVisitor
{
    virtual void VisitFlushUnit(int positionOfFlushUnit, const FlushUnitHeader& h) = 0;
};

const FlushSeqNumber DONT_CHECK_INITIAL_FSN = -1;

// Visit all the valid flush units within the range [i1,i2) of the given segment where i1 and i2
// are multiples of the disk sector size.
// Returns the end position of the scan, which will be a multiple of the disk sector size.  This
// may be i2, or less than i2 if an invalid flush unit was encountered.

int VisitValidFlushUnitsInSegment(
    Segment& segment,
    int i1, int i2,                 // Range [i1,i2) where i1 and i2 are on disk sector boundaries
    FlushSeqNumber& fsn,            // Can equal DONT_CHECK_INITIAL_FSN
    const Guid& checkPointId,
    IFlushUnitVisitor& visitor);