TinyLFU
ben-manes opened this issue · 4 comments
Can you give this policy a try? I'd be interested in hearing feedback, concerns, ideas, etc.
I'm implementing TinyLFU as we speak :)
If it helps see my CountMinSketch and BloomFilter (32-bit hash due to Java's hashCode()). There is also the go-tinylfu, which I think you saw, that is very readable. I think writing sketches is pretty fun part of this algorithm.
My current use case is a DNS server, where the primary focus of the cache policy is not the hit ratio. Latency and adversarial defense are more important.
Resetting the TinyLFU counters is a blocking operation, and may be a showstopper for that use case.
In my simulations an incremental reset performed equally well. So while it increases the error, it doesn't really diminish whether an entry is a heavy hitter. Those entries will quickly max out the frequency, or we end up taking a warm (but not hot) candidate. Then the algorithm is O(1) and not merely amortized O(1). I used periodic reset since that can easily be vectorized or, in my case, deferred to be async.
In the implementation, I also added HashDoS protection by randomly accepting a warm candidate. That disrupts an attack trying to artificially raise the victim's frequency due to a collision, thereby halting admissions.