闲话缓存：算法

从前面的文章中，我们已经了解到了缓存设计的目标，缓存设计应该考虑的因素。今天我们来看看一系列缓存算法以及它们如何去解决问题的。同时，我们也会涉及到各种缓存算法的优缺点。

这里我并不想讨论与预取（pre-fetch）相关的算法，主要是考虑各种淘汰算法。因为相比于预取算法，淘汰算法具有更大的通用性，对缓存好坏影响更大。

1.      时间（完全从最近使用的时间角度考虑）

a.      LRU（least recently used）：这种策略就是永远替换掉最近最少使用的缓存单元。它是最古老，应用最广泛的的一种淘汰算法。它的致命的缺陷就是没有考虑缓存单元的使用频率，在某些I/O 模式中，会把一些有价值的缓存单元替换出去。比如，假设我们有10个缓存单元，客户端应用来了一次顺序读写，这样可能把这10个现有的缓存单元替换出去，而把这次顺序读写的数据缓存起来。但是，这种顺序读写的数据在以后都不会被再次用到。反而，那些因为顺序读而被替换出去的缓存单元却是更有价值的。为此，有了各种各样的基于LRU的优化策略被提出来。

2.      频率（完全从使用频率的角度考虑）

a.      LFU（least frequently used）: IRM(独立的引用模型)提供了一种用来获取频率的负载特性。它趋向于淘汰最近使用频率最少的缓存单元。这种策略的弊端是：

                                                  i.      它的实现复杂度于缓存大小成对数关系（logarithmic）;

                                                ii.      对最近的缓存单元的访问情况基本没考虑；

                                              iii.      对访问模式的改变基本上没有应变的策略。

3.      LRU-2（LRU-K）：一种对LRU的改进型策略 （频率）

a.      LRU-2于LFU很相似，如果我们不考虑它对缓存单元引用频率进化分布的自适应性。它的基本思想是对每一个缓存单元，记住最近两次访问的时间。总是淘汰最近两次时间间隔最长的缓存单元。在IRM的假设下，对于任何知道最多两次最近引用缓存单元的在线算法，我们可以得出LRU-2具有最高的命中率。

b.      但是LRU-2也有一些实际的限制：

                                                  i.      它需要维护一个优先级队列。也就是说它具有对数的实现复杂度；

                                                ii.      它需要一个可调参数：CIP（correlated information period）。

c.       在现实中，对数的实现复杂度是一个非常严重的overhead（负担）。所以另外一个策略2Q被提了出来。

4.      2Q：对LRU-2的改进策略 （频率）

a.      相对于LRU-2，2Q的主要改进是用一个简单的LRU list取代了LRU-2中的优先级队列。其它的2Q和LRU-2基本相同。

b.      但是在2Q中，LRU-2的第二个不足还是存在，并且更严重了。因为它需要两个可调参数：K_in和K_out。

c.       为什么可调参数一个很严重的限制？这是我们在实施一个系统时，必须确定这些参数，而且不可更改。一旦确定了一组参数，这个缓存系统往往只能对某一类workload表现很好。也就是这种缓存系统缺少了自适应性。

5.      LIRS（Low Inter-reference Recency Set）（频率）

a.      详细描述参考：“LIRS： An efficient low inter-reference recency set replacement policy to improve buffer cache performance”

b.      第一个不足在于需要两个可调参数L_lirs 和L_hirs ；

c.       它的第二个缺点在于，在最坏的情况下，它需要一个“栈修剪”。这个操作需要遍历数量庞大的缓存单元。

6.      时间和频率（同时考虑时间和频率的算法：LRU和LFU）

a.      FBR（Frequency-based replacement）:详细描述请参考“Data cache management using frequency-based replacement”。这个算法的不足之处在于：

                                                  i.      需要可调参数：缓存中三块的大小，C_max 和A_max：大小调整的时间周期。

                                                ii.      Cache pollution（解决cache污染的机制）

b.      LRFU（Least Recently/Frequently Used）: 参考“LRFU： A spectrum of policies that subsumes the least recently used and least frequently used policies”

c.       ALRFU(adaptive LRFU): 参考“On the existence of a spectrum of policies that subsumes the least recently used and least frequently used policies”

7.      临时距离分布（Temporal distance distribution）

a.      MQ(multi-queue replacement policy MQ ): 参考“The multi-queue replacement algorithm for second level buffer caches”

8.      ARC: adaptive replacement cache(IBM), adjusted replacement cache(ZFS)

a.      一种自适应，低成本的淘汰算法

b.      它集合了LRU和LFU的优点，并且没有额外的使用和实现成本。

c.       它可以更具workload的改变而自动的改变淘汰策略。

ARC是目前应用非常广泛的一种淘汰算法。我们应该详细的研究它，并实现它。在ZFS源码中就是它的完整实现。当然，ZFS中的实现和IBM当初提出的内容有点改变。这个我们留在下篇文章中讲述。