淘汰策略

你可以手动控制程序的I/O操作，但大多数情况下都只是依赖自动的缓冲（bufferization）和缓存（caching），要么是因为懒惰，要么是因为计算环境的限制。

然而，自动缓存也有自己的挑战。当一个程序用完其用于存储中间数据的工作内存时，如果要为新数据创建空间，就需要去除一个现存的数据块。在冲突情况下决定在缓存中保留哪些数据的具体规则被称为淘汰策略（eviction policy）。

这个规则可以是任意的，但有几个流行的选择：

  • 先入先出（first in first out，FIFO）：简单地淘汰最早添加的块，而不考虑之前访问的频率（与FIFO队列的方式相同）。
  • 最近最少使用（least recently used，LRU）：淘汰最长时间未访问的块。
  • 后入先出（last in first out，LIFO）和最近最常使用（most recently used，MRU）：与前两者相反。删除最热的块似乎有害，但是在某些情况下，这些策略是最优的，例如需要在有限的周期内循环遍历同一个文件（优先移除最新缓存的，这样等再次循环到文件开头时，内容还在缓存中）。
  • 最少频率使用（least-frequently used，LFU）：记录每个块被请求的频次并丢弃最少使用的块。一些变种还会考虑随时间变化的访问模式，例如使用时间窗口只考虑最近nn次访问，或使用指数平均以给予最近访问更多权重。
  • 随机替换（random replacement，RR）：随机丢弃一个块。优点是不需要维护任何包含块信息的数据结构。

驱逐策略的准确性与其实施复杂度带来的额外开销之间存在着自然的权衡（trade-off）关系。对于CPU缓存，你需要一个可以轻易地在硬件中实现并且几乎没有延迟的简单策略。而对于可以允许一定延迟，并且有计划性的情况，例如Netflix决定在哪个数据中心存储他们的电影，或者Google Drive优化存储用户数据的位置，使用更复杂的策略是有意义的，比如可能涉及到用机器学习来预测数据下一次被访问的时间。

最佳缓存

除了上述策略外，还有理论上的最优策略，被标记为OPTOPT或MINMIN，它确定对于给定的查询序列，应保留哪些块以最小化缓存未命中的总数。根据给定的查询序列，选择保留哪些块可以使得缓存未命中的次数最少（然而，在实际运用中，由于无法预知未来的所有查询序列，因此这种策略并不常用）。

可以使用一种名为Bélády算法的简单贪婪方法来进行这些决策：我们只需保留在未来最晚会被使用（latest-to-be-used）的块，通过反证法可以证明这样做总能得到最优解。这种方法的缺点是你必须提前得知所有的查询请求，或者可以预测未来的访问需求。

好消息是，从渐进复杂性的角度来看，使用哪种特定方法并不真正重要。Sleator和Tarjan在他们的研究中展示，在大多数情况下，流行的策略如LRULRU（最近最少使用）与OPTOPT（理论上最优的缓存算法，一般被用作其他缓存算法的性能对照基线）的性能只是相差一个常数因子（但这并不意味着在具体的系统设计中，这些策略的表现会完全一样，因为它们依然会受到具体问题规模、数据特性等因素的影响）。

定理：设LRUMLRU_M和OPTMOPT_M分别表示，在相同的MM内存大小条件下，遵循不同缓存替换策略（LRU和OPT）的计算机在执行相同算法时需要访问的“块”数。那么：

LRUM≤2⋅OPTM/2LRU_M≤2\cdot OPT_{M/2}

证明的主要思路是考虑最差的情况。对于LRU策略，最差的情况是循环出现MB\frac{M}{B}个不同的块：每一个块都是新的，因此LRU的缓存未命中率为100%。同时，OPTM/2OPT_{M/2}（M/2表示内存大小为原来一半）将能够缓存其中一半的块（但不会更多，因为它只有一半的内存）。因此，LRUMLRU_M需要获取的块的数量是OPTM/2OPT_{M/2}所需获取的块的数量的两倍，这基本上就是这个不等式所表达的，对于LRULRU来说，任何更好的结果只会弱化这个不等式。如下图所示，其中灰色块是被OPTOPT缓存，但LRULRU未缓存的：

这是一个非常令人宽慰的结果。尽管在特定情境下，不同的缓存替换策略（如LRULRU和OPTOPT）在性能上有所差别，但在渐进I/O复杂度（衡量随着输入数据规模增大，算法的I/O操作次数如何增长）这个层面上，这些策略的差异可以被忽略。这就意味着，当你在进行算法复杂度分析时，你可以选择使用LRULRU或者OPTOPT这样的策略（取决于那个对你来说更容易实现），分析的结果可以推广应用到其他任何合理的缓存替换策略。这大大简化了算法复杂度的分析过程，并且有助于设计更高效的系统。

缓存实现

在合理的时间内找到正确的块以进行淘汰并不总是一件简单的任务。尽管CPU缓存是在硬件级别实现（通常实现为LRU的一些变体），但更高层次的淘汰策略必须依赖软件来存储块的某些统计信息，并在其上维护数据结构以加快找到要被淘汰数据块的速度。

让我们思考一下实现一个LRU缓存所需要考虑的因素。假设我们正在存储一些中等大小的对象，例如我们要为一个数据库开发缓存，这里的查询命令和查询结果都是某种SQL语言的中等大小的字符串，因此我们结构的开销虽然小，但不能忽视。

首先，我们需要一个哈希表来查找数据本身。由于我们处理的是较大的可变长度字符串，因此可以使用查询命令的哈希作为key，使用堆上分配内存的字符串的指针作为值。

要实现LRU逻辑，最简单的方式是创建一个队列，当我们访问对象时，将当前时间和对象的ID/key推入队列，并存储上次访问每个对象的时间（不一定是时间戳，任何递增的计数器都可以）。

现在，当我们需要释放空间时，我们可以通过从队列的前面弹出元素来找到最近使用最少的对象。我们不能直接删除它们，因为它们被添加到队列后，可能会再次被访问。因此，我们需要检查将它们放入队列的时间是否与上次访问它们的时间相匹配，然后才能释放内存。

但这里还有一个问题，每次访问块时，我们都会向队列中添加一个条目，只有在缓存未命中时才会开始从前面弹出它们，直到成功释放内存，将新的块加到缓存中。这可能会导致队列溢出，为了缓解这种情况，我们可以在缓存命中时立即将其移动到队列的末尾，而不是无脑地添加条目。

为了实现这一点，我们需要利用双链表实现队列，并将指向队列中节点的指针存储在哈希表中。然后，当我们有缓存命中时，我们通过指针，可以在恒定时间内从链表中删除节点，并在队列的末尾添加一个新节点。这样，在任何时间点，队列中的节点数量都将与对象数量一样多，并且每个缓存项的内存开销将保证恒定。

作为练习，试着思考如何实现其他缓存策略。