基于数据访问模式挖掘的磁盘数据预取技术研究

摘要

计算机系统计算单元与存储单元的性能差距越来越大。存储系统性能的优化对文件系统乃至计算机的整体性能提高有非常重要的作用。数据预取技术是重要的优化手段之一，它不仅用在CPU内部预取指令与数据，更是在数据存储领域得到广泛的研究与应用。
　　然而，大多数的缓存预取算法对应用程序的访问模式有较严格的前提或者假设，使得算法只能优化特定的一类应用程序。本文试图使用数据挖掘的手段从应用程序的数据访问历史中找到其访问模式，以此来帮助预取程序识别访问模式，并做出正确的预取决策。我们的算法不对应用程序做假设，只依赖挖掘出来的访问模式。
　　本文在回顾了一些具有代表性的研究成果和Linux内核所实现的预取算法的基础上，提出了在系统更底层实施预取算法的构想。
　　本文提出了面向预测的关联规则，讨论了这种规则的约束条件以及区别于一般关联规则的特点，重点讨论了时间约束条件对规则的挖掘和应用方面的影响。并指出磁盘的数据访问模式可以用这样的关联规则表示，同时它也能直接用于预取算法中对磁盘访问的预测。在第三章中我们详细讨论了规则挖掘算法设计要点与优化手段。
　　为了达到预取程序所需的实时性，规则的匹配也要求具有较强的实时性。在第四章我们讨论了基本的规则匹配算法以及实时性更佳的基于布隆过滤器的匹配算法。该方法可以避免几乎全部的无效查询。实验表明，每次规则匹配中，该算法几乎能保证一次查询就匹配到规则数据库中的结果。
　　最后文章给出了一个模拟仿真实验环境，在此环境中可以评估本文提出的挖掘、预取算法的性能指标。为了能获取任意真实应用程序的磁盘访问行为，本文还给出了一个在Linux内核中实现的磁盘访问记录抓取程序。作者使用这个工具分别记录下系统运行OLTPBench程序和编译一次Linux内核时，发生的所有磁盘访问记录。连同另外一个公共数据集[54]测试了算法的可行性与性能指标。实验表明，预取算法能够明显提升应用程序的响应时间，并达到了良好的实时性。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究状况

1．3 研究内容

1．4 论文组织结构

1．5 本章小结

第2章 基础预取技术原理与体系结构

2．1 引言

2．2 预取技术原理

2．3 内存页顺序读的预取技术

2．3．1 虚拟文件系统层和块数据层概览

2．3．2 VFS中的顺序预取算法原理

2．4 本章小结

第3章 磁盘块语义关联信息的挖掘算法

3．1 引言

3．2 磁盘块相关性

3．3 使用统一编址的数据块

3．4 面向预测的关联规则

3．4．1 数据块的关联规则示例

3．4．2 时间约束

3．5 关联规则的挖掘算法

3．5．1 预处理

3．5．2 挖掘单项目先导规则

3．5．3 模式扩展

3．5．4 算法并行化

3．6 总结

第4章 基于关联规则的预取

4．1 匹配规则

4．1．1 观察窗口

4．1．2 对规则库的查询

4．2 基础规则匹配方案

4．3 改进的规则匹配方案

4．3．1 布隆过滤器

4．3．2 基于布隆过滤器的规则匹配

4．4 预取项目的选择

4．5 本章小结

第5章 实验评价

5．1 实验设置

5．2 实验数据

5．2．1 数据集描述

5．2．2 磁盘访问记录器

5．3 实验分析

5．3．1 挖掘算法开销

5．3．2 挖掘算法命中率的比较

5．3．2 规则匹配算法的查询次数

5．3．3 与其他预取的比较

5．4 本章小结

第6章 总结与展望

6．1 工作总结

6．2 展望

参考文献

致谢

研究生期间研究成果情况