论文部分内容阅读
随着社会的不断发展，需要保存和处理的信息量日益增加，对存储系统在存储容量、数据可用性以及I/O性能等方面提出了越来越高的要求。信息技术正在从以计算为核心的计算时代进入到以存储为核心的存储时代。网络存储系统因其高性能、高可扩展、高可用性、高可管理性等特点在信息的存储和管理中扮演了越来越重要的角色。
在开放的网络存储系统中，为了满足其对高性能的需求，数据往往被缓存在I/O数据通路的各个层次，从而成了多级缓存架构，其中二级缓存的访问模式与一级缓存的访问模式有着很大的不同，具有较少的局部性，传统的适用于一级缓存的LRu及其变种算法难以适用于二级缓存的管理。
本文主要研究了在网络存储系统中几种典型工作负载下的二级缓存访问模式，通过对二级缓存访问纪录进行时域和频域以及命中率的分析，归纳出二级缓存访问模式的五个特征：1)相同数据被访问的时间间隔较长；2)具有相当数量的一次性访问请求；3)不存在短期过热访问导致缓存块的访问频率异常偏高的情况；4)多次被访问的数据非常有可能被继续访问；5)访问请求偏重于顺序和循环访问模式。
综合考虑以上二级缓存访问模式的特征，我们提出了一种新的针对二级缓存访问模式的高效的在线缓存替换算法MRLFU，MRLFu结合MRU和LFU算法的思想，主要考虑访问请求的频域特征并尽量避免缓存一级缓存已经缓存的数据，访问记录驱动的模拟测试结果表明，MRLFU算法在二级缓存访问记录下与LRU、ARC、MQ等算法相比具有明显的优势，在网页搜索工作负载下其命中率甚至比其它算法高几个数量级。
为了降低MRLFu算法的复杂性，提出了其优化算法MRLFU2，MRLFU2算法的时间复杂度为O(1)，实现复杂度与LRU算法类似，并且不存在需要静态调整的参数。模拟测试结果表明MRLFU和MRLFU2算法在所有测试中表现基本相同，命中率相对误差最多不超过10％，绝对误差最多不超过1.5个百分点。
为了验证模拟测试的结果，在实际系统中实现MRLFU2算法和LRU算法，通过对这两种算法进行对比的性能测试，验证了在联机事务处理工作负载下MRLFU2算法的有效性。