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.