摘要

现代数据中心更喜欢单个文件系统实例，它跨越整个数据中心，支持数十亿个文件。在这种情况下，文件系统元数据的维护面临着独特的挑战，包括在保持局部性的同时实现负载平衡、长路径解析和近根热点。

为了解决这些挑战，我们提出了INFINIFS，这是一种用于超大规模分布式文件系统的高效元数据服务。它包括三个关键技术。首先，INFINIFS将目录的访问元数据和内容元数据解耦，这样就可以使用元数据局部性和负载平衡对目录树进行分区。其次，INFINIFS设计了并行遍历路径的推测路径解析，这大大减少了元数据操作的延迟。第三，INFINIFS在客户端引入了乐观访问元数据缓存，缓解了近根热点问题，有效提高了元数据操作的吞吐量。广泛的评估表明，INFINIFS在延迟和吞吐量方面都优于最先进的分布式文件系统元数据服务，并为包含多达1000亿个文件的超大规模目录树提供稳定的性能。

1. 引言

用于快速扩展业务的现代数据中心通常包含大量文件，这些文件很容易超过当前分布式文件系统的单个实例的容量[23、27、35、36、39、42]。目前，数据中心通常被划分为相对较小的集群，每个集群分别运行一个分布式文件系统实例。然而，更可取的做法是使用一个文件系统实例来管理整个数据中心，这样可以提供全局数据共享、高资源利用率和低操作复杂性。例如，Facebook引入了分布式文件系统，将小型存储集群整合到一个包含数十亿文件的实例中[28]。

可扩展且高效的元数据服务对于分布式文件系统至关重要[14,22,23,25,28,31–33,36,41]。由于现代数据中心通常包含数百亿甚至数千亿个文件，使用一个超大规模的文件系统来管理所有文件给元数据服务带来了严峻的挑战。首先，随着目录树的扩展和工作负载的多样性，目录树分区在实现高元数据局部性和良好的负载平衡方面具有挑战性。其次，路径解析的延迟可能很高，因为在超大规模的文件系统中，文件深度很深。第三，客户端元数据缓存的一致性维护开销变得巨大，因为超大规模的文件系统通常需要为大量并发客户端提供服务。

本文介绍了INFINIFS，这是一种用于超大规模分布式文件系统的高效元数据服务。为了解决上述挑战，INFINIFS通过以下设计分发文件系统目录树并加速元数据操作。

首先，我们提出了一种访问内容解耦分区方法，以实现高元数据局部性和良好的负载平衡。关键思想是将目录的访问元数据（名称、ID和权限）和内容元数据（条目列表和时间戳）解耦，并在细粒度级别进一步划分这些元数据对象。具体来说，我们首先将每个目录的访问元数据与其父目录分组，将内容元数据与其子目录分组，从而实现高元数据局部性。然后，我们将这些细粒度组划分到不同的元数据服务器，并对目录ID进行一致的哈希，从而确保良好的负载平衡。

其次，我们设计了一个推测路径解析来并行遍历目录树，这大大减少了元数据操作的延迟。关键思想是为每个目录分配一个可预测的ID，这样客户机就可以推测所有中间目录的ID，然后并行地发送多组件路径的查找。

第三，我们引入乐观访问元数据缓存来缓解近根热点，从而实现可伸缩的路径解析。其关键思想是在客户端缓存目录访问元数据，以吸收对近根目录的频繁查找，并在元数据服务器上以低开销惰性地使缓存项无效。具体来说，目录重命名和目录集_权限操作将向元数据服务器而不是多个客户端发送缓存失效通知，以便每个服务器在处理客户端元数据请求时都可以惰性地验证缓存过时性。

总之，本文做出了以下贡献：

我们确定了在大规模场景中影响元数据服务性能的挑战（§2）。
我们提出了一种可扩展且高效的分布式元数据服务INFINIFS，其特点是访问内容解耦分区（§3.2）、推测路径名解析（§3.3）和乐观访问元数据缓存（§3.4）。
我们实施并评估了INFINIFS，以证明INFINIFS在元数据操作的延迟和吞吐量方面都优于最先进的分布式文件系统，并为包含多达1000亿个文件的超大规模目录树提供稳定的性能（§5）。

2. 背景及动机

在本节中，我们首先解释为什么需要一个跨越整个数据中心的文件系统实例（§2.1）。然后，我们讨论了在这种情况下（超过数十亿个文件）高效元数据服务面临的独特挑战（§2.2）。最后，我们分析了真实数据中心工作负载中元数据访问的特征（§2.3）。

2.1 大规模文件系统

文件系统通常为用户提供分层名称空间（即目录树）来管理文件。在目录树中，每个文件\目录都拥有元数据信息。元数据操作通常涉及两个关键步骤，即路径解析和元数据处理。当用户访问路径名为/home/Alice/paper.tex的文件时，元数据的访问方式如下：首先，文件系统执行路径解析来定位目标文件，并检查用户是否具有适当的权限；然后，文件系统执行元数据处理，以原子方式更新相应的元数据对象。

元数据服务是大规模分布式文件系统的可伸缩性瓶颈[22,32,36]。分布式文件系统是数据中心的重要基础设施组件[2,12,35,39]。随着数据中心内文件数量的快速增长，元数据服务成为分布式文件系统的可扩展性瓶颈。目前，数据中心通常由一组文件系统集群组成。例如，阿里云维护着近数千个盘古分布式文件系统，共同支持数据中心多达数百亿个文件[2]。Facebook还需要许多HDFS集群来在一个数据中心存储数据集[28]，因为由于元数据限制，每个HDFS集群最多支持1亿个文件[36]。

然而，一个跨越整个数据中心的大规模文件系统更可取。例如，Facebook引入了分布式文件系统，将小型存储集群整合到一个实例中[28]。每个数据中心一个大型文件系统在以下方面优于一组小型文件系统集群：

全局数据共享。一个大型文件系统提供了一个全局名称空间，使数据中心能够更好地共享数据。相比之下，在单独的集群中存储不同的数据集效率很低，需要专门的数据放置并导致数据移动。它还使计算服务的逻辑复杂化，因为相关数据可能会在不同的文件系统中分割。
资源利用率高。全局数据共享可以消除不同集群之间的重复数据，从而提高磁盘容量利用率。此外，一个文件系统允许更好的资源共享。相比之下，在集群方法中，一个文件系统集群中的空闲资源无法重新分配到其他集群。
操作复杂度低。一个大型文件系统可以显著降低操作复杂性，因为只有一个系统需要维护。相比之下，在一个大型数据中心（如阿里云）中维护数千个文件系统集群需要耗费大量人力，而且容易出错。

2.2 可伸缩元数据的挑战

一个跨越整个数据中心的大型文件系统需要支持数十亿个文件，并为大量客户机提供服务。这给分布式文件系统的元数据服务带来了严峻的挑战，如下所述。

挑战1：随着目录树的扩展和工作负载的多样性，目录树分区在实现高元数据局部性和良好的负载平衡方面具有挑战性。

元数据位置对于高效的元数据处理非常重要。文件系统操作通常处理多个元数据对象。例如，文件创建首先锁定父目录以使用目录列表操作进行序列化[25]，然后以原子方式更新三个元数据对象，包括文件元数据、条目列表和目录时间戳。使用元数据局部性，我们可以避免分布式锁和分布式事务，从而实现低延迟和高吞吐量的元数据操作。
负载平衡对于实现高可扩展性很重要。元数据操作通常会导致目录树中的负载不平衡。对于现实世界中的数据中心工作负载来说尤其如此，其中相关文件被分组到子树中[4,41]。连续子树中的文件和目录可能会在短时间内被大量访问，从而在存储子树的元数据服务器上造成性能瓶颈。
在超大规模的场景中，现有的分区策略无法实现高局部性和良好的负载平衡。管理数据中心中的所有文件会导致目录树在深度和广度上快速扩展。此外，由于文件系统支持所有数据中心服务，因此它面临着具有不同特征的各种工作负载。这对现有的目录树分区策略来说是一个挑战。细粒度分区，比如直接将元数据对象散列到服务器[25,37]，可以实现负载平衡。然而，它牺牲了局部性，并经常导致分布式锁定，引入昂贵的协调开销，导致高延迟和低吞吐量[8,20]。粗粒度分区，例如将连续子树分组到同一服务器上[4,41]，保留了局部性并避免了跨服务器操作。然而，它容易受到工作负载倾斜的影响，从而导致负载不平衡。

挑战2：路径解析的延迟可能很高，因为在超大规模的文件系统中，文件深度很深。

在超大规模的文件系统中，文件深度变得越来越深。以前的文件系统通常假定目录树中大多数文件的深度小于10[7，10]。然而，我们发现，当将所有服务整合到一个文件系统中时，文件的深度会迅速增加。图1（a）显示了实际工作负载中访问文件的深度分布（§2.3）。我们可以观察到，几乎一半被访问的文件深度超过10。
深层目录层次结构对文件系统性能有很大影响。我们基于构造[28]的设计实现了一种简单的路径解析机制，并评估了路径解析随深度增长的延迟。图1（b）显示路径解析的延迟随文件深度线性增加。根据目录ID将目录划分到不同的元数据服务器，因此，解析深度为N的路径需要解析N−1个中间目录，这导致N−1个连续的网络请求。

挑战3：客户端元数据缓存的一致性维护开销变得巨大，因为超大规模的文件系统通常需要为大量并发客户端提供服务。

路径解析需要从根目录遍历目录树，并按顺序检查路径中所有中间目录的权限。这会导致近根目录被大量读取，即使对于平衡的元数据操作工作负载也是如此。然后，文件系统吞吐量将受到存储近根目录的服务器的限制。本文称之为近根热点。许多分布式文件系统依赖客户端元数据缓存来缓解近根热点[13、23、30、31]。
我们观察到，以前的客户端缓存机制在具有大量客户端的大规模场景中不能很好地工作。例如，基于租约的机制将租约授予在固定期限后到期的每个缓存项。租约到期时，相应的缓存项将自动失效。NFS v4[30]、PVFS[13]、LocoFS[23]和IndexFS[31]广泛使用租赁机制。但是，租约机制会因近根目录的缓存续订而导致负载不平衡。这是因为所有客户机都必须重复更新其近根目录的缓存条目以进行路径解析。随着客户端数量的增加，近根目录上的这种负载不平衡最终将成为性能瓶颈，并影响总体吞吐量。

2.3 真实世界工作负载的特征

为了了解超大规模分布式文件系统的特征，我们分析了真实工作负载中元数据操作的相对频率。我们从最大的云提供商之一阿里巴巴云追踪生产部署中的元数据操作。我们从三个支持不同服务的盘古文件系统实例中捕获工作负载：数据处理和分析服务、对象存储服务和块存储服务。我们合并了这些不同服务的工作负载，以表示跨越整个数据中心的大型文件系统的工作负载。元数据操作的相对频率如表1所示，从中我们可以看到：

文件操作占∼95.8%的业务。
readdir是最频繁的目录操作，占∼93.3%的目录操作。
目录重命名和目录设置权限操作很少发生，仅占∼0.0083%的所有元数据操作。

这些见解也完善了我们的INFINIFS设计。

3. 设计及实现

我们设计INFINIFS的三个关键理念如下：

解耦目录元数据。INFINIFS将目录元数据分为目录本身的访问状态（名称、ID和权限）和与子目录相关的内容状态（条目列表和时间戳），因此可以对其进行细粒度的分区以实现负载平衡，同时仍然为创建、删除和readdir等常见操作的元数据处理保留良好的局部性。
在路径解析中推测目录ID。INFINIFS基于父ID、名称和版本号上的加密哈希，为每个目录使用可预测的ID。它使客户端能够推测目录ID，并并行启动多组件路径的查找。
惰性地使客户端缓存无效。INFINIFS在客户端缓存目录访问元数据，以避免根附近的热点，从而实现可伸缩的路径解析。客户端使用缓存项进行路径解析，不知道它们是否过时。在处理客户端元数据请求时，元数据服务器会延迟验证缓存过时性。

3.1 总览

INFINIFS是一种用于超大规模分布式文件系统的高效元数据服务。图2展示了INFINIFS的体系结构，其中包含以下组件：

客户端。INFINIFS提供了一个由客户端共享的全局文件系统目录树。客户端通过用户空间库或FUSE用户级文件系统与INFINIFS联系。它们通过推测路径解析（§3.3）遍历目录树，该解析通过预测目录ID和并行查找来最小化延迟。客户端在路径解析期间使用乐观元数据缓存（§3.4），以减轻近根目录上的过度读取负载。
元数据服务器。文件系统目录树通过访问内容解耦分区（§3.2）分布在元数据服务器上，该分区实现了高元数据局部性和良好的负载平衡。每个服务器管理本地键值存储（即KV存储）中的元数据对象，该存储通常将元数据缓存在内存中，并将更新记录在NVMe SSD中以获得高性能。元数据服务器使用失效列表（即Inv.list）来惰性地验证客户端元数据请求。
重命名协调员。中心重命名协调器用于处理目录重命名和目录设置权限操作。它使用重命名图检查并发目录重命名，以防止孤立循环（§4.1），并将修改信息广播到元数据服务器的无效列表。

3.2 访问内容解耦分区

在本节中，我们首先解释为什么要分离访问和内容元数据。然后，我们展示了如何通过分组实现元数据局部性，以及如何通过分区实现负载平衡。最后，我们展示了如何将元数据存储在键值对中。

解耦目录元数据。如§2.2所述，以前的细粒度和粗粒度分区未能同时实现高元数据局部性和良好的负载平衡。本质上，根本原因是它们将目录元数据视为一个整体。因此，在对目录树进行分区时，他们必须将目录从父目录或子目录拆分到不同的服务器，这会无意中破坏相关元数据的位置。

我们分析了目录元数据的组成，发现目录元数据由两个独立的部分组成：访问和内容。如图3（b）所示，access元数据包含用于访问目录树的目录名、ID和权限。内容元数据包含与子项相关的条目列表、时间戳等。因此，我们建议将目录元数据分解为访问和内容，以便对元数据局部性和负载平衡两部分进行独立分组和分区。

按局部性分组。我们将相关的元数据对象分组到同一个元数据服务器，以实现元数据处理阶段的高局部性。我们首先分析各种元数据操作的元数据需求，确定元数据处理过程中相关的元数据对象。我们将元数据操作分为以下三类：

只处理目标文件或目录元数据的操作，例如打开、关闭和统计。例如，文件统计将只读取目标文件的元数据。
处理目标文件或目录及其父级元数据的操作，例如创建、删除和读取目录。例如，文件创建将首先插入文件元数据，然后锁定并更新父目录的条目列表和时间戳。
重命名操作很特殊，因为它处理两个文件或目录及其父目录的元数据。

我们观察到，在元数据处理过程中，大多数元数据操作（类别1和类别2）都需要目标文件或目录和父目录中的元数据。使用解耦的目录元数据，我们将每个目录的内容元数据与其子目录的访问元数据和文件元数据分组，如图3（c）所示。通过这种方式，我们将目录树拆分为独立的每个目录组，以便以后进行分区，同时为目录readdir和文件create/delete/open/close/stat/set_permission操作保留元数据位置。根据元数据操作的相对频率（表1），这些操作占∼90%的业务。因此，INFINIFS为大多数元数据操作实现了较高的局部性。

用于负载平衡的分区。我们进一步在细粒度级别对目录树进行分区，以实现良好的负载平衡。基于位置感知元数据分组，我们将目录树拆分为独立的每个目录组，然后通过散列目录ID将这些组划分到不同的元数据服务器。这种细粒度散列分区有效地平衡了元数据操作[28]。

我们在图3（c）中演示了分区。元数据组（包含C的内容元数据以及f1和f2的元数据）被划分到元数据服务器1。这样，在C下create的文件只需要元数据服务器1中的本地事务来插入新的文件元数据，然后更新C的条目列表和时间戳。而C上的readdir只需要元数据服务器1首先锁定目录条目列表进行隔离，然后从条目列表中读取文件名。

INFINIFS还利用一致散列[29]将这些细粒度元数据组映射到服务器，以便在集群扩展或收缩期间最小化迁移。

存储。我们使用KV store作为后端存储来实现访问内容解耦分区。表2详细介绍了键值索引模式，它由三种键值对组成，两种用于目录访问和内容元数据，一种用于文件元数据。要解析/A/B/file（令/、A和B的ID分别为0、1和2），我们首先使用⟨0，A⟩ 作为获取A的访问元数据的密钥，并发现A的ID等于1。然后，我们使用⟨1，B⟩ 获取B的访问元数据，并发现B的ID等于2。最后，我们使用⟨2⟩ 获取B的内容元数据，以及⟨2、file⟩获取file的元数据。

3.3 推测路径解析

在本节中，我们首先介绍如何生成可预测的目录标识符（§3.3.1）。然后，我们描述了如何将路径分辨率与推测并行化（§3.3.2）。

3.3.1 可预测的目录ID

在这里，我们将介绍INFINIFS如何生成和维护可在以后从路径名预测的目录ID。

1）creating。创建一个新目录时，我们通过散列其出生三元组来生成该目录的ID：⟨①父ID，②目录名，③名称版本⟩, 如图4（a）所示。创建目录的父目录称为目录的出生父目录。我们使用这个版本来保证出生三元组的普遍唯一性。

2）renaming。将目录重命名到另一个位置时，只需更新其访问元数据的密钥；其内容元数据和ID保持不变，因此目录下的所有子体元数据保持不变。目录创建后首次重命名时，其出生父目录将记录rename-list（RL）：⟨①目录名，②名称版本⟩, 目录本身将记录一个back-pointer（BP）：⟨①出生父母的ID，②姓名版本⟩。目录的RL记录了在该目录中生成但已移动到其他地方的子目录。重命名目录（即已从其出生父目录移到其他位置的目录）的BP指向其出生父目录。我们在目录创建中使用父级的RL来确定名称版本。例如，图4（b）显示了b第一次被重命名时的重命名（/A/B，/B）。B的访问元数据的密钥从2:B更新为1:B，而B的ID保持不变。A记录RL⟨B，0⟩ 在与其内容元数据相同的服务器上。B记录BP⟨2，0⟩ 在其访问元数据中。此时，如果在/A下创建一个新的B，它的名称版本应该是1，因为/A的RL表示存在一个在这里出生的重命名B。再次重命名目录时，只需更新其访问元数据的键，而其内容元数据BP和出生父级的RL保持不变。删除重命名目录的出生父目录时，出生父目录的访问和内容元数据将被删除，但出生父目录的RL将被保留。只有在删除重命名的目录时，才会通过BP删除RL。

3）deleting。当删除重命名的目录时，我们使用该目录的BP来删除其出生父目录的RL，如图4（c）所示。此时，如果在/A下创建一个新的B，其名称版本将返回默认的零。

身份唯一性。在这里，我们首先展示可预测的目录ID是普遍唯一的，然后展示哈希冲突非常罕见，INFINIFS可以正确地检测和处理它们。目录ID是通过散列出生三元组生成的，因此如果每个出生三元组都是唯一的，则该ID也应该是唯一的，除非发生散列冲突。文件系统语义要求同一父目录中的两个目录在任何时候都不具有相同的名称。没有目录重命名，⟨亲生父母的ID、目录名⟩ 足以成为全局唯一的。当在其他地方重命名目录时，允许在同一父目录中创建具有相同名称的新目录。如前所述，我们使用一个版本号来解决目录重命名问题，从而保证每个出生三元组都是唯一的。我们使用加密哈希（例如SHA256）生成ID，因此发生冲突的可能性非常小。由于目录ID是每个目录的内容元数据的密钥，因此在创建目录期间插入新的内容元数据时，我们可以很容易地检测到哈希冲突。我们使用版本号、RL和BP，以与重命名相同的方式处理哈希冲突。在INFINIFS中，冲突和重命名情况对后续目录创建具有相同的影响，可以通过RL条目格式进行区分。

3.3.2 并行路径解析

基于可预测的目录ID，客户端可以通过以下两个步骤并行执行路径解析：

预测目录ID。客户端通过使用路径或子路径的根ID来预测所有中间目录的ID。它首先用0作为版本号重建出生三元组，然后重新计算哈希结果。使用推测的目录ID，客户机为所有路径组件重建密钥。
并行查找。客户端并行发送所有中间目录的查找请求。每个查找请求都将检查访问权限，并将推测的ID与元数据服务器中存储的ID进行比较。如果推测的ID与服务器上的ID不匹配，则查找请求会将真实ID返回给客户端。
重复步骤1）和2），直到解析完成。

图5展示了推测路径解析机制。如果其中一个中间目录曾重命名为此处，则重命名目录的推测ID将是错误的（即h（2，X，0）≠ 12). 但是，查找请求可以使用正确的键2:X找到X的访问元数据，并将目录的真实ID返回给客户端。如果真实ID为X，客户端将继续解析X下的子路径。

3.4 乐观访问元数据缓存

在本节中，我们首先展示INFINIFS如何在客户端缓存中组织目录访问元数据。然后，我们介绍了客户端如何乐观地使用缓存项，以及元数据服务器如何惰性地使过时的缓存项无效。

缓存结构。INFINIFS只在客户端缓存目录访问元数据（即目录名、ID和权限）。缓存命中将消除对近根目录的查找请求，从而避免根目录附近的热点，并确保可扩展的路径解析。如图6所示，INFINIFS基于文件系统层次结构以树状结构组织缓存项，并将叶条目链接为最少使用（LRU）列表。当发生缓存替换时，最近使用最少的叶条目将被逐出，以确保近根目录保持缓存状态。

惰性无效化。在目录重命名或目录设置权限操作后，许多缓存项都会过时。在每次目录重命名操作期间，使所有关联客户端上的过时缓存项无效是不切实际的。因为客户机的成员身份很难管理，而且客户机的数量可能很大，远远超过元数据服务器的数量。惰性失效通过将失效信息广播到元数据服务器（其数量明显少于客户机）来解决这个问题，这样每个服务器在处理客户机请求时都可以惰性地验证缓存过时性。具体来说，目录重命名将联系中心重命名协调员以防止孤立循环（§4.1），然后将重命名信息广播到元数据服务器。单个协调服务器应该足以处理这些不频繁的操作，因为很少发生目录重命名操作（仅∼0.0083%），基于§2.3中的实际工作量研究。

如图7（a）所示，INFINIFS通过以下过程处理目录重命名：

INFINIFS将目录重命名操作发送给重命名协调器，以检测此目录重命名是否会与正在运行的循环产生孤立循环。然后，协调器为每个目录重命名操作分配一个增量版本号。
INFINIFS通过锁定目标目录，将目录重命名与其他操作序列化，以便在重命名完成之前阻止对子树的新访问。然后，它将重命名信息及其版本并行地广播到元数据服务器，并等待确认。元数据服务器在按版本排序的无效列表中维护重命名信息。
INFINIFS将目录的访问元数据从源服务器移动到目标服务器，并在首次重命名目录时更新RL和BP。

如图7（b）所示，INFINIFS通过以下方式在服务器上惰性地验证缓存过时性：

INFINIFS客户端对过时性不可知，并在路径解析期间乐观地利用本地缓存项。每个客户端都有一个本地版本，这表明其缓存在该版本之前已通过重命名操作进行了更新。当客户端联系元数据服务器时，它会发送请求以及路径名和版本。
元数据服务器通过比较路径名和无效列表中的重命名操作来验证过时性。只需比较请求版本和失效列表中最新版本之间的操作。如果服务器发现请求的路径名有效，则会成功处理并返回请求。
如果服务器发现请求无效，它将中止请求并返回这些新重命名操作的信息。然后，客户端更新缓存和版本。

4. 一致性

在本节中，我们将介绍INFINIFS如何防止目录重命名操作（§4.1）导致的孤立循环，以及如何实现事务元数据操作（§4.2），以确保文件系统目录树的一致性。

4.1 孤立循环

并发目录重命名可能会导致孤立循环，从而导致服务器数据丢失。图8显示了由两个目录重命名引起的这种孤立循环。如图8（a）所示，文件系统目录树应该是连接的、非循环的。在图8（b）和8（c）中，Client1尝试将E重命名为C的子级，而Client2尝试将B重命名为F的子级。两次重命名所需的元数据对象完全独立，因此允许并行执行。但它们会导致一个孤立的循环，它会破坏目录树，如图8（d）所示。没有客户端可以访问孤立循环中的任何文件。

INFINIFS通过在执行每个目录重命名操作之前使用中心重命名协调器检查每个目录重命名操作来解决孤立循环问题。重命名协调器维护一个重命名图，该图跟踪当前正在进行的目录重命名的源路径和目标路径。在允许新的目录重命名操作继续之前，重命名协调器首先验证它是否会导致与正在运行的循环之间的孤立循环。在整个重命名过程中，目录重命名操作的源路径和目标路径保留在重命名图中，并在重命名操作完成后删除。

目录重命名操作很少发生（占不到∼ 0.0083%），基于§2.3中的实际工作量研究。因此，一个重命名协调器应该足以处理目录重命名操作。

4.2 事务元数据操作

INFINIFS中的操作可分为三种类型：

1）单服务器操作。这些操作包括目录readdir和文件create/delete/open/close/stat/set_permission，这是最常见的操作。它们在单个元数据服务器中处理元数据对象。单服务器操作利用键值存储后端的事务机制来保证原子性。当元数据服务器在崩溃后重新启动时，它会恢复元数据操作的事务，并咨询重命名协调器以更新其失效列表。

2）双服务器操作。这些操作包括目录mkdir/rmdir/statdir和文件rename。它们跨两个元数据服务器处理元数据对象，需要分布式事务来保证正确的行为。INFINIFS采用两阶段提交协议[21,24,31]来实现服务器间更新的原子性。由于客户端不可靠且难以跟踪，因此选择两个元数据服务器中的一个作为事务的协调器。为了从失败中恢复，协调器和参与者都使用预写日志记录来记录事务的部分状态。

3）目录重命名操作。目录rename和目录set_permission操作很少发生。这些操作被委派给重命名协调器，该协调器检测孤立循环，将修改广播到所有元数据服务器，并跨两个服务器处理目标目录元数据。这些操作是通过类似于两个服务器操作的分布式事务实现的，不同之处在于它们选择重命名协调器作为事务中的协调器，并在提交阶段开始时广播修改。如果重命名协调器在广播过程中崩溃，它将通过重新启动广播来重新启动和恢复事务，以确保修改至少传递到所有服务器一次。

5. 评估

6. 相关工作

高效的分布式文件系统一直是重要的研究课题。由于文件数量迅速增加，元数据服务成为大规模分布式文件系统的性能瓶颈[22、32、33、36]。

目录树分区。早期的分布式文件系统，如GFS[12]、HDFS[35]、Farsite[11]和QFS[27]，将文件数据分发到多个数据服务器，同时在单个专用元数据服务器中管理所有元数据。然而，它们在具有数十亿文件的超大规模场景中失败，因为元数据的数量超过了单个服务器的容量，并且由于资源有限，元数据操作的吞吐量将受到限制。

一些分布式文件系统将目录树划分为子树，如AFS卷[15]、Sprite域[26]和HDFS联合[9,35]。基于子树的元数据分区可以实现较高的元数据局部性，但由于负载不平衡和数据迁移，其可扩展性较低。一些分布式文件系统将目录树划分为用户可见的分区，并且不允许跨分区重命名。随着目录树的扩展，组织和维护静态分区方案变得不切实际。Cepfs[6,39–41]也将元数据划分为子树，但当检测到负载不平衡时，它会跨元数据服务器迁移热子树。Mantle[34]提供了一个可编程接口，用于调整CEPFS针对各种元数据工作负载的平衡策略。然而，当工作负载多样且频繁变化时，它们会受到频繁元数据迁移的高开销的影响。

一些分布式文件系统按照每个目录的粒度对目录树进行分区，例如IndexFS[31,46]、HopsFS[25]和Structural[28]。由于细粒度分区，它们可以实现负载平衡和良好的可扩展性。然而，它们牺牲了元数据的局部性，导致频繁的分布式锁和分布式事务。这些分布式协议带来了昂贵的协调开销，导致高延迟和低吞吐量[8,20]。

路径解析。LocoFS[23]将所有目录元数据存储在单个元数据服务器上，以减少路径解析的延迟，但它存在单节点瓶颈。一些分布式文件系统使用完整路径名或完整路径名上的哈希来索引文件，例如BetrFS[17,18,44,45]、Giraffa[37]和CalvinFS[38]。BetrFS使用完整路径名为本地文件系统中的文件编制索引。Giraffa使用完整路径名作为文件元数据的主键。CalvinFS通过散列完整路径名来定位文件元数据。然而，它们使得层次语义难以实现。例如，目录重命名操作成本过高，因为它会更改所有子体的完整路径名，导致所有子体的元数据必须迁移到新位置。

客户端元数据缓存。HopsFS在服务器端缓存元数据位置信息，以实现并行路径解析。但是，它会受到近根热点的影响，因为所有元数据操作都需要读取近根目录以进行路径遍历和权限检查。LocoFS[23]、IndexFS[31]和NFS v4[30]利用租用机制在客户端缓存目录项和权限。但是，租约机制会因近根目录的缓存续订而导致负载不平衡。随着客户端数量的增加，近根目录上的这种负载不平衡将成为性能瓶颈，影响总体吞吐量。

7. 总结

本文介绍了INFINIFS，这是一种用于超大规模分布式文件系统的高效元数据服务。INFINIFS将目录的访问和内容元数据解耦，因此可以使用高元数据局部性和良好的负载平衡对目录树进行分区；然后将路径解析与推测并行，以大幅减少元数据操作的延迟；最后，通过延迟失效，在客户端乐观地缓存访问元数据。广泛的评估表明，INFINIFS为大规模文件系统目录树提供了高性能元数据操作。