Please wait a minute...
浙江大学学报(工学版)
J4  2010, Vol. 44 Issue (12): 2257-2262    DOI: 10.3785/j.issn.1008-973X.2010.12.005
自动化技术、计算机技术     
PWLRU: 一种面向闪存数据库的缓冲区存取算法
寿黎但, 廖定柏, 徐昶, 陈刚
浙江大学 计算机科学与技术学院,浙江 杭州 310027
PWLRU: a buffer replacement algorithm for flash-based Database
SHOU Li-dan, LIAO Ding-bai, XU Chang, CHEN Gang
College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
 全文: PDF  HTML
摘要：

针对现有缓冲区替换算法无法充分发挥闪存数据库性能的不足,研究了缓冲区存取方法.根据数据库OLTP应用中IO行为的特点以及闪存的物理特性,提出一种新的缓冲区存取算法——基于页面权重的最近最少使用替换(PWLRU).PWLRU首先对缓冲区内的页面设定权重,在扫描与修改某页面时对权重进行调节,并优先替换权重为零的页面.实验选用基于MYSQL的TPCC测试标准作为模拟仿真环境,实验结果证明：PWLRU不仅能保证缓存命中率不低于经典的最近最少使用替换算法(LRU),而且在闪存上的IO平均读取代价和能耗均优于LRU和之前面向嵌入式闪存环境提出的先清除最近最少使用替换算法(CFLRU),是一种特别适合闪存数据库的缓冲区存取算法.
Abstract:

Studied the buffer page replacement methods on flashbased database, in order to address the performance inadequacy of the current methods therein. Proposed a new buffer page replacement algorithm named page-weight-least-recent-used (PWLRU), based on the characteristic analysis of the I/O and the flash media in OLTP application. PWLRU algorithm set sdefault reserved weight for each page in the buffer, and adjusts the weight when the corresponding page is scanned or modified, furthermore, the page with weight zero will be evicted from the buffer. The simulation conducted on the TPC-C benchmark and MYSQL database indicated that PWLRU are more efficient on both energy costs and I/O performance than the traditional least-recent-used (LRU) and clean-first-least-recent-used (CFLRU), which is tailored for the embedded flash environment. Therefore, PWLRU algorithm is suitable for page replacement in flash-based database management system
出版日期: 2010-12-01
:  TP 393.08  
基金资助:

国家自然科学基金资助项目(60803003，60603044)；浙江省科技计划资助项目(2008c141060).
作者简介: 寿黎但（1974—），男，浙江萧山人，副教授.从事数据库技术研究.E-mail: should@cs.zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

寿黎但, 廖定柏, 徐昶, 陈刚. PWLRU: 一种面向闪存数据库的缓冲区存取算法[J]. J4, 2010, 44(12): 2257-2262.

SHOU Li-dan, LIAO Ding-bai, XU Chang, CHEN Gang. PWLRU: a buffer replacement algorithm for flash-based Database. J4, 2010, 44(12): 2257-2262.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2010.12.005    或    http://www.zjujournals.com/eng/CN/Y2010/V44/I12/2257

［1］ RAMON C, FRED D, KAL L, et al. Operating system implications of solidstate mobile computers［C］∥ Proceedings of the 4th IEEE Workshop on Workstation Operating Systems Napa. CA, USA: IEEE, 1993: 21-27.
［2］ Samsung semiconductor corporation ［EB/OL］. ［2009-10-05］.  http:∥www.samsung.com/Products/Semiconductor/Flash.
［3］ Sina technology［EB/OL］. ［2008-08-19］. http:∥tech.sina.com.cn/i/2008-08-19/14402400711.shtml.
［4］ CHIANG M L, LEE P C, CHANG R C. Using data clustering to improve cleaning performance for plash memory［J］ Software: Practice and Experience, 1999, 29(3): 267-290.

［5］ MAREK C, JOHN N. LRU is better than FIFO［C］∥ Proceedings 9th Annual ACMSIAM Symp on Discrete Algorithms. San Francisco, California, United States: ACM, 1998: 78-81.
［6］ PARK S Y, JUNG D, KANG J U, et al. CFLRU: a replacement algorithm for flash memory［C］∥ Proceedings of the 2006 International Conference on Compilers, Architecture. Seoul, Korea: ACM, 2006: 234-241.
［7］ Intel X25E Extreme SATA SolidState［EB/OL］. ［20091005］. http:∥download.intel.com/design/flashnandextreme/319984.pdf.
［8］ GAL E, SIVAN T. Algorithms and data structures for flash memories［J］. ACM Computing Surveys, 2005, 37(2): 138-163.
［9］ CHANG L P, KUO T W, LO S W. Realtime garbage collection for flashmemory storage systems of realtime embedded systems［J］. ACM Transactions on Embedded Computing Systems, 2004,3(4): 837-863.
［10］ WU C H, KUO T W, CHANG L P. An efficient Btree layer implementation for flashmemory storage systems［J］. ACM Transactions on Embedded Computing Systems, 2007, 6(3): 19.
［11］ LEE S W, MOON B K. Design of flashbased DBMS: an inpage logging approach［C］∥ Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. Beijing, China: ACM, 2007: 55-66.
［12］ Transaction processing performance council ［EB/OL］. ［2009-10-05］. http:∥www.tpc.org.
［13］ TPC BENCHMARK ［EB/OL］. ［2009-10-05］. http:∥www.tpc.orgtpccspec/tpcc_current.pdf.
[1] 徐昶, 寿黎但, 陈刚, 胡天磊. 一种基于闪存的数据库复合存储模型[J]. J4, 2012, 46(2): 294-300.
[2] 吴羽, 盛振华, 寿黎但, 陈刚. TrigSigs：一种有效的非结构化记录关联合并算法[J]. J4, 2010, 44(12): 2284-2290.
[3] 皮俊波, 陈珂, 陈刚, 董金祥. 基于用户兴趣模型两段式排序的隐私保护方法[J]. J4, 2010, 44(9): 1659-1665.
[4] 魏蔚, 董亚波, 鲁东明. 基于支持向量机和多资源最大最小公平的DDoS防御[J]. J4, 2010, 44(2): 265-270.