7

我正在学习缓存，并且对缓存的并发性有疑问。

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

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

4

1 回答 1

12

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

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

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

ConcurrentLinkedHashMap (CLHM) 和Guava 的 Cache采用的方法是将访问记录在缓冲区中。这个缓冲区在 LRU 的锁下被耗尽，并且try-lock没有其他操作必须被阻塞。CLHM 使用多个环形缓冲区，如果缓存无法跟上，则这些缓冲区是有损的，因为丢失事件比性能下降更可取。

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

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

于 2013-09-24T03:13:57.017 回答