|
|
|
| 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 |
|
|
|
Abstract Studied the buffer page replacement methods on flashbased 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
|
|
Published: 01 December 2010
|
|
|
PWLRU: 一种面向闪存数据库的缓冲区存取算法
针对现有缓冲区替换算法无法充分发挥闪存数据库性能的不足,研究了缓冲区存取方法.根据数据库OLTP应用中IO行为的特点以及闪存的物理特性,提出一种新的缓冲区存取算法——基于页面权重的最近最少使用替换(PWLRU).PWLRU首先对缓冲区内的页面设定权重,在扫描与修改某页面时对权重进行调节,并优先替换权重为零的页面.实验选用基于MYSQL的TPCC测试标准作为模拟仿真环境,实验结果证明：PWLRU不仅能保证缓存命中率不低于经典的最近最少使用替换算法(LRU),而且在闪存上的IO平均读取代价和能耗均优于LRU和之前面向嵌入式闪存环境提出的先清除最近最少使用替换算法(CFLRU),是一种特别适合闪存数据库的缓冲区存取算法.
|
|
| ［1］ RAMON C, FRED D, KAL L, et al. Operating system implications of solidstate 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 ACMSIAM 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 X25E Extreme SATA SolidState［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. Realtime garbage collection for flashmemory storage systems of realtime 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 Btree layer implementation for flashmemory storage systems［J］. ACM Transactions on Embedded Computing Systems, 2007, 6(3): 19.
［11］ LEE S W, MOON B K. Design of flashbased DBMS: an inpage 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. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
