LFU: Deterministic eviction

[erwanor]

Consider an LFU cache with capacity=10 i.e:

gc, _ := gcache.New(10).LFU().Build()

We fill the cache:

for key := 0; key < 10; i++ {
    value := fmt.Sprintf("val%d", key)
    gc.Set(key, val)
}

Now that the cache is filled, the next call to Cache.Set should lead to the eviction of the Least-Frequently-Used entry. So far, so good.

When multiple entries share the same frequency (here all our entries have freq=0) we "pick" one at random. That is, the Cache.evict internal function will iterate over the internal map until we have evicted enough entries. Iterating over a map is done in a randomized order (per Golang maps semantics). We should explore whether that's a desirable behavior or if we should evict the least recent entry when everything else is equal.

Potential solution: Use a sorted map for the internal LFU maps.