Locking does not mean blocking. If you don't block the readers on the LRU reordering then it scales very well. That's a trick that's been in my production systems for 14 years now, and pretty much everywhere in Java land, that scales to over 900M reads/s on my laptop. Instead of probabilistic eviction you can use probabilistic reordering, e.g. via lossy sampling of the hits. The main benefit over sampled eviction or clock policies is that it is easier to use more robust and constant time algorithms.