43.3 Segment Eviction Queue (SEQ)

The Segment Eviction Queue (SEQ) is responsible for tracking access to segments on behalf of the SegmentCache, and for providing an LRU eviction policy for segments that are not currently accessed.

The Segment Cache has a constraint on the maximum number of segments that may be resident in memory. Once the Segment Cache is full, each time we load or write a segment we must first free the segment at the front of the SEQ.

Segments are loaded lazily (i.e. on demand).

When physical memory runs low it may be necessary to unload some segments. Only segments with an access count of zero are allowed to be unloaded.

When a segment is accessed by a client, it is first removed from the SEQ. This eliminates any chance that it will be evicted while it is used by the client.

When the client has finished with the segment it must be released. To allow a segment to be accessed by multiple clients, we have the concept of an access count. When the access count falls back to zero the segment is returned to the back of the SEQ where it is queued for eviction. Note that this has the effect of implementing a Least Recently Used (LRU) segment eviction policy.

Access count

Each segment records an access count initialised to 1:

class Segment
{
    ...

    // Counts the number of clients that are accessing the segment.
    int accessCount_ = 1;
};

While a segment is in use, a positive access count protects the segment from being unloaded. You can use a SegmentAccessor to hold the reference.

Double linked list

A doubly linked list is a suitable data structure for the SEQ because it supports fast insertion and removal from any position.

It is necessary to store the prev and next segment pointers within a segment so they can be found given a pointer to a segment. Each segment in memory has prevInSEQ_ and nextInSEQ_ segment pointers to support placement in the SEQ. Both of these pointers are NULL if the segment doesn't currently reside in the SEQ.

class Segment : public SegmentBase
{
    ...

    ///////////// State used by the Segment Eviction Queue (SEQ) ///////////////////////////////
    // This state must not be accessed by anything but the SEQ

    // Counts the number of clients that are accessing the segment.  Initialised to 1 in the constructor.
    int accessCount_;

    // Segments in the eviction queue form a doubly linked list
    Segment* prevInSEQ_;
    Segment* nextInSEQ_;

    ManualResetEvent loadedEvent_;

    // This flag is used to indicate that the loading of the segment from disk has been completed.
    // A write-release synchronises with a read-acquire.
    std::atomic<bool> isLoading_;

    friend class SEQ;
};

The SEQ has segment pointers first_ and last_ to point at the first and last segments in the SEQ. These are NULL if the SEQ is empty. first_ points at the next segment to be evicted.

class SEQ
{
    ...
private:
    // Pointers to the first and last segments (resp) in the doubly linked list of segments
    // that comprise the SEQ.  Both of these pointers will be nullptr if and only if the SEQ
    // is empty.  It is an error for only one of these pointers to be nullptr.
    Segment* first_;
    Segment* last_;
};

Note that a std::list is not suitable for the SEQ, because given a segment pointer we need to be able to quickly remove the segment from the SEQ, and that is fast with a std::list when one has an iterator that points at the element to be removed.

Code

class SEQ
{
public:
    SEQ() {}
	~SEQ();
    void Clear();
    void PushFront(Segment* s);
    void PushBack(Segment* s);
    void Remove(Segment* segment);
    Segment* TryPopFront();
    void BlockUntilNonEmpty();

private:
    Segment* first_ = nullptr;
    Segment* last_ = nullptr;
    mutable ManualResetEvent queueNonEmptyEvent_;
};