你不可不知的几种Cache Block的替换算法

　    现在有很多的替算法，今天呢，就让课课家带领你一起来了解“Cache Block的替换算法”。认真看文章你一定会了解的。

      在处理器系统处于正常的运行状态时，各级Cache处于饱和状态。由于Cache的容量远小于主存储器，CacheMiss时有发生。一次CacheMiss不仅意味着处理器需要从主存储器中获取数据，而且需要将Cache的某一个Block替换出去。

　　不同的微架构使用了不同的CacheBlock替换算法，本篇仅关注采用Set-Associative方式的CacheBlock替换算法。在讲述这些替换算法之前，需要了解CacheBlock的状态。如图2‑4所示，在Tag阵列中，除了具有地址信息之外，还含有CacheBlock的状态信息。不同的Cache一致性策略使用的Cache状态信息并不相同，如IllinoisProtocol[32]协议使用的相关的状态信息，该协议也被称为MESI协议。

　　在MESI协议中，一个CacheBlock通常含有MESI这四个状态位，如果考虑多级Cache层次结构的存在，MESI这些状态位的表现形式更为复杂一些。在有些微架构中，CacheBlock中还含有一个L(Lock)位，当该位有效时，该Block不得被替换。L位的存在，可以方便地将微架构中的Cache模拟成为SRAM，供用户定制使用。使用这种方式需要慎重。

　　在很多情况下，定制使用后的Cache优化结果可能不如CPU自身的管理机制。有时一种优化手段可能会在局部中发挥巨大作用，可是应用到全局后有时不但不会加分，反而带来了相当大的系统惩罚。这并不是这些优化手段的问题，只是使用者需要知道更高层面的权衡与取舍。不谋万世者，不足谋一时；不谋全局者，不足谋一域。

　　在CacheBlock中，除了有MESIL这些状态位之外，还有一些特殊的状态位，这些状态位与CacheBlock的更换策略相关。微架构进行CacheBlock更换时需要根据这些状态位判断在同一个Set中CacheBlock的使用情况，之后选择合适的算法进行CacheBlock更换。常用的Replacement算法有MRU(MostRecentlyUsed)，FIFO，RR(RoundRobin)，Random，LRU(LeastRecentlyUsed)和PLRU(PseudoLRU)算法。

　　所有页面替换算法与Belady'sAlgorithm算法相比都不是最优的。Belady算法可以对将来进行无限制的预测，并以此决定替换未来最长时间内不使用的数据。这种理想情况被称作最优算法，Belady'sAlgorithm算法只有理论意义，因为精确预测一个CacheBlock在处理器系统中未来的存活时间没有实际的可操作性，这种算法并没有实用价值。这个算法是为不完美的缓存算法树立一个完美标准。

　　在以上可实现的不完美算法中，RR，FIFO和Random并没有考虑CacheBlock使用的历史信息。而Temporal和SpatialLocality需要依赖这些历史信息，这使得某些微架构没有选用这些算法，而使用LRU类算法，这不意味着RR，FIFO和Random没有优点。

　　理论和Benchmark结果[23][35][37]多次验证，在MissRatio的考核中，LRU类优于MRU，FIFO和RR类算法。这也并不意味着LRU是实现中较优的Cache替换算法。事实上，在很多场景下LRU算法的表现非常糟糕。考虑4-WaySet-Associative方式的Cache，在一个连续访问序列{a,b,c,d,e}命中到同一个Set时，CacheMissRatio非常高。

　　在这种场景下，LRU并不比RR，FIFO算法强出多少，甚至会明显弱于Random实现方式。事实上我们总能找到某个特定的场景证明LRU弱于RR，FIFO和上文中提及的任何一种简单的算法。我们也可以很容易地找到优于LRU实现的页面替换算法，诸如2Q，LRFU，LRU-K，Clock和Clock-Pro算法等。

　　这些算法在分布存储，web应用与文件系统中得到了广泛的应用。Cache与主存储器的访问差异，低于主存储器与外部存储器的访问差异。这使得针对主存储器的页面替换算法有更多的回旋空间，使得在狭义Cache中得到广泛应用的LRU/PLRU算法失去了用武之地。PLRU算法实现相对较为简单这个优点，在这些领域体现得并不明显，不足以掩饰其劣势。

　　LRU算法并没有利用访问次数这个重要信息，在处理FileScanning这种WeakLocality时力不从心。而且在循环访问比广义Cache稍大一些的数据对象时，MissRate较高[42]。LRU算法有几种派生实现方式，如LRFU和LRU-K。

　　LRFU算法是LRU和LFU(LeastFrequentlyUsed)，LFU算法的实现要点是优先替换访问次数最少的数据。LRU-K算法[38]记录页面的访问次数，K为最大值。首先从访问次数为1的页面中根据LRU算法进行替换操作，没有访问次数为1的页面则继续查找为2的页面直到K，当K等于1时，该算法与LRU等效，在实现中LRU-2算法较为常用。

　　LRU-K算法使用多个PriorityQueue，算法复杂度为O(log2N)[39]，而LRU，Front这类算法复杂度为O(1)，采用这种算法时的Overhead略大，多个Queue使用的空间相互独立，浪费的空间较多。2Q算法[39]的设计初衷是在保持LRU-2效果不变的前提下减少Overhead并合理地使用空间。2Q算法有两种实现方式，Simplified2Q和FullVersion。

　　Simplified2Q使用了A1和Am两个队列，其中A1使用FIFO算法，Am使用LRU算法进行替换操作。A1负责管理Cold数据，Am负责管理Hot数据，其中在A1的数据可以升级到Am，但是不能进行反向操作。

　　如果访问的数据p在Am中命中时将其放回Rear[1]；如果在A1中命中，将其移除并放入到Am中。如果p没有在A1或者Am中命中时，率先使用这些Queue中的空余空间，将其放入到A1的Rear；如果没有空余空间，则检查A1的容量是否超过Threshold参数，超过则从A1的Front移除旧数据，将p放入A1的Rear；如果没有超过则从Am的Front移除旧数据，将p放入A1的Rear。

　　在这种实现中，合理设置Threshold参数至关重要。这个参数过小还是过大，都无法合理平衡A1和Am的负载。这个参数在AccessPattern发生变化时很难确定，很难合理地使用这些空间。LRU-2算法存在同样的问题。这是FullVersion2Q算法要解决的问题。

　　FullVersion2Q将A1分解为A1in和A1out两个Queue，其中Kin为A1in的阈值，Kout为Aout的阈值。此外在A1in和A1out中不再保存数据，而是数据指针，使用这种方法Am可以使用所有Slot，在一定程度上解决了Adaptive的问题。

　　如果访问的数据x在Am中命中时将其放回Rear；如果在A1out命中，则需要为x申请数据缓冲，即reclaimfor(x)，之后将x放入Am的Rear；如果x在A1in中命中，不需要做任何操作；如果x没有在任何queue中命中，则reclaimfor(x)并将其放入A1in的Rear。

　　如果A1in，A1out或者Am具有空闲Slot，reclaimfor(x)优先使用这个Slot，否则在Am，Ain和Aout中查询。如果|Ain|大于Kin时，则首先从Ain的Front处移除identifiery，然后判断|Aout|是否大于Kout，如果大于则淘汰Aout的Front以容纳y，否则直接容纳y。如果Ain和Aout没有超过阈值，则淘汰Am的Front。

　　这些算法都基于LRU算法，而LRU算法通常使用LinkList方式实现，在访问命中时，数据从LinkList的Front取出后放回Rear，发生Replacement时，淘汰Front数据并将新数据放入Rear。这个过程并不复杂，但是遍历LinkList的时间依然不能忽略。

　　Clock算法可以有效减少这种遍历时间，而后出现的Clock-Pro算法的提出使FIFO类页面替换算法受到了更多的关注。传统的FIFO算法与LRU算法存在共同的缺点就是没有使用访问次数这个信息，不适于处理WeakLocality的AccessPattern。

　　SecondChance算法对传统的FIFO算法略微进行了修改，在一定程度上可以处理WeakLocality的AccessPattern。SecondChance算法多采用Queue方式实现，为Queue中每一个Entry设置一个ReferenceBit。访问命中时，将ReferenceBit设置为1。进行页面替换时查找Front指针，如果其ReferenceBit为1时，清除该Entry的ReferenceBit，并将其放入Rear后继续查找直到某个Entry的ReferenceBit为0后进行替换操作，并将新的数据放入Rear并清除ReferenceBit。

　　Clock算法是针对LRU算法开销较大的一种改进方式，在SecondChange算法的基础之上提出，属于FIFO类算法。Clock算法不需要从Front移除Entry再添加到Rear的操作，而采用CircularList方式实现，将SecondChange使用的Front和Rear合并为Hand指针即可。

　　这些算法各有优缺点，其存在的目的是为了迎接LIRS(LowInter-ReferenceRecencySet)[40]算法的横空出世。从纯算法的角度上看，LIRS根本上解决了LRU算法在FileScanning，Loop-LikeAccesses和AccesseswithDistinctFrequencies这类AccessPattern面前的不足，较为完美地解决了WeakLocality的数据访问。其算法效率为O(1)，其实现依然略为复杂，但在I/O存储领域，略微的计算复杂度在带来的巨大优势面前何足道哉。

　　在LIRS算法中使用了IRR(Inter-ReferenceRecency)和Recency这两个参数。其中IRR指一个页面最近两次的访问间隔；Recency指页面最近一次访问至当前时间内有多少页面曾经被访问过。在IRR和Recency参数中不包含重复的页面数，因为其他页面的重复对计算当前页面的优先权没有太多影响。IRR和Recency参数的计算示例如图2‑11所示。

　　其中页面1的最近一次访问间隔中，只有三个不重复的页面2，3和4，所以IRR为3；页面1最后一次访问至当前时间内有2个不重复的页面，所以Recency为2。我们考虑一个更加复杂的访问序列，并获得图2‑12所示的IRR和Recency参数。

　　这组访问序列为{A，D，B，C，B，A，D，A，E}，最后的结果是各个页面在第10拍时所获得的IRR和Recency参数。以页面D为例，最后一次访问是第7拍，Recency为2；第2~7中有3个不重复的页面，IRR为3。其中IRR参数为Infinite表示在指定的时间间隔之内，没有对该页面进行过两次访问，所以无法计算其IRR参数。LIRS算法首先替换IRR最大的页面，其中Infinite为最大值；当IRR相同时，替换Recency最大的页面。

　　IRR在一定程度上可以反映页面的访问频率，基于一个页面当前的IRR越大，将来的IRR会更大的思想；Recency参数相当与LRU。在进行替换时，IRR优先于Recency，从而降低了最近一次数据访问的优先级。有些数据虽然是最近访问的却不一定常用，可能在一次访问后很长时间不会再次使用。如果Recency优先于IRR，这些仅用一次的数据停留时间相对较长。

　　在一个随机访问序列中，并在一个相对较短的时间内精确计算出IRR和Recency参数并不容易。但是我们不需要精确计算IRR和Recency这两个参数。很多时候知道一个结果就已经足够了。在LIRS算法中比较IRR参数时，只要有一个是Infinite，就不需要比较其他结果。假如有多个infinite，比如C和D，此时我们需要进一步比较C和D的Recency，但是我们只需要关心CR>DR这个结果，并不关心C是4还是5。

　　LIRS算法的实现没有要求精确计算IRR和Recency参数，而是给出了一个基于LIRSStack的近似结果。LIRS算法根据IRR参数的不同，将页面分为LIR(LowIRR)和HIR(HighIRR)两类，并尽量使得LIR页面更多的在Cache中命中，并优先替换在Cache中的HIR页面。

　　LIRSStack包含一个LRUStack，LRUStack大小固定由Cache决定，存放Cache中的有效页面，在淘汰Cache中的有效页面时使用LRU算法，用以判断Recency的大小；包含一个LIRSStackS，其中保存Recency不超过RMAX[2]的LIR和HIR页面，其中HIR页面可能并不在Cache中，依然使用LRU算法，其长度可变，用于判断IRR的大小；包含一个队列Q维护在Cache中的HIR页面，以加快这类页面的索引速度，在需要Free页面时，首先淘汰这类页面。淘汰操作将会引发一系列连锁反应。我们以图2‑13为例进一步说明。

　　我们仅讨论图2‑13中Access5这种情况，此时StackS中存放页面{9，7，5，3，4，8}，Q中存放{9，7}。StackS的{9，7，3，4，8}在Cache中，{3，4，8}为LIR页面，{9，7，5}为HIR页面。其中Cache的大小为5，3个存放LIR页面，2个存放HIR页面。

       看完，对“Cache Block的替换算法”还有不了解的么？如果有随时可以提问，有不明白的也可以提问，课课家24小时在线帮你解答。