I've implemented an LRU cache. The process to insert a new item looks like this:
- Check if enough space in haystack. If yes, skip to 4.
- Remove least recently used item.
- Check if enough space. If not, repeat 2.
- Insert item in free space.
Items are ordered effectively randomly in the haystack.
The problem arises when an item needs to be inserted that is bigger than previous items. It leads to a "mass eviction", where it keeps on evicting until enough items have been evicted that there happen to have been evictions of several contiguous items.
This "mass eviction" often involves evicting tens of thousands of items.
What can be done to avoid or mitigate this "mass eviction"?