[barrkel]

The batched log approach mentioned in the comments is also interesting. Possibly not directly applicable to cache page eviction policy where I expect the pressure to free up an old page to make space for data is more time-critical, but a useful model to keep in mind, alongside the probabilistic list sharding described in the article.

[pstrateman]

That's certainly an interesting approach.

It's got a maximum latency problem though.

If for some reason the unlucky thread that acquires the lock cannot process the batch faster than other threads are adding.... well that ends poorly

[NovaX]

That would require a write rate very atypical for a cache and easily mitigated, though largely an almost impossible scenario.