onEvicted is called with incorrect item when a previous Add overwrites an existing item

[kaancfidan]

When the cache is full and updated with an existing item and a new item is added on top of that, onEvicted callback function is called with incorrect key and value.

See below example:

package main

import (
	"fmt"

	lru "github.com/hashicorp/golang-lru/v2"
)

var cache *lru.Cache[int, struct{}]

func main() {
	var evictedKeys []int

	cache, _ = lru.NewWithEvict(
		2,
		func(key int, _ struct{}) {
			evictedKeys = append(evictedKeys, key)
		})

	cache.Add(1, struct{}{})
	fmt.Printf("cache keys: %v\n", cache.Keys()) // cache keys: [1]

	cache.Add(2, struct{}{})
	fmt.Printf("cache keys: %v\n", cache.Keys()) // cache keys: [1, 2]

	cache.Add(1, struct{}{})
	fmt.Printf("cache keys: %v\n", cache.Keys()) // cache keys: [2, 1]

	cache.Add(3, struct{}{})
	fmt.Printf("cache keys: %v\n", cache.Keys()) // cache keys: [1 3]

	// expecting [2], or even [1 2] would be OK as 1 is overwritten
	fmt.Printf("evicted keys: %v\n", evictedKeys) // evicted keys: [1]
}

The problem is caused in these lines:

https://github.com/hashicorp/golang-lru/blob/master/lru.go#L84
https://github.com/hashicorp/golang-lru/blob/master/lru.go#L133
https://github.com/hashicorp/golang-lru/blob/master/lru.go#L157

These only take the first evicted key and the eviction caused by overwritten key appears as the first. The reason it's there is because the overwritten key is added to evictedKeys and evictedValues lists, but evicted flag is false when it's overwritten, so onEvicted is not called for it when it's actually evicted.

Either the onEvicted method must be called in a loop to consume all the keys and values, or the evicted flag must be true in the case of overwriting existing keys.

[jefferai]

That's an interesting question about whether an Add that updates an existing value with the same key should be considered an eviction. I can easily see both ways. It seems like the intent of the code was to consider it evicted (since it's added to the evicted keys/values lists) but based on this report it seems like this was never the actual behavior of the code? Or do you think there's a path by which it would ever hit the callback?

If there was never a mechanism by which it would actually have the eviction callback called due to an overwrite, my gut says we should keep that behavior, at least as a default, and have the code modified to simply not add values to evicted keys/values on an overwrite. Alternately, make that an option when constructing the cache and fix the behavior if that option is specified.

Thoughts?

[kaancfidan]

I could actually go both ways to call the key 1 evicted or not.

The major problem here is the key 2 is definitely evicted (out of the cache) but the user of the library never received that notification in the callback.

If any of the keys are evicted silently without calling the callback function, I say it's definitely a bug.

[kaancfidan]

To give perspective to this issue, in our application I'm using this cache as a proxy for models loaded in an Nvidia Triton Inference Server and I want to unload models after the number of total loaded models exceed some threshold (memory limitations). I definitely have to know every eviction because I will call the unload method in the eviction callback.

To overcome this issue of silent evictions, I had to use the following lines to not cause any key overwrites:

exists, _ := modelCache.ContainsOrAdd(modelName, struct{}{})
if exists {
    modelCache.Get(modelName)
}

instead of simply using:

modelCache.Add(modelName, struct{}{})

[jefferai]

Hi @kaancfidan -- don't worry, I'm agreed that it's a bug with the current behavior. I'm just trying to figure out the right way forward with respect to behavior.

Do you agree with my analysis that currently although the intent of the original code was to call evict when a key was given a new value that this doesn't actually ever happen right now? If so then I think the behavior to continue forward with is that behavior -- not evicting on changed value -- and making it an option to allow that if people need.

[kaancfidan]

Overwritten keys triggering eviction callbacks is a bit counter-intuitive, but I agree that it could be useful to some use-case and having an option for it is justified.

I don't get what you mean when you say it doesn't ever happen right now. Do you mean in my use-case or any other use-case that was targeted by this design?

[jefferai]

I don't get what you mean when you say it doesn't ever happen right now

What I'm saying is that if you look at the current code, it looks like it was written with the intent that an overwrite with Add would cause an eviction, but that the current implementation means that this will never happen. At least, that's how it looks to me.

The reason I'm asking is that it suggests that the correct way forward then would be to not call evict on replaced values because that will keep the current behavior. Then, if people want the evict-on-replace behavior, it can be added at some future time as an option.

[paskal]

Here is a test I wrote from the case above:

func TestCache_EvictionSameKey(t *testing.T) {
	var evictedKeys []int

	cache, _ := NewWithEvict(
		2,
		func(key int, _ struct{}) {
			evictedKeys = append(evictedKeys, key)
		})

	cache.Add(1, struct{}{})
	if !reflect.DeepEqual(cache.Keys(), []int{1}) {
		t.Fatalf("keys differs from expected: %v", cache.Keys())
	}

	cache.Add(2, struct{}{})
	if !reflect.DeepEqual(cache.Keys(), []int{1, 2}) {
		t.Fatalf("keys differs from expected: %v", cache.Keys())
	}

	cache.Add(1, struct{}{})
	if !reflect.DeepEqual(cache.Keys(), []int{2, 1}) {
		t.Fatalf("keys differs from expected: %v", cache.Keys())
	}

	cache.Add(3, struct{}{})
	if !reflect.DeepEqual(cache.Keys(), []int{1, 3}) {
		t.Fatalf("keys differs from expected: %v", cache.Keys())
	}

	// expecting [2], or even [1 2] would be OK as 1 is overwritten
	if !reflect.DeepEqual(evictedKeys, []int{2}) {
		t.Fatalf("evictedKeys differs from expected: %v", evictedKeys)
	}
}

Fails in master, however, works in my expirable LRU implementation. The only alteration you need to do to test it there is cache creation:

	cache := NewExpirableLRU[int, struct{}](
		2,
		func(key int, _ struct{}) {
			evictedKeys = append(evictedKeys, key)
		},
		0)

Should I worry that some behaviour (bug or not) from NewWithEvict differs in the new cache type?

[mgaffney]

The reason I'm asking is that it suggests that the correct way forward then would be to not call evict on replaced values because that will keep the current behavior.

I agree with this.

[mgaffney]

@dongnguyenvt -- it looks like PR #135 introduced this bug so I'm planning on reverting that change shortly. I'm happy to consider alternative solutions to address your use case but I think any solution we come up with would need to be a new mechanism not a change to existing behavior.

[dongnguyenvt]

@mgaffney no worry, in #135 I did suggest another alternative way which I've used before creating PR

[dongnguyenvt]

on another thought, I think debugging when you do expect NOT evict cb but it does is much more easier than expecting cb but it not :) in my case where evict is used for cleanup and remove temp files I did see some dangling files in long run which hard to find out the reason, but anw adding same key/val to the cache seems to be a not uncommon pattern