caching - 缓存高频率并发

Question

我正在学习缓存，有一个关于缓存并发的问题。

据我所知，LRU缓存是通过双链表+哈希表实现的。那么LRU缓存是如何应对高频并发的呢？请注意，从缓存获取数据和将数据放入缓存都会更新链表和哈希表，因此缓存始终会被修改。

如果使用互斥锁来保证线程安全，如果缓存被大量访问，速度会不会变慢？如果我们不使用锁，会使用什么技术？提前致谢。

Answer 1

由于硬件有限，传统的 LRU 缓存并不是为高并发而设计的，而且命中惩罚远小于未命中惩罚(例如数据库查找)。对于大多数应用程序来说，如果缓存仅用于更新底层结构(不计算未命中的值)，则锁定缓存是可以接受的。当锁发生争用时，诸如分段 LRU 策略之类的简单技术通常就足够了。

使 LRU 缓存扩展的方法是避免在每次访问时更新策略。需要进行的关键观察是，缓存的用户并不关心当前的 LRU 排序是什么。调用者唯一关心的是缓存保持阈值大小和高命中率。这通过避免每次读取时改变 LRU 策略打开了优化之门。

memcached采取的方法是丢弃一个时间窗口内的后续读取，例如1秒。缓存预计会非常大，因此通过这个更简单的 LRU 驱逐较差候选者的可能性非常低。

ConcurrentLinkedHashMap采取的方法(CLHM)，随后Guava's Cache ，就是将访问记录在缓冲区中。该缓冲区在 LRU 的锁定下被耗尽，并且通过使用尝试锁定，无需阻止其他操作。 CLHM 使用多个环形缓冲区，如果缓存无法跟上，这些缓冲区就会有损，因为丢失事件比降低性能更好。

Ehcache采取的方法和 redis是一个概率 LRU 策略。读取更新条目的时间戳，写入迭代缓存以获得随机样本。最旧的条目将从该样本中逐出。如果样本构建速度快并且缓存很大，则被逐出的条目可能是一个不错的候选者。

可能还有其他技术，当然还有伪 LRU 策略(如 CLOCK)，可以以较低的命中率提供更好的并发性。