42 LazyCleaner

The cleaner basically needs to clean segments with the lowest utilisation first.

It would be very expensive to maintain a list of (segment Id, utilisation) pairs ordered by utilisation. For a one terabyte store, there are 2 million segments. To continually remove elements and move them to a new position would be quite expensive.

Consider that the cleaner only occasionally scans the SUT in order to calculate a list of segments to be cleaned. This can be done at startup, and after each check point. This could involve the following approach:

  • Perform a linear scan of the SUT. For each segment id, add it to a "bin" according to the utilisation. The bins correspond to utilisation ranges [0%,10%), [10%,20%), .... , [90%,100%). Note that binning gives us reasonable ordering without the need for an O(nlogn) sorting algorithm
  • From the bins, determine what segments need to be cleaned

The third-party literature includes research on cleaning algorithms for log-structured stores.

Running the cleaner in the background at regular intervals

Previously

The LazyCleaner used to use a TimeOutTask. The TimeOutTask has a dedicated std::thread which (effectively) sits in a loop waiting for 1000 milliseconds then cleaning segments for up to 200 milliseconds. So the cleaner has an upper bound of about 20% usage of one CPU processor.

The LSS has a LazyCleaner directly in a member variable, so their lifetimes are tied. Start/stop on an LSS calls Start/Stop on the LazyCleaner. This used to in turn call Start/Stop on the TimeOutTask which starts/stops the std::thread: 


class LSS
{
    void Start() { lazyCleaner_.Start();  }
    void Stop()  { lazyCleaner_.Stop();   }

    LazyCleaner lazyCleaner_;
};

class LazyCleaner
{
    void Start() { timeOutTask_.Start(...); }
    void Stop()  { timeOutTask_.Stop();     }

    TimeOutTask timeOutTask_;
};

class TimeOutTask
{
    void Start() { thread_ = std::thread(...); }
    void Stop()  { thread_.join(); }

    std::thread thread_;
};

Now

The LazyCleaner now uses an AsyncRepeatedTask.

In other words the LazyCleaner doesn't have a std::thread, instead it uses a boost::asio::io_context from an IoContextPool and a dead-line timer. That means we have no counterpart to calling join() on a std::thread to wait until the thread has finished running the lambda.

An AsyncRepeatedTask is similar to a TimeOutTask in that it repeatedly runs a given task and it provides a Stop() function that synchronously guarantees that the task is no longer executed. 


#include "Ceda/cxThread/AsyncRepeatedTask.h"

class LazyCleaner
{
public:
    LazyCleaner(LSS& lss)
        lss_(lss)
    {
    }

    void Start()
    {
        asyncRepeatedTask_ = MakeAsyncRepeatedTask(lss_.GetAnIoContext());
        asyncRepeatedTask_->Start(1000,
            [this](std::atomic<bool>& abort)
            {
                CleanSomeSegments(abort);
            });
    }

    void Stop()
    {
        asyncRepeatedTask_->Stop();
    }

private:
    void CleanSomeSegments(std::atomic<bool>& abort);

    LSS lss_;
    std::shared_ptr<AsyncRepeatedTask> asyncRepeatedTask_;
};

Cleaning

The cleaner is able to relocate objects without loading them into C++ objects (i.e. it simply moves the bytes around). It works at the level of the packets. Therefore it doesn't need a CedaLock, improving concurrency.

The cleaner uses a LRS-op. It transfers live packets within one or more segments to the end of the log, to allow the segments to be freed (ie returned to the FSS). There is no need to flush the log after cleaning a segment.

It is important to understand that cleaning a segment doesn't write to the segment - either in memory or on disk. On the contrary, it is important that it be left alone! This is because the segment is still needed in case of power failure because it is reachable from the last valid check point. In fact it is not permissible to return a cleaned segment back to the FSS, because that may mean that the segment gets reallocated (saying for writing more data to the end of the log). Instead, it is necessary to wait for the end of the next check point. Only then is the segment ready to be re-used. This gives us the concept of the delta-FSS to track the segments that have been freed since the last valid check point. The delta-FSS is only transferred to the FSS at the end of a check point.

Steps to clean a segment

  1. Choose the next segment to be cleaned
  2. Access the segment in the SC. This will load the segment if required
  3. Open a commit phase on the LSS. This will gain a write lock on the log
  4. Scan the packets in the segment, and interrogate the RPM to find out which packets are live. Write the live packets to the end of the log
  5. Close the commit phase. This will write a snapshot record, update the SUT, RPM and release the write lock on the log
  6. Add the SegId of the cleaned segment to the delta-FSS. (Actually this may be implicit - because the utilisation of the segment should have fallen to zero and the SUT detects this transition)

Note that the cleaner only interrogates the RPM during the commit phase. The cleaner sees a stable version of an up to date RPM at this time, so it can't make mistakes about what packets are live.

The cleaner is only permitted to clean segments that come before the last check point. In these segments, only live packet records are useful. Snapshot records have already been taken into account by the last valid check point and are obsolete.

The cleaner can't work on segments that haven't been flushed to disk because the cleaner may only work on segments that come before the last valid check point, and a check point flushes the log.

Choosing the segment to clean

There are significant advantages in prioritising segments to clean, according to the utilisation and the assumed likelihood that the segment will undergo further changes. Cleaning is performed by a low priority background thread that spends most of its time asleep. It wakes up occasionally and checks whether the utilisation of any segments has fallen below a threshold. If so those segments are cleaned.

In practise some packets are "hot" and are changed repeatedly, while other packets are "cold" and are only rarely changed.

A segment is as hot as the hottest live packet remaining within it. It is assumed that coldness of a live packet is proportional to its age. The age of a segment is defined to be the age of the youngest live packet remaining within it (ie the minimum of all the ages).

A hot segment should be cleaned at a lower utilisation threshold than a cold segment because it is likely that the utilisation of a hot segment will continue to fall - and the longer we wait the less unnecessary work that is performed by the cleaner. A particularly hot segment should not be cleaned because its utilisation may fall rapidly to zero, so the cleaner only needs to remove it from the log.

The Sprite log structured storage uses the following measure to prioritise segment cleaning

quality = benefit/cost = free space generated * age / cost = (1-u) * age / (1+u)

where u is the utilisation (from 0 to 1) of the segment. The "benefit" is proportional to the age because a long age suggests that the cleaning will be long lasting.

When a transaction commits, all packets marked as dirty as part of that transaction are stamped with the current system clock. We record the timestamp of the youngest live object within each segment in the SUT. When a transaction commits, for each dirty object (ie live object that becomes obsolete in a segment), we compare its modification time stamp in the PBT to the time stamp stored in the SUT. The SUT is adjusted if necessary so it continues to provide the modification timestamp of the youngest live object remaining in the segment.

When the SUT is check pointed (ie written to the root block) there is probably no advantage in recording the timestamps. This will help reduce the size of the root block.

When segments are first loaded into memory, the modification timestamp is initialised to the current time. This represents very hot segments that are less likely to be cleaned.

Code



class LazyCleaner
{
public:
    LazyCleaner(LSS& lss);

    void Start();
    void Stop();
    void CalcSegmentsToClean();

private:
    void CleanSegment(SegId segid);
    void CleanSomeSegments(std::atomic<bool>& abort);

private:
    LSS& lss_;
    std::shared_ptr<AsyncRepeatedTask> asyncRepeatedTask_;
    std::atomic<bool> haveSegmentsToClean_;
    std::deque<SegId> segmentsToClean_;
};