Here is a prototype of an idea I've had for a while for an efficient concurrent LRU cache.
It is completely untested... consider it more "code as design". It should feature faster cleaning - O( n ) when it works well.
In addition to low and high water marks, it adds the concept of an "acceptable" water mark. A cleaning phase will try to go to the low water mark, but will be considered successful if it hits the acceptable water mark.
This is coupled with a multi-pass cleaning phase. From the comments:
The oldestEntry and newestEntry in the set of entries currently being considered is recorded for each phase. Entries that are new enough such that they are guaranteed to be kept are immediately removed from consideration, and entries that are old enough such that they are guaranteed to be removed are immediately removed (no sorting necessary). After 2 phases of this (configurable) and we still haven't removed enough entries, a priority queue is used to find the oldest entries out of those remaining.
There are undoubtedly some other tricks we can use, but this was the best I could come up with for now.