search

jedisct1 / rust-arc-cache

An Adaptative Replacement Cache for Rust
Other
11 stars 3 forks source link

TinyLFU #1

Closed ben-manes closed 4 years ago

ben-manes commented 8 years ago

Can you give this policy a try? I'd be interested in hearing feedback, concerns, ideas, etc.

jedisct1 commented 8 years ago

I'm implementing TinyLFU as we speak :)

ben-manes commented 8 years ago

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.

jedisct1 commented 8 years ago

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.

ben-manes commented 8 years ago

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.