基于数据挖掘的文件元数据预取研究与实现

论文摘要

在大规模的文件存储系统中,元数据访问性能的优化对文件系统的整体性能提高有着非常重要的影响。为了使元数据服务的性能达到最优,建立一种基于元数据预取有效的、正确的模型显得尤其重要。然而,目前存在的缓存预取算法大多是设计来应用在文件数据的存取访问中,没有考虑到元数据访问的特征与元数据本身尺寸较小的特点。若将适用于文件数据的缓存预取算法应用于元数据的预取操作中显然不具有针对性,反而可能导致访问效率低下。针对这种情况,本文提出一种利用存储系统中的元数据操作日志文件对用户未来可能要操作的元数据进行成组预取的模型,并设计了充分体现元数据特点的缓存和预取的新算法。通过对n-gram预测模型的分析,考虑到元数据之间的长距离信息的重要性,引入数据挖掘技术来辅助n-gram模型来实现元数据成组预取。通过评估不同参数值n对模型的影响,本文选用3-gram模型作为预测模型;并综合运用3-gram预测模型和数据挖掘相结合的方法来实现元数据的成组预取,提高元数据访问的缓存命中率,缩短元数据访问请求的平均响应时间,从而提高元数据的访问效率。模拟实验证明,对于不同用户的文件元数据操作日志序列,新元数据预取模型的Cache（缓存）命中率与NEXUS算法相比平均提高了3.9%,与LRU算法比较平均提高了16%。但是新元数据预取算法的空间复杂度较高,不利于其应用于真实的文件系统。为将元数据预取算法应用于文件系统中,文中实现了在线元数据预取改进算法。该在线改进算法支持增量的频繁闭项集挖掘,且不保留中间挖掘信息,很大程度上减少了挖掘的空间复杂度。模拟实验表明,该算法所占用的平均内存空间明显低于新元数据预取算法所占用的空间,仅为其的24%。综合来看,在线元数据预取算法所消耗的时间也有相应的缩短。故在线元数据预取算法是非常有效的,极大地改进了新元数据预取算法在内存空间上占用过多所造成的不足,同时加快了算法的执行速度,对于元数据预取算法成功的应用于真实的文件系统提供了极大可能性与可行性。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 论文的选题和意义
• 1.2 国内外研究现状
• 1.2.1 引言
• 1.2.2 文件数据预取算法
• 1.2.3 针对文件元数据预取的NEXUS 算法
• 1.3 论文研究的主要内容
• 2 元数据的访问预取
• 2.1 元数据访问的相关技术
• 2.2 元数据访问的流程
• 2.3 提高Cache 命中率的意义
• 2.4 本章小结
• 3 数据挖掘与n-gram 预测模型的研究
• 3.1 数据挖掘
• 3.1.1 引言
• 3.1.2 数据挖掘概述
• 3.1.3 关联规则数据挖掘
• 3.1.4 闭集频繁访问组的关联规则挖掘
• 3.2 n-gram 预测模型
• 3.2.1 引言
• 3.2.2 n-gram 预测模型构造
• 3.2.3 n-gram 预测模型中参数n 的选择
• 3.3 数据挖掘与n-gram 相结合的思想
• 3.4 本章小结
• 4 新的元数据预取模型
• 4.1 模型的构造
• 4.2 模型构造实例
• 4.3 预测算法设计
• 4.3.1 Cache 替换设计
• 4.3.2 预测算法
• 4.4 仿真实验
• 4.4.1 实验环境简介
• 4.4.2 实验结果与分析
• 4.5 本章小结
• 5 在线改进元数据预取模型
• 5.1 在线元数据预取模型的提出
• 5.2 在线改进算法设计
• 5.2.1 基本概念
• 5.2.2 在线算法设计
• 5.3 实验结果
• 5.4 本章小结
• 6 结束语
• 6.1 本文工作总结
• 6.2 对进一步研究工作的建议
• 致谢
• 参考文献
• 附录
• A. 作者在攻读学位期间发表的论文目录
• B. 作者在攻读学位期间参加的科研项目