47 Recovery

The recovery scan uses a RecoveryLogRecordVisitor.

Recovery scan

Conceptually, recovery involves two separate phases

1. Initialise the store according to the last valid check point.
2. Scan forwards through the daisy chained segments from the last valid check point, "replaying history" but only when snapshot log records are encountered. Note that this scan typically begins midway through the first segment to be scanned.

The "replay history" concept forces certain design decisions. For example, at the end of phase 1 the LSS should be in a valid state, and corresponding to the time when the last valid check point was performed. This makes phase 2 optional apart from a desire to recover as much data as possible.

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

Now 2^128 = 3.4 x 10^38 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 generates bytes look like the check point Id.

During recovery, the system will find the last valid Log Flush Unit (LFU). All the following must be true for a valid LFU.

• The CPID 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 disk sector is correctly padded with zeros
• The CRC is correct

Note that segments can be recycled (from the free segment stack) without clearing away old data. The system must robustly identify the end of the log - it certainly must not inadvertently recover garbage. It is assumed that the above validity test will have extremely low probability of making a mistake.

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 CPID will comprise a single linear list of segments.

Example scenario :

• Store is gracefully shut down. This always involves a check point, and therefore a new CPID 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.
  Consider that the store is copied after it has been gracefully shutdown. Unfortunately both stores will use the same CPID. The downside is that the file system may recycle disk sectors as one file is deleted or truncated, and the other file grows, allowing for erroneous yet valid looking flush units to be seen in the growing file.
• 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 CPID. 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 CPID. At that point we don't care about all the old flush units because they will have an out of date CPID 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.

Replaying history

Conceptually recovery should be compared to replaying history. During the scan numerous function calls must be made to bring the RPM, SUT, FSS, delta-FSS etc up to date. These should match the same calls that were made when the data was originally written to the log.

Note that during this "replay", the utilisation of segments may fall to zero and therefore they will automatically be saved in the delta-FSS.

To ensure transactions are atomic, these changes should only be applied when the snapshot log records are encountered.

Replay must include the calls to UnreserveSegment() and AllocateGivenSegId() on the SUT.

Truncation of the log

The recovery scan must avoid making any changes to the flush units. Attempting to make a change could cause data loss because writing flush units is not guaranteed to be atomic - particularly if the flush unit is larger than a disk sector. I.e. trying to modify a flush unit can leave it in a partially written state (if there is a power failure during the recovery), and its CRC is no longer valid.

As a result of this, we only allow the log to be truncated at flush unit boundaries. Therefore the recovered flush units may contain log records that aren't actually committed by a snapshot record.

The log is always truncated at the end of the last valid flush unit containing a snapshot record.

Regeneration of the last delta file

Note that different hard-disks can have different amounts of write cache, and therefore it can't be assumed that on power failure the data actually written to the disks is consistent with the order in which write operations were issued by the software.

During recovery it is necessary to regenerate the delta file - because it may have been written on a different hard-disk and less was written to the delta file because that disk happens to use a large write cache.

Recovery can come across RPM log records. In fact there could be any amount of such records without ever encountering a snapshot record. In that case we assume there is nothing to recover and therefore no check point will be performed at the end of the recovery. This aligns well with the idea to use dirtiness of the RPM as a test for whether an attempted check point is done.

It seems possible that during recovery we write flush units to a delta file, but it is eventually found that there was no "real" data to recover. Testing the RPM is the best indicator. In that case the delta file should be rewritten from scratch!

Note that only valid flush units (e.g. valid CRC) are recovered, and written to the delta file. Therefore barring disk failures, an invalid flush unit should never been seen in a delta file. However, we must allow for flush units that contain log records that are never actually committed by a snapshot log record.

The recovery only iterates over the flush units a single time. Therefore it will write flush units to the delta file without actually knowing whether they will end up being committed by a subsequent snapshot log record. At the end of the recovery it may be necessary to truncate the delta file.

To achieve this we need to calculate the length of the delta-file. This is done as follows

int64 committedLength = 0;
int64 deltaLength = 0;

int committedfsn = 0;

int fsn = 1;
for each flush unit
{
    < process flush unit >

    deltaLength += size of flush unit;

    if (flush unit contained snapshot record)
    {
        committedLength += deltaLength;
        deltaLength = 0;

        committedfsn = fsn;

        endOfLog = position at end of flush unit
    }

    ++fsn;
}

Recovery of the FSN

During the recovery scan, each time we read a snapshot log record we should record the FSN of the flush unit containing the snapshot record. This gives us the last flush unit, and is used to initialise the FSN in the SegmentWriter.

Recovery

An initial implementation of recovery can simply truncate the log at the position of the last valid check point. However this may cause excessive data loss on failure.

A more advanced recovery algorithm scans the log from the last valid check point, because a number of valid snapshots of committed transactions may be present. These must be applied to the RPM and SUT.

It is assumed that the recovery effort is not great, and there is no need to log the recovery process itself. If the system crashes before recovery is complete, then the same work must be repeated the next time the recovery is performed.

It is not allowable for transactions to run while recovery is in progress – because the LSS can’t reliably return the most up to date version of a serial element until recovery has brought the RPM up to date. Therefore recovery is completed before the LSS returns the ILSS interface pointer, preventing clients from calling any ILSS methods while recovery is in progress.

Truncation of the log

When the recovery scan reaches the end of the log, it is possible that a number of packet records have been scanned without the subsequent snapshot record (perhaps because of a power failure before all data was flushed to the log). Before the log can be used, it is necessary to truncate the log – or otherwise these packet records may wrongly be realised as part of a subsequent snap shot in another recovery.

If truncation is required, it is performed synchronously at the end of recovery by

1. Rewrite the segment trailer for each segment being removed from the log. Set the nextSegId, size, and SSN to zero. This must be done in reverse order – ie start at the last segment in the log and work backwards.
2. Rewrite the size in the segment trailer of the segment containing the last snapshot or check point record.

Recovery algorithm

Recovery involves a scan of the log records beginning from the last valid check point.

Let the following structure be used to store information about a data packet

struct PacketInfo

{

LogRecordPosition m_position; // The position of this data packet (ie SegId and offset)

OID m_oid; // The OID assigned to the packet

int m_size; // The size of the packet in bytes

}

Let the PacketList (PL) be a std::deque<PacketInfo>, used to store information about all the data packets that have been encountered during the recovery scan.

Let the DeletionList (DL) be a std::deque<OID> used to accumulate all the LR_DELETE_PACKET records during the recovery scan.

Steps

1. Read the root block, according to Challis’ algorithm. Load the SUT, root RPM-node and the segment and offset of the last valid check point
2. Initialise the truncate-log-position to null
3. Initialise the PL and DL to empty
4. Initialise a vector S SegId to empty
5. Let SSN equal the SSN of the segment containing the last valid check point.
6. Scan the log records from just after the last valid check point. For each encountered segment add its SegId to S.
   7. If we come across an RPM-packet record then goto 7.
   8. Store each data packet record in the PL
   9. If reach a snapshot record

SW.SSN += S.size()

1. Clear S
2. For each packet in the PL, add entry to the RPM and apply change to the SUT (ie account for obsoleted packet, if any and the new packet).

• For each OID in the DL, remove the entry from the RPM. Decrease the utilisation of the segment containing the packet by the size of the packet with the given OID.

1. Clear the PL and DL
2. Set the truncate-log-position to just after the snapshot record

7. If the truncate-log-position is not null and it doesn’t match the end of the log then truncate the log to that position. S contains the list of segments that need to be removed from the log.

Code

struct RecoveryScanInfo
{
    RecoveryScanInfo();
    Guid checkPointId_;
    FlushSeqNumber fsn_;
    LogRecordPosition endOfLog_;
    SegId nextSegid_;
};