LS-LRU: A lazy-split LRU buffer replacement policy for flash-based B+-tree index

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.