一种基于闪存的低能耗缓冲区管理算法

汤 显，周军锋（1.燕山大学经济与管理学院，河北秦皇岛066004；.燕山大学信息科学与工程学院，河北秦皇岛066004）

一种基于闪存的低能耗缓冲区管理算法

汤 显1，∗，周军锋2
（1.燕山大学经济与管理学院，河北秦皇岛066004；2.燕山大学信息科学与工程学院，河北秦皇岛066004）

摘 要：闪存以其低能耗、低延迟、小巧轻便及高抗震性等特点广泛应用于不同环境中以消除磁盘机械寻址所带来的高能耗及高延迟等问题。提出一种基于闪存硬盘（SSD）的低能耗缓冲区置换算法AFC。当需要选择置换页时，AFC使用基于代价的启发式来选择置换页。AFC的设计目标是基于用户设定的权值，在最小化能耗和最大化吞吐量之间取得平衡。对不同型号的闪存芯片进行了实验验证，实验结果表明，基于AFC来管理缓冲区数据时，可以显著降低系统的能耗。

关键词：闪存；能耗；缓冲区；置换策略

0　引言

绿色计算是最近一段时间大家关注的热点，对于计算机系统来说，基于磁盘的存储子系统需要消耗大约40%的电量［1］，降低存储子系统的耗电量可有效降低系统的总能耗。

和磁盘相比，闪存是一种低能耗的纯电子产品，符合绿色计算的初衷和目标。目前各种应用中基于闪存存储设备的表现形式是闪存硬盘SSD，SSD提供与磁盘同样的存取接口。由于SSD随机读写操作在耗时和耗能方面表现不一致，且不同型号SSD的不一致性存在较大的差异，在一些对性能或者能耗要求苛刻的应用场合，需要充分考虑闪存读写速度不一致、低能耗的特点来设计合适的数据结构和算法，以便在降低能耗的同时提升系统性能。

缓冲区是计算机系统的基本组成部分之一。由于容量有限，缓冲区置换算法的有效性严重影响计算机系统的整体性能。文献［2］在三十多年前已经意识到数据页在缓冲区中的读写状态会影响置换策略的有效性。对于闪存而言，读写延迟和能耗存在不对称性问题，数据页的读写状态对系统性能的影响更严重。然而现有的基于闪存的缓冲区置换策略［3⁃7］没有考虑能耗问题。已有方法考虑的都是单位时间最大化系统吞吐量的问题，由于不同类型的闪存的读写延迟和所需能耗之间不符合正比关系，因而单位时间最大化系统吞吐量可能需要耗费更多的电量。

针对现有缓冲区置换算法存在的问题，本文提出一种基于闪存的低能耗自适应缓冲区管理算法AFC。AFC的设计目标是基于用户设定的权值，在最小化能耗和最大化吞吐量之间取得平衡。AFC通过减少读写操作的能耗来降低系统耗电量，这和已有的磁盘休眠调度算法及用SSD取代磁盘并不矛盾，且具有互补性。

1　背景及相关工作

基于磁盘的缓冲区置换策略［8⁃15］的基本假设是每次置换操作的代价相同。由于闪存的读写代价不一致，当设计基于闪存的缓冲区管理算法时，以上假设不再成立。

数据页置换的目的是最小化请求序列的总代价。文献［16］提出了最优离线算法并通过最小代价最大流问题［17］进行求解。对于在线算法来说，未来的请求序列是未知的。FAB［4］方法将数据页组织成不同的物理块，不同物理块用一个块层LRU链表来组织。BPLRU［5］和FAB的区别在于将随机写变成顺序写来提高写操作的效率。

假设闪存的写代价远远大于读代价，CFLRU［3］用LRU链表来组织数据页，如图1所示。LRU链表分成工作区（Working Region）和置换区（Clean⁃First Region）两个部分。数据页未命中时，CFLRU从置换区中选择最近最少使用的只读页进行置换，如图1的p6。当置换区中没有只读页时，CFLRU选择链表尾部的修改页进行置换。

图1　CFLRU置换策略示意图Fig.1　Illustration of the CFLRU replacement strategy

文献［6］根据置换区中数据页的修改状态，将将置换区中的数据页组织为不同的队列。CFDC［7］通过将数据页进行重新组织来提升系统性能，如图2所示。注意CFDC中块的大小并非固定的。

图2　CFDC置换策略示意图Fig.2　Illustration of the CFDC replacement strategy

尽管文献［18］提出了可以避免多线程环境下锁争用问题的算法，但其对于循环和序列的检测却由于多线程的存在而降低准确性；同时，该方法没有从能耗的角度来考虑如何基于单位能耗最大化系统吞吐量。

文献［19］基于日志的特点，提出相应的缓冲区数据页置换算法。文献［20］对绿色计算所涉及到的问题进行了综述。文献［21］综述了大数据存储的相关问题，并讨论了闪存在其中的作用。

2　AFC算法

2.1数据结构

和文献［18］类似，AFC将缓冲区中的数据页根据其读写状态组织为两个环形数据结构CC和DC，分别维护只读页和修改页，如图3所示。假定缓冲区的容量是s，则｜CC∪DC｜＝s∧CC∩DC＝Ø。AFC维护了一个全局计数器Counter，每当发生一次数据页请求，Counter值加1。对于缓冲区中的每个数据页p，AFC为其关联3个变量：T、C和I，其中T表示p进入缓冲区的时间（当时的Counter值），否则为最近一次被命中的时间）；C是p的访问位计数器，表示p被访问的频繁程度；I表示p最近两次被命中之间对其他数据页访问的次数，称为命中距离［18］。

图3　AFC置换策略Fig.3　The AFC replacement strategy

如图3所示，虚线环用于处理循环模式的数据页访问，称为子环，CC和DC中的子环分别用SCCC和SCDC表示。虽然AFC和FClock［18］的数据结构基本一致，二者的主要区别体现在对数据页的操作策略上，具体来说体现在以下几点：1）对于循环和序列模式数据页的侦测和处理方式上；2）数据页的代价计算方式；3）置换页的选择策略。本文所用符号的意义如表1所示。

2.2基于代价的置换页选择策略

如果缓冲区满且当前请求的数据页p不在缓冲区中，AFC根据“代价”从CC或DC中选择一个数据页进行置换，并从SSD读入数据页p。对于AFC来说，CC和DC的大小用公式（1）来计算，其意义可阐述为：大小和付出成正比，这里的付出指过去一段时间内由于数据页缺失所付出的外存存取代价。假设缓冲区最多可放s个数据页，AFC置换策略可表述为：若｜CC｜＜βs，则DC过大，那么从DC中选择一个数据页进行置换；反之从CC中选择一个数据页进行置换。本文中过去一段时间指过去s次访问，CC的代价记为CCC，DC的代价记为CDC。

β＝CCC/（CCC＋CDC）（1）

为了计算式（1）中的代价值，需要知道对于CC和DC中的每个数据页而言，以什么作为其代价值。为了综合考虑置换延迟和能量消耗，本文提出使用CR和CW作为每个未修改页和修改页的加权值来表示数据页的置换代价，ER和EW表示读和写一个数据页所需的能耗，其计算方法为

显然，当x＝1时，本文提出的代价计算方法仅考虑操作延迟、不考虑能耗，这和FClock相同；当x＝0时，本文提出的代价计算方法仅考虑能耗、不考虑操作延迟；其它情况可根据用户和实际系统的需求在能耗和操作延迟之间选择合理的搭配比例。

基于式（2）和（3），笔者使用式（4）和（5）来计算式（1）中CCC和CDC的值。其中s/n表示数据页被命中的概率，相应的没有命中的概率是（1－s/n）。式（4）和（5）同时考虑了逻辑操作和物理操作。

上述内容仅仅解决了当所请求的数据页不在缓冲区中时，从CC还是DC中选择置换页的问题。当确定了置换页的出处后，下一步的工作是选择哪个数据页进行置换的问题。

已有方法在选择置换页时，都是选择访问位计数器的值等于0的数据页予以置换，这种方法没有充分考虑循环和序列访问模式的影响，或者说对循环和序列访问模式的侦测方式不够好。FClock通过检查连续未命中数据页的个数来判断是否为循环和序列访问模式，这种方式的最大问题在于判断不够准确。考虑以下两种情况：1）在多线程环境下，前面的线程已经提前读取了10号数据页，当后续线程需要循环读取1～20号数据页时，由于10号数据页已经在缓冲区中，因此，FClock无法判定1～20号数据页是一个循环或者完整序列；2）当连续未命中的数据页个数超过指定的阈值后，FClock会将后续未命中的数据页放入子环中。除非当前数据页属于某个循环序列访问模式，否则保留子环中的数据页都是对缓冲区中有效空间的浪费，不幸的是，FClock无法区分循环和序列访问模式。

针对以上问题，本文的置换页选择策略如算法1所示。第1行根据CC和DC的代价比值确定置换页来自哪里。第2～9行确定选择DC中的哪个数据页进行置换。如果当前处理的数据页属于一个序列中（第3行），该序列是一个循环序列（第4行）且DC中该序列的长度大于预先指定的阈值（第5行，λ｜DC｜＜DC.F，DC.F表示当前序列的长度），这时选择SCDC中的当前页进行置换，即使用MRU策略（第6行）。如果第5行的条件不满足，则说明当前处理的是循环序列且该循环序列的长度仅有一小部分在缓冲区中，则处理策略是选择DC中的一个数据页进行置换（第7行）。如果第4行的条件不满足，说明当前处理的是顺序存取序列，则可以直接依照MRU策略扔掉当前数据页（第8行）。如果第3行的条件不满足，说明当前处理的数据页不是序列中的一个数据页，则依照优先置换最不频繁使用的数据页的原则，优先置换第一个访问位计数器的值等于0的数据页（第9行）。对于CC中数据页的处理类似，这里不再赘述。需要注意的是这里序列的检测方法是地址连续且访问连续的数据页个数大于预先设定的阈值即可，和在访问这些数据页的过程中是否有命中没有关系。对于循环访问序列的检测，可以通过维护一个哈希表结合LRU链表来记录过去一段时间的访问序列即可。当一个序列中的数据页被连续访问，且出现在哈希表中的概率较大（可以指定一个阈值），即可认为被访问的数据页是循环序列中的数据页。所有以上操作均可在O（1）代价的基础上完成。具体的操作方法和数据页访问位修改策略见文献［18］中的描述。

2.3AFC置换策略

AFC数据页置换算法的基本思想可以表述为：如果缓冲区未满且请求页p没有命中，则根据对p的读写类型从闪存硬盘上读取数据页并将其放入CC或者DC中，然后更新平均命中距离。如果p命中，则在CC或者DC将相应的逻辑操作次数加1，并将命中距离置0。如果对p的操作类型是写且p∈CC，则将p从CC移动到DC中。同时，如果p的命中距离大于等于平均命中距离，则p的访问计数加1，最后更新平均命中距离的值。具体的更新方法和［18］相同，本文不再赘述。

如果缓冲区已满且p命中时，其操作和前面一段所介绍的方法相同。如果p没有命中，则从CC或者DC中选择一个数据页进行置换，具体的选择方法见算法1，其基本思想和计算方法已在2Ʊ 2小节进行了说明。然后根据p的操作类型从闪存硬盘读入p并将其放入缓冲区中，最后更新平均命中距离的值。对于循环序列，则直接插入子环中，否则插入CC或者DC中，之后进一步修改序列标识即可。

3　实验

3.1实验环境

本文的实验目的为：在考虑能耗的情况下，本文方法针对不同SSD的有效性。对于不考虑能耗的情况，感兴趣的读者可以参考文献［18］获取详细实验结果。用于测试的SSD型号为三星MCAQE32G5APP（用FD1表示）。FD1的随机读写的延迟比率是1∶118，能耗比是1∶9。

对SSD来说，如文献［18］所述，缓冲区置换算法的性能受物理读写次数的影响，然而FTL层的实现是设备相关的，由硬盘制造商提供，并没有为用户提供跟踪读写次数的接口。因此，和文献［18］类似，本文使用模拟器［22］来进行测试。实验了6种置换策略进行比较，即：LRU、CLOCK［9］、CFLRU［3］、CFDC［7］、FClock［18］及本文提出的AFC。所有的置换策略都用Visual C＋＋实现的。这里将CFLRU算法中“置换区”的“窗口大小”设为缓冲区大小的75%，将CFDC的“置换区”的“窗口大小”设为缓冲区的50%，将CFDC的“聚类大小”设为64。参数取自对应文献实验中所采用的数值。

将数据库的文件大小模拟为64 MB，相当于32 000个的物理页，每页为2 KB。缓冲区的大小范围从2 000个页到8 000个页。本文实验中，模拟器假定数据页的大小是2 KB，每个数据块包含64个数据页。

生成了4种类型的测试数据，其统计数据如表2所示，其中“读/写比率”列中的“x%/y%”表示对某种测试数据来说，所有请求的x%为读操作、y%为写操作；“局部性”列中的“x%/y%”表示对某种测试数据来说，在y%的页上有x%的操作。

表1中读写代价Cr和Cw可以通过SSD的技术手册得到，或者通过执行一定量的读写操作后取平均值来获得。本文实验所用数据来自于技术手册。

笔者选择以下标准来评价缓冲区置换策略：1）运行时间；2）能耗比，指不同闪存执行相同操作耗费的电量的比值。

3.2性能比较和分析

下面分为3种情况比较不同方法的能耗：1）x ＝1，即最大化单位时间吞吐量为目标；2）x＝0.5，即部分考虑能耗的情况；3）x＝0，即最大化单位能耗吞吐量为目标。3种情况对应的算法名字分别是AFC1、AFC2和AFC3。

图4展示了不同方法在FD1上运行T1到T4后得到的运行时间和能耗比，其中子图（a）、（c）、（e）、（g）展示不同方法的运行时间，与之对应的4个子图（b）、（d）、（f）、（h）展示不同方法的能耗比。

从图4可以看出，由于已有方法没有考虑能耗，因而其运行时间和x值的变化无关。与之对应，随着式（2）和（3）中x值的变化，发生变化的是AFC1、AFC2和AFC3。从图4的（a）、（c）、（e）、（g）可以看出，在没有考虑能耗时，AFC1因其可以更好的处理循环和序列访问模式而取得了最好的性能结果；而当更多的考虑能耗时，即从单位时间最大化吞吐量向单位能耗最大化吞吐量时，AFC3的性能出现了一定程度的下降。结合图4的（b）、（d）、（f）、（h）可以看出，AFC3尽管在单位时间吞吐量方面不如AFC1，但对于相同的任务，AFC3所需的能耗是最小的，原因在于对于AFC3而言，式（2）和（3）中的x＝0，即AFC3的目标是单位能耗吞吐量的最大化。总的来看，由于可以较好的处理循环和序列访问模式，AFC算法无论从单位时间还是单位能耗的角度来说，和已有方法相比，均可以做的更好。

图4　不同方法在FD1上运行T1～T4时的运行时间和能耗比Fig.4　Comparison of the running time and power consumption of different algorithms

4　结束语

针对闪存的读写操作所需能耗不同且不同类型闪存的读写能耗比差别大的问题，本文提出一种基于闪存硬盘（SSD）的低能耗缓冲区管理算法AFC。当需要选择置换页时，AFC使用基于代价的启发式来选择置换页。AFC的设计目标是基于用户设定的权值，在最小化能耗和最大化吞吐量之间取得平衡。实验结果验证了AFC算法的有效性。

参考文献

［1］Roberts D Kgil T Mudge T N.Using non⁃volatile memory to save energy in servers C //Proceedings of the 2009 International Con⁃ference on Design Automation and Test in Europe Nice France 2009 743⁃748.

［2］Effelsberg W Haerder T.Principles of database buffer management J .ACM Transactions on Database Systems 1984 9 4 560⁃595.

［3］Park S Y Jung D Kang J U et al.CFLRU a replacement algorithm for flash memory C //Proceedings of the 2006 International Con⁃ference on Compilers Architecture and Synthesis for Embedded Systems Seoul Korea 2006 234⁃241.

［4］Jo H Kang J U Park S Y et al.FAB flashaware buffer management policy for portable media players J .IEEE Transactions on Consumer Electronics 2006 52 2 485⁃493.

［5］Kim H Ahn S.BPLRU a buffer management scheme for improving random writes in flash storage C //Proceedings of the 6th USE⁃NIX Conference on File and Storage Technologies San Jose Cali⁃fornia USA 2008 239⁃252.

［6］Koltsidas I Viglas S.Flashing up the storage layer J .Proceedings of the VLDB Endowment Auckland New Zealand 2008 1 1 514⁃525.

［7］Ou Y Haerder T Jin P.CFDC a flash⁃aware replacement policy for database buffer management C //The 5th International Workshop on Data Management on New Hardware DaMoN＇09 Providence Rhode Island USA 2009 15⁃20.

［8］Robinson J Devarakonda M V.Data cache management using fre⁃quency⁃based replacement C //Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Com⁃puter Systems University of Colorado Boulder Colorado USA 1990 134⁃142.

［9］Babaoglu O Joy W.Converting a swap⁃based system to do paging in an architecture lacking page⁃reference bits J .ACM SIGOPS Op⁃erating Systems Review 1981 15 5 78⁃86.

［10］Robinson J T Devarakonda M V.Data cache management using frequency⁃based replacement C //Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Com⁃puter Systems Boulder Colorado USA 1990 134⁃142.

［11］OƷ Neil E J OƷ Neil P E Weikum G.The lru⁃k page replacement algorithm for database disk buffering C //Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data Washington USA 1993 297⁃306.

［12］Johnson T Shasha D.2q A low overhead high performance buffer management replacement algorithm C //Proceedings of the 20th International Conference on Very Large Data Bases Santiago de Chile Chile 1994 439⁃450.

［13］Jiang S Zhang X.Making lru friendly to weak locality workloads A novel replacement algorithmto improve buffer cache performance J .IEEE Transactions on Computers 2005 54 8 939⁃952.

［14］Megiddo N Modha D S.Arc A self⁃tuning low overhead replace⁃ment cache C //Proceedings of the FAST′03 Conference on File and Storage Technologies San Francisco California USA 2003 115⁃130.

［15］Lee D Choi J Kim J H et al.LRFU a spectrum of policies that subsumes the least recently used and least frequently used policies J .IEEE Transactions on Computers 2001 50 12 1352⁃1361.

［16］Chrobak M Karloff H J Payne T H et al.New results on server problems J .SIAM Journal on Discrete Mathematics 1991 4 2 172⁃181.

［17］Cormen T H Leiserson C E Rivest R L et al.Introduction to Al⁃gorithms M .USA The MIT Press 2001.

［18］汤显 孟小峰.FClock 一种面向SSD的自适应缓冲区管理算法 J .计算机学报 2010 33 8 1460⁃1471.

［19］卢科 金培权 岳丽华.一种针对块内日志存储模型的缓冲区管理方法 J .小型微型计算机系统 2013 34 5 1021⁃1027.

［20］金培权 邢宝平 金勇 等.能耗感知的绿色数据库研究综述J .计算机应用 2014 34 1 46⁃53.

［21］金培权 郝行军 岳丽华.面向新型存储的大数据存储架构与核心算法综述 J .计算机科学与工程 2013 35 10 12⁃24.

［22］Jin P Su X Li Z.A flexible simulation environment for flashaware algorithms C //Proceedings of the 18th ACM Confer⁃ence on Information and Knowledge Management Hong Kong China 2009 2093⁃2094.

A flash⁃based buffer replacement algorithm towards low power consumption

TANG Xian1ZHOU Jun⁃feng2
1.School of Economics and Management Yanshan University Qinhuangdao Hebei 066004 China 2.School of Information Science and Engineering Yanshan University Qinhuangdao Hebei 066004 China

AbstractAs an important alternative to conventional magnetic disks flash⁃based devices which have the features of lower power consumption no mechanical parts portable and shock resistance are used extensively in different environments to reduce the power consumption and long time of mechanical addressing for conventional magnetic disks.An adaptive flash⁃aware buffer replacement al⁃gorithm namely AFC is proposed based on flash chip based hard disk namely Solid⁃State Disk SSD .AFC adopts cost⁃based heu⁃ristics to select victim pages for replacement.The aim of AFC is to leverage between maximum performance and minimum power consumption.The experimental results show that AFC significantly reduces power consumption based on different flash chips.

Key wordsflash power consumption buffer replacement strategy

作者简介：∗汤显（1978⁃），女，山东荣成人，博士，讲师，主要研究方向为闪存数据库，Email：txianz＠gmail.com。

基金项目：国家自然科学基金资助项目（61303040，61472339）

收稿日期：2015⁃03⁃16

文章编号：1007⁃791X（2015）03⁃0269⁃07

DOI：10.3969/j.issn.1007⁃791X.2015.03.011

文献标识码：A

中图分类号：TP391