Clearing LFU cache doesn't actually clear it about bitfaster.caching HOT 9 CLOSED

You beat me to it - I was going to try with ForegroundScheduler.

I think the reason ForegroundScheduler is working and BackgroundThreadScheduler fails (even when calling Clear twice) is due to a bug - the Clear method is immediately purging the write buffer which contains the removed items that were just added by TryRemove - they are removed before they have been processed in the background. Foreground scheduler works because TryRemove is fully completed before the write buffer is cleared.

What isn't clear to me is how the unit test for this can pass. I will debug this in detail.

from bitfaster.caching.

I looked at this some more yesterday - the code is wrong and leaves orphan nodes in the window/probation/protected LRUs. These are the bogus items you observed in the probation LRU.

The unit test I have passes because it only validates via the count and whether the removed keys exist. Both count and exists are based on the internal dictionary. Clear internally calls TryRemove which immediately removes the key from the dictionary (thus test criteria is met and the unit test passes). TryRemove also stores a record of removal in the write buffer (so the LRUs can be cleaned up by maintenance later). But since Clear immediately drops the buffers before maintenance, orphans are left behind in window/probation/protected. These are not observable by the test when performing only a single iteration of clear.

In your test, it is possible background maintenance runs before Clear drops the write buffer (so it can pass sometimes). If maintenance doesn't run, orphans are left behind and subsequent iterations build up more orphans. Since Clear will attempt to Trim n cache entries, the orphans with dupe keys will be processed ahead of other valid items that appear in the list after n items are processed. For example, let's say the cache is size 3 and contains keys [a, b, c], but the probation LRU ends up with orphans of key a, so contains [a, a, a, b, c]. Trim will take n=3 candidates from probation, then attempt to remove key a 3 times. The next time around, it may have cleared all the orphans and produce a valid result, so it works intermittently.

I will fix this so that the write buffer items are not dropped. I will also implement an integrity check in the tests to validate the internal data structures are in a consistent state to prevent re-introducing this bug. Last month I added some soak tests for ConcurrentLru (multi-threaded tests that interleave different read/write method pairs), I will also get this done for LFU and check for any other similar bugs.

from bitfaster.caching.

Update: I tested with ForegroundScheduler, and that makes the test green of course, which means that the test doesn't reflect the real-world situation, where BackgroundThreadScheduler supposedly never gets around to clean things up.

from bitfaster.caching.

I would have thought that calling Clear multiple times would work, since it calls Maintenance internally, which also is what the background scheduler does.

from bitfaster.caching.

Hey @bitfaster! 👋🏻

I think we're bumping up against the same bug. Can you confirm this also affects ConcurrentLru<K, V>?

Is there a workaround? Looping through entries and calling TryRemove?

We're using v2.2.1.

UPDATE: Looping with TryRemove seems to leave the cache in a broken state as well 😅

from bitfaster.caching.

Moved repro to #402

from bitfaster.caching.

Moved repro to #402

from bitfaster.caching.

Moved repro to #402

from bitfaster.caching.

@khellang I created a new issue for ConcurrentLru here #402, and copied over all your notes.

from bitfaster.caching.