43 SegmentCache

SegmentCache owns the set of Segment objects resident in memory and provides pinned access to them by SegId. It is both a read cache for segments loaded from the Random Access Store (RAS) and a write cache for segments prepared by the SegmentWriter and awaiting output by the lazy writer.

A successful call to GetSegment() or AllocateFreeSegment() returns a segment with one acquired access, called a pin in this chapter. The caller must eventually release that pin. A pinned segment remains resident and cannot be evicted or recycled. Code normally uses SegmentAccessor to release a pin automatically.

Public operations

GetSegment(segid): Returns a pinned segment, loading it from the RAS if it is not already resident. It may block while another thread loads the same segment, or while waiting for an unpinned cache entry that can be evicted.
AllocateFreeSegment(segid): Returns a pinned, empty in-memory segment for a SegId which the caller has already allocated from the SUT free-space machinery. It does not read the former contents of that physical segment. It may create a new cache object, recycle an unpinned cache object, or reuse an unpinned object with the requested SegId which is still resident.
ReleaseSegment(segment): Releases one pin. When the access count becomes zero, the segment is inserted into the Segment Eviction Queue (SEQ) and becomes eligible for eviction or recycling.
SetMaxNumSegmentsInCache(n): Sets the cache-size limit, which must be at least four, and immediately attempts to evict enough unpinned segments to meet it. Shrinking is best effort when segments are pinned.
GetStats(stats): Returns a synchronized snapshot of cache counters, the configured limit, and the number of resident segments.
Clear(): Deletes every resident segment. Although access to the cache structures is synchronized, the caller must ensure that every pin has already been released and no cache operation remains in progress. The SegmentCache destructor calls this operation.

Clients and read path

The ordinary packet-read path first uses the RPM to map a logical packet Seid to a LogRecordPosition. The position supplies the physical SegId and byte offset. RetrievePacketBufferAtGivenPosition() then calls GetSegment() and addresses the packet at that offset in the pinned segment buffer. Packet chains repeat this process for their remaining packets.

The lazy cleaner is another important client. It pins an entire source segment with a SegmentAccessor while scanning its log records and identifying live packets. Dumping, checkpointing and recovery scanning also use scoped accessors when examining resident segments.

Owned state and representation

The cache owns a map from SegId to resident Segment*, and owns every segment in that map. It also owns the SEQ, the configured capacity, statistics and the mutex which protects their combined state.

The following diagram shows a snapshot of this state. Every entry in map_ points to one resident segment. The clients above the cache hold pins on the top three segments, whose positive access counts equal their incoming pin arrows. The bottom three segments have zero access counts and form the intrusive doubly linked SEQ; the SEQ object points to its first and last members.

SegmentCache containing a SegId-to-Segment map, three client-pinned segments and three zero-access segments in an intrusive doubly linked eviction queue

Part of the cache representation is stored intrusively in each Segment:


int accessCount_;
Segment* prevInSEQ_;
Segment* nextInSEQ_;

These fields are physically members of Segment, but semantically belong to the SegmentCache module. They are private and accessible only to SegmentCache and SEQ. This intrusive representation permits constant-time removal from the eviction queue without a separate node allocation or lookup.

Representation invariant

For every segment resident in the cache:

If its access count is positive, it is pinned and is not in the SEQ.
If its access count is zero, it occurs exactly once in the SEQ.
Every segment in the SEQ is owned by the cache and is present in the cache map.
Only code holding the SegmentCache mutex changes map membership, access counts or SEQ links.

The cache mutex therefore protects state distributed across three classes:


SegmentCache::maxNumSegmentsInCache_
SegmentCache::map_
SegmentCache::stats_
SEQ::first_
SEQ::last_
Segment::accessCount_
Segment::prevInSEQ_
Segment::nextInSEQ_

The following operations access this protected state:


SEQ::Clear()
SEQ::PushFront()
SEQ::PushBack()
SEQ::Remove()
SEQ::TryPopFront()

SegmentCache::Clear()
SegmentCache::GetStats()
SegmentCache::SetMaxNumSegmentsInCache()
SegmentCache::EvictExcessSegments_()
SegmentCache::TryEvictSegment_()
SegmentCache::TryRecycleSegment_()
SegmentCache::TryAddSegment_()
SegmentCache::_TryGetSegment()
SegmentCache::TryAllocateFreeSegment_()
SegmentCache::ReleaseSegment()

The public SegmentCache operations in this list acquire the mutex. The private helpers and SEQ operations are called only when the SegmentCache mutex is already held. This gives the complete set of related state one synchronization boundary even though that state is distributed across SegmentCache, SEQ and Segment.

None of these operations waits for cache capacity or performs RAS I/O while holding the mutex. GetSegment() releases the mutex before loading a segment or waiting on an event, and AllocateFreeSegment() releases it before waiting for the SEQ to become nonempty. This avoids lock-order dependencies between the cache mutex, I/O and blocking waits, and prevents unrelated segment operations from being held behind them.

Cache hits and concurrent loading

Internally, a lookup produces one of three results:


LOADING_OR_AVAILABLE
NEED_TO_LOAD
SEGMENT_CACHE_FULL

For a cache hit, the access count is incremented under the mutex. If it was previously zero, the segment is first removed from the SEQ. The returned pin prevents the segment from being evicted while the client reads it.

For a miss, one thread installs a pinned segment in the map and becomes responsible for loading it. It sets isLoading_, resets the segment's loadedEvent_, releases the cache mutex and calls Segment::ReadFromRAS(). Other threads requesting the same SegId acquire their own pins and wait on that event. Completion is published with a release store to isLoading_; waiting threads use an acquire load before accessing the buffer.

Loading is coordinated per segment, not globally. The cache permits different segments to be loaded concurrently because it does not retain its mutex across RAS I/O. This establishes what SegmentCache permits; it does not by itself establish that every RAS implementation supports those overlapping calls correctly.

Capacity, eviction and recycling

The default LssSettings::maxNumSegmentsInCache is 32. With the historical default segment size of 512 KiB this represents 16 MiB of segment buffers. The setting limits the number of resident segments, so the corresponding byte capacity changes with the configured segment size.

There are no separately sized read and write caches. Segments loaded for reading and segments in the write pipeline share the complete capacity. This allows an unpinned read-cache entry to be recycled instead of blocking a writer merely because a fixed write-cache partition is full, and conversely allows recently written segments to remain useful as cached read data.

If a missing segment is requested while the number of resident segments is below the configured limit, the cache creates a new Segment. At the limit it instead pops an unpinned segment from the front of the SEQ, removes its old map entry, resets it and inserts it under the requested SegId. Recycling avoids a deallocation and allocation of the segment and its buffer.

If the cache is full and the SEQ is empty, every resident segment is pinned. The caller waits on the SEQ's manual-reset event. Releasing the final pin on a segment inserts it into the SEQ, signals the event and allows a waiting request to try again.

Eviction policy

The eviction policy is thread-local and defaults to LSS_LRU_EVICTION. Under the LRU policy, the final release pushes a segment onto the back of the SEQ and eviction pops the segment which has been inactive longest from the front. Under LSS_MRU_EVICTION, the final release pushes the segment onto the front, making a recently released segment the next candidate. The public LssEvictionPolicySetter provides scoped changes to this thread-local policy.

Resizing

Reducing the configured limit immediately evicts available SEQ entries. If all remaining segments are pinned, the attempt stops and the actual cache size may temporarily exceed the new limit. In the current implementation, a later ReleaseSegment() adds an entry to the SEQ but does not itself resume EvictExcessSegments_(); convergence to the lower limit therefore depends on subsequent cache activity. This behaviour should be considered if prompt shrinking is required.

Writable segments

The SegmentWriter calls AllocateFreeSegment() to obtain an empty pinned segment. The pin is handed from the SegmentWriter to the lazy writer along with the completed segment. The lazy writer releases it after writing it to disk. Consequently, segments in the write pipeline cannot be evicted even when the cache is under pressure.

All packets in a segment being prepared in memory can become obsolete before the lazy writer writes that segment. The segment must nevertheless continue through the write pipeline: it forms part of the forward log sequence, including its flush-unit sequence numbers and recovery framing. Its pin prevents cache pressure from discarding it merely because its live-packet utilisation has fallen to zero.

The current log-tail segment is mutable while the SegmentWriter prepares it. Once the SegmentWriter has finished a segment and handed it to the lazy writer, readers may share it while it remains pinned for output; the lazy writer does not modify its recorded contents.

Relationship with segment utilisation and free space

The SegmentCache does not decide whether a physical SegId is logically free. The SUT, reservations, FSS and delta-FSS establish when a SegId may safely be allocated for new log data. The SegmentCache answers a different question: whether a resident in-memory Segment object is currently unpinned and may be evicted or repurposed.

The cache does not inspect utilisation when a pin is released, and it does not add segments to the delta-FSS. A segment with zero live packet utilisation may remain resident like any other cached segment. When the SUT later supplies its SegId to AllocateFreeSegment(), the old cache object can be reset and reused if it is unpinned.

For the ordinary data-read path, this separation permits cleaning to coexist with readers. A cleaner can relocate a live packet and atomically redirect the RPM while an earlier reader continues to use the old packet through its pinned segment. The SUT reservation held by that reader prevents the old physical segment from entering the delta-FSS until the read has released both its cache pin and reservation. The cleaner and reservations chapters describe the wider relocation and reuse protocol.

An allocated SegId already resident in the cache

A segment can remain cached across the checkpoint which makes its SegId reusable. If AllocateFreeSegment() finds that SegId in the map, the current implementation requires its access count to be zero. It removes the segment from the SEQ, sets its access count to one, clears its recorded size and returns it as the new writable segment.

A positive access count in this case is an assertion failure, not a defined blocking path. The ordinary data-read path supports this assertion by pairing the cache pin with a SUT reservation: the RPM lookup reserves the physical segment before the packet buffer is obtained, and PacketInfo destroys its SegmentAccessor before its SegmentUnreserver. A contiguous zero-copy read likewise releases its segment before unreserving the SegId. This proves the required ordering for those read paths: a long-running reader prevents a zero-utilisation segment from reaching the delta-FSS and, ultimately, the reusable FSS. It has not yet been established here that every other cache client which can overlap checkpoint publication preserves an equivalent lifetime rule.

Error handling

If ReadFromRAS() throws a FileException, the loading thread records the error in the LSS file-exception status, clears isLoading_, signals waiting threads, releases its pin and rethrows. The cache contains no per-segment load-result state. A waiting caller therefore wakes after the event is signalled without directly receiving the loader's exception from SegmentCache.

The wider LSS error state may prevent useful work after such a failure, but this dependence is not expressed by the SegmentCache interface. The failure path should be reviewed to ensure that every waiting caller observes the failed load before using the segment buffer.

Open questions

The following points are not resolved by the current review and should not be treated as established properties of the implementation:

All pin and reservation lifetimes. The ordinary packet and contiguous zero-copy read paths release their SegmentCache pin before their SUT reservation. A complete audit is still needed for recovery, checkpointing, dumping, cleaning, the writer pipeline and any other client that can overlap checkpoint publication. Until that audit is complete, the assertion in TryAllocateFreeSegment_() that an already-resident free SegId has access count zero is supported for normal readers but not proved globally.
Concurrent RAS reads. SegmentCache deliberately permits different segments to execute ReadFromRAS() concurrently. Each concrete RAS backend must be checked for the required thread safety and for any hidden serialization or shared file-position state.
Failure observed by waiting loaders. When the responsible loading thread fails, it signals the same completion event used for success. A waiting caller does not receive a stored per-segment exception. It remains to be established that the global LSS error state is checked on every such path before the caller can use an invalid buffer, or else the cache needs an explicit failed-load state.
Convergence after shrinking. If SetMaxNumSegmentsInCache() cannot reach the new limit because all candidates are pinned, later releases only place candidates in the SEQ. It is unresolved whether delayed convergence is intentional or whether final release should resume eviction until the configured limit is met.
Redundant segments in the writer pipeline. The implementation keeps a completed segment pinned until the lazy writer writes it, even if its live-packet utilisation has fallen to zero. The historical rationale is preservation of the forward log and flush-unit recovery sequence. That rationale should be checked against the current recovery format to determine whether writing every such redundant segment remains required or is merely a consequence of the current pipeline.

Implementation components

The following subchapters describe the principal representation components owned by this module:

Segment contains the buffer, write size, loading coordination and intrusive cache state.
SegmentAccessor provides scoped release of a pinned segment.
Segment Eviction Queue (SEQ) holds unpinned eviction candidates.

Code


// Available implementations of the map
#define LSS_SC_STD_MAP              0
#define LSS_SC_STD_UNORDERED_MAP    1
#define LSS_SC_BOOST_UNORDERED_MAP  2
#define LSS_SC_BOOST_FLAT_MAP       3

class SegmentCache
{
public:
    SegmentCache(LSS& lss, int maxNumSegmentsInCache);
    ~SegmentCache();
    void GetStats(SegmentCacheStats& stats);
    void SetMaxNumSegmentsInCache(int n);
    void Clear();
    Segment* AllocateFreeSegment(SegId segid);
    Segment* GetSegment(SegId segid);
    void ReleaseSegment(Segment* s);

private:
    void EvictExcessSegments_();
    Segment* TryEvictSegment_();
    Segment* TryRecycleSegment_(int segid);
    Segment* TryAddSegment_(int segid);

    enum ETryGetSegment
    {
        LOADING_OR_AVAILABLE,
        NEED_TO_LOAD,
        SEGMENT_CACHE_FULL
    };

    std::pair<ETryGetSegment,Segment*> _TryGetSegment(SegId segid);
    Segment* TryAllocateFreeSegment_(SegId segid);

private:
    LSS& lss_;
    mutable std::mutex mutex_;
    int maxNumSegmentsInCache_;
    SEQ seq_;
    SEGMENT_CACHE_MAP map_;
    SegmentCacheStats stats_;
};

Previous42 LazyCleaner Next43.1 Segment