import { WindowTinyLfu } from "https://deno.land/x/velo@1.0.0/mod.ts";
Window-TinyLFU (W-TinyLFU) implementation as per https://dl.acm.org/citation.cfm?id=3149371 inspired by Caffeine's implementation: https://github.com/ben-manes/caffeine.
A new cache entry is first placed into a small window cache and remains there while it has high temporal locality (LRU). An entry that is evicted from the window gets the chance to be inserted in main cache (SLRU). If the main cache is full at that point, the TinyLFU admission policy picks between the windows' and the main cache's eviction victim. TinyLFU determines the winner via a historic frequency filter. Here a 4-bit CountMinSketch is emnployed for estimating the frequency.
In this implementation the total cache capacity is split into (1) the window LRU cache with 1% of the total capacity, (2) the main SLRU cache with 99% of the total capacity, which is again split into 80% for the hot/protected and 20% for the cold/probationary part.
Properties
Methods
Evicts an entry from the window cache into the main cache's probationary segment, when the window cache is full. If the probationary segment is full, the TinyLFU admission policy is applied. Which chooses a winner between the window and main cache victim. The entry with the worse frequency is evicted.
Executes a function on the cache segment that the entry belongs to. Passes the entries pointer to the function.
Promotes pointer to the protected MRU position. If the protected cache is full, the LRU position of the protected cache is demoted to the probationary segment.