A Kind of Metadata Prefetch Method for Distributed File System

1 简介

随着云计算和大数据技术的发展和普及，为了处理和保存大量数据，存储系统发展迅速。例如，在数据分析和数据价值探索领域中，存储系统不仅保障数据存储的可靠性，而且提供高性能数据传输和交互。然而，随着用户和数据量的爆炸式增长，业界对于满足大规模数据访问和存储的高可靠、高可扩展性设备的需求日益提升。分布式文件系统是一种具有高可靠性和高可扩展性的共享文件存储系统，可以提供完整的并发访问机制，因此分布式文件系统已吸引越来越多地关注。
多数流行的分布式文件系统中，元数据操作通常占所有文件操作的30-70%。因此元数据的操作性能是直接影响分布式文件系统整体性能的关键因素之一。由于分布式文件系统具有频繁操作文件元数据的特征，因此已有许多对文件元数据预取的研究 [1][2]。尽管这些预取方法在很大程度上缓解了分布式文件系统中频繁操作元数据的问题，但它们还有预取文件的命中率低的问题，这使得预取范围较大且预取精度较低。
当前主流的元数据预取方法大多基于文件的访问相关性。它们使用离线方法在文件系统的历史访问记录中寻找相关信息，并使用频繁访问的文件集合同时进行后续的预取 [3][4]。但是，基于文件访问相关性的这种预取方法有强局限性，难以根据系统负载的实时特性来动态调整文件的关系。因此，如何挖掘文件数据间的潜在关联与如何准确预测用户访问的后续文件已成为重要的问题。
本文介绍了一种基于隐性数据相关性特性的元数据预取方法 HR-meta（Hidden Relationship for Metadata Prefetch）。当元数据服务器响应目标文件的元数据请求时，提前通过预取方法将相关文件的元数据预取到客户端，从而缩短了相关文件的元数据访问过程并减少系统的元数据请求。实验结果表明，当文件相关程度从 0.25 增加到 1 时，使用 HR-Meta 预取的系统相较原先的缓存命中率可提升 9.1% 至 47.7%。

2 相关工作

2.1 元数据预取

近年来，许多学者对元数据预取和缓存进行了深入研究。这些研究主要关注于通过运用文件间的访问相关性和应用程序提示来预取相关信息。Diskseen [5] 分析了磁盘访问的时间和空间关系，分两个窗口进行文件读取和预取，并使用读窗口指导预取窗口进行数据预取。Quickmine [6] 通过应用程序级的上下文信息的事务查询来预测未来的访问序列。Gu 等 [7] 提出了一种加权图的基础分组方法 Nexus。元数据关系图中的顶点表示文件和目录，边的权值表示顶点之间的局部强度，通过元数据服务器维护图，动态插入或删除边并调整相关权重，从而实现元数据预取。Nguyen 等 [8] 使用了一种非常类似的方法来挖掘元数据和预取数据之间的相关性。除了相关性的挖掘外，还有一些研究使用元数据与关联文件在物理上共位存储的新架构，使得它们能一起访问。SmartStore [9] 根据元数据的语义组织并分组相关的文件，以提供低延时的复杂查询。CFFS [10] 将文件及其元数据之间的一对一映射关系更改为多对一的映射，集成文件目录、文件内部关联和文件访问频率以探索相关性，并执行元数据预取。

2.2 文件相关性的表示

文件相关性在分布式文件系统的研究中较为广泛。SEER [11] 记录最近若干相关文件之间每个文件的语义距离，并使用公共邻居的数量来计算文件之间的相关性。Griffioen 和 Appleton [12] 提出了一种基于组的文件缓存管理方法，将文件与其后代组成一组，并使用加权概率图来描述文件之间的关系。Li 等提出了一个高效的文件系统块相关性搜索算法 C-Miner [13]。使用数据挖掘技术和改进的 CloSpan 方法来发掘频繁关闭的块访问序列，找出存储服务器中块的相关性，并使用已发现的序列生成关联规则以指导块预取和布局优化。除了上述描述文件关系的方法之外，还有一些采用树结构记录文件关系和访问模式的研究 [14][15]。这些方法通过访问树结构捕获用户进程文件之间的依赖关系。在从根节点到叶节点的树结构中，各条路径构成了一组连续文件序列的访问路径，并可为访问模式不同的程序维护多个访问树。访问树可匹配程序的当前访问活动，并用于指导文件预取。这些方法多数适用于常规文件系统，但不适合含有大量文件的分布式文件系统。

2.3 机器学习方法

机器学习的概念已在分布式文件系统中存在许久。随着机器学习技术的快速发展，机器学习方法已广泛应用于分布式文件系统。Amp [16] 使用一种已经广泛用于自然语言处理的 n-gram 模型 [17] 来学习访问序列中的隐式语义，并依据历史访问序列预测待预取文件。ProMP [18] 使用类似的方法挖掘访问过程与文件源目录中的对应文件和访问历史之间的关系，试图获取更准确和丰富的信息。SMURF [19] 结合高可靠性的并发传输机制设计了一种新型的管道机制，可有效地预取和缓存元数据。它不仅提高了预取数据的准确性，而且大幅降低了元数据预取的平均时延。RMD [20] 在主元数据表前新增了一个元数据表，用来控制成对相关的上下文预取器的预取度，进而决定系统是否需要从主元数据表中提取数据以减少过度预测。Chen 等 [21] 提出了一种基于文件数据关联的元数据预取机制 SMeta，根据语义分析机制探索文件间的数据关联，并采用轻量的模式匹配算法发掘文件的关联关系。

3 方法

为了更好地处理文件元数据预取的问题，我们设计模型时主要考虑以下两个方面：1）模型可以在读取过程中学习提取的文件和要分析的文件之间的隐藏关系：如果两个文件都与当前提取的文件有关，那么模型需要考虑这两个文件与当前提取的文件有关；2）模型可以分析未读取的文件，并预取相应元数据。

3.1 文件相关特性

对于上述两个问题，我们考虑使用计算文件的隐藏特性的方法。如果取出一个文件后，有另外两个文件相继被取出，则这两个文件应相关或有某处相似，因此向量空间中两个文件的特征向量之间的距离理应比被提取的文件更近。如果取出一个文件后并未取出其他文件，则这些文件与被提取的文件无关，因此他们的特征向量理应远离被提取的文件。
为了使隐藏特性能更完全地表达文件之间的关系，我们选择了数个典型特性作为计算隐藏特性的基础：

（1）频繁文件访问序列的特征
文件系统中某些文件的访问序列呈现出重复片段的形式，这是因为文件系统中的访问序列模式具有频繁和周期性的特征，因此有较大概率后续访问的文件将在特定时间段内重复访问序列。这表明同一访问序列模式中的文件有一定的相关性。
（2）同级目录存储关系的特征
在实际环境中，用户通常会将其认为有某种关系的文件放入合适的目录中，这使得同一目录中的文件通常具有很强的关系。
（3）应用内部访问序列的特征
在应用程序执行过程中，调用文件的序列具有一定的规律性。因此通过分析应用程序调用文件的序列，可以获得文件间的一些关系。源文件通过预编译、编译、汇编和链接生成可执行文件。如果我们从这个角度分析，则当执行或编译一系列源文件时，将以特定的顺序生成并存储对应的中间文件，这些文件之间应该也具有相关性。
（4）用户直接读取序列的特征
因为不同的用户有自己独特的访问习惯，所以同一用户访问的文件通常具有强烈的高度相关。每个用户都有自己的用户文件夹，且几乎所有由用户生成的文件都存储在该文件夹中。与同级目录存储关系相比，用户产生的目标访问文件夹不受路径限制。

3.2 文件预取模型

为了便于介绍模型，设$U$为提取文件的集合，$I$为待分析文件的集合，$F^U$为提取文件的特征集，$F^I$为待分析文件的特征集。已经取出的每个文件都与要分析的一系列文件进行交互，这些文件要么与提取的文件有关（正相关）要么无关（负相关）。分别记正负数据为$S^+$和$S^-$，则待分析的提取文件的所有关系对可以表示为$(u,i) \in U \times I$。
提取文件和待分析文件都可以由其特性完整表示，任意提取文件$u$的所有特征可表示为特征集$f_u \subset F^U$，同理$f_i \subset F^I$表述待分析文件$i$的特征。
对每个特征$f$，设参数维度为$d$，其与提取文件和待分析文件的特征向量$e_f^U, e_f^I$有关。每个特征也有一个额外的偏移量$b$，分别用$b_f^U, b_f^I$表示提取文件和待分析文件的特征偏移量。
则提取文件$u$的隐式表示可以由相关特征向量计算：\begin{equation}q_u=\textstyle\sum_{j \in f_u} e_j^U\end{equation}同理对于待分析文件$i$的隐式表示可以用如下公式计算：\begin{equation}p_i=\textstyle\sum_{j \in f_i} e_j^I\end{equation}提取文件$u$的偏移量可以通过对所有相关特征的偏移量求和得到：\begin{equation}b_u=\textstyle\sum_{j \in f_u} b_j^U\end{equation}待分析文件$i$的偏移量为：\begin{equation}b_i=\textstyle\sum_{j \in f_i} b_j^I\end{equation}综上，提取文件$u$和待分析文件$i$的模型预测可以由两个特征的点积和偏移量修正求得：\begin{equation}\hat{r}_{ui}=f(q_u \cdot p_i+b_u+b_i)\end{equation}实际应用中函数$f(\cdot)$有多种选择，不同的函数对于预测效果的影响不尽相同。这里我们选择 Sigmoid 函数用于预测：\begin{equation}f(x)=\tfrac{1}{1+exp(-x)}\end{equation}为了使模型表现出更好的结果，我们通过最大化上述参数的似然函数来优化模型：\begin{equation}L(e^U,e^I,b^U,b^I)=\textstyle\prod_{(u,i) \in S^+} \hat{r}_{ui} \times \textstyle\prod_{(u,i) \in S^-} (1-\hat{r}_{ui})\end{equation}

3.3 预取数据结构

图2介绍了预取元数据的结构。在将 MDS 中的预取元数据返回到客户端时，需要以规定的组织形式序列化。预取队列使用目录项（directory item）作为基本单元以记录其名称和 inode 信息。元数据 inode 包括 ino、文件大小和上次修改时间等信息。在对文件访问序列执行特征分析与对目录和文件路径名执行语法分析后，提取文件的特征代码被存储在元数据 inode 的扩展属性中。同时，将文件和特征信息和模型计算得到的预取得分（prefetch score）以 <K, V> 对的形式存储在相关文件的元数据 inode 的扩展属性中。当客户端需要访问目标文件时，它可以直接从文件元数据 inode 读取，而不需要向 MDS 发送请求，从而缩短相关文件的元数据访问过程并减少系统中的元数据访问请求的数量。

3.4 元数据预取算法

HR-Meta 接受两部分输入：待读取文件中提取的相关特征，预读取文件的分析特征。
为了将提取的四种数据特征编码为可计算的特征向量，算法使用定序词典（fixed order dictionary）将提取的数据特征中的文本转换为对应的 id，以便根据设置的顺序拼接它们，并最终得到可计算文件特征向量。然后，这些文件的特征向量用于判决是否预取。为了获取一系列文件的特征向量，使用先前评估的标准向量对其进行比较和分析，并确定是否预取文件的元数据，最后输出获得的预取元数据序列。算法1描述了元数据预取算法的过程。

Algorithm 1 Metadata prefetching algorithm
Input: 用户访问文件(X), 待分析文件集(fileSets), (thresh), (N)???
Output: 预取元数据序列(Y)
Prefetch process:
  if The prefetch record for the file in the prefetch cache do
    return Y ← The file queue recorded in the prefetch cache
  end if
  while Prefetch limit not reached N do
    for Files to be analyzed without judgment do
      score ← Use HR-Meta to calculate the prefetch score of the file
      if score ≥ thresh do
        Add the metadata corresponding to the file to the prefetch queue (Y)
        Record the file to the prefetch record related with the file
      end if
    end for
  end while
  return Prefetched metadata queue (Y)

4 实验

4.1 基本设置

该模型部署在由 5 台飞腾（Phytium）服务器组成的本地分布式文件系统集群上。每台服务器的软硬件资源信息如表I所示。

在系统群集中，1台服务器作为监视节点，部署 Monitor 监视进程以实时监控群集的运行状况。1台服务器用作元数据服务器节点，部署 MDS 元数据守护进程以提供集群元数据服务。其余3台服务器用作数据服务器节点，并且在每台服务器上部署四个 OSD 对象守护进程。每个 OSD 都分配了独立的硬盘作为持久存储设备。合计12个 OSD 提供数据服务。同时，使用40GbE 交换机构建局域网，为系统集群提供通信服务。
记录3天的本地服务器群集的文件访问历史记录为此实验的数据集。在记录访问的文件时，我们还记录了与访问文件相关的一些文件，转换为 {文件, [相关文件1, 相关文件2]} 的形式，将其作为文档相关特征性能分析的测试数据 。

4.2 模型设置

...

4.3 文件相关特征的准确性分析

本节主要分析文件相关特征的选择与 HR-Meta 预取结果的准确性之间的关系，并证明文件相关特征在文件元数据预取中发挥关键作用。实验结果如表II，表III和表IV所示。
频繁文件访问序列的特征缩写为频繁访问（FA），同级目录存储关系的特征缩写为对等存储（PS），应用内部访问序列的特征缩写为应用访问（AA），用户直接读取序列的特征缩写为用户读取（UR）。
从表II可以看出，文件相关性预测中影响最大的特征是文件的频繁访问序列。这正是因为文件系统中的访问序列模式具有频繁和周期性的特征，因此有较大概率后续访问的文件将在特定时间段内重复访问形式。从表III和表IV结果可以大致看出，几个特性组合的收益不仅是简单的叠加，而是有一些额外的益处。例如，四个特征组合的预取结果比四个特征准确率之和高出 7.17%。

4.4 缓存命中率结果及分析

我们选择 LRU（least recent used）和 ARC（adaptive replacement cache used）两种缓存替换策略实现存储缓存模拟器，并使用 HR-Meta 指导元数据预取，我们使用 HR-Meta 指导的这两种方法与其原始方法比较，评估预取的缓存命中率的提升。
hr-LRU 表示与预取方法结合的 LRU，hr-ARC 表示与预取方法结合的 ARC。实验结果如图3和图4所示。通过分析结果，可以得出结论：与预取算法结合内存缓存模拟器的效率大幅提高。hr-LRU 的平均缓存命中率为 LRU 的1.25倍，hr-ARC 的平均高速缓存命中率为 ARC 的1.33倍。当缓存大小设置为20M 时，连续观察的72小时，其缓存命中率基本稳定，且总优于 LRU 和 ARC。这也意味着文件相关性可长时间有效。特别是当缓存大小相对较小时，与预取算法结合的 hr-LRU 和 hr-ARC 具有更高的缓存命中率和更明显的优点。对于基于替换策略的方案的结果，除非另有说明，后续比较实验使用 ARC 作为缓存替换策略。

由于系统对一个文件的相关文件的访问概率不固定，因此我们引入参数 $\nu$ 控制系统在每次读取后继续访问其相关文件的概率，以进一步分析 HR-Meta 的稳定性，$\nu \in [0,1]$。在实验中，$\nu$ 从 0.25 增加到 1 来调整模拟系统的实际负载。通过对图5中实验数据的分析，当文件相关性从 0.25 增加到 1 时，使用 HR-Meta 预取的系统相较原先的缓存命中率可提升 9.1% 至 47.7%。可以看出，系统访问的相关文件越多，系统的缓存命中率越高。
在引入 HR-Meta 之前，文件系统无法识别数据和预取文件元数据的相关性。因此无论 $\nu$ 如何更改，系统的缓存命中率基本相同。引入 HR-Meta 后，当元数据服务器响应目标文件的元数据请求时，系统可以预先将其相关文件的元数据发送到客户端，从而缩短了相关文件元数据的访问过程并减少了系统中元数据的请求次数。随着文件访问概率 $\nu$ 的增加，客户端和元数据服务器之间的交互频率大大减少，且文件系统利用模型预取的元数据也相应地有所改进。

5 结论

现有的分布式文件系统通常将元数据与数据的操作和管理分离，以简化系统设计并提高系统的可扩展性。但是，由于分布式文件系统中的元数据频繁操作，如何提高元数据的访问性能，避免其成为系统性能的瓶颈非常重要。本文提出了一种用于分布式文件系统的元数据预取方法 HR-Meta。它学习被提取的文件和文件访问序列中待分析文件之间的隐藏关系以提取文件的相关特征，并使用已提取的特征执行元数据预取。实验结果表明，与仅由单一文件相关特征组成的模型相比，由多个文件相关特征组合的模型准确性增加 57.67%。仿真实验结果表明，基于 ARC 替换策略，当文件系统与预取策略相结合时，缓存命中率明显高于未使用任何预取策略。理想环境下，当文件相关性从 0.25 增加到 1 时，HR-Meta 预取方法可以通过预取文件元数据并缓存至本地客户端，将客户端元数据访问请求的缓存命中率提高 9.1% 至 47.7%。下一步将在生产环境中应用该预取方法，并尝试将数据相关性集成到文件数据访问的性能优化中，可预取相关文件的文件数据，以便进一步优化文件系统元数据和数据访问性能。

基金项目：上海市科技创新行动计划 19510750200。