Chinaunix首页 | 论坛 | 博客
  • 博客访问: 361015
  • 博文数量: 38
  • 博客积分: 256
  • 博客等级: 入伍新兵
  • 技术积分: 846
  • 用 户 组: 普通用户
  • 注册时间: 2012-12-14 23:21
文章分类

全部博文(38)

文章存档

2015年(1)

2014年(1)

2013年(28)

2012年(8)

我的朋友

分类: 云计算

2013-08-06 15:02:31

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

这里我并不想讨论与预取(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的第二个不足还是存在,并且更严重了。因为它需要两个可调参数:Kin和Kout

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.      第一个不足在于需要两个可调参数Llirs 和Lhirs

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

6.      时间和频率(同时考虑时间和频率的算法:LRU和LFU)

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

                                                  i.      需要可调参数:缓存中三块的大小,Cmax 和Amax:大小调整的时间周期。

                                                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当初提出的内容有点改变。这个我们留在下篇文章中讲述。

阅读(7343) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

Bean_lee2013-08-06 21:25:44

好文章啊,期待展开详细分析