High frequent concurrency for cache

Question

I am learning caching and have a question on the concurrency of cache.

As I know, LRU caching is implemented with double linked list + hashtable. Then how does LRU cache handle high frequent concurrency? Note both getting data from cache and putting data to cache will update the linked list and hash table so cache is modified all the time.

If we use mutex lock for thread-safe, won't the speed be slowed down if the cache is visited by large amount of people? If we do not use lock, what techniques are used? Thanks in advance.

Answer 1

Traditional LRU caches are not designed for high concurrency because of limited hardware and that the hit penalty is far smaller than the miss penalty (e.g. database lookup). For most applications, locking the cache is acceptable if its only used to update the underlying structure (not compute the value on a miss). Simple techniques like segmenting the LRU policy were usually good enough when the locks became contended.

The way to make an LRU cache scale is to avoid updating the policy on every access. The critical observation to make is that the user of the cache does not care what the current LRU ordering is. The only concern of the caller is that the cache maintains a threshold size and a high hit rate. This opens the door for optimizations by avoiding mutating the LRU policy on every read.

The approach taken by memcached is to discard subsequent reads within a time window, e.g. 1 second. The cache is expected to be very large so there is a very low chance of evicting a poor candidate by this simpler LRU.

The approach taken by ConcurrentLinkedHashMap (CLHM), and subsequently Guava's Cache, is to record the access in a buffer. This buffer is drained under the LRU's lock and by using a try-lock no other operation has to be blocked. CLHM uses multiple ring buffers that are lossy if the cache cannot keep up, as losing events is preferred to degraded performance.

The approach taken by Ehcache and redis is a probabilistic LRU policy. A read updates the entry's timestamp and a write iterates the cache to obtain a random sample. The oldest entry is evicted from that sample. If the sample is fast to construct and the cache is large, the evicted entry was likely a good candidate.

There are probably other techniques and, of course, pseudo LRU policies (like CLOCK) that offer better concurrency at lower hit rates.