Writing a concurrent LRU cache

30 points 42jd

I am looking at writing a thread-safe performant LRU cache as a fun side project (working my up to try and write a graph db!). I saw this blog post which investigated different replacement policies for neo4j’s pagecache: https://xwkuang5.github.io/neo4j-pagecache-study/. neo4j uses gclock as it doesn’t have contention issues. The issue with a doubly-linked list is that one needs an exclusive lock when moving a node to the front.

To resolve this the post mentions two ideas:

1.\tbatching in-thread operations if possible. So if two reads hit, no eviction is needed so can batch them together to update list once. (see: http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-09-1.pdf)
2.\tbatching multiple-thread operations and have a separate thread perform the operations. (See: http://www.cs.bgu.ac.il/~hendlerd/papers/flat-combining.pdf)

Part 1 makes sense, 2 is a little confusing. The blog post ends up using this Java library: https://github.com/ben-manes/concurrentlinkedhashmap which implements those ideas. I am curious if there is something equivalent implemented in rust, or is it something I should write? Also is there an even better way to do thread-safe performant LRU?

If I write this myself I got a lot of research to do but I am guessing I would use an already implemented concurrent hashmap backed by a doubly linked list. And would have to figure out how the batching works.

Side note: I found this blog post which seems to be doing something similar to the above points, https://tech.ebayinc.com/engineering/high-throughput-thread-safe-lru-caching/

Side note 2: Be kind as while I’ve implemented a simple non-thread safe LRU for my cs class I’m brand new to parallelism :)