本文由阿里巴巴集团客户体验组剑石贡献，剑石结合工作场景对缓存做了一些研究，翻译了一篇文章，供同行们学习借鉴。

原来的：

缓存是提高性能的常用方法。当今大多数缓存实现都使用经典技术。在本文中，我们将探索 中的现代实现。它是一个开源 Java 缓存库，提供高命中率和出色的并发性。我希望读者能从这些想法中受到启发，并将它们应用于您喜欢的任何编程语言。

驱逐策略

缓存驱逐策略就是预测哪些数据在短期内最有可能被再次使用，从而提高缓存命中率。LRU（最少使用）策略可能是最受欢迎的驱逐策略，因为它实现简单、运行时性能高效，在常见使用场景中命中率高。然而，LRU 在通过历史数据预测未来方面存在局限性。它会假设最后到达的数据最有可能被再次访问，从而赋予其最高优先级。

现代缓存扩展了历史数据的使用，将接近度（）和访问频率（）结合起来，以便更好地预测数据。保留历史信息的一种方法是使用（一种压缩的、概率的数据结构）从大量访问事件中定位频繁访问者。可以参考~/pubs//.pdf 算法，该算法由计数矩阵和多种哈希方法实现。当发生读取时，矩阵中每一行对应的计数器都会增加，而在估计频率时，则取所有行中最小计数对应的数据。这种方法使我们能够在空间、效率以及通过调整矩阵的长度和宽度而导致的哈希碰撞的错误率之间做出权衡。

(W-) 算法充当过滤器，当新数据比要驱逐的数据更频繁时，数据将被缓存接受。这个允许窗口使每个数据项都有机会积累流行度，而不是立即被过滤掉。这避免了连续的缺失，特别是在流量突然激增的场景中，一些短暂的重复流量不会长时间保留。为了刷新历史数据，会定期或增量地执行时间衰减过程，将所有计数器减半。

对于长期保留数据，W-采用分段式LRU（LRU，简称SLRU）策略。最初，一个数据项存储在试用段（），当后续被访问时，会提升到保护段（）（保护段占总容量的80%）。当保护段写满时，部分数据会被淘汰回试用段，这也可能引发级联式试用段的淘汰。这种机制确保访问间隔小的热数据得到保留，而重复访问较少的冷数据则被回收利用。

从数据库和搜索场景的结果可以看出，通过考虑接近度和频率，LRU 的性能可以得到很大的提升。一些高级策略，如 ARC ()、LIRS () 和 W- () 提供了接近理想的命中率。更多场景测试请查看相应的论文，或者你可以使用 () 来测试你自己的场景。

到期政策

在过期的实现中，往往每个数据项都有不同的过期时间，由于容量限制，过期后需要对数据进行惰性淘汰，否则这些过期的脏数据会污染整个缓存。一般在缓存中启用专门的清理线程，定期遍历清理缓存。这种策略比每次读写时都清理按过期时间排序的优先级队列中的过期缓存要好，因为后台线程隐藏了清除过期数据的时间开销。

由于大多数场景下不同数据项的过期时间都是固定的，因此采用统一的过期时间方式。这个限制使得可以使用 O(1) 有序队列来组织数据。对于写入后过期的数据，维护一个写顺序队列，对于读取后过期的数据，维护一个读顺序队列。缓存可以在下文介绍的驱逐策略和并发机制下重用这些队列，从而在缓存维护阶段丢弃过期的数据项。

并发

由于在大多数缓存策略中，数据的读取都伴随着对缓存状态的写入，因此并发缓存读取被认为是一个难题。传统的解决方案是使用同步锁。这可以通过将缓存数据划分为多个分区进行锁分割来优化。不幸的是，热数据持有的锁比其他数据持有的锁更多，锁分割在这种场景下的性能提升并不那么好。当单把锁的竞争成为瓶颈时，下一个经典的优化方法是只更新单条数据的元数据信息，并使用随机采样（）和基于FIFO（#-）的驱逐策略来减少数据操作。这些策略将导致高性能读取和低性能写入，并且也很难选择要驱逐的对象。

另一个可行的方案（）来自于数据库理论，就是通过提交日志来延长写入性能。写入操作先记录在日志中，然后批量异步执行，而不是立即写入数据结构。这个思路可以应用到缓存中，进行哈希表操作sketch 试用，将操作记录在缓冲区中，然后在合适的时机执行缓冲区的内容。这个策略仍然需要同步锁或，区别在于将锁的竞争转移到对缓冲区的追加写入。

中有一组缓冲区用于记录读写操作。一次访问会先根据线程散列到环中，当检测到竞争时，缓冲区会自动扩展。当某个环已满时，会触发异步执行，后续对该环的写入将被丢弃，直到该环可以使用。虽然由于环已满而无法记录该访问，但缓存的值仍然会返回给调用者。这种策略信息的丢失不会带来很大影响，因为 W- 可以识别出我们想要保存的热数据。通过使用随线程变化的散列算法sketch 试用，而不是对数据项的键进行散列，缓存避免了瞬时热键竞争的问题。

在写入数据时，使用更传统的并发队列，每次更改都会导致立即执行。虽然数据丢失是不可接受的，但仍有许多方法可以优化写入缓冲区。所有类型的缓冲区都由多个线程写入，但由单个线程执行。这种多生产者/单消费者模型允许实现更简单、更高效的算法。

缓冲区和细粒度写入会引入竞争条件，即对单个数据项的操作会乱序。插入、读取、更新和删除都可能以各种顺序重放，如果策略控制不当，可能会导致悬空索引。解决方案是通过状态机定义单个数据项的生命周期。

在基准测试 (#read-100-1) 中，缓冲区会随着哈希表的增长而增长，从而使其使用起来更加节省资源。读取性能与 CPU 核心数量成线性关系，占哈希表吞吐量的 33%。写入性能会降低 10%，因为更新哈希表时的争用是主要开销。

综上所述

这里没有涉及许多实际主题，包括最小化内存使用的技术、在复杂性增加时确保质量的测试技术以及确定优化是否值得的性能分析方法。这些都是缓存从业者需要关注的领域，因为一旦忽视了这些，就很难重新获得掌握缓存引入的复杂性的信心。

的设计是众多贡献者众多见解和贡献的结果。多年来，如果没有 Fry、Adam Zell、Gil、Roy、Kevin、Bob Lee、Doug Lea、Josh Bloch、Bob Lane、、Müeller、、Louis 和 Adam Zell、Roy 以及 Will Chu 的帮助，它的演变是可能的。

本文来自微信公众号“麦芽面包”，id“”

如有侵权请联系删除！