[potential bug (?)] Sets on an existing key does not overwrite the value with small LFU sizes (and nothing to evict from slru)

[2785]

func main() {
    c := tinylfu.New(100, 10000)

    c.Add("foo", "bar")

    val, _ := c.Get("foo")
    fmt.Println(val)

    c.Add("foo", "baz")

    val, _ = c.Get("foo")
    fmt.Println(val)
}

the above snippet prints bar and bar when doing .Add() on the same key. This seems to be because the code here

https://github.com/dgryski/go-tinylfu/blob/master/tinylfu.go#L85-L113

• t, t.lru, and t.slru all share the same underlying map[string]*list.Element

• L89 - t.lru.add for the new item decides to evict the old item ("bar") because ll.Len() of 1 is not smaller than lru.cap which is also 1 when tinylfu size is 100

• at L94 the shared map[string]*list.Element contains the correct entry baz

• L95 t.slru.victim() finds no victims to evict

• L97 t.slru.add(oitem) adds the old item into the slru and overwrites the baz value on the shared map with bar

• by the time this function exits the data contains foo: bar instead of foo: baz

• we do have the work around of deleting prior to adding

• I'd give a PR a stab but I don't fully understand how this package works to know what'd be the architecturally correct fix

[dgryski]

I'll take a look. Thanks for the detailed report.

[dominikh]

@dgryski any ETA on looking at it?

[dgryski]

The cache didn't handle "Add" well if a key was already in the cache. We now detect this case and handle list movements as if it was "Get".