4 ms·
> 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 rando
by KAdot 7y ago
> 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 https://play.golang.org/p/dT1CWuqoHEM.
- deleted 7y ago[deleted]
- mrjn 7y agoBased 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.