Nexus: a novel weighted-graph-based prefetching algorithm for metadata servers in petabyte-scale storage systems

1 简介

...

2 相关工作

此前关于磁盘级和文件级的预取算法可分为以下三类：预测型（predictive）预取 [12]、应用控制型（application-controlled）预取 [13] 和编译器指导型（complier-directed）预取 [14]。
...

3 Nexus：一种基于加权图的预取算法

作为更有效的元数据预取方法，Nexus 算法有两处突出点。首先，通过观察即时和间接后继之间的亲和力，Nexus 可以更准确地捕获元数据访问流中的时间局部性。其次，Nexus 利用元数据通常较小的事实，采取激进的预取策略。

3.1 关系图概述

本文算法使用元数据关系图辅助预取决策。关系图用于动态表示元数据访问流中的前驱和后继之间的局部强度。由于前驱和后继间的关系基本上是单向的，所以使用有向图表示。图的顶点为对应文件或目录的元数据，边使用元数据项之间的局部强度（locality strength）作为权重。图2为一个包含 6 个文件或目录的关系图示例。图中可观察到 /usr 和 /usr/bin 的前驱后继关系要远强于 /usr 和 /usr/src。

3.2 关系图构建

为了理解关系图如何提高预取性能，有必要先了解建图方式。关系图是在 MDS 接收和服务来自大量客户端的请求时动态构建的。具有预定义容量的历史窗口（history window）用于保存MDS最近收到的请求。例如，当容量设置为10时，则窗口中只保留10个最近的请求。在新请求到达时，新请求将取代历史窗口中最旧的请求，如此动态更新，可随时保持当前的前驱后继关系。随后，关系信息将在各请求时集成到图中，具体方法是在图中插入新边（如果前驱后继关系是第一次发现）或向现有边添加适当的权重（如果已有该关系）。下面给出了构建关系图的伪代码。

Let G denote the graph to be built
Build-Relationship-Graph(G)
  G ← ∅
  foreach new incoming metadata request j
    foreach metadata request i (i≠j) in history window
      if edge (i,j) \notin G
      then add an edge (i,j) to G with appropriate weight
      else add appropriate weight to edge (i,j)
    replace the oldest item in history window with j

例如对于观测到的请求序列 ABCADCBA...，历史窗大小为 2，图3(a)为逐步构造图的过程（使用线性递减分配权重，详见3.5节）。与之相对比，图3(b)显示了历史窗大小为 3 时的图构建过程。

3.3 基于关系图的预取

当序列ABCADCBA...构建了如图3(a)和图3(b)所示的关系图后，可在一组内某个元素缓存未命中时，通过关系图预取一组可调节大小的后继组。预测结果取决于该元素的出边权重的顺序（图中使用带权值的箭头表示）。更大的权值表示更强的关系和更高的预取优先级。在前文例子中，假设最后一个请求 A 缓存未命中，根据图3(a)关系图，预取组大小为 1 时预测 {C}，大小为 2 是则为 {C,D}；同理，使用图3(b)推断的结果分别为 {B} 和 {B,C}。

3.4 Nexus 的主要优势

（1）“看得越远，决策越好”：...
（2）元数据服务器应使用激进的预取：...

3.5 算法设计的考虑

算法的实现方面需要考虑几个设计因素以优化性能。对这些因素的敏感性研究如下。
（1）后继关系强度：在节点之间分配合适的权重以表示与前驱和后继之间的关系强度，对该算法至关重要，因为其会影响算法的预测准确性。该问题的公式化描述为：给定一个长度为 n 的访问序列 $M_1M_2M_3\cdots M_n$，需要对前驱-后继边 $ (M_1,M_k),\;2 \le k \le n$ 分别增加多少权重。考虑四种方式：

• 等权重分配（identical assignment）：给所有 $M_1$ 的后继相同的权重。这种方法与 Griffioen 和 Appleton 提出的概率模型非常相似 [19]。它看起来简单且直接，但确实有效。关键在于要考虑直接后继节点的至少一个后继。然而这种方法的不足也很明显：它无法区分直接后继与其后节点的重要性，这可能会导致关系强度延伸至别处。后文中，使用等权重分配表示这种方法。
• 线性递减分配（linear decremental assignment）：该方法假定引用流（reference stream）中越近的访问距离关系越强。例如，以线性递减的顺序分配边权，例如 $(M_1,M_2)$ 分配 10，$(M_1,M_3)$ 分配 9，$(M_1,M_4)$ 分配 8 等等。（图3(a)和3(b)的示例中使用了该方法计算权重。）该方法本文称为线性递减分配。
• 多项式递减分配（polynomial decremental assignment）：有可能递减的激进程度超过线性，联系到空气中的辐射衰减，多项式递减也是一种可能的方式。
• 指数递减分配（exponential decremental assignment）：边权重的衰减甚至可能比多项式递减更快。在这种情况下，采用指数递减模型，因而该方式称为指数递减分配。

为了解哪些分配方法能更好地反映元数据引用流中的关系强度，我们引入对 HP trace [10] 的实验，以比较上文四种边权分配方法可实现的命中率。为了使实验更全面，其进行了三个维度的不同配置：缓存大小，后继个数（或历史窗大小），以及预取分组的后继数量（或预取组大小）。 由于多项式递减的结果非常接近指数分配，因此我们删去前者以显示更清晰的数字给读者。余下三种方法的结果如图4所示。
...
线性递减分配始终优于其他方式。因此，接下来的实验中都使用其作为边权分配方案。
（2）提前看多远以及预取多少：
...
（3）面向服务器的分组（server-oriented grouping）与面向客户端的分组（client-oriented grouping）：...
我们开发了面向客户端分组的算法，并通过运行 HP trace，与面向服务器的分组进行比较，结果如图6所示。图6表明面向客户端的分组算法总是优于面向服务器。因此，应尽可能采用面向客户端的分组算法。

4 评估方法和结果

4.1 工作负载

我们通过在2003年7月 Lawrence Livermore 国家实验室收集的 LLNL trace [20] 和 2001年12月惠普实验室收集的惠普文件系统 trace [21] 上运行轨迹仿真来评估我们的设计。它们收集了文件数据和元数据的 I/O 事件。仿真中我们过滤掉文件数据活动，并仅向模拟器提供元数据事件。
（1）LLNL trace：使用 PB 级存储系统的主要原因之一是需适应对 I/O 和存储容量、能力越来越苛刻的科学应用。因此，由科学应用生成的 trace 是评估预取算法的最佳数据之一。据我们所知，近期唯一可用于大型集群的科学应用程序的 trace 是 LLNL2003 文件系统 trace。它获取于 Lustle Lite 并行文件系统 [1]，其运行在超过 800 个双处理器节点的大型 Linux 群集上。包含 6403 个 trace 文件，总共 46,537,033 个 I/O 事件。本文仿真中只考虑元数据活动，如图7所示。
元数据操作又进一步分为两种：元数据读和元数据写。诸如 access 和 stat 等操作属于元数据读，而ftrungate64 和 unlink 属于元数据写入，因为它们需要修改文件的属性。然而，open 和 close 的分类是模糊的。open 操作不能简单地被分类为元数据读，因为根据 UNIX 语义它可以创建文件。类似地，根据文件属性是否是脏的，可以将 close 操作分到读、写两个组，因为可能会产生元数据更新操作。对于 open 请求，情况比较容易，因为可以查看系统调用的参数和返回值以确定其类型。例如，如果参数是 O_RDONLY 并且返回值为正，可知这是一个元数据读取操作。对于 close，假定每次关闭文件时都会更新最后修改时间字段，则可始终视为元数据写入。
（2）HP trace：为了提供更完备的比较，我们还在 HP trace [21] 上进行了模拟，其收集了 10 天内一台总计 500GB 存储容量和 236 个用户的分时服务器上的文件系统 trace。由于它不是科学应用追踪，因此通过将多个 trace 文件合并增加访问密度，提升规模以模仿多 MDS 多客户端的应用程序，同时保持原访问序列的时序。在仿真中，还筛去与元数据无关的任何 I/O 操作。

4.2 仿真框架

文中开发了一款仿真框架，可仿真适用于多MDS多客户端的集群MDS的存储系统上的缓存与预取算法。在这种存储体系中，元数据一致性控制是设计者面临的重要问题。然而，这不是本研究聚焦的地方，本文主要关注设计和评估一个新的元数据预取算法。为了简化仿真设计，我们的框架使用一种广泛使用的层级缓存设计——协作缓存 [22] 以及其一致性控制机制——写失效 [23] 来解决仿真框架的一致性问题。必须注意的是，本文基于实用性选择协作缓存，因为它相对成熟和简单，然而这不意味着它是一致性控制的唯一或最佳选择。事实上，我们认为需要面向元数据的一致性协议来优化性能，这也是我们未来的研究方向之一。
在我们的仿真框架中，存储系统分为(1)客户端缓存、(2)MDS缓存、(3)协作缓存、(4)硬盘四个层级，当系统接收到一个元数据请求时，首先检查客户端本地缓存，如果未命中则发送请求至对应的MDS，如果MDS缓存也未命中则在协作缓存中查找，而协作缓存则向硬盘请求数据。
因而从客户端的视角而言，整体的缓存命中率由以下三者组成：本地命中率（客户端缓存）、远程命中率（MDS缓存）和协作缓存命中率。显然，本地缓存命中率直接反映了预取算法的效率，因为分组和预取都是在客户端一侧完成的。
在最理想的情况下，一个元数据请求的响应时间大约为客户端本地主存的访问时延。而当请求需发送给MDS时，服务器缓存命中则响应时间仅需考虑网络时延开销，未命中则还需考虑协作缓存带来的额外网络时延。在最坏的情况下，MDS还需要向硬盘查询，因而需要引入额外的磁盘访问开销。
预取发生在客户端缓存缺失时，此时元数据请求需要发送至MDS。MDS则可以将完整预取组和需要访问的元数据信息一起返回给客户端。

4.3 轨迹驱动仿真

...

4.4 命中率对比

...

4.5 平均响应时间对比

...

4.6 一致性控制的影响

在 HP 和 LLNL trace 上也进行了一致性控制对算法影响的研究。由于HP trace 读请求主导的，因此其结果不如 LLNL trace 有代表性。由于篇幅有限，这里只展示在 LLNL trace上收集的平均响应时间结果，如图10所示。结果表明，平均响应时间没有明显受到一致性控制的影响，这说明 Nexus 对写负载不是很敏感。一个可能的解释是，该科学应用程序中的工作负载具有大部分元数据为只读或一次性写入的特性。

5 结论

...