《Mutilevel Cache Management Based on Application Hints》由会员分享，可在线阅读，更多相关《Mutilevel Cache Management Based on Application Hints（13页珍藏版）》请在金锄头文库上搜索。
1、基于应用提示的多级 cache 管理摘要多级缓存在许多存储配置中是很常见的，它给缓存管理带来了新的挑战。一些现有的cache 替换策略旨在在缺少时间局部性的情况下提高 cache 命中率，而其余替换策略旨在避免多个 cache 间的数据复制。另外的策略使用应用程序提示，它是一个已被证实能够显著提高 cache 利用率的方法，但这个方法只在多级 cache 层次结构的最高层中有效。我们主要的贡献是为多层次 cache 提出了一个全局的、非集中化的、动态的以及消息灵通的管理策略。Karma 这个 cache 管理策略是针对例如数据库等应用提出的，它能很容易地提供提示。这些提示促进 Karma 在所
2、有的 cache 层次上作出明智的分配和替换决定，同时保留独家缓存并且适应在存储模式上的变化。这种综合解决方案在利用总 cache 资源方面明显优于其他方法。为了说明 Karma 的重要性，我们拿它与 LRU、2Q、ARC、MultiQ 、LRU-SP 以及在数据库和 Zipf 跟踪路径上应用的 Demote 策略相比较。为了完整的评估 Karma 的性能，我们另外定义了每个策略的扩展使其工作在一个分层次的缓存中。除了在非常小的缓存中外，Karma 比其它策略表现出更显著的改善。例如，在一个 TPC-H 查询排列中，Karma 比纯LRU 平均提高了 85%的性能。缓冲器 cache 常用于服
3、务器中以减少缓慢磁盘访问和网络消息传递的次数。这些缓冲器 cache 形成了一个多层次的 cache 层次机构。在这样一个层次结构中，第二级 cache 与第一级的 cache 具有不同的访问模式，因为对第二级 cache 的方位实际上就是第一级 cahce 的失效。因此，常用的 cache 替换算法例如 LRU（最近最少使用）很好的适用于第一级 cache中，但不一定能很好的适用在第二级 cache 中。这个论文研究了多个方法以有效地管理二级 cache。1 介绍cache 替换策略在 cache 满的情况下决定哪个块是最佳的替换块。LRU 是最常用的在线替换策略。纯 LRU 没有频率的概念
4、，它使缓存容易受到来自循环或顺序访问模式的污染。各种各样的 LRU 变体，例如 LRU-K、2Q 、LRFU、LRIS 和 ARC，它们都试图解释频率和时间局部性。一种不同的方法是用最适合各个访问模式的替换策略来管理每个访问模式。这种方法是有可能的，例如通过对访问模式的自动分类来实现。在消息灵通的缓存中，替换决定都基于应用本身透露的提示。虽然消息灵通的缓存对任意应用来说存在缺点，但这些缺点在数据库系统中能得到解决。文件系统也可以从各种文件属性中获得其访问模式,例如文件扩展名或访问文件的应用程序。这个可扩展的文件系统提供了一种让用户对文件和系统进行分类的接口以获得文件的属性。现代工具依据文件和存
5、储系统提供了文件访问模式的自动分类。尽管消息灵通的缓存具有上述已被证实的优点，但它仅在高层 cache 中被采用。上述方法都是将努力实现最大 cache 命中率作为最大限度地提高整体性能的一种手段。但是，在现代系统中，服务器和存储控制器通常有很重要的 cache,因此多级缓存分层结构就形成了。在一个多级缓存分层结构中，简单地提高任意层单独 cache 的命中率不一定会最大限度地提高系统整体性能。因此，对多级缓存分层结构来说，我们希望最小限度的减少加权 I / O 成本，这种加权 I/O 成本需要考虑在缓存间的所有数据传输以及访问每层缓存在成本上的差异。多级缓存分层结构在 cache 替换中主要
6、涉及到以下三个问题。第一个问题是在高层缓存中，引用局部性的隐藏。第二个问题是：在资料冗余中块被保存在多个 cache 层次中。第三个问题是：缺乏低层 cache 块的属性信息，例如它们的文件、发出 I/O 请求的应用程序等属性。对较低层次 cache 的访问就是对较高层次 cache 的访问失效。因此，这些访问都具有弱时间局部性的特点。由于 LRU 是基于引用局部性的，所以它在第二级 cache 中的效率会降低。MultiQ、 FBR、ARC 及 CAR 等策略通过考虑近因和频率的访问来试图解决该问题。例如 MultiQ 采用多个生命期递增的 LRU 队列。ARC 和它的近似方法 CAR 的区
7、别在于那些是访问了一次还是访问不止一次的块。假定高层 cache 由 LRU 管理，上述策略都没有将 cache分层结构作为一个整体处理，而是独立地管理各层 cache。在独家缓存中，一个数据块每次只能被缓存在至多一个缓存层次中。一种方法是利用降级操作。当高层 cache 读取低层 cache 中的数据块时，低层 cache 就将该块从它的缓存中删除。当高层 cache 替换掉缓存中的一个未经修改的块时，利用 DEMOTE 操作将这个块送到低层 cache 中。低层 cache 努力为这个被降级的块找到一个位置，如果有必要的话还要替换掉另一个块。我们提出 Karma，它是一个管理试图一致解决上
8、述问题的多级 cache 系统的新方法。Karma 协同管理所有的 cache 层次。通过利用所有层次的应用提示，我们把所有缓存块划分成不相交的集合，并根据这种分类对缓存进行分区来实现唯一性。我们区分了 REDA 和READ-SAVE，一个 READ 操作删除从低层 cache 读的数据块，一个 READ-SAVE 操作指示一个较低层保存一个数据块到它的缓存中。我们也用 DEMOTE 来保持横跨多个 cache 的分区的唯一性。通过组合这些机制，Karma 根据不同的访问模式优化了其缓存内容，以适应随时间变化的模式。这些提示将磁盘块划分成基于各自预期的访问模式和访问频率的集合。为每个集合分配它
9、自己的缓存分区，这个缓存分区的大小取决于集合的访问频率、大小以及对集合中块的访问模式。将具有较高访问频率的分区放在一个较高的 cache 层次中。由与各个分区的集合最适合的替换策略来管理每个分区。因为为较低的 cache 层次提供了应用提示，所以这些 cache 能够独立地计算分区大小，但仅仅只为那些不在较高层次中的分区分配空间。Karma 对任何能够对其访问模式提供基本提示的应用程序都适用。数据库就是这类应用的一个典型例子，在数据库中，查询优化器能够提前判定应用的访问模式。我们将实验估计基于真实的数据库踪迹上，也基于 Zipf 分布式的人工模拟踪迹上。对真实的踪迹，我们将 PostgreSQ
10、L 数据库的解释机制作为应用提示的来源。对于人工仿真的工作负荷，我们为 Karma 提供了数据集中块的访问频率。为了将 Karma 和 LRU,2Q,ARC,MultiQ,LRU-SPH 和Demote 做比较，我们模拟了一个两层 cache 的分层结构和一个存储层次。同样我们定义和实现了这些策略的扩展，以使得它们应用到多级 cache 层次中。这个比较是通过加权 I/O成本的方法。Karma 与其他所有策略相比具有更好的优势：Karma 应用提示的使用使得最优策略能够匹配各种访问模式，它的动态再分区消除了对改变访问模式的灵敏度，并且其独家缓存能够实现对总缓存大小每次增加的利用。在非常小的缓存
11、大小上，Karma 遭受降级的开销，因为被降级的块在再次被访问之前已经被淘汰了。对所有其他缓存大小，Karma 相对所有其他的策略表现出极大的改善。在查询排列的踪迹上，Karma 能够改善 LRU 加权 I / O 成本平均高达 85%。在这样的踪迹上，当与 LRU 相比 Karma 另外表现出比最佳基于 LRU 的策略平均改善 50%的性能更能，并且其比最佳消息灵通策略平均改善 25%的性能。论文的余下部分布局如下。第二节是模型定义。在第三节中我们定义了界益，在第四节中我们阐述了 Karma 策略。实验测试平台在第五节中讨论，实验结果在第六节。第七节描述了相关的工作，第八节我们做了总结。2
12、模型定义 图 1 ：我们的存储模型包括了 n 个缓存层次，每层有一个 cache。操作有从第 i 个cache 读到第 i-1 个 cache 的 READ,REDA-SAVE 以及从第 i-1 个 cache 到第 i 个 cache 的DEMOTE 操作。如图 1 所示，我们的模型包括了一个客户端,n 个 cache 层次，Cache 1,Cachen,以及一个存储层次 Disk，各层以线性的层次结构安排。Cache i 的大小是 Si,其访问开销是 Ci。磁盘的访问开销是 CDisk。把一个块从 Cachei-1 降级到 Cachei 的开销是 Di。假定一个较低的 cache层次拥有递
13、增的访问开销，并且在一个给定的层次中，降级和访问的开销是相同的，即C1=D1C2=D2Cn=DnCDisk一般来说，Cache 1 在客户端的内存中，Cache n 在存储控制器中。另外的缓存层次可能在其中的任一位置，也可能在网络中的其他位置。访问开销 Ci 和 Di 代表了计算、网络以及排队延迟的一系列组合。C Disk 也包括寻道时间。这个模型要求分页，只读并且定义了三种操作：1 READ（ x，i） -把块 x 从 Cachei+1 移到 Cachei，并将 Cachei+1 中的块删掉。如果在 Cachei+1中没有找到块 x，递归执行 READ（x，i+1） ，如果没有早点找到块 x
14、，则 READ 操作在磁盘中结束。2 READ-SAVE（ x，i）-把块 x 从 Cachei+1 中复制到 Cachei 中。只有块 x 的分区在 Cachei=1 中分配了空间才将该块继续保存在 Cachei+1 中。如果在 Cachei+1 中没有找到块 x，递归执行READ-SAVE（x，i ） ，如果没有早点找到块 x，则 READ-SAVE 操作在磁盘中结束。3 DEMOTE（x，i）-把块 x 从 Cachei 移到 Cachei+1，并将 Cachei 中的块删掉。一个策略在一次踪迹上的加权 I / O 成本是该策略在那个踪迹上执行 READ，READ-SAVE和 DEMOT
15、E 操作的所有开销之和。3 边际效益对一级 cache 来说，最优脱机替换策略是 Belady s MIN。当一个块需要从 cache 中被淘汰时，MIN 淘汰具有最大前向距离的块。前向距离（forward distance）指的是在这个块被再次访问前那些将要被访问的不同块的数目。为了开发我们的在线多级算法，我们已经选择了利用应用程序的提示，这种提示在一定程度上能最佳的近似这一前向距离。为此，我们使用边际收益的概念，正如【25】中定义。一个访问踪迹的边际效益就是命中率的增加。如果 cache 的大小是一块一块的增加的，那命中率的增加就能够通过这个踪迹来看到：MG（m）=Hit（m）-Hit(m
16、-1) ，在这里 m 是cache 的大小，Hit（m）是大小为 m 的 cache 的期望命中率。下面我们展示对三种常见的访问模式-循环，顺序和随机，是如何来计算 MG（m）的。尽管我们只关注了这三种模式，同样的考虑也可以用来计算那些命中率可以估计的访问模式的边际效益。显而易见，边际效益取决于 cache 的替换策略。我们假定为每个访问模式使用最佳的替换策略 MRU 是已知的用于顺序和循环模式的最佳替换策略，而随机访问通常采用 LRU替换策略。顺序访问 对任意的 cache 大小 m，因为没有块是前面被访问过的，对一个顺序访问踪迹的命中率是 Hit（m）=0。因此，合成边缘效益也是 0。随机（均匀）访问 对均匀分布的 R 个块的访问踪迹来说，访问每个块的概率都是1/R。对任何 cache 大小 mR,命中率因此是 Hitrand（m）=m/R。合成边际效益是：循环访问 一个循环访问的循环长度（loop length）是再次被访问到的块的数目。对于一个循环长度为 L 的循环访问，由 MRU 策略管理的大小为 m 的 cach
