摘要: 1．本文的创新点
互联网和企业内部网的普及使得分布式存储系统受到了广泛关注。在分布式存储系统中，可以通过行关键字来直接访问表的某一行。然而，如果一个查询谓词是对非行关键字所在的列进行筛选，则表中所有行都要被检索。这会严重影响系统性能。为了解决此问题，提出了一种新颖的查询结果缓存方法DICE（Distribute Interval Cache for a rEgion server）。分布式存储系统中的每台机器都保存了一张表中的若干行。DICE 的基本思想是每台机器独立缓存查询结果，并且重用这些缓存的数据来回答后继查询。
2．实现方法
分布式存储系统体系结构中有三个主要部分：主服务器，域服务器和客户端。主服务器负责把域（如行的集合）分配到域服务器上。域服务器负责处理客户端的读写请求。它通过与主服务通信以获取要服务的域的列表，并告知主服务器它的存在。我们的方法基于这样一个事实：许多元组不会被经常查询，因此没有必要缓存或者索引这些元组。一般来说，对于某一列的范围查询通常可以表示为一个区间，如(l, h，用户想要获得的是那些列值在一个指定区间内的行。如果查询q_j 包含查询q_i，那么域服务器就可以使用q_j 的查询结果RS_j 来回答q_i。在这种情况下，如果每个查询结果分开保存，那么会非常浪费内存。为了降低内存的使用，使用一个链表来维护查询缓存。查找和维护被缓存的查询，需要索引结构。为此，我们使用了区间跳表。据我们所知，区间跳表是用于搜索包含某一值的区间的最高效数据结构。区间跳表的检索，插入和删除的时间复杂度是O(log n)。然而，我们必须选择一个最小的缓存查询结果，以减少之后的处理代价。因此，我们修改了区间跳表的搜索过程。
现有的缓存管理技术以单个数据值为管理单位。而我们要维护一组区间来支持范围查询，因此不能直接使用现有技术。时间局部性（如经常被使用的对象在不久的将来也会被使用）是缓存管理的重要启发算法。而我们的方法DICE 还额外考虑了区间的其他特性，例如区间的长度，区间内包含的行数等。
通过与 LRU，LFU 和2Q 等方法对比，说明了DICE 的有效性和我们提出的缓存置换策略的效率。为了评价DICE 的性能，我们采用了两种数据分布和两种查询集。首先产生数据分布UniformDisk，令将被查询的列值在0, 100,000)内均匀分布。还产生了偏斜的数据分布SkewDisk，其中列值遵循Zipf 分布。使用了两个查询集，UniformQuery 和SkewQuery，各包含10,000 个查询。UniformQuery 中每个区间的起点值在对应列的域中均匀选择。SkewQuery中，各区间的起点值则符合Zipf 分布。实验结果表明DICE 在各种环境下性能都是最佳的。
3．结论及未来待解决的问题
本文提出了一种新颖的分布式存储系统区间缓存方法 DICE。它的基本思想是每台机器独立缓存查询结果并为将来的查询所重用。
4．实用价值或应用前景
本文的贡献如下：
(1) 提出了一种有效的分布式存储系统查询缓存策略。该策略最小化对系统组件的改动以支持分布式查询缓存，因而不会影响系统的伸缩性和可靠性，这对于分布式存储系统尤为重要。所以该方法适用于各种分布式环境。
(2) 利用高效的索引机制快速地为给定查询找出合适的缓存结果。此外，设计了专门的数据结构对范围查询结果进行高效地缓存。
(3) 由于传统的替换算法是基于数据项的，不满足我们的要求。为此，针对范围查询设计了高效的缓存替换算法。
(4) 通过大量实验验证了 DICE 的有效性。实验表明，与其它方法相比DICE 在性能上有较大改进。