Module ccache::swtlfu [−][src]
W-TinyLFU cache with lazy scan enanchment
TLFU is a series of counters and an SLRU cache. W-TinyLFU adds another LRU window in front of all of this.
The Window is 1% of the total cache, while the main SLRU is divided in 20% probation, 80% protected cache.
WTLFU keeps a bloom filter of the Window.
If an entry in the Window receives
a HIT it is moved to the SLRU, where its access are counted better.
This second counters can be limited to a few bits, but they are kept
separate from the bloom filter for efficiency.
If the cache is designed for X entries, after X inserts we have to halve all counters. This implies blocking all the cache
Our variant, the Scan-Window-TinyLFU, is your average WLTFU
but we keep full counters for all elements.
The cache is already wasting a lot of space in memory due to memory
alignment caused by the very short Cache Id and pointers that need to be
memory-aligned.
We reuse that otherwise wasted space to track the generation and the counter for the element, and apply a “lazy” scan that eventually will scan everything
The “Scan” part works simply by tracking the generation of the counter
(Day/Night) and if the generation is not the current one, the counter
is halved. To assure that all counters are halved every X inserts,
every get/insert will scan just one more element.
Structs
| SWTLFUShared | Actual implementation of the Shared |