Probability-Based Buffer Management Algorithm For Flash-Based Databases

As a new storage medium, flash memory has many attractive features, including low power consumption, shock resistance, low weight, high density, and high I/O performance. With the decrease of price and the increase of storage capacity, flash memory becomes more and more competitive than traditional disk. It is now widely used as storage media in digital cameras, mobile phones, PADs and notebooks, and there are a growing number of enterprise-level data storage systems using flash memory as secondary storage device.However, several hardware limitations exist in flash memory. Firstly, erase operations are done one block at a time, which contains a fixed number of contiguous pages. Secondly, it is impossible to re-write the page in-place in a flash memory. Thirdly, the life time of a flash memory is shorter than that of a hard disk and a DRAM. Finally, there exist differences among I/O latencies according to the kinds of I/O operations, i.e., a write/erase operation is much slower than a read operation.When taking flash memory as secondary storage device, buffer management algorithms need to take into account the unique characteristics of flash memory for achieving good performance. Traditional buffer management algorithms are not optimized for flash-based database systems and do not take the characteristics of flash memory into consideration, which means they are not able to achieve good performance when directly used in flash-based database systems.This paper proposes a new approach to buffer management for flash-based database systems, i.e., APB-LRU. First, in APB-LRU, the buffer is divided into two regions, i.e., cold region and hot region, so as to get the access frequency information of various data pages. Cold region holds those pages only accessed once, and hot region contains those pages accessed more than once. Second, unlike other existing methods, APB-LRU adopts a new mechanism of replacement based on probability, in which clean pages are replaced with greater probability and dirty pages are replaced with smaller probability, so that clean pages in cold region will not immediately be replaced and cold dirty pages cannot reside in the buffer for a long time. Through this way, APB-LRU achieves a high buffer hit ratio and a better overall performance than other available methods. Third, dynamical adjustment of the ratio between the sizes of cold region and hot region is proposed, which is able to dynamically change the ratio according to the real workloads with various access patterns, so that good performance can be achieved under various workloads. We carry out large amounts of experiments with different datasets, and the experimental results show that APB-LRU is superior to its competitors in most cases.