论文部分内容阅读
随着信息技术的不断发展,需要保存和处理的信息量爆炸式增长,应用程序对存储系统的I/O性能提出了越来越高的要求。预取技术作为一种重要的I/O性能优化手段而被广泛地应用于各级存储系统,它使得数据访问能在高速的缓存介质中命中而无需访问后端的慢速存储设备。传统的预取策略都操守,只预取较大概率被访问的数据,且在第一次访问前刚好准备就绪,而这就可能会限制对I/O性能的提升空间。一些更激进的预取策略则会预取更多数据且会更早地进行预取,但传统预取策略认为这会浪费CPU、内存和带宽等资源。然而,随着技术的发展,缓存的容量越来越大,这不仅降低了潜在的资源浪费,而且会极大地提升激进式预取策略的相对收益。
本文在缓存容量逐渐增大的趋势下,研究一种新的较为激进的预取策略。我们首先提出了一种新的基于局部性原则的数据访问模型——稳定集模型,并在此基础上定义了大范围空间局部性。根据我们的稳定集模型进行预取可以有效地利用缓存容量并大大降低缓存缺失率。本文所取得的研究成果包括:
首先研究了大范围空间局部性和传统的顺序空间局部性的关系和本质区别,并分析验证了在大容量缓存下,基于大范围空间局部性的预取技术可以有效地降低缓存缺失率,而这是由它的两个特点决定的:预取数据范围大及预取准确性高。
设计并实现了基于稳定集模型的高效挖掘算法。其创新性地通过集合“分裂”来生成稳定集,同时使用了高效的数据结构,这使得时间复杂度由传统挖掘算法的NP问题降为O(L)。测试结果表明,稳定集挖掘算法可以有效地识别出数据访问关系,且挖掘开销小,具备了在大规模存储系统中在线挖掘的可行性。
设计并实现了基于稳定集模型的数据预取技术,其根据挖掘算法的挖掘结果进行预取。提出了基于数据效用的预取激进度控制策略,并给出了数据效用的量化计算方法,经验证,该策略在各种情况特别是缓存容量较小时,能够有效地平衡预取激进度。同时,本文也给出了稳定集状态的维护方法,实现了在线实时地状态更新。测试结果表明,该预取技术在各个角度的测试中都表现出了明显的优势,相比自适应顺序预取而言,可以将缓存缺失率最低降至1/36。