一个古代的缓存设计方案

原文地址：Design Of A Modern Cache
译文地址：现代化的缓存设计方案

缓存是晋升性能的通用办法，当初大多数的缓存实现都应用了经典的技术。这篇文章中，咱们会挖掘 Caffeine 中的现代化的实现办法。Caffeine 是一个开源的 Java 缓存库，它能提供高命中率和杰出的并发能力。冀望读者们能被这些想法激发，进而将它们利用到任何你喜爱的编程语言中。

驱赶策略

缓存的 驱赶策略是为了预测哪些数据在短期内最可能被再次用到，从而晋升缓存的命中率。因为简洁的实现、高效的运行时体现，以及在惯例的应用场景下有不错的命中率，LRU（Least Recently Used）策略或者是最风行的驱赶策略。但 LRU 通过历史数据来预测将来是局限的，它会认为最初到来的数据是最可能被再次拜访的，从而给与它最高的优先级。

古代缓存扩大了对历史数据的应用，联合就近水平（recency）和拜访频次（frequency）来更好的预测数据。其中一种保留历史信息的形式是应用 popularity sketch（一种压缩、概率性的数据结构）来从一大堆拜访事件中定位频繁的访问者。能够参考 CountMin Sketch 算法，它由计数矩阵和多个哈希办法实现。产生一次读取时，矩阵中每行对应的计数器减少计数，估算频率时，取数据对应是所有行中计数的最小值。这个办法让咱们从空间、效率、以及适配矩阵的长宽引起的哈希碰撞的错误率上做衡量。

Window TinyLFU（W-TinyLFU）算法将 sketch 作为过滤器，当新来的数据比要驱赶的数据高频时，这个数据才会被缓存接收。这个许可窗口给予每个数据项积攒热度的机会，而不是立刻过滤掉。这防止了继续的未命中，特地是在忽然流量暴涨的的场景中，一些短暂的反复流量就不会被长期保留。为了刷新历史数据，一个工夫衰减过程被周期性或增量的执行，给所有计数器减半。

对于长期保留的数据，W-TinyLFU 应用了分段 LRU（Segmented LRU，缩写 SLRU）策略。起初，一个数据项存储被存储在试用段（probationary segment）中，在后续被拜访到时，它会被晋升到爱护段（protected segment）中（爱护段占总容量的 80%）。爱护段满后，有的数据会被淘汰回试用段，这也可能级联的触发试用段的淘汰。这套机制确保了拜访距离小的热数据被保留下来，而被反复拜访少的冷数据则被回收。

如图中数据库和搜寻场景的后果展现，通过思考就近水平和频率能大大晋升 LRU 的体现。一些高级的策略，像 ARC，LIRS 和 W-TinyLFU 都提供了靠近最现实的命中率。想看更多的场景测试，请查看相应的论文，也能够在应用 simulator 来测试本人的场景。

过期策略

过期的实现里，往往每个数据项领有不同的过期工夫。因为容量的限度，过期后数据须要被懒淘汰，否则这些已过期的脏数据会净化到整个缓存。个别缓存中会启用专有的打扫线程周期性的遍历清理缓存。这个策略相比在每次读写操作时依照过期工夫排序的优先队列来清理过期缓存要好，因为后盾线程暗藏了的过期数据革除的工夫开销。

鉴于大多数场景里不同数据项应用的都是固定的过期时长，Caffien 采纳了对立过期工夫的形式。这个限度让用 O（1）的有序队列组织数据成为可能。针对数据的写后过期，保护了一个写入程序队列，针对读后过期，保护了一个读取程序队列。缓存能复用驱赶策略下的队列以及上面将要介绍的并发机制，让过期的数据项在缓存的维护阶段被摈弃掉。

并发

因为在大多数的缓存策略中，数据的读取都会随同对缓存状态的写操作，并发的缓存读取被视为一个难点问题。传统的解决形式是用同步锁。这能够通过将缓存的数据划成多个分区来进行锁拆分优化。可怜的是热点数据所持有的锁会比其余数据更常的被占有，在这种场景下锁拆分的性能晋升也就没那么好了。当单个锁的竞争成为瓶颈后，接下来的经典的优化形式是只更新单个数据的元数据信息，以及应用随机采样、基于 FIFO 的驱赶策略来缩小数据操作。这些策略会带来高性能的读和低性能的写，同时在抉择驱赶对象时也比拟艰难。

另一种可行计划来自于数据库实践，通过提交日志的形式来扩大写的性能。写入操作先记入日志中，随后异步的批量执行，而不是立刻写入到数据结构中。这种思维能够利用到缓存中，执行哈希表的操作，将操作记录到缓冲区，而后在适合的机会执行缓冲区中的内容。这个策略仍然须要同步锁或者 tryLock，不同的是把对锁的竞争转移到对缓冲区的追加写上。

在 Caffeine 中，有一组缓冲区被用来记录读写。一次拜访首先会被因线程而异的哈希到 stripped ring buffer 上，当检测到竞争时，缓冲区会主动扩容。一个 ring buffer 容量满载后，会触发异步的执行操作，而后续的对该 ring buffer 的写入会被抛弃，直到这个 ring buffer 可被应用。尽管因为 ring buffer 容量满而无奈被记录该拜访，但缓存值仍然会返回给调用方。这种策略信息的失落不会带来大的影响，因为 W-TinyLFU 能辨认出咱们心愿保留的热点数据。通过应用因线程而异的哈希算法代替在数据项的键上做哈希，缓存防止了刹时的热点 key 的竞争问题。

写数据时，采纳更传统的并发队列，每次变更会引起一次立刻的执行。尽管数据的损失是不可承受的，但咱们依然有很多办法能够来优化写缓冲区。所有类型的缓冲区都被多个的线程写入，但却通过单个线程来执行。这种多生产者 / 单个消费者的模式容许了更简略、高效的算法来实现。

缓冲区和细粒度的写带来了单个数据项的操作乱序的竞态条件。插入、读取、更新、删除都可能被各种程序的重放，如果这个策略管制的不适合，则可能引起悬垂索引。解决方案是通过状态机来定义单个数据项的生命周期。

在基准测试中，缓冲区随着哈希表的增长而增长，它的的应用绝对更节俭资源。读的性能随着 CPU 的核数线性增长，是哈希表吞吐量的 33%。写入有 10% 的性能损耗，这是因为更新哈希表时的竞争是最次要的开销。

论断

还有许多实用的话题没有被笼罩到。包含最小化内存的技巧，当复杂度上升时保证质量的测试技术以及确定优化是否值得的性能分析方法。这些都是缓存的实践者须要关注的点，因为一旦这些被忽视，就很难重拾掌控缓存带来的复杂度的信念。

Caffeine 的设计实现来自于大量的洞见和许多贡献者的共同努力。它这些年的演变离不开一些人的帮忙：Charles Fry, Adam Zell, Gil Einziger, Roy Friedman, Kevin Bourrillion, Bob Lee, Doug Lea, Josh Bloch, Bob Lane, Nitsan Wakart, Thomas Müeller, Dominic Tootell, Louis Wasserman, and Vladimir Blagojevic. Thanks to Nitsan Wakart, Adam Zell, Roy Friedman, and Will Chu for their feedback on drafts of this article。