Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21]


Journal of Information Science and Engineering, Vol. 31 No. 3, pp. 1113-1132 (May 2015)

LS-LRU: A Lazy-Split LRU Buffer Replacement Policy for Flash-Based B+-tree Index*

1Department of Computer Engineering
Ajou University
Suwon, 443-749 South Korea
2Department of Software
Kyungpook National University
Sangju, 742-711 South Korea
E-mail: {jinrize; tschung};

Most embedded systems are equipped with flash memory owing to its shock resistance, fast access, and low power consumption. However, some of its distinguishing characteristics, including out-of-place updates, an asymmetric read/write/erase speed, and a limited number of write/erase cycles, make it necessary to reconsider the existing system designs to explore its performance potential. For example, the buffer replacement policy of flash-based systems should not only consider the cache hit ratio, but also the relative heavy write and erase costs that are caused by flushing dirty pages. Most of the recent studies on buffer designs have focused on a Clean-First LRU strategy that evicts clean pages preferentially to reduce the number of writes to flash memory. However, each of them fails to distinguish dirty pages, which may have a different effect on the flash memory. In this paper, we propose a Lazy-Split LRU-based buffer management scheme that not only considers an imbalance of the read and write speeds but also different effects of different dirty pages and frequent changes of the B+-tree index structure caused by intensive overwrites. Specifically, it introduces a semi-clean state to further classify some dirty pages into clean part and dirty part and several efficient replacement policies to reduce the number of B+-tree splits. The experimental results show that our solution outperforms other algorithms including pure LRU and CFDC, and is effective and efficient for improving the performance of B+-tree on flash memory.

Keywords: buffer management, B+-tree, flash memory, replacement policy, split policy

Full Text () Retrieve PDF document (201505_19.pdf)

Received September 16, 2013; revised November 12, 2013 & January 3, 2014; accepted February 4, 2014.
Communicated by Xiaodong Zhang.
* This work was partially supported by Basic Science Research Programs through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF-2013R1A1A2A- 10012956 and NRF-2012R1A1A2043422).
+ Corresponding author.