flaky test: TestInstrumentedIndexBehavior/ConcurrentOperations fails intermittently

[yankay]

The test TestInstrumentedIndexBehavior/ConcurrentOperations is flaky and often fails on CI. Example failure log:

=== RUN   TestInstrumentedIndexBehavior/ConcurrentOperations
    index_test.go:248: 
        Error Trace:	/home/runner/work/llm-d-kv-cache/llm-d-kv-cache/pkg/kvcache/kvblock/index_test.go:248
        		/opt/hostedtoolcache/go/1.24.1/x64/src/runtime/asm_amd64.s:1700
        Error:      	[]kvblock.PodEntry{kvblock.PodEntry{PodIdentifier:"pod-50-9", DeviceTier:"gpu"}, kvblock.PodEntry{PodIdentifier:"pod-20-6", DeviceTier:"gpu"}, kvblock.PodEntry{PodIdentifier:"pod-70-6", DeviceTier:"gpu"}, kvblock.PodEntry{PodIdentifier:"pod-30-9", DeviceTier:"gpu"}, kvblock.PodEntry{PodIdentifier:"pod-80-6", DeviceTier:"gpu"}, kvblock.PodEntry{PodIdentifier:"pod-40-9", DeviceTier:"gpu"}, kvblock.PodEntry{PodIdentifier:"pod-90-9", DeviceTier:"gpu"}} does not contain kvblock.PodEntry{PodIdentifier:"pod-0-0", DeviceTier:"gpu"}
        Test:       	TestInstrumentedIndexBehavior/ConcurrentOperations
--- FAIL: TestInstrumentedIndexBehavior (0.04s)
    --- PASS: TestInstrumentedIndexBehavior/BasicAddAndLookup (0.00s)
    --- PASS: TestInstrumentedIndexBehavior/DuplicatePodHandling (0.00s)
    --- PASS: TestInstrumentedIndexBehavior/FilteredLookup (0.00s)
    --- PASS: TestInstrumentedIndexBehavior/EvictBasic (0.00s)
    --- FAIL: TestInstrumentedIndexBehavior/ConcurrentOperations (0.03s)

Reference CI failure: https://github.com/llm-d/llm-d-kv-cache/actions/runs/21009734880/job/60401398582?pr=255

Please investigate the cause of flakiness and fix the concurrency issues in this test.

[delavet]

It's speculation right now, but it looks like there is a race condition in the InMemoryIndex.Add method that occurs under high concurrency when multiple goroutines operate on the same requestKey.

The Scenario is described as follows:

1. Goroutine A retrieves podCacheA from m.data.Get(requestKey)
2. Goroutine B executes Evict, clearing podCacheA and removing it from m.data
3. Goroutine C executes Add, finds no cache in m.data, creates podCacheB, and adds it to m.data
4. Goroutine A continues using the stale podCacheA reference and adds entries to it
5. Goroutine A executes Lookup, retrieves podCacheB from m.data, and cannot find the entries it just added (they're in podCacheA, which is no longer in m.data)

While individual lru.Cache operations are thread-safe, the compound operation (get cache → add entries) is not atomic, creating a window where the cache can be evicted and replaced

I think this problem should be extremely rare in actual scenarios, and I haven't thought of a good way to solve it yet. First, let's throw out the question.

[vMaroon]

That's accurate @delavet - and this window was left open to avoid holding the lock on the entire index throughout the Add/Evict calls.

We discussed this once - here: #107 (and the thread the PR references). I think the concurrency test may not be reflective of feasible or real-world scenarios, but this could be an underestimation.

Let's discuss whether it makes sense to change the test, or to fix the issue by coarser locking across the index. I personally lean towards the first.

[vMaroon]

@yankay @delavet are you fine with #366?

[delavet]

@yankay @delavet are you fine with #366?

I think it's OK, and it feels unnecessary to spend effort on passing the current test. Perhaps the most effective solution is to add a global lock, but considering that this situation rarely occurs and adding a lock would significantly impact efficiency, it’s not worth it.

[yankay]

@yankay @delavet are you fine with #366?

I also think the solution of #366 is resonable