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

摘要

闪存是一种新型的存储设备，具有耗电少、高可抗震性、重量轻、体积小、速度快等优点。随着闪存的容量的增加和价格的下降，闪存相对于磁盘的竞争优势变得更加明显，已经在数码相机、移动电话、笔记本等设备中广泛使用，并且，有越来越多的企业级别的数据存储系统使用闪存作为底层存储设备。
　　然而，闪存有一些固有的硬件限制:(1)闪存中数据的擦除是以块为单位，一个数据块包含固定数量的连续的页，数据的读写是以页为单位;(2)闪存中不能原地更新数据;(3)闪存的生命周期比磁盘和DRAM短;(4)闪存中，读写速度不一致，写操作和擦除操作比读操作慢很多。当使用闪存作为存储设备时，为了充分发挥闪存的优势，数据库系统的缓冲区替换算法需要考虑闪存独有的特性。现有的缓冲区替换算法如LRU、LIRS、以及ARC，都没有考虑闪存的读写效率不一致的特性，无法在闪存数据库系统中获得较好的性能。
　　本文提出了一种新的面向闪存数据库的缓冲区替换算法——APB-LRU:(1)该算法将缓冲区分为冷区和热区，用来捕获数据访问频度，前者用于存放只访问过一次的数据页，后者用于存放至少访问过两次的数据页;(2)采用了其他研究所没有的概率替换机制，即以较大的概率替换冷区中的干净页，以较小的概率替换冷区中的脏页，从而避免了冷脏页长期驻留缓冲区的情况，提高了命中率，获得了较好的整体性能;(3)设计了冷、热区比例动态变化机制，可以根据工作负载的变化动态调整冷、热区所占缓冲区的比例，从而使得替换算法在不同的负载模式下都可以取得较好的性能。基于不同测试数据集的大量实验结果表明，APB-LRU算法可以比其他已有的算法获得更好的性能。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 本文研究内容

1．4 本文结构

第二章 闪存数据库缓冲区替换算法

2．1 传统的面向磁盘的数据库缓冲区替换算法

2．2 需要重新设计面向闪存数据库的缓冲区替换算法的必要性

2．3 设计面向闪存数据库的缓冲区替换算法考虑因素

2．4 面向闪存数据库的缓冲区替换算法

2．5 本章小结

第三章 基于替换概率的缓冲区替换算法

3．1 基本思想

3．2 算法设计

3．3 与其他算法的比较

3．4 本章小结

第四章自适应的基于概率的缓冲区替换算法

4．1 改进策略

4．2 算法设计

4．3 算法时间复杂度分析

4．4 本章小结

第五章 实验设计与结果

5．1 实验设计

5．2 APB-LRU算法最佳替换概率的选择

5．3 命中率

5．4 物理读操作次数

5．5 物理写操作次数

5．6 运行时间

5．7 本章小结

第六章 结论

6．1 总结

6．2 后续工作

参考文献

攻读硕士学位期间发表的论文

致谢