背景

在OSD端实现读写缓存以优化服务器性能，提升IO性能

任务

设计并实现数据缓存模块，包括缓存存储结构的设计，提供缓存刷新与替换机制及预读机制

设计

参考Linux内核使用基树构建读写混合缓存，整个缓存空间基于一个大的内存池，该内存池使用buddy算法进行管理，读缓存方面实现LIRS算法取代LRU算法以提高缓存命中率，写缓存方面使用异步写回策略（做IO聚合），一定时间需要进行赃页回收以给读缓存热区预留空间。

关于LIRS，主要是LRU算法存在以下问题：

1, 顺序扫描。顺序扫描的情况下LRU没有命中情况，而且会淘汰其它将要被访问的item从而污染cache。

2, 循环的数据集大于缓存大小。如果循环访问且数据集大于缓存大小，那么没有命中情况。

LIRS将数据分为两部分：LIR热区和HIR冷区，第一级是HIR，第二级是LIR，数据先进入到第一级，当数据在较短的时间内被访问两次时成为热点数据则进入LIR，HIR和LIR内部都采用LRU策略。这样，LIR中的数据比较稳定，解决了LRU的上述两个问题。除Recency外引入与locality相关的的IRR概念，即使用最近两次访问之间其他唯一块的数目。该数目体现了再次出现的可能性（越大越不可能再次出现）使用该概念后的LIRS最有可能将最新的访问缓存起来并在下次访问剔除，但是依旧使用recency进行缓存内的调整。

在设计时使用一个栈来剔除recency较大且HIR的块以方便考察（在栈中的HIR块才可能变为LIR块，相应在栈中Recency最大的LIR块被出栈并转化为HIR块，注意这些转化并未导致被剔除出缓存，被剔除缓存的一定是HIR块而无论其是否在栈中）工程实现时无论是栈还是队列都使用list将块链起来实现即可，mysql ndb也是这么干的。每次决定是否将一个HIR块加入到LIR的时候都需要往栈里扫描一遍，这个时间开销是O(c)

优化、难点

读写混合缓存与LIRS算法的冲突的问题采用回收线程定期回收赃页进行改善。多线程并发时有时使用读写锁效率不如互斥锁，原因在前文已述，且多线程调试充满困难。malloc在小文件频繁申请上损耗较多，所以采用内存池解决。

关键点：内存空间管理，多线程同步，缓存替换算法，异步写回