Explicit Data Correlations-Directed Metadata Prefetching Method in Distributed File Systems

1 简介

为了应对前所未有的数据容量增长，分布式文件系统（distributed file system，DFS），如 GFS [1]、HDFS [2] 和 Ceph [3] 等，已成为构建可扩展存储服务的关键的数据存储组件。图1展示了典型的 DFS 架构，分别由元数据服务器（metadata server，MDS）和数据服务器管理解耦的文件元数据和数据。前期研究表明元数据访问量极大，占整个文件系统操作的50％以上 [4-7]，且多数文件很小，其中位数为 100kB 甚至更小 [8-12]。这些趋势表明元数据性能在 DFS 中至关重要。然而，最近研究表明 MDS 已经成为严重的性能瓶颈 [7][13-15]。

...
为了解决访问相关性指导的预取的限制，我们首先提出一种新的相关抽象，显式数据相关性，其捕获许多应用程序中文件的内部引用关系，且与已广泛研究的访问相关性有显著不同。其次，为了揭示显式数据相关性的重要性，本文通过 Web 应用程序 [10] 和 Linux 内核编译任务进行了全面的分析。该研究可得结论是显式数据相关性广泛存在于这两个实际应用程序中，并且与访问相关性的差异明显。因此，显式数据相关性或许可用以改善 DFS 元数据性能。
第三，我们提出了一种新的元数据预取方案 SMeta，其基于显式数据相关性这一新视角而设计。SMeta 使用一种合算的语法分析方法实时发掘显式数据相关性。为避免更改文件系统 API，数据相关性使用键值对表示，并存储在文件元数据的保留扩展属性中。为了适应文件的变更，我们引入了一种合算的操作数据相关性的方法。为了进一步提高预取准确度并降低网络流量，我们提出了一种轻量级的自适应反馈机制，通过客户端预取元数据的使用统计调整数据相关性。
我们基于一种广泛部署的 DFS Ceph [18] 实现 SMeta，并用合成和实际工作负载评估。实验结果表明，与原始 Ceph 相比，SMeta 可以达到10.5倍的总峰值吞吐量和2.75倍的线性可扩展性的性能提升。SMeta 显著优于最具代表性的访问相关性的预取算法 C-Miner，将实际工作负载下的元数据访问的平均延迟降低11.8-20.2%。与原始 Ceph 相比，SMeta 和 C-Miner 的组合将实际工作负载下的元数据性能提升25.5-29.7%。此外，在启用数据访问时，SMeta 可将整体延迟降低10-45%。
据我们所知，我们是首个显式数据相关性的研究，提高了 DFS 的元数据性能，主要做出了以下贡献。

• 我们首次进行测量研究揭示了数据相关性的重要性，并且发现其比访问相关性更普遍但重叠极少，例如，Web 应用程序和 Linux 内核编译中分别只有2.6%和0.5％的数据相关性也是访问相关性。
• 我们实现了一种高效透明的元数据管理机制，其探索并支持显式数据相关性。为了使数据相关性的探索更为轻量和普适，我们构建了插件式语法分析引擎，它依赖于模式匹配算法，并快速定位文件中不同格式的显式数据相关性。最后我们使用文件元数据的保留扩展属性来存储数据相关性，避免更改文件系统 API。
• 我们提出了一种自适应机制，以提高预取准确度并降低网络流量。使用分数表示显式数据相关性，并在 MDS 收到客户端的预取元数据的使用统计数据时，实时调整分数。预取将忽略分数比阈值低的相关文件，以提高预取准确度并降低预取的成本。

本文的其余部分内容如下。第2节阐述了工作的动机。第3节和第4节中描述预取的设计和实施细节。第5节展示并分析了评估结果。最后，第6节中将我们的工作与相关研究进行对比，并使用第7节进行总结。

2 背景和动机

在本节中，我们首先描述了基于访问相关性的典型预取机制的特征和限制。然后我们通过全面的相关空间（correlation space）研究揭示数据相关性的重要性。

2.1 访问相关性指导的预取

...

2.2 观测和数据相关性

...

2.3 相关空间研究

...

3 设计

...

3.1 探索数据相关性

与现有的离线训练相关性的由访问相关性指导的预取方案不同，数据相关性计划实现在线探索，以适应工作负载的变化。
探索数据相关性的主要挑战是以不同的格式分析各种文件。为了克服这一挑战，我们观察并利用了一个关键点，即文件经常采用的超链接格式引用其相关文件，如表1所示。尽管表1中表明文件格式因应用程序而各异，但这些链接都一致地表示它们通常嵌入在关键字指定的锚点内，如 include、import、href 等。这足以设计一种更通用的语法分析方式以查找匹配指定格式的字符串，比如内核依赖于模式匹配算法和一套暴露于各种应用的统一接口，如图4所示。程序员所需的唯一输入是针对目标应用程序的关键字和正则表达式。
第二个挑战是确定在哪个位置提取数据相关性，是应用程序或是 DFS 代码中。为了保持 DFS 函数的完整性，我们主张调用上述语法分析过程是在文件内容写入文件系统之前的应用程序代码中。这种设计仅需要对应用程序逻辑进行几行代码的更改。这样也能够处理需要编码或压缩内容的文件，只需在编码或压缩函数之前进行语法分析过程即可。由于以下原因，本文不考虑语义相互关联的文件中的复杂和隐式数据相关性。首先，很难泛化和缩放深度理解文件内容的方法。其次，如表1所示，显式数据相关性在各种应用中存在广泛。

3.2 表示和存储 DFS 中的数据相关性

...

3.3 操作和同步数据相关性

...

3.4 数据相关性指导的预取

我们的目标是利用显式数据相关性设计一种新的元数据预取方法，以提高 DFS 元数据性能。本节介绍了基本元数据预取机制的细节和一种进一步优化 SMeta 设计的自适应反馈算法。

3.4.1 基本预取算法

如算法1中所示，数据相关性指导的预取方法流程如下。当 DFS 客户端发出代表相同位置的应用程序的加载文件$f_1$的请求时，MDS 首先定位$f_1$的元数据（inode 和目录条目）。然后搜索并判定 inode 的扩展属性是否有满足预取的数据相关性集合，即分数 score 高于阈值 threshold。最后，将在一个 I/O 轮中发送携带$f_1$的元数据及其数据相关的文件的消息。此外，MDS 依据 3.3 节删去被删除的目标文件的已过时数据相关性，并跳过无法查询权限的相关文件。

Algorithm 1. Metadata Prefetching Algorithm
Input: in ← Inode structure of target file
       reply ← Reply message to client
Procedure SMeta_Prefetcher (in, reply)
  foreach item ∈ in.xattrs do
    if exist(item.ino) == false then
      target.xattrs.erase(item);
      Continue;
    end
    if item.score ≥ threshold then
      dc ← mdcach[item.ino];
      if permission_failed(dc) then
        Continue;
      end
      dc_ancestor ← mdcache[dc.ancestor];
      preallocate_capability(dc, dc_ancestor);
      item.score ← item.score + score_inc;
      reply.insert(dc, dc_ancestor);
    end
  end
  return;

除了元数据信息之外，客户端还需要获得两条信息，即表示操作相应的元数据和数据的各种权限能力（capabilities），以及祖先文件的元数据（即目录条目和 inode）。为避免获取这两条信息的 I/O 分离，我们的预取算法（调用于查找的请求处理函数处）给出预取文件的读能力，并批量处理给定预取文件的祖先信息。
一致性讨论。并发操作预取元数据时，不同步将引入不可接受的元数据不一致。为避免这种情况，我们使用缓存同步协议协调客户端之间的能力授权和撤销，以防止并发读写元数据。当客户端 A 预取文件元数据时，MDS 将授权其消费（consume）此元数据的能力。同时当其他客户端希望更新元数据时，MDS 将撤消 A 相应的功能，以便所有后续读取都可从 MDS 中检索其最新的元数据。据此，SMeta 可保证不消费陈旧的预取元数据。然而，预取方法可能在高写入时由于撤销能力而引入额外的开销。但是由于以下原因，我们认为此开销可以忽略不计：首先，在大多数文件系统工作负载中，只读请求占主要 [4][5][22-24]；其次，文件很少被多个客户端共享。例如，超过76%的文件仅由单个客户端打开，而仅有5%的文件同时被多个客户端打开，90%的同时访问为只读请求 [4][5]。

3.4.2 自适应反馈机制

但是，并非所有的数据相关文件都将在与源文件相对近的距离内访问，因此并非所有的预取元数据都在将来访问中有效。为避免不必要的元数据预取并提高预取准确度，我们设计了一种高级预取方案，利用了每个数据相关对的分数值，以消除不必要的元数据预取。为此我们提出了一种自适应反馈方法，当 MDS 接收到预取元数据的使用统计数据时，周期性地使用正反馈或负反馈 delta 来调整相关性相关性分数。
为了实现这一目标，如图6所示，每个客户端维护反馈表（feedback table）和访问序列（access sequence）这两个数据结构。反馈表跟踪所有预取元数据和产生预取的数据相关性。访问序列监视时间$T$中的文件访问。在 inode 结构中使用一位来表示对应元数据是否在客户端被预取。设反馈表中的记录$<c, a>$表示$c$由$a$预取，当客户端访问已预取元数据的文件$c$时，客户端从后往前扫描访问序列，并检查$a$的元数据访问是否在$c$之前。如果是，则标记该记录为 inc，否则为 dec，而 inc/dec 表示应用程序的正/负 delta。当经过预定义的时间$T$时，客户端遍历反馈表并批量将这段时间内的记录打包至一个反馈消息中，其中每个记录包括文件、数据相关文件和和 inc/dec 标志。然后，客户端向 MDS 发送这条编码了过去$T$时间内记录的反馈消息。
最后，MDS 会根据反馈信息将对应的数据相关性得分加上预定义的 score_inc 或减去 score_dec。为了减轻 MDS 的压力，当 MDS 进行预取时仅对数据相关性加上 score_inc，而当客户端反馈时才传播负反馈结果，这可以减少发送给 MDS 的数据量以及明显减少处理反馈数据的工作量。例如，如图6所示，反馈给 MDS 的信息包含两条记录$<f,d>$和$<f,e>$，当接收到该信息时，MDS 将削弱文件$d$和$e$对$f$的数据相关性。

4 实现细节

...