Using provenance to boost the metadata prefetching in distributed storage systems

1 简介

大规模文件系统的存储容量正在爆炸式增长，容量已接近 EB，并且存储的对象数可达数十亿 [1]。当前大多数的分布式文件系统将元数据从文件数据中分隔，从而将实际文件数据流与元数据流隔离。这种架构具有出色的可扩展性，并且大大减轻了存储系统中的 I/O 瓶颈 [2-4]。
分布式文件系统中的 I/O 请求可分为元数据请求和用户数据请求两类（见图1）。通常，元数据保存在一个或多个元数据服务器（MDS）中，MDS 负责响应用户的元数据请求，包括文件属性、访问权限和数据索引。 而文件数据则存储在数据节点中。通常，元数据的大小远小于文件数据，但元数据请求量可占所有I/O请求的50%以上 [5]。随着文件数据和客户端数量的急剧增长，MDS 受到了巨大的工作负载压力。因此，MDS 的效率也往往是整个分布式文件系统的性能瓶颈。

缓存和预取是两种利用数据布局的空间和时间局部性以提高 I/O 性能的有效方法。预取元数据且随后在客户端缓存可以有效地减少 MDS 需要调度的元数据请求量，从而改进 I/O 系统的整体性能 [6]。然而，传统的用于预取和缓存文件数据的方法，由于以下原因不适于预取和缓存元数据：

a) 传统文件数据的大小远大于元数据。因此，对于特定大小的缓存空间，缓存文件数据的数量通常小于元数据的数量，并且针对文件数据设计的缓存策略非常保守。这是因为当缓存未命中时，由于文件数据较大，已缓存的文件数据会导致显著的 I/O 惩罚。假设文件系统的块大小为4Kb，65％的元数据小于128b，98％的元数据小于4224b [7]。元数据缓存未命中不会占用过多缓存空间，仅导致微小的 I/O 惩罚。因此，元数据的预取策略更倾向于预取大量元数据以充分利用缓存空间。

b) 利用元数据中包含的语义信息可以提高文件访问相关性的挖掘精度 [8]。溯源关系是一种与用户进程的行为密切相关的元数据。此类元数据描述了数据项的来源以及为何在其当前位置可被找到 [9]。因此，可以通过分析数据对象的溯源关系来反映文件和进程之间的相关性。

许多研究基于利用过去的文件访问模式来开发新的元数据预取方法 [7][8][10]。然而，这些方法不考虑进程和相应文件之间的相关性（例如，文件的溯源信息）。该缺点导致取得的相关信息不够丰富，从而降低了元数据预取的有效性。本文提出了一种基于溯源关系的元数据预取方案（ProMP），利用元数据的特征提高缓存命中率。ProMP 分析所请求数据的溯源关系，然后生成溯源窗（PW），计算同一溯源窗内被请求数据的文件的访问相关性。利用文件访问相关性，可实现一种有效和激进的元数据预取方案。
本文余下部分的组织结构如下：第二节介绍相关工作。第三节讨论背景知识。第四节介绍本文提出的ProMP方案的详细设计。第五节展示评估ProMP方法的实验结果。最后，第六节对本文进行总结。

2 相关工作

溯源关系是一种元数据，它代表了数据对象的衍生，描述了一个对象从何而来，以及为何在当前位置存在 [9]。该关系在科学计算、档案系统、安全系统等之中发挥着重要作用 [11]。
已有许多研究对收集和应用溯源关系进行了努力。Muniswamy-Reddy 等人 [12][13] 提出了一种溯源感知的存储系统，来收集和存储溯源关系。考虑到溯源关系规模大，许多能有效降低溯源数据的储存成本的方法被提出 [9][14]。一种基于溯源关系的访问控制模型被提出，以增强计算机系统的安全性 [15]。Liu 等人利用溯源有效地改善了基于云的存储系统的搜索性能 [16]。但是，溯源关系从未用于分布式文件系统中的文件访问相关性分析和元数据预取。
分布式文件系统中，元数据预取和缓存技术已经被研究且用以提升元数据服务的性能 [6][17]。然而，现有的元数据预取算法主要聚焦于使用数据挖掘技术，根据过往的文件访问模式来挖掘文件访问相关性。
AMP（基于亲和力的元数据预取）[10] 提出了一种 n-gram 语言模型和利用过去的 I/O 请求流预取用户未来一组元数据操作的数据挖掘技术。此外，Peng 等人 [7] 提出了一种名为 Nexus 的新型基于加权图的预取算法。 它利用直接和间接的后继关系获取元数据服务器集群中的组预取的性能优势。与传统的文件预取算法相比，上述元数据预取算法利用激进的预取达到高缓存命中率。但是，这些方法仅关注过往文件访问模式的分析，而未考虑元数据的丰富语义属性。
结合语义属性和过去的文件访问模式的研究投入较少。FARMER [8] 有效地挖掘并提高了文件访问相关性的精度。然而 FARMER 仅使用文件的静态属性来评估文件间的语义距离，而未考虑文件的动态语义属性，如文件溯源关系。
与现有的元数据预取算法的工作相比，本研究涵盖了溯源和元数据流的特征，我们提出了 ProMP 算法来提高分布式文件系统的元数据访问性能。

3 背景

基于 OPM（Open Provenance Model）[18] 提出的溯源的定义，其由过程（Process，P）、数据（Data，A）和代理（Agent，Ag）组成。（译者注：OPM 中 Data 应该为 Artifact，其定义大致为可持久存储的实例体；Artifact 一词表示人工创造（非自然的）的物品，亦引申为工业批量生产的物品，敏捷开发等语境下 Artifact 都被译为工件，本文中由于介绍存储，所以用 Data 一词代替也算合理；同理，本文中 Process 也能翻译为“进程”）这三个组成部分之间形成以下五个关系：

1. 使用（used）：过程 P 访问数据 A；
2. 生成（wasGeneratedBy）：数据 A 由过程 P 生成；
3. 控制（wasControlledBy）：过程 P 受代理 Ag 控制；
4. 触发（wasTriggeredBy）：过程 P1 由过程 P2 触发；
5. 衍生（wasDerivedFrom）：数据 A2 由数据 A1 衍生。

演示这类关系的一个典例如图2所示，其中 X 轴上的 T 开头的符号表示不同的时间点（例如，T1表示第一个时间点）：当用户看电影时，触发过程 P1，并访问元数据 M。之后用户想写文章 B，过程 P2被触发，读取并复制文章 A 到新建的文章 B。过程 P2 请求元数据 A 和 B。引证参考文献时，过程 P3 由 PDF 阅读器生成，其请求元数据 C、D 和 F。过程 P4 由打开 Web 浏览器来搜索互联网触发。过程 P4 请求元数据 E 和 G。综上，一系列元数据 M 及 A 到 G 被过程 P1 到 P4 请求。
基于 OPM 模型，图2中用户生成的溯源关系可以由图3的因果依赖图（causal dependency graph）描述。图3显示文件不仅相互有关联（wasDerivedFrom），还与过程有关系（used 或 wasGeneratedBy）。这说明相同过程访问的文件之间存在相关性。例如，元数据 E 和 G 与相同的过程 P4 关联。此外，触发关系的过程，如P2、P3、P4，可以聚合为单个任务。定义该任务的生命周期为 PW（Provenance Window，溯源窗）。我们可以确定在相同的 PW 中访问的文件间也存在相关性，例如 A 到 G。

两个不同的 PW 通常相关性很弱或不相关，例如图2中的$PW[T_1\rightarrow T_2]$和$PW[T_3\rightarrow T_8]$，它们是由不同的目标触发的。因此，在同一 PW 内的 I/O 请求 A 到 G 有强相关性，而在不同 PW 内的请求是弱相关的。所以，基于溯源关系，我们能够挖掘文件间的文件访问相关性。
前文提到的元数据缓存和预取方仅利用过去的文件访问模式，而忽略文件和进程之间的相关性。由于使用不同任务之间不相关的 I/O 请求来挖掘文件相关性，因此得到的文件访问相关性是不准确、不充足的。考虑图2中的文件访问请求M、A 到 G，观看电影和写文章是两个独立的任务。因此，采用传统方法来计算 M 和 ABCDEFG 之间的相关程度将产生大量噪声。为了减轻这种情况，我们假设不同任务的 I/O 请求是不相关的。通过提取特定任务的 PW，可以过滤不同 PW 内的不相关 I/O 请求，从而提高预取准确度。

4 ProMP：一种基于溯源的元数据预取方案

4.1 概述

图4为 ProMP 的流程图和主模块图，包含一个基于溯源的相关性计算模块和一个预取模块。 图4下部的虚线框中为基于溯源的相关性计算模块，包括三个重要组件，溯源窗提取器（provenance window extractor，PWE），相关度计算器（correlation degree calculator，CDC）和关联规则生成器 （association rules generator，ARG）。此模块进行以下四个重要步骤：

1. 收集溯源信息并存储至溯源数据库，例如进程的生命周期和元数据 I/O流；
2. PWE 定期分析收集的溯源信息并提取 PW；
3. CDC 使用提取的 PW 和元数据访问频率计算相关度；
4. ARG 基于计算的相关程度生成元数据预取的关联规则列表。

预取器模块由元数据缓存和生成的关联规则组成。该模块的主要步骤已在图中使用序号标出。(a) 当客户端的应用程序请求元数据时，直接查找元数据缓存；(b) 如果缓存未命中，则预取器通过搜索关联规则，选择强相关的元数据；(c) 客户端向元数据服务器批量发送相关元数据请求；(d) 由此，强相关的元数据对象将从元数据服务器获得，然后在客户端的本地缓存中缓存。这将减少元数据请求所产生的网络传输开销。

4.2 溯源窗提取器

为了简化描述，我们定义 PW 如下：
【定义1】一个过程 P 的生命周期表示为 $L(P)$，表示过程 P 开始时刻与结束时刻的区间：\begin{equation}L(P)=[st,et]\end{equation}【定义2】如果存在时刻 t 有 $t\in L(P_a)$ 且 $t\in L(P_b)$，则称 $P_a$ 与 $P_b$ 相关，记作 $P_a \sim P_b$。
【定义3】一个任务 T 由 n 个相关联的过程组成，表示为$T=\{P_1,P_2,\cdots,P_n\},n \ge 1$。具有以下三条性质：
（1）任务 T 的生命周期为\begin{equation}L(T)=\left[\min_{1 \le i \le n}(st_i), \max_{1 \le i \le n}(et_i)\right]\end{equation}（2）$\forall t \in L(T)$，$\exists P \in T$ 使得 $t \in L(P)$；
（3）任意两个不同的$T_1, T_2$有：\begin{equation}L(T_1) \cap L(T_2) = \emptyset\end{equation}【定义4】任务 T 的生命周期定义为 PW（Provenance Window，溯源窗）。
由于任务之间存在一定时间间隔（定义3性质3），任务具有不相交性。因此，只要获取每个进程的生命周期，就可以使用公式(2)确定每个起源信息窗口的边界。
这种方式会导致一个问题，即类似守护程序的进程总是保持连接。由于守护进程的生命周期长，很难提取有效的 PW。为了解决这一问题，我们使用阈值 max_strength 来滤去守护进程。当一个特定进程的生命周期大于 max_strength 时，该进程将被滤去。为了简单起见，在 PWE 算法中 max_strength 设为3小时。
根据 PW 的定义，PWE 算法如算法1所示。该算法遍历整个进程列表，并根据每个进程的开始时间$st$来排序。相关进程组合成一个任务 T。当下一个任务与当前任务无关时，一个 PW 就生成了。PWE算法通过执行这种排序和遍历操作来输出 PW 列表。最坏情况下，该算法的时间复杂度为$O(n\log n)+O(n)=O(n\log n)$。该复杂度是可接受的。基于被提取的 PW，ProMP 可在下一步中计算任意两个元数据对象的相关度。

Algorithm 1: extractor for provenance window
Input: max_strength, list of processes with start time and end time (st, et) PLIST
Output: list of provenance windows TLIST
  // To sort PLIST by start time st
  Sort(PLIST);
  T = P1;
  forall process P \in PLIST do
    if P.et - T.st > max_strength then
      TLIST.push(T);
      T = <T.et, P.et>;
    else if P \sim T then
      // correlated, combined
      T.et = P.et;
    else // not correlated, generate a new provenance window
      TLIST.push(T);
      T = P;
    end
  end
  return TLIST

4.3 相关度计算器

我们假设在同一 PW 内的所有元数据访问具有相关性 [19]。然而依据时序，元数据访问流中的前驱和后继之间存在不同的相关强度。例如，元数据 B 和 C 始终在元数据 A 之后被访问。元数据$(A,B)$和$(A,C)$强相关，而时序上$(A,C)$的相关强度弱于$(A,B)$。为量化当前元数据访问与其后继之间的相关强度，本文采用随时间衰减的函数确定任意两个元数据对象的相关程度。
考虑元数据请求$Q$之后一系列元数据请求$Q_1,Q_2,\cdots,Q_n$。首先，相关度设置为初始值$S_0$。相关度随根据请求$Q$和后继请求$Q_k$之间的时间间隔$\Delta t$值衰减。当递归到$Q_k$时，相关度更新为$S_k$。递归计算$Q$和后继的相关度$S_k$，直到$S_k$减小到小于$0$。随着时间递减的函数如式(4)所示：
\begin{equation}S_k=S_{k-1}-\lceil \Delta t\rceil , 1\le k \le n\end{equation}我们使用一个例子（见图5）来说明任意两个不同元数据对象间相关程度的计算的基本思想。坐标轴上方的字符表示元数据访问流 A-G。坐标轴下方的数字表示对应请求到达时的时间点。

如果$S_0$初值为10，则根据式（4），请求 A 与其后继间的相关度计算如下：

• $(A,B)=S_0-\lceil 0.5-0\rceil =9\rightarrow S_1$
• $(A,C)=S_1-\lceil 1-0\rceil =8\rightarrow S_2$
• $(A,D)=S_2-\lceil 1.1-0\rceil =6\rightarrow S_3$
• $(A,E)=S_3-\lceil 3-0\rceil =3\rightarrow S_4$
• $(A,F)=S_4-\lceil 3.5-0\rceil =-1\rightarrow\text{小于 }0\text{，结束}$

以此类推，可以获得元数据访问流 A-G 之间的相关度。图6展示了该流的相关度。图中用下划线标记了值小于0的无效相关度。相关强度随着表示两个元数据对象间的相关度数值的增加而增长。因此，数字越大意味着不同的两个元数据对象之间的相关程度越精确。 图7总结了该PW中元数据访问流 A-G 的相关度。

4.4 关联规则生成器

使用基于溯源关系的相关度计算器，我们通过处理大规模的溯源关系和元数据访问历史来生成关联规则。ProMP 的计算范式是由处理大量数据的需求驱动的。现有大数据的计算范式可分为流处理和批处理式。流处理是直接对数据流的实时处理。其更为复杂，且内存开销大。作为一种先存储后处理的模式，批处理适用于非实时的情境，因其离线处理数据，且内存资源消耗低。考虑到内存开销和溯源关系特性，生成关联规则可选用批处理。
...

5 评估方法和结果

5.1 工作负载特征

我们设计了由轨迹（trace）驱动的模拟器，并使用了三种现实世界的 trace 来评估 ProMP 方案。模拟器的模块和流程图如图4所示。三种 trace 的特征列于表1。Lase trace 是一个安全研究项目的一部分，在 2000 至 2001 年记录了系统调用级别的 trace [20]。Web trace 收集自一个在线图书馆项目的网站服务器 [21]。Res trace 收集自存储研究生科研项目的惠普系列700工作站上的 HP-UX 9.05 [21]。
由于三个 trace 全部都收集自系统调用级别，因此可以将 trace 中的请求表示为三元组 (时间戳, 系统调用名, 请求对象)。但是，文件数据活动和元数据事件也被这三个 trace 收集。在我们的模拟中，筛去了包括读写在内的文件数据有关请求的系统调用，仅向模拟器提供有关元数据请求的系统调用。例如，Web trace 中被保留的系统调用和相应请求的数量总结于表2。

所有的三个 trace 不仅都包含系统 I/O 调用，还包含进程行为的系统调用，如 exit 等。在模拟中，将一个进程的首次 I/O 操作的时间戳作为该进程的开始时间（st），而完成系统调用 exit 的时间戳作为结束时间（et）。因此可以通过算法1，从具有前文所述的生命周期$(st,et)$的 trace 进程中提取出 PW。
初始时，通过训练两天的数据请求来计算初始相关度。新的溯源关系数据（原数据请求和进程的生命周期）被存储在键值数据库中。定期通过分析新的溯源关系可提取PW。基于新提取的PW，计算并更新相关度到相关度数据库中。
为了评估缓存大小对算法性能的影响，我们假定元数据大小相等；然后，我们将比较不同数量的元数据下 ProMP 的性能，该数量表示缓存大小。在我们的模拟中，我们测试了五种不同的缓存大小。

5.2 初始相关度$S_0$的影响

...

5.3 预取大小的影响

...

5.4 评估命中率

...

5.5 评估内存开销

...

5.6 评估关联规则的查询性能

当缓存未命中时，将会频繁地获取关联规则。与传统的用于文件数据的预取算法不同，元数据预取算法会激进地预取十几个元数据，所以需要频繁地查询关联规则。因此，关联规则的查询性能被认为是元数据预取算法实现效果的另一个指标。Nexus 作为流处理范式，需及时更新关系图。Nexus 必须遍历所有出度以找出相关度最强的几个对象。与之相对，ProMP 离线生成关联规则并直接通过快速哈希查找来获取关联规则。图13中，ProMP 同预期一样具有最佳的查询性能。

6 结论

本文提出了一种用于分布式文件系统的 ProMP 方案。设计了轨迹驱动的模拟器以评估 ProMP 的有效性。提出了溯源窗（PW）以滤去使用传统方法挖掘相关性时产生的噪声。实验结果表明，利用溯源窗和历史文件访问模式，ProMP 可以挖掘进程和相应文件之间的相关性，从而实现激进地预取。此外，ProMP 的有效性随缓存大小的增加而增加。进一步地，本文提出的算法比当下最先进的元数据预取算法 Nexus 更有效，且内存开销更少。实验结果表明，ProMP 相比于现有方案内存开销更少，有效性更强，比传统的 LRU 和先进的 Nexus 的命中率分别提高49%和7%。
基金项目：中国国家自然科学基金61572232和61272073，广东省自然科学重点计划基金S2013020012865。