AModernCacheDesign原文地址：DesignOfAModernCache翻译地址：ModernCacheDesign缓存是提高性能的通用方法，现在大多数缓存实现都采用经典技术。在本文中，我们将探索Caffeine中的现代实现。Caffeine是一个开源的Java缓存库，可提供高命中率和出色的并发性。我希望读者能从这些想法中得到启发，并将它们应用到任何你喜欢的编程语言中。逐出策略缓存的逐出策略是预测哪些数据在短期内最有可能被再次使用，从而提高缓存的命中率。LRU（LeastRecentlyUsed）策略可能是最流行的驱逐策略，因为它实现简洁，运行时性能高效，并且在常见使用场景中具有良好的命中率。然而，LRU在通过历史数据预测未来方面存在局限性。它会认为最后传入的数据最有可能被再次访问，从而赋予它最高的优先级。现代缓存扩展了历史数据的使用，结合新近度和频率以更好地预测数据。保存历史信息的一种方法是使用流行草图（一种压缩的概率数据结构）从大量访问事件中定位常客。可以参考CountMinSketch算法，它是由一个计数矩阵和多种哈希方法实现的。当发生读取时，矩阵中每一行对应的计数器都会递增。估计频数时，取所有行中计数的最小值对应的数据。这种方法允许我们在空间、效率和适配矩阵的长度和宽度导致的散列冲突错误率之间做出权衡。WindowTinyLFU(W-TinyLFU)算法使用草图作为过滤器。当新数据比要驱逐的数据更频繁时，数据将被缓存接受。这个权限窗口让每个数据项都有机会积累人气，而不是马上被过滤掉。这样就避免了连续的miss，尤其是在流量突然飙升的场景下，一些短暂的重复流量不会被长时间保留。为了刷新历史数据，时间衰减过程被周期性地或递增地执行，将所有计数器减半。对于长期保留的数据，W-TinyLFU采用分段LRU（SegmentedLRU，缩写SLRU）策略。最初，一个数据项存储存储在试用段中，稍后访问时，将其提升为保护段（保护段占总容量的80%）。保护段满后，部分数据会被淘汰回试段，也可能级联触发试段的淘汰。这种机制保证了访问间隔小的热数据被保留，而重复访问次数少的冷数据被回收。如图中数据库和搜索场景的结果所示，通过考虑邻近性和频率，LRU的性能可以得到很大的提升。ARC、LIRS和W-TinyLFU等一些高级策略都提供了接近最佳的命中率。如果想看更多的场景测试，请查看相应的论文，或者使用模拟器测试自己的场景。在过期策略过期的实现中，往往每个数据项都有不同的过期时间。由于容量限制，数据过期后需要惰性淘汰，否则这些过期的脏数据会污染整个缓存。在通用缓存中，开启了一个专门的清理线程，周期性的遍历和清理缓存。这种策略比每次读写操作用一个按过期时间排序的优先级队列清除过期缓存要好，因为后台线程隐藏了清除过期数据的时间开销。鉴于大多数场景下不同的数据项使用固定的过期时间，Caffien采用了统一的过期时间方式。这个限制使得在O(1)有序队列中组织数据成为可能。对于数据的写后过期，维护写顺序队列，对于读后过期，维护读顺序队列。缓存可以在下面介绍的逐出策略和并发机制下重用队列，从而在缓存的维护阶段丢弃过期的数据项。并发性因为在大多数缓存策略中，数据读取都伴随着对缓存状态的写入，所以并发缓存读取被认为是一个难题。传统的解决方案是使用同步锁。这可以通过将缓存数据分成多个分区来针对锁拆分进行优化。不幸的是，热点数据持有的锁比其他数据持有的频率更高，锁拆分在这种场景下的性能提升不是很好。当单个锁的竞争成为瓶颈时，下一个经典的优化方法是只更新单个数据的元数据信息，并使用随机采样和基于FIFO的驱逐策略来减少数据操作。这些策略导致读性能高，写性能低，而且驱逐对象也很难选择。另一种可行方案来自于数据库理论，即通过提交日志来扩展写入的性能。写入操作首先被记录下来，然后异步地进行批处理，而不是立即写入数据结构。这个思想可以应用到缓存中，执行哈希表的操作，将操作记录到缓冲区中，然后在合适的时候执行缓冲区中的内容。这个策略还是需要同步锁或者tryLock，但是不同的是锁的竞争转移到了对buffer的追加写入。在Caffeine中，一组缓冲区用于记录读写。根据线程，访问将首先散列到剥离的环形缓冲区。当检测到竞争时，缓冲区会自动扩展。当一个ringbuffer满时，会触发一个异步执行操作，后续对该ringbuffer的写入将被丢弃，直到ringbuffer可以使用为止。虽然由于环形缓冲区已满而无法记录访问，但缓存的值仍然返回给调用者。这种策略信息的丢失不会有太大的影响，因为W-TinyLFU可以识别出我们要保存的热点数据。通过使用特定于线程的散列算法而不是对数据项的键进行散列，缓存避免了瞬态热键争用问题。写入数据时，使用比较传统的并发队列，每一次变化都会立即执行。尽管数据丢失是不可接受的，但仍有许多方法可以优化写入缓冲区。所有类型的缓冲区都由多个线程写入，但由单个线程执行。这种多生产者/单一消费者模式允许更简单、更有效的算法来实现。缓冲区和细粒度写入引入了竞争条件，其中对单个数据项的操作是无序的。插入、读取、更新和删除可以以各种顺序重放。如果这种策略控制不当，可能会导致悬空索引。解决方案是通过状态机来定义单个数据项的生命周期。在基准测试中，缓冲区随着哈希表的增长而增长，并且它的使用相对资源高效。读性能随CPU核数线性增加，占哈希表吞吐量的33%。写入有10%的性能损失，因为更新哈希表时的争用是主要开销。结论有许多实际主题没有涉及。包括最小化内存的技巧、复杂性增加时的质量保证测试技术，以及确定优化是否值得的性能分析方法。这些都是缓存从业者需要注意的点，因为一旦忽略了这些，就很难重拾信心去掌握缓存带来的复杂性。Caffeine的设计和实现是大量洞察力和许多贡献者共同努力的结果。如果没有以下人员的帮助，它不会在这些年里得到发展：CharlesFry、AdamZell、GilEinziger、RoyFriedman、KevinBourrillion、BobLee、DougLea、JoshBloch、BobLane、NitsanWakart、ThomasMüeller、DominicTootell、Louis沃瑟曼和弗拉基米尔·布拉戈耶维奇。感谢NitsanWakart、AdamZell、RoyFriedman和WillChu对本文草稿的反馈。
