Cache eviction fails when entries inserted at the same time and cause cache to grow beyond settings #27
Description
Describe the bug
Cache eviction, triggered when a given shard reaches capacity, fails if the entries are inserted at (effectively) the same time. When eviction fails, each subsequent insert will again trigger eviction which doesn't actually evict anything. This adds a lot of overhead to lock the shard repeatedly on each insert. In addition since nothing is actually evicted, the capacity can grow without bound irregardless of the capacity set at cache creation.
This stems from this time conditional logic here in quickselect:
Line 9 in d368220
Expected behavior
One would expect that when eviction occurs it occurs on the oldest entries by insertion/access order. However I know you rely on a timestamp rather than ordering. In this case, at the minimum you still need to evict "mid"-timestamp to ensure the capacity doesn't grow without bound. If you rely on timestamp only, that division line for for eviction needs to be arbitrary.
To Reproduce
See minimal working example playground here: https://go.dev/play/p/ONpOPdxo8S5
No eviction occurs and the cache grows to 200 entries even though the cache is set to a capacity of 10.
Add a time.Sleep and the eviction works properly: https://go.dev/play/p/l6CGE6MyjHT
However if you add a time.Sleep at some later iteration (i > 150 in this case), there is still no eviction due to the quickselect partitioning logic: https://go.dev/play/p/NTac6SjX4Ls