vimpunk
commented
7 years ago @ben-manes Thanks for taking a look, it's an honor! :)
My use case for the cache is very specific and since it will only be used by internal parts of the project, I haven't considered protection against hash-collisions or the other more advanced features Caffeine offers.
However, eventually I'll fix this and strive for a more general solution, as time allows. So thanks for the observation and pointers to your code!
P.S. That is exactly what I thought when I read your paper :)
A topic not discussed in the paper is denial of service attacks by exploiting the hash codes. For TinyLFU this occurs when an attacker is able to place an entry as the main cache's victim. Then the attacker artificially raises the victim's frequency by exploiting hash collisions so that all new arrivals are rejected. This would lead to a very poor hit rate and exhaust the underlying resource.
Initially, I tried to protect against this by using a random smear in the sketch. However that doesn't protect against entries with the same hash code. The proper solution was to instead add a random admittance if the candidate is "warm". This adds enough jitter to break the attack vector without impacting the hit rate.
See the relevant function and the test case.
P.S. This is neat :)