News for hackers. Stuff that matters.
Re:Ristretto: A High Performance, Concurrent, Memory-Bound G... by KAdot on Saturday September 21, 2019 @02:48PM (#21037145)
> we used the natural randomness provided by Go map iteration to pick a sample of keys and loop over them to find a key

The iteration order of Go maps is randomized, but it's far from being evenly distributed (it could be good enough for the Ristretto use case though). Here is a test that shows that some keys are 6 times more likely to be selected on the first iteration https://play.golang.org/p/dT1CWuqoHEM.

Re:Ristretto: A High Performance, Concurrent, Memory-Bound G... by mrjn on Saturday September 21, 2019 @03:05PM (#21037232)
Based on this behavior, the two scenarios for Ristretto would be:

1. If the chosen sample keys have high Estimate, the incoming keys could be rejected, affecting the Hit ratios. However, our Hit ratio benchmarks didn't show such behavior (within 1% of exact LFU).

> With this approach, the hit ratios are within 1% of the exact LFU policies for a variety of workloads.

2. The chosen keys have low Estimates, in which case they'd be removed and hence, won't suffer from repeated selection.

So, yeah. Doesn't affect Ristretto. But, good thing to keep in mind for other workloads.