地理复制文件系统的可用性和管理一致性

70 浏览量更新于2023-12-04 收藏 13.06MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

Vinh TAO THANH0皮埃尔和玛丽居里大学博士学位论文0专业：计算机科学0博士学位授予学校：皮埃尔和玛丽居里大学0完成于：巴黎第六大学计算机实验室和Scality0提交人：0以获得：0皮埃尔和玛丽居里大学博士学位0论文题目：0确保可用性和管理一致性0地理复制文件系统0答辩日期：0在以下评审委员会面前答辩：0Mme. Sara BOUCHENAK 评审员0M. Pascal MOLLI 评审员0Mme. Annette BIENIUSA 评审员0Mme. Julia LAWALL 评审员0M. Vivien QUEMA 评审员0M. Vianney RANCUREL 博士论文联合导师0M. Marc SHAPIRO 博士论文联合导师i0摘要0地理分布式系统面临高延迟和网络分区的问题。由于没有延迟，并在后台传播它们。这种乐观复制面临一些异常情况。0为了实现这一点，并确保高可用性，这些系统通常在本地提交更新，并在后台传播它们。这种乐观复制面临着一些异常情况。0没有延迟，并在后台传播它们。这种乐观复制面临一些异常情况。0两个主要挑战：（i）检测并发更新之间的冲突并解决它们；（ii）支持不具备处理并发性的传统应用程序。0以对用户有意义的方式解决它们，同时保持系统完整性不变。0和（ii）支持不具备处理并发性的传统应用程序。0异常情况。0我们的博士研究针对一个大规模地理分布式文件系统的特定用例解决了这些挑战。0规模的地理分布式文件系统。这是一个很好的展示：确实，地理分布式文件系统是一个具有挑战性的案例。0我们的博士研究针对一个大规模地理分布式文件系统的特定用例解决了这些挑战。0（例如树结构）对并行更新的冲突是具有挑战性的；应用程序将文件系统视为一个整体，而不是一组独立的文件。0文件系统具有复杂的层次结构；在维护文件系统不变性的同时支持并发更新是具有挑战性的。0现有的乐观地理分布式文件系统无法解决这些挑战。0通过传统的POSIX API访问文件系统。0某些并发重命名的情况下；所有现有系统都使用自动解决方案。0挑战。例如，Dropbox不支持硬链接；Andrew文件系统在某些并发重命名的情况下失败。0我们在设计和实现中提出了解决上述问题的解决方案。0原型地理分布式文件系统Tofu的设计包括一个新的冲突解决方案，违反了传统的POSIX语义。0会话抽象以支持传统API，同时允许乐观更新。与以往的方法不同，我们的解决方案基于一个覆盖文件系统所有方面的形式化模型。0与以往的方法不同，我们的解决方案基于一个覆盖文件系统所有方面的形式化模型。0类Unix文件系统，包括目录、inode、硬链接等。它能够检测这些冲突，并以我们认为用户会发现合理的方式解决它们。0在这些数据结构上检测所有冲突，并以我们认为用户会发现合理的方式解决它们。0实验表明，Tofu具有高度可扩展性，并且在性能方面优于现有的学术和工业系统。0增加了线性开销，改进了现有的学术和工业系统。0关键词：复制、地理分布、文件系统、最终一致性、CRDT、异常情况。0冲突解决2.1.1Inode Stat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.1.2Inode Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.1.3Inode Names. . . . . . . . . . . . . . . . . . . . . . . . . . . . .92.2File System Structure. . . . . . . . . . . . . . . . . . . . . . . . . . . .102.3File System Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.3.1Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.3.2Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .123File System Operations153.1Preliminaries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153.1.1Helper Functions . . . . . . . . . . . . . . . . . . . . . . . . . . .153.1.2Path Resolution. . . . . . . . . . . . . . . . . . . . . . . . . . .153.2Read Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .163.3Modiﬁcation Operations . . . . . . . . . . . . . . . . . . . . . . . . . . .173.3.1create . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .173.3.2mkdir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183.3.3link . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183.3.4setattr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193.3.5write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203.3.6unlink . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203.3.7rmdir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203.3.8rename . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22iii0目录01 引言 10I 顺序语义 502 顺序文件系统模型 702.1 文件系统数据对象 . . . . . . . . . . . . . . . . . . . . . . . . . . 7ivTABLE OF CONTENTS3.3.9Other Operations . . . . . . . . . . . . . . . . . . . . . . . . . . .22IIConcurrency Semantics274Concurrency Model294.1Replication in Distributed File Systems. . . . . . . . . . . . . . . . . .294.2Concurrency Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .305Sessions335.1start_session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .335.2connect_session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .345.3finish_session. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .356Conﬂicts376.1Issues Of Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . .376.2Conﬂict Deﬁnition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .386.3Types Of Conﬂict . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .386.4Direct Conﬂict Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . .396.4.2Update-Update Concurrency On Files . . . . . . . . . . . . . . .396.5Indirect Conﬂict Case. . . . . . . . . . . . . . . . . . . . . . . . . . . .416.5.2Indirect Conﬂict Detection . . . . . . . . . . . . . . . . . . . . . .427.1Conﬂict Resolution Principles . . . . . . . . . . . . . . . . . . . . . . . .457.2.1Delete-Update Conﬂict . . . . . . . . . . . . . . . . . . . . . . . .477.2.2File Data-Data Conﬂict. . . . . . . . . . . . . . . . . . . . . . .487.2.3File Names-Names Conﬂict. . . . . . . . . . . . . . . . . . . . .497.2.4Directory Data-Data Conﬂict . . . . . . . . . . . . . . . . . . . .497.2.5Directory Names-Names Conﬂict . . . . . . . . . . . . . . . . . .517.3Conﬂict Resolution For Indirect Conﬂicts. . . . . . . . . . . . . . . . .528Replica Convergence558.1CRDTs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .558.1.1CRDT Principles for State-based Replication . . . . . . . . . . .5506.4.1 所有inode类型的常见并发情况 . . . . . . . . . . . . . . . . . . . . 3906.4.3 目录上的更新-更新并发 . . . . . . . . . . . . 4006.5.1 间接冲突的定义 . . . . . . . . . . . . . . . . . . . . . 4107 冲突解决 4507.2 直接冲突的解决方法 . . . . . . . . . . . . . . . . . . . 46TABLE OF CONTENTSv8.1.2Replica Convergence Using CRDT . . . . . . . . . . . . . . . . .568.2Ensuring Commutativity . . . . . . . . . . . . . . . . . . . . . . . . . . .578.2.1Deterministic File Name Generation . . . . . . . . . . . . . . . .578.2.2Deterministic Inode Number Generation . . . . . . . . . . . . . .588.2.3Deterministic Directory Merge. . . . . . . . . . . . . . . . . . .588.3Ensuring Associativity . . . . . . . . . . . . . . . . . . . . . . . . . . . .588.3.1Delete-Update Dectection Issue and Delete Marker . . . . . . . .598.3.2Concurrency Cases Between Three Updates . . . . . . . . . . . .598.3.3Associativity For Causally Related Updates . . . . . . . . . . . .598.3.4Associativity For Full Concurrency On Inodes . . . . . . . . . . .608.3.5Associativity For Concurrency On Mapping Entries . . . . . . . .64IIIImplementation And Evaluation679Implementation699.1Metadata-Data Decoupling. . . . . . . . . . . . . . . . . . . . . . . . .699.2Directory Data Layout in the Metastore . . . . . . . . . . . . . . . . . .709.2.1Directory Inode-Data Decoupling . . . . . . . . . . . . . . . . . .719.2.2Advantages and Disadvantages. . . . . . . . . . . . . . . . . . .729.3Session Data Layout in the Metastore. . . . . . . . . . . . . . . . . . .729.3.1Object Versioning in the Metastore . . . . . . . . . . . . . . . . .729.3.2Object Versioning With Version Vectors . . . . . . . . . . . . . .739.4Committing a Session. . . . . . . . . . . . . . . . . . . . . . . . . . . .749.4.2Committing with Fine-Grain Locking. . . . . . . . . . . . . . .7510.1 Basic Conﬂict Resolutions . . . . . . . . . . . . . . . . . . . . . . . . . .7710.3 Micro-Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8210.3.2 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8210.3.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8411.1 Distributed File Systems By Consistency . . . . . . . . . . . . . . . . . .8909.4.1 使用序列器提交 . . . . . . . . . . . . . . . . . . . 75010 评估 77010.2 冲突解决性能 . . . . . . . . . . . . . . . . . . . . . . . 80010.3.1 实验设置 . . . . . . . . . . . . . . . . . . . . . . . . . 82010.3.3 工作负载 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83011 之前的工作 8911.1.1 Strongly-Consistent Distributed File Systems . . . . . . . . . . .8911.1.2 Eventually Consistent Distributed File Systems . . . . . . . . . .9011.1.3 Consistency-Tunable Distributed File Systems . . . . . . . . . . .9111.2 State-Based And Operation-Based Approaches. . . . . . . . . . . . . .9111.3 Namespace-Based and Inode-Based Approaches . . . . . . . . . . . . . .9211.3.1 The Namespace Approach . . . . . . . . . . . . . . . . . . . . . .9211.3.2 The Inode Approach . . . . . . . . . . . . . . . . . . . . . . . . .9311.4 Other Conﬂict Resolution Systems . . . . . . . . . . . . . . . . . . . . .9311.4.1 Merging framework . . . . . . . . . . . . . . . . . . . . . . . . . .9311.4.2 Version control systems. . . . . . . . . . . . . . . . . . . . . . .9311.4.3 Database Systems. . . . . . . . . . . . . . . . . . . . . . . . . .9411.4.4 Collaborative Text Editing Systems . . . . . . . . . . . . . . . . .9412 Conclusions and Future Work97A Merging Inode stat109B Résumé de la thèse111B.1Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111B.2Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112B.3Modèle de système de ﬁchiers . . . . . . . . . . . . . . . . . . . . . . . . 114B.3.1Métadonnées d’un nœud d’index. . . . . . . . . . . . . . . . . . 114B.3.2Données d’un nœud d’index . . . . . . . . . . . . . . . . . . . . . 115B.3.3Noms d’un nœud d’index. . . . . . . . . . . . . . . . . . . . . . 116B.4Structure du système de ﬁchiers . . . . . . . . . . . . . . . . . . . . . . . 116B.5Invariants du système de ﬁchiers. . . . . . . . . . . . . . . . . . . . . . 117B.5.1Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117B.5.2Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118B.6Cas de Conﬂit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119B.6.1Déﬁnition d’un conﬂit . . . . . . . . . . . . . . . . . . . . . . . . 119B.6.2Types de conﬂict . . . . . . . . . . . . . . . . . . . . . . . . . . . 120B.7Résolution des conﬂits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122B.7.1Principes de résolution de conﬂit . . . . . . . . . . . . . . . . . . 122B.7.2Détails de résolution de conﬂit. . . . . . . . . . . . . . . . . . . 124B.8Convergence de réplique . . . . . . . . . . . . . . . . . . . . . . . . . . . 127B.8.1CRDTs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127B.8.2Convergence de répliques à l’aide du CRDT . . . . . . . . . . . . 127B.8.3Assurer la commutativité. . . . . . . . . . . . . . . . . . . . . . 1290vi 目录B.8.4Assurer l’associativité. . . . . . . . . . . . . . . . . . . . . . . . 1310目录 vii0B.9 评估。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136List of Figures2.2File system model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1102.1 iNode模型。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.1 并发模型。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3005.1 访问实现示例06.1 并发重命名操作创建的间接冲突示例07.1 解决inode删除-更新冲突07.2 使用不同方法解决文件数据-数据冲突的示例07.3 文件命名冲突的合并语义07.4 目录数据-数据冲突的冲突解决07.5 目录名称-名称冲突的冲突解决07.6 间接冲突的合并语义09.1 使用键值存储抽象实现元数据的示例0tion09.2 元数据版本化实现示例09.3 使用顺序器的示例010.1 评估Dropbox和Tofu010.2 用于评估的系统基准010.3 延迟的实验结果010.4 会话期间的延迟010.5 会话事件的时间线0ix0表格列表06.1 所有inode类型的常见直接并发情况06.2 目标为文件时的直接更新-更新并发情况06.3 目标为目录时的直接更新-更新并发情况07.1 映射条目上的并发情况08.1 索引节点上三个更新之间的并发情况08.2 索引节点上三个更新之间的并发情况010.1 使用商业系统评估我们的合并语义0B.1 映射条目上的并发情况0B.2 索引节点上三个更新之间的并发情况0xi0算法列表01 路径解析02 遍历树03 创建空普通文件04 创建空目录05 创建文件的硬链接06 更新inode的属性07 更新文件的数据08 删除文件09 删除目录010 重命名目录011 重命名文件012 合并inode的st_mode013 合并 inode 的 st_gid 和 st_uid . . . . . . . . . . . . . . . . . . . . . . 1100xiii10第1章0引言0地理分布式文件系统通常跨越多个远程副本。0地理分布式文件系统的副本之间的网络带宽和延迟有限，特别是与副本内部的通信相比。为了使用户体验到低延迟，需要采取措施来减少网络延迟。0特别是与副本内部的通信相比，地理分布式文件系统的副本之间的网络带宽和延迟较大。0为了实现高可用性，地理分布式文件系统必须解决一致性和可用性之间固有的权衡。0一致性和可用性之间的固有权衡，这是CAP定理[6, 22]所强调的。0许多大规模的地理分布式文件系统选择采用最终一致性（EC）的方法。0方法[70, 72, 73]。在EC系统中，更新在其原始副本上本地提交，而不需要副本之间的协调。0在被传播到其他副本之前，更新会先在原始副本上异步地进行提交；EC确保当所有副本都接收并应用了彼此的所有更新时，它们将处于相同的状态。0所有副本都接收并应用了彼此的所有更新后，它们将处于相同的状态，从而确保用户体验到低延迟。0相同的状态。由于提交是本地的，没有副本之间的协调，用户可以在一个副本上进行修改，即使该副本保持长时间断开连接，从而实现低延迟。0这种EC方法必须处理来自不同副本的并发更新之间的冲突。0长时间断开连接，从而确保高可用性。0挑战：(i)检测（所有）并发更新之间的冲突；(ii)解决这些冲突，以便用户体验到低延迟。0面临两个主要挑战：(i)检测并解决并发更新之间的冲突；(ii)支持遗留应用程序，这些应用程序没有准备好处理并发异常情况。0支持遗留应用程序，这些应用程序没有准备好处理并发异常情况。0以有意义的方式呈现给用户，同时保持系统完整性的不变性；以及(ii)支持遗留应用程序，这些应用程序没有准备好处理并发异常情况。0在地理分布式文件系统中检测和解决冲突是困难的，因为这些系统的复杂性。0所在的位置。0目录树的结构。目录可以包含其他目录或文件；然而，文件系统受到严格的不变性规则的约束，例如目录中名称的唯一性或不存在循环。0复杂的层次结构。文件系统通常由目录树组成；目录可以包含其他目录或文件；然而，文件系统受到严格的不变性规则的约束，例如目录中名称的唯一性或不存在循环。0由于这种复杂系统中检测和解决冲突的困难，现有的方法通常放弃一些系统不变性，或者限制冲突的检测范围。0由于硬链接的存在，文件可以包含在多个目录中。这种复杂的结构增加了解决冲突的难度。0通过忽略硬链接、将多个链接视为不同的文件来简化文件系统模型。0目录循环的存在。0因此，由于这种复杂系统中检测和解决冲突的困难，现有的方法通常放弃一些系统不变性，或者限制冲突的检测范围。0第2章引言0通过忽略一些系统不变性，或者限制冲突的检测范围，来简化文件系统模型。0检测和解决能力。一些系统，包括Dropbox [13]或Unison [3]，通过简化文件系统模型来简化冲突检测和解决。0通过忽略硬链接、将多个链接视为不同的文件来简化文件系统模型。0使它们看起来像是不同的文件，从而导致文件系统副本的分歧，并且不必要地增加了网络/存储的使用量。0网络/存储的使用量。其他一些系统，包括Ficus [56]、Coda [30]或Microsoft OneDrive [37]，将涉及冲突的目录和文件移动到特殊目录中，期望用户手动解决问题。0OneDrive [37]将困难冲突案例的协调工作留给用户；他们可能会将涉及冲突的目录和文件移动到特殊目录中，从而导致文件系统副本的分歧。0以期望用户手动解决问题的方式，将涉及冲突的目录和文件移动到特殊目录中。0手动解决问题。其他一些系统，包括AFS [26]和Google Drive [23]，选择了手动解决困难冲突案例的方式。0以选择任意更新来解决冲突的简单的最后写者胜（LWW）方法。0以取胜于冲突的方式来解决问题；这种方法放弃了更新的持久性。0此外，现有的EC地理分布式文件系统不支持遗留应用程序。0应用程序良好地运行。这些系统会在意外情况下自动更改文件系统。0适应这种行为的遗留应用程序是困难的，因为它们可能会在不同的时间和以非直观的方式进行更新。0行为将需要复杂的逻辑。例如，当两个用户同时写入0到同一个文件时，Dropbox和Google Drive通过创建新的0带有任意名称的文件；即使在文件处于活动状态时也可能发生0使用。传统应用程序无法应对这种突然和不可预测的0更改。0这篇论文解决了这些问题：支持并发更新和兼容性0与传统应用程序的兼容性。因此，我们设计了一个地理分布式文件系统0名为Tofu。我们的贡献如下。01.冲突检测和解决机制的设计和实现，该机制0根据我们的正式文件系统模型（第02和3），支持所有文件系统组件，包括硬链接和我们的0冲突解决语义（第7章和第8章），保留所有并发更新的0同时呈现有意义的冲突解决结果。Tofu的实现0（第9章）基于冲突自由复制数据类型（CRDT）的概念066]以确保收敛和正确性。02.会话概念将传统POSIX应用程序与意外的自动化隔离开来0文件系统中的自动更改。我们的会话系统（第4章和第5章）将0使用分布式文件系统的会话。会话是一种长事务的一种，0在其中，应用程序可以享受传统POSIX的强顺序语义0文件系统。多个会话可以同时存在，每个会话都与其他会话隔离开来0其他。一个会话在开始时对整个文件系统进行一致的快照0在开始时对整个文件系统进行一致的快照，并在结束时将其所有更改原子地合并到文件系统中。Tofu0自动解决提交会话和其他会话之间的并发更新30任何先前提交的会话。只有在自动化无法解决的情况下才需要手动干预0冲突解决已经进行了不兼容应用程序的更改0后续会话。这样的手动干预仅限于重命名目录和文件。03.实验结果显示我们的方法与现有方法相比的完整性0与冲突解决能力相关的现有系统。通过实验我们展示了0（第10章）Tofu检测和解决所有冲突，包括那些0以前的系统存在困难。Tofu的会话系统能够提供低延迟0最终一致性方法的更新延迟。我们还展示了0会话的提交对其他正在进行的会话的延迟影响最小。

下载后可阅读完整内容，剩余1页未读，立即下载