SSD和传统的磁盘相比,有着许多不同的特性,比如读写不对称性,异地更新,先擦除后写入等。当为闪存设计缓存策略时,我们应该充分考虑到这些特性,如果直接把针对磁盘设计的缓冲区管理算法应用到闪存上,并不能充分发挥算法的性能。
这篇文章主要介绍了目前学术界关于闪存缓冲区管理的一些算法设计。前面部分介绍的是传统的缓冲区管理算法,后面部分介绍的是基于闪存优化的缓冲区管理算法。
LRU-K 算法
出处:O’Neil E J. The LRU-K page replacement algorithm for database disk buffering[J]. Proc.acm Sigmod Intl Conf.on Management of Data, 1993, 22(2):297-306.
LRU-K 中的 K 代表最近使用的次数,因此 LRU 可以认为是 LRU-1。LRU-K 的主要目的是为了解决 LRU 算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过 K 次”。
相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。
- (1)数据第一次被访问,加入到访问历史列表;
- (2)如果数据在访问历史列表里后没有达到K次访问,则按照一定规则(FIFO,LRU)淘汰;
- (3)当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;
- (4)缓存数据队列中被再次访问后,重新排序;
- (5)需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。
LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。
(Refrence: http://www.cnblogs.com/-OYK/archive/2012/12/05/2803317.html)
2Q 算法
出处:Johnson T, Shasha D. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm[C]. International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc. 1994:439-450.
LRU 算法每次替换的时候都是替换掉最近最久未被使用的页面,但是如果新加入的页面是冷数据,那么就会驱逐一个相对热的数据而加入了一个冷数据,而且这个冷数据还会驻留在缓冲区很久才会被替换掉,很显然这不是最优的。2Q算法可以解决这个问题。
简化的2Q算法
2Q算法维护两个列表,一个是 Al,采用先进先出原则,对于第一次访问的页面都放入到 Al 中,如果 Al 中的页面再次被访问,那么它有可能是热数据,则把它移到 Am 队列中,Am 队列采用LRU算法来管理。
1 | if(p is on the Am queue){ |
因为 Al 队列大小的最大值的设置对性能有较大的影响,过大或者过小都不合适,所以对上面的算法进行了改善。
2Q Full Version
改进后的算法,把 Al 分为 Alin 和 Alout 两部分,Alout 中保存最近被驱逐页的引用。对于一个大小为B的缓冲区,被分为了 Am,Alin(最大Kin,最小1)和Alout(最大Kout)。这些参数设置成这样会更优:Kin 设置成页面数量的20%,Kout记录页面的引用的数量最大为缓冲区大小的50%。
1 | // If there is space, we give it to X. |
1 | On accessing a page X : |
2Q算法有两个缓存队列,一个是FIFO队列,一个是LRU队列。当数据第一次访问时,2Q算法将数据缓存在FIFO队列里面,当数据第二次被访问时,则将数据从FIFO队列移到LRU队列里面,两个队列各自按照自己的方法淘汰数据。
- (1)新访问的数据插入到FIFO队列;
- (2)如果数据在FIFO队列中一直没有被再次访问,则最终按照FIFO规则淘汰;
- (3)如果数据在FIFO队列中被再次访问,则将数据移到LRU队列头部;
- (4) 如果数据在LRU队列再次被访问,则将数据移到LRU队列头部;
- (5)LRU队列淘汰末尾的数据。
CFLRU 算法
出处:Park S Y, Jung D, Kang J U, et al. CFLRU: A replacement algorithm for flash memory[C]. International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES 2006, Seoul, Korea, October. 2006:234–241.
闪存的读写操作在响应时间和能耗方面都具有不对称性,Clean-First LRU (CFLRU) 替换算法将这些不对称性考虑进去了。CFLRU 算法将LRU列表分为工作区(working region)和 clean-first 区。每次发生替换时,优先从 clean-first 区域中选择一个干净的页被替换掉。这样的做法就是故意将一部分脏的页留在缓冲区中,减少把脏页刷新到闪存所带来的写操作的数量。当替换一个新的页的时候可以直接将这个页剔除掉而不需要刷新到闪存中。
如上图所示,工作区(working region)主要是保存最近被访问的页面,cleaning-first主要是保存将要被替换的候选页面。当缓冲区满了需要选取一个页面被替换时,会从 cleaning-first 区的尾部开始寻找第一个干净的页,将它替换掉,如果没有找到,那么久在 clean-first 区的尾部找一个脏的页将其替换掉。
clean-first 区的大小设置也是非常重要的,如果太大会造成缓冲区命中率过小,如果太小,会使大量的脏页被替换,从而带来更多的写操作。clean-first 区的大小可以一开始就根据经验值来指定,也可以在程序运行的时候来动态调整,这两种方式分别对应静态的CFLRU算法和动态的CFLRU算法。
2QW-Clock 算法
出处:He D, Wang F, Feng D, et al. 2QW-Clock: An Efficient SSD Buffer Management Algorithm[C]. IEEE, International Conference on High PERFORMANCE Computing. 2015:47-53.
2QW-Clock(Two Queue Weight-Clock)算法吸取了 2Q 算法的优点,并对读写页面分别赋予不同的权值以此来反映闪存读写速度的不对称性。
该算法对读写操作赋予了不同的权重,所以会避免想 CFLRU 算法一样使大量的只写一次的页面存在缓冲区中。(CFLRU 总是首先替换干净的页而忽略它们有可能在不久的将来还会被访问。)
同时,该算法还结合了 2Q 算法,所以有很好的冷热数据区分能力和扫描阻抗能力(scan resistant)。
在 2QW-Clock 算法中有两个队列:Alin 和 Alout,还有一个首尾相连的环形队列 AClock。 Alin 和 AClock 是在缓冲区中,Alout 并不在缓冲区中,只是保存页面的标识符。
当一个页面从 Alin 中被替换后,从缓冲区中剔除这个页面,并将它的标识符放入 Alout 中。当一个页面从 AClock 中被替换后,直接剔除这个页面。在 AClock 中,对读写页面给予不同的权重,权重从0到5。基于测试的结果,读操作的权重设为1,写操作的权重设为5能够使性能达到最佳。
当访问一个页面 x 的时候
1 | if(x is in A1in){ |
Make_Room_For(page x) 的实现
1 | if(there are free page slots){ |