page cache 替换策略

现有的page cache替换策略

Linux内核中文件Cache替换的具体过程如图3-1所示：刚刚分配的Cache项链入到inactive_list头部，并将其状态设置为active，当内存不够需要回收Cache时，系统首先从尾部开始反向扫描 active_list并将状态不是referenced的项链入到inactive_list的头部，然后系统反向扫描inactive_list，如果所扫描的项的处于合适的状态就回收该项，直到回收了足够数目的Cache项。其中Active_list的含义是热访问数据，及多次被访问的，inactive_list是冷访问数据，表示尚未被访问的。如果数据被访问了，Page会被打上一个Refrence标记，如果Page没有被访问过，则打上Unrefrence标记。

LRU算法根据数据的历史访问记录来进行淘汰数据，对于当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重，Cache命中率会大幅降低

reuse的算法

ARC算法（adaptive replacement cache）

基于recency和frequency建立两个LRU 链表分别保存recency block和 frequency block。
ARC算法中存在四个链表：LRU list ，LFU list，LRU Ghost链表（存储那些最近从最近最多使用链表中淘汰的页面信息（Ghost list for LRU）），LFU Ghost链表（存储那些最近从最近最频繁使用链表中淘汰的页面信息（Ghost list for LFU））。两个Ghost链表不储存数据（仅仅储存页面信息，比如offset，dev-id），举例介绍ARC算法的工作流程：

假设从磁盘上读取一个页面，并把它放入cache中。首先这个页面会放入LRU 链表中，接下来读取另外一个不同的页面。它也会被放入缓存，然后页面二就会被放入LRU 链表的最近最多使用的位置，当再读一次第一个页面时，这个页面在缓存中将会被移到LFU链表中。所有进入LFU链表中的页面都必须至少被访问两次。无论什么时候，一个已经在LFU链表中的页面被再次访问，它都会被放到LFU链表的开始位置（most frequently used），这样，那些真正被频繁访问的页面将永远呆在缓存中，不经常访问的页面会向链表尾部移动，最终被淘汰出去。

随着时间的推移，LRU，LFU两个链表不断的被填充，直到被填满。假设LRU链表已经满了，而此时有一个新的数据页被读入，LRU链表中，最近最少使用的页面将会被淘汰出去。这个页面的信息会被放进LRU Ghost链表中（仅含有页面信息，数据信息会被释放掉），随着更多的页面被淘汰，这个在LRU Ghost中的页面信息也会向Ghost链表尾部移动。在随后的一个时间点，这个被淘汰页面的信息也会到达链表尾部，LRU链表的下一次的淘汰过程发生之后，这个页面信息也会从LRU Ghost链表中移除，意味着就再也没有任何对它的引用了。如果该页面在被从LRU Ghost链表中移除之前，被再一次访问了，将会将会引起一次幽灵（phantom）命中，由于这个页面的数据已经从缓存中移除了，所以系统还是必须从后端存储媒介中再读一次，但是由于这个幽灵命中，系统知道，这是一个刚刚淘汰的页面，而不是第一次读取或者说很久之前读取的一个页面。ARC用这个信息来调整它自己，以适应当前的I/O模式（workload）。该种情况的出现说明LRU缓存太小了。在这种情况下，LRU链表的长度将会被增加一，显然，LFU链表的长度将会被减一。同样的机制适用于LFU链。

ARC算法的优点在于：利用这种行为，ARC算法使它自己自适应于工作负载。如果工作负载趋向于访问最近访问过的文件，将会有更多的命中发生在LRU Ghost链表中，也就是说这样会增加LRU的缓存空间。反过来一样，如果工作负载趋向于访问最近频繁访问的文件，更多的命中将会发生在LFU Ghost链表中，这样LFU的缓存空间将会增大。这种行为开启了一个灵活的特性：假设当处理log文件而读取了大量的文件，却需要每个文件一次时，一个LRU 缓存将会把所有的数据缓存住，这样也就把经常访问的数据也淘汰出去了。但是由于只需要访问这些文件一次，它们不会带来任何价值一旦它们填满了缓存。

FRD算法（frequency and reuse distance）

将数据分为四类，FS （Frequently accessed, short reuse distance）、FL （Frequently accessed, long reuse distance）、IS (Infrequently accessed, short reuse distance)和IL（Infrequently accessed, long reuse distance），并采用两层LRU设计思想，如下图所示：

FRD并不是像LIRS和ARC一样，将Filter Stack中再次命中的数据移到reuse distance stack上，而是history block 在reuse distance stack 中命中，才会将数据移到到reuse distance stack。因此，相对于前两种方法，FRD避免了infrequently accessed block 对reuse distance stack的pollution；同时，即使filter Stack 很小，也能够有效命中FL（前两种都无法做到）。