基于替换概率的闪存数据库缓冲区替换算法

摘要

闪存具有和传统磁盘不同的特性,包括写前擦除、异地更新、读写延迟非对称等.传统的面向磁盘的缓冲区替换算法无法在闪存数据库系统中获得较好的性能.文中提出了一种新的面向闪存数据库的缓冲区替换算法——APB-LRU,其特点:(1)该算法将缓冲区分为冷区和热区,用来捕获数据访问频度,前者用于存放只访问过一次的数据页,后者用于存放至少访问过两次的数据页;(2)采用了其它研究所没有的概率替换机制,即以较大的概率替换冷区中的干净页,以较小的概率替换冷区中的脏页,从而避免了冷脏页长期驻留缓冲区的情况,提高了命中率,获得了较好的整体性能;(3)设计了冷、热区比例动态变化机制,可以根据工作负载的变化动态调整冷、热区所占缓冲区的比例,从而使得替换算法在不同的负载模式下都可以取得较好的性能.基于不同测试数据集的大量实验结果表明,APB-LRU算法具有比其它已有的算法更好的性能.%Different from traditional disk,flash memory has characteristics of erase-before-write,out-of-place update and asymmetric I/O latencies for read,write,and erase operations.Traditional buffer replacement 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.Firstly,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.Secondly,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 can not 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.Thirdly,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.