A question about the eviction strategy

[anhoder]

I wrote a demo for otter, and its results puzzled me.

Otter uses the S3 FIFO eviction strategy, which works as shown in the following gif:

But in my demo, otter cleared the "0" that was hit the most.

playground

package main

import (
    "fmt"
    "time"

    "github.com/maypok86/otter"
)

func main() {
    t, err := otter.MustBuilder[int, int](64).Build()
    if err != nil {
        panic(err)
    }

    for i := range 128 {
        t.Set(i, i)

        t.Get(0)
    }

    fmt.Println(t.Get(0)) // 0 true

    time.Sleep(time.Second) // wait for eviction

    fmt.Println(t.Get(0)) // 0 false
}

[maypok86]

Hi, this is a small feature of the strategy that otter uses to reduce contention (also used by ristretto, theine, ccache, caffeine, moka...). Write operations are performed asynchronously in the background. As Ben has already pointed out in this issue, in languages with GC, it doesn't make much sense to be too strict in this case.

[ben-manes]

Oh, I guess you only process read events when that buffer is full. That takes a while since the selection is random, so on this test eviction was fifo (insertion order) because it evicted before enough reads accumulated.

Would it make sense to drain the read buffers during the write processing before triggering an eviction? That’s what I did, but could easily argue it’s an unnecessary change as unit tests don’t often reflect real world behavior.

[maypok86]

Oh, I guess you only process read events when that buffer is full.

I did this simply because historically all caches in Go that use BP-Wrapper process read events only when the buffer is full. (ristretto, theine).

Would it make sense to drain the read buffers during the write processing before triggering an eviction?

Maybe yes, but I haven't heard about problems because of this in otter and other caches. I also didn't see anything suspicious in the tests close to reality (zipf distributions and some real-world traces). So far, removing prefetching seems to be a higher priority, as well as recalculating the test results for ristretto. As it turned out, there is nothing wrong with its core. Dgraph just broke the default behavior of ristretto and almost nowhere wrote about it. As a result, a huge number of current clients have an extremely low hit ratio.

Adding this parameter broke the behavior of clients who use cost = 1. It is absolutely not obvious that the size of metadata will be taken into account when setting capacity. There is also nothing about this parameter in the README (there are other parameters) :(.

[maypok86]

I'll close this for now, as it looks resolved.