计算机科学２００４Ｖｏ１．３１Ｎ￣－．１２ ＤＣＲ２Ｓ：分布式协作冗余复制存储机制 周旭卢显良魏青松 （电子科技大学计算机学院 成都６１００５４） 摘要文件复制和编码校验是分布式文件容错中常用的方法。结合两者的优点，本文提出了一种分布式协作冗余复 制存储机制（ＤＣＲ。Ｓ）。ＤＣＲ０Ｓ通过Ｘ０Ｒ校验文件实现了分布在不同主机上的多个文件之间的相互协作，使得各个文 件不仅可以通过复制冗余复本来提高自身的客错抗毁性能，并且可以通过检验文件协助其他文件提高容错性，既提高 了单个文件的容错性能，更大大提高了一组文件的整体客错性能。本文对ＤＣＲ０Ｓ的原理进行了图论表述，给出了概率 计算公式，定量地分析了ＤＣＲ Ｓ的容错性能。通过计算比较，ＤＣＲ０Ｓ的容错性能远高于完全复制。 关键词分布式，容错，冗余，协作，图论，校验 ＤＣＲ Ｓ：Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｏｐｅｒａｔｉｖｅ Ｒｅｄｕｎｄａｎｃｙ Ｒｅｐｌｉｃａｔｉｏｎ Ｓｔｏｒａｇｅ Ｍｅｃｈａｎｉｓｍ Ｚｈｏｕ Ｘｕ ＬＵ Ｘｉａｎ－－Ｌｉａｎｇ ＷＥＩ Ｑｉｎｇ－·Ｓｏｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ｏｆ ＵＥＳＴ ｏｆ Ｃｈｉｎａ。Ｃｈｅｎｇｄｕ ６１００５４） Ａｂｓｔｒａｃｔ Ｆｉｌｅ ｒｅｐｌｉｃａｔｉｏｎ ａｎｄ ｃｏｄｉｎｇ ａｒｅ ｔｗｏ ｃｏｍｍｏｎ ｍｅｔｈｏｄ ｕｓｅｄ ｉｎ ｆａｕｌｔ—ｔｏｌｅｒａｎｃｅ ０ ｄｉｓｔｒｉｂｕｔｅｄ ｆｉｌｅ ｓｙｓｔｅｍｓ． Ｃｏｍｂｉｎｉｎｇ ｔｈｅ ａｄｖａｎｔａｇｅ ｏｆ ｒｅｐｌｉｃａｔｉｏｎ ａｎｄ ｃｏｄｉｎｇ，ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｎｏｖｅｌ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｏｐｅｒａｔｉｖｅ ｒｅｄｕｎｄａｎｃｙ ｒｅｐｌｉｃａｔｉｏｎ ｓｔｏｒａｇｅ ｍｅｃｈａｎｉｓｍ（ＤＣＲ。Ｓ）．Ｂｙ ｕｓｉｎｇ ＸＯＲ ｃｏｄｉｎｇ，ＤＣＲ。Ｓ ｍａｋｅｓ ａ ｇｒｏｕｐ ｏｆ ｆｉｌｅｓ ｗｈｉｃｈ ｄｉｓｔｒｉｂｕｔｅｄ ａ． ｍｏｎｇ ｄｉｆｆｅｒｅｎｔ ｈｏｓｔｓ ｃｏｏｐｅｒａｔｉｖｅ，ＳＯ ｔｈａｔ ｎｏｔ ｏｎｌｙ ａ ｓｉｎｇｌｅ ｆｉｌｅ ｉｎ ｔｈｅ ｇｒｏｕｐ ｃａｎ ｕｓｉｎｇ ＸＯＲ ｆｉｌｅｓ ｔｏ ｉｍｐｒｏｖｅ ｉｔｓ ｏｗｎ ａｖａｉｌａｂｉｌｉｔｙ，ｂｕｔ ａｌｓｏ ｔｈｅ ｔｏｔａｌ ａｖａｉｌａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｗｈｏｌｅ ｇｒｏｕｐ ｃａｎ ｂｅ ｉｍｐｒｏｖｅｄ ｇｒｅａｔｌｙ．Ｕｎｄｅｒ ｔｈｅ ｇｒａｐｈ ｔｈｅｏｒｙ ｄｅ． ｓｃｒｉｐｔｉｏｎ ｏｆ ＤＣＲ。Ｓ。ａｕｔｈｏｒ ｇｉｖｅｓ ａ ｑｕａｎｔｉｔａｔｉｖｅ ａｎａｌｙｓｉｓ ｔｏ ＤＣＲ。Ｓ’ｐｅｒＩｏｒｍａｎｃｅ．Ｃｏｍｐａｒｉｎｇ ｔｏ ｃｏｍｐｌｅｔｅ ｒｅｐｌｉｃａｔｉｏｎ ｍｅｔｈｏｄ。ＤＣＲ。Ｓ ｈａｓ ｍｕｃｈ ｈｉｇｈｅｒ ｆａｕｌｔ—ｔｏｌｅｒａｎｃｅ ｐｅｒｆｏｒｍａｎｃｅ． Ｋｅｙｗｏｒｄｓ Ｄｉｓｔｒｉｂｕｔｅｄ，Ｆａｕｌｔ—ｔｏｌｅｒａｎｔ，Ｒｅｄｕｎｄａｎｃｙ，Ｃｏｏｐｅｒａｔｉｖｅ，Ｇｒａｐｈ ｔｈｅｏｒｙ，Ｘ０Ｒ １ 引言 随着现代网络技术的不断发展以及计算机存储计算能力 的多个拷贝），同时还与其他一个或多个文件（协作文件）生成 ＸＯＲ校验文件。这些复本文件和校验文件被分布在系统中不 同的机器上。这样，即使一个文件所有的原始复本都不可获 得，仍然可以使用协作文件和校验文件通过计算恢复文件数 据，实现比单纯复制更好的文件容错性能。 本文第２节介绍ＤＣＲ。Ｓ的基本原理；第３节分析ＤＣＲ Ｓ 的容错性能；最后是结论和未来的工作。 的不断提高，使得在广域网内集合大量计算机的存储资源，构 建大规模的分布式网络文件存储系统成为可能。目前，很多研 究机构和公司都提出了各自不同的分布式网络文件系统结 构，其中比较著名的有ＦｒｅｅＨｅａｖｅｎ［！］，Ｆａｒｓｉｔｅ［ｚ］，０． ｃｅａｎＳｔｏｒｅｒ ，ＦＴＤＳＳＥ‘ 和ＰＡＳＴＥ。 等。 但是，随着系统规模的不断扩大。加入的机器不断增加， 在增加了整个系统资源数量的同时，也增加了文件系统管理 ２ ＤＣＲ Ｓ的基本原理 ２．１ 常见文件数据容错方法 的复杂度和不确定性。如何有效地提高分布在众多机器上的 文件数据的可靠性和可用性，使得存放在大量相互独立的计 完全复制、ＦＴＤＳＳ和Ｅｒａｓｕｒｅ Ｃｏｄｅｓ编码这几种文件数 据冗余容错方法原理各不相同，其空间复杂度、编码效率、文 件容错性、读写效率也是各有千秋［７］。完全复制思想简单，将 文件的多个复本分布到不同的机器上实现冗余容错，复本管 理的空间复杂度小，且不涉及编码运算，效率高，容错性能较 算机上的资源得到更加安全高效的利用，已经成为大规模分 布式存储系统中重要的研究课题之一。 为了获取文件的高可用性和高容错性，将文件数据进行 各种形式的冗余并分布在存储网络中多个节点上是目前使用 得最多的方法之一。很多系统都是基于这种思想：ＰＡＳＴ和 好，但是要想提高文件的容错性能。只能通过增加文件的冗余 度来实现，占用存储资源较多；ＦＴＤＳＳ将文件分片，并在这些 分片之间相互进行异或运算，再将原始数据片和校验片分布 到不同的机器上实现数据的容错，其使用的ＸＯＲ编码效率 高，容错性能较好，但是最后生成校验分片过多，增加了文件 Ｆａｒｓｉｔｅ采用了完全复制（Ｃｏｍｐｌｅｔｅ ｒｅｐｌｉｃａｔｉｏｎ）的方式； ＦＴＤＳＳ采用了文件分块（ｓｅｇｍｅｎｔ）加ｘＯＲ校验的方式； ＦｒｅｅＨｅａｖｅｎ和ＯｃｅａｎＳｔｏｒｅ则采用了文件分块加Ｅｒａｓｕｒｅ Ｃｏｄｅｓ编码 。 管理的空间复杂度，且要提高文件的容错性能，只能更加细分 文件分块，这会导致占用的存储资源和空间复杂度快速上升； Ｅｒａｓｕｒｅ Ｃｏｄｅｓ也是采取的文件分块校验、分片存储的方法， 与ＦＴＤＳＳ不同的是它的校验分块是由原始数据分块经过 本文提出了一种新颖的分布式协作冗余复制存储机制 ＤＣＲ。Ｓ（Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｏｐｅｒａｔｉｖｅ Ｒｅｄｕｎｄａｎｃｙ Ｒｅｐｌｉｃａｔｉｏｎ Ｓｔｏｒａｇｅ Ｍｅｃｈａｎｉｓｍ）。ＤＣＲ。Ｓ结合了完全复制和ｘ０Ｒ校验的 思想，不仅将文件复制成若干个复本（ｒｅｐｌｉｃａ，指同一个文件 －）本文受国家９５重点攻关项目支持．周旭Ｅｒａｓｕｒｅ Ｃｏｄｅｓ编码后生成的，这是一种十分复杂的编码方 教授。博士生导 博士研究生．主要研究方向：计算机网络、网络存储、分布式操作系统等．卢显良博士研究生，主要研究方向：计算机网络、网络存储． 师。主要研究方向：计算机网络、操作系统．魏青松２０７· 式，在和ＦＴＤＳＳ同样的分片数量下可以实现更小的空间复 杂度和更好的容错性能，但是由于编码效率较低，一般只用于 只读文件的容错。 研究以上几种文件冗余容错方案，我们可以发现它们都 是针对单个文件进行独立的冗余容错，没有考虑在文件之间 进行协作。同时我们知道，一个系统中的某些文件之间往往存 在某种内在的相互依赖和关联关系，特别是在分布式文件系 统中，某个应用可能需要同时读取分布在不同的机器上的几 个文件，如果这些文件中的一个或多个受损或丢失，应用往往 不能运行或者功能受到影响。所以，对于分布式文件系统来 说，我们不仅需要考虑单个文件的容错性能，同时也应该考虑 单元 多个分散而又有关联的文件的整体容错性能。 ２．２ ＤＣＲ Ｓ的基本原理和图论表示 分布式协作冗余复制存储机制ＤＣＲ Ｓ正是基于以上思 想的一种新的分布式容错机制，它结合了完全复制和ＸＯＲ 校验的方法，将分布在不同机器上的多个文件通过相互之间 的校验文件联系起来，形成一个整体，各个文件不仅可以通过 复制冗余复本来提高自身的容错性能，并且可以通过校验文 件协助其他文件提高容错性。通过多个主机上的文件的相互 协作，不仅可以提高单个文件的容错性能，更可以使得这一组 文件的整体容错性能得到大大提高。 如图１．ａ所示，设文件Ａ和Ｂ是系统中的原始文件（相对 于校验文件而言），其中Ａ文件有ｍ份复本（Ａ ，…，Ａ ），Ｂ 文件有 份复本（ ，…， ），Ａ ＸＯＲ Ｂ表示 和 通过异 或运算生成校验文件，这些文件都分布在不同的主机上。由异 或运算的性质可以知道，当存放Ａ文件复本的ｍ台主机都出 现故障或不在线，只要校验文件和任意一个Ｂ文件的复本在 线，仍然可以使用这两者进行异或运算将Ａ恢复。同理，Ｂ文 件损失后也可以借由校验文件和Ａ文件复本进行恢复。 为了表示和计算的方便，我们将所有的Ａ文件复本记为 个点Ａ ，Ｂ的复本记为点 ，将文件Ａ和Ｂ异或运算后生 成的校验文件Ａ ＸＯＲ Ｂ表示为连接Ａ。和 两点的一条边 ａ。这样，借用图论中“图”的概念，图１．ａ中几个文件的关系可 以简化地表示为图１．ｂ。 田．、／田［ ］．．：： Ｌ －＿Ｉ－－－＂－Ｃ－－－￣ Ｊ ——／—— 厂—－—］／校验文件 — Ｌ ＿＿ｊ １ Ｉ 文件＾ 文件Ｂ 基本原理 ＾ ｌ丑 ｂ．圈论表示 图１ ＤＣＲ Ｓ原理和图论表示 如图２．ａ所示，我们将一组用校验文件联系起来的分散 文件称为一个ＤＣＲ Ｓ单元（ＤＣＲ Ｓ ｕｎｉｔ）。在系统的任意时 刻，单元中的某些校验文件可能由于所在主机的原因而导致 不能获得，这表现在该单元对应的图中就是一部分边的缺失。 所以，在任意时刻，单元对应的图都可能只是原来完整时的一 个子图。图２．ｂ就是在某个时刻，由于图２．ａ中两条边丢失而 形成的子图。 ·２０Ｒ· ｂ．单元子圈 图２ ＤＣＲ 中的单元 为了叙述的方便，下面给出几个定义。在一个单元中，每 个点都有两种状态：若点Ａ 对应的文件Ａ的所有ｍ个复本 都不在线时，称点Ａ 不在线，反之称点Ａ 在线。若一个点 不在线但是可以通过ＸＯＲ编码重新生成，称点 是可 恢复的。若一个点Ａ 在线或是可恢复的，称点 可得。如果 个单元中所有点都是可得的，称该单元是整体可得的． 有了这些定义，就可以使用图论的表述方式来准确地描 述ＤＣＲ Ｓ中一个单元单点和整体的可恢复条件： （１）在一个单元中，点Ａ 是可恢复的充要条件是当前单 元的图中至少存在另一个在线的点 并且存在一条连接Ａ 和 的道路。 （２）一个单元是整体可得的充要条件是当前该单元的任 意连通子图中都至少有一个点是在线的。 ５ ＤＣＲ Ｓ的容错性能分析 ５．１环形和链形ＤＣＲ Ｓ结构 对于多个文件，可以有链形、星形、环形、树形和更加复杂 的网形等多种方式将它们相互连接起来，形成一个ＤＣＲ。Ｓ单 元（如图３所示）。这些连接方式的空间复杂度和占用的存储资 源各不相同，容错性能也有差别。下面我们重点讨论链形 （ｃｈａｉｎ）和环形（ｒｉｎｇ）结构，并定量地分析一下这两种结构的 容错性能。 链形 星形 环．形 树彤 网形 图３几种不同的ＤＣＲ Ｓ单元结构 为了简化模型，假设系统中每台主机出现故障的概率均 为户，每个文件有 份复本（即文件在系统中共有 份拷贝）， 每个校验文件在系统中保存的份数只有一份，所有这些文件 都分布在不同的主机上。 设单元中每个点不在线的概率为Ｐ，每条边不在线的概 率为Ｑ。则根据定义，有Ｐ＝ｐ ，Ｑ＝ｐ。 设Ｃｈａｉｎ（ｎ）表示有ｎ个点（口 ａ。…ａ ）的链形单元结构， 记Ｃｈａｉｎ（ｎ）中单点ａ 可得的概率为 ，记Ｃｈａｉｎ（ｎ）整体可 得的概率为ｃ 。则根据概率论原理，可以求出： １．１—１一Ｐ， ２．１一 ２、２一（１一Ｐ）＋Ｐ·（１一Ｑ）·ｃ１．１ 当ｎ≥３时，用递推法（推导过程从略）可以得出： １一 （１一Ｐ）＋Ｐ·（１一Ｑ）· 一１．１ Ｃ 一（１一Ｐ）＋Ｐ·（（１一Ｑ）·Ｃ．一ｌ、】＋（１一Ｑ）·Ｃ…．１一（１一 Ｑ）０· 一１．】· ～１），ｉ＝２，…，ｎ一１ 同理可以计算出Ｃｈａｉｎ（ｎ）的整体可得概率： Ｃ１一（１一Ｐ）， Ｃ２一（１一Ｐ）０＋２·Ｐ·（１一Ｐ）·（１一Ｑ） Ｃ 一（１＋Ｐ一２ＰＱ）·Ｃ＿一Ｉ—Ｐ·（１一Ｑ）。·Ｃ＿一２，月≥３ 设Ｒｉｎｇ（ｎ）表示有ｎ个点（吼ａｚ…口 ）的环形单元结构。很 明显，Ｒｉｎｇ（ｎ）中每个点的单点可得概率都一样，记为ｒｌ，另用 尺ｎ表示Ｒｉｎｇ（ｎ）的整体可得概率。则 ＾一１ （１一Ｐ）＋厶Ｐ·（１一Ｐ）·Ｐ一。·（（１一Ｑ） ＋（１一 ＿一１ ＾…１， Ｑ）一一（１一Ｑ）一）＋∑∑Ｐ．（１一Ｐ）。．ｐ．－ 一 ．（（１ ｊｌ ２一一１ Ｑ） ＋（１一Ｑ）…一， 一（１一Ｑ）一什 ），ｎ≥３ 同样使用递推法，可以得出 Ｒ３—１一Ｐ’一３Ｐ。（１一Ｐ）（Ｑ’＋３Ｑ。（１一Ｑ））一３Ｐ（１一 Ｐ）０ 见一２ ｃ ＋ ｃ ＋ ＾－－３ Ｐ一 ·（１一Ｑ）一 ·（３Ｐ·Ｑ—Ｐ—Ｑ一１）＋厶（ｎ—ｍ一 ２）·（１一Ｐ）·（１一Ｑ）…－１·Ｐ…一 ·Ｑ Ｃ ，ｎ≥４ 从直观上分析，环形单元结构的单点可得概率和整体可 得概率都应该比链形结构大，下面通过计算来验证这一点。 假设每台主机出现故障的概率为１０％，每个文件只有一 份，即ｐ一０．１，ｋ一１，可得Ｐ一０．１，Ｑ一０．１。 １ ０．９ｇ日 ０．９９８ ｊ＋环形； ０．９９７ ｊ＋链形ｊ ０．９９６ ０．９９ｌ５ ３ ４ ５ ６ ７ ８ ９ １０ 单点可得概率比姻 ｌ Ｉ一—＿｛———●Ｌ～一 一 ０．９９ ０．９８ Ｉ ● ● ● ● ●０．９７ ● ， ０．％ ０．９５ ３ ４ ５ ６ ７ ８ ９ ｌ０ 整体可得概率比较图 图４环形和链形结构的容错性能对比 对于ｎ一３，…，１０，根据前面的公式可以计算出两种结构 的单点和整体可得概率，如图４所示（由于链形结构中各点的 可得概率不同，取其最大值）。 从图４中可以看出，ＤＣＲ。Ｓ的单点可得概率随着ｎ的增 加而增加，整体可得概率随ｎ的增加而缓慢减小．且环形单元 结构的单点和整体可得概率一直大于链形结构。当ｎ≥７时， 环形结构的单点可得概率的增长变得十分微小，与链形结构 单点可得概率之间的差距也越来越小，逐渐趋于一致。这说明 环形和链形单元中单点的可得概率主要受图中距离它比较近 的点的影响，当单元中的点数增加到一定数量时，继续增加下 去并不能有效地提高单点的可得概率。 ５．２完全复制和环形结构ＤＣＲ Ｓ的容错性能比较 ＤＣＲ。Ｓ是从完全复制的思想发展而来，下面比较一下在 占用相同存储空间的条件下，完全复制和环形结构ＤＣＲ。Ｓ容 错性能的差别。 以下仍然设户一０．１，并假定单元中每个文件的大小都相 同，设为一个存储单位。则ｋ一１时，点数为ｎ的环形ＤＣＲ。Ｓ单 元将占用２ 个存储单位。 同样占用２ｎ个存储单位，使用完全复制的方法，我们为 这ｎ个原始文件每个再复制一个复本。可以求出这时每个文 件的单点可得概率为１一Ｐ。，而ｎ个文件的整体可得概率为１ （户。） 。 图５是ｎ取不同值时，环形ＤＣＲ。Ｓ结构和完全复制的容 对于所有的ｎ来说，在同样 占用２ｎ个存储单位时，环形ＤＣＲ。Ｓ结构的单点可得概率和 整体可得概率都大于完全复制。另外，由于环形ＤＣＲ。Ｓ结构 整体可得概率下降的趋势大大缓于完全复制，随着ｎ的增加， 两者之间的差距越来越大，环形ＤＣＲ。Ｓ的优势愈加突出。 １ ０．９９ ０．９８ ０．９７ ０．９６ ０．９５ ０．９４ ０．９３ ０．９２ ０．９１ ０．９ ３ ４ ５ ６ ７ ８ ９ １０ 图５环形结构和完全复制冗错性能比较 以ｎ一５为例，如图６所示，设有５－／＇－分布在不同主机上的 文件，它们的单点可得概率为０．９，整体可得概率等于０．９ 一 ０．６５６１。若使用完全复制的方法，为每个文件增加一个复本， 则文件的单点可得概率为０．９９，整体可得概率为 ０．９５０９９００４９９；若使用环形ＤＣＲ。Ｓ，ｋ—Ｉ时文件的单点可得 概率为０．９９８７８３５９８６，整体可得概率为０．９９４５３２７８２５。所以， 同样增加５个存储单位建立校验文件形成一个环形单元，可以 将文件的单点容错性能提高到不容错时的 Ｉ－－ Ｕ ．而丽 ≈８ ２．２ １倍，将整体容错性能提高到不容错时的 （下转第２１３页） ２０９· 错性能比较图。从图中可以看出，的路径，如果这些路径可以被使用，那么反向页表的开销则可 以避免，如图４所示 地址转换方法来获得更高的页迁移效率。 结束语 页迁移技术是实现ＣＣ—ＮＵＭＡ系统存储优化 的重要方法，它动态地解决了数据局部性问题 由于迁移过程 中频繁涉及到实虚地址的转换，其开销影响了页迁移的效率 以优化页迁移技术为出发点，本文提出了操作系统中实现快 速实虚转换、支持页迁移的关键部件——反向页表技术 经过 测试，在高端系统和负载很大的情况下，反向页表支持的页迁 移系统性能明显优于传统页迁移系统 当然，目前这种技术还面临着许多问题，主要体现在反向 页表的空间开销上，而且ｆｏｒｋ（）系统调用将会对进程地址空 间中的每个页面增加一个新的反向页表项，大大增加了反向 页表的维护开销。这些都是今后需要研究和解决的内容 器Ａ０ Ｂ０图４文件映射页面的一种反向映射路径 ｐａｇｅ结构中有一项指向ａｄｄｒｅｓｓ—ｓｐａｃｅ结构的域ｍａｐ— ｐｉｎｇ，该域描述了备份这个页面的文件。ａｄｄｒｅｓｓ—ｓｐａｃｅ结构包 参考文献 １ Ｖｅｒｇｈｅｓｅ Ｂ，Ｄｅｖｉｎｅ Ｓ．Ｇｕｐｔａ Ａ，Ｒｏｓｅｎｂｌｕｍ Ｍ．Ｏｐｅｒａｔｉｎｇ ｓｙｓｔｅｍ Ｓｕｐｐｏｒｔ ｆｏｒ Ｉｍｐｒｏｖｉｎｇ Ｄａｔａ Ｌｏｃａｌｉｔｙ ｏｎ ＣＣ－ＮＵＭＡ Ｃｏｍｐｕｔｅｒ Ｓｅｒｖｅｒｓ．Ｉｎ：ｐｒｏｃ．Ａｒｃｈｉｔｅｃｔｕｒａｌ Ｓｕｐｐｏｒｔ ｆｏｒ Ｐｒｏｇｒａｍｍｉｎｇ Ｌａｎ— ｇｎａｇｅｓ ａｎｄ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ．１ ９９６．２７９￣２８９ ２ Ｎｉｋｏｌｏｐｏｕｌｏｓ Ｄ．ｅｔ ａ１．Ｓｃｈｅｄｕｌｅｒ—Ａｃｔｉｖａｔｅｄ Ｄｙｎａｍｉｃ Ｐａｇｅ Ｍｉｇｒａ— 括备份文件的ｉｎｏｄｅ、文件页面的数据结构和两个ｖｍ—ａｒｅａ— ｓｔｒｕｃｔ（ＶＭＡ）的链表 ＶＭＡ链表说明了特殊进程地址空间 的映射关系。文件／ｐｒｏｃ／ｐｉｄ／ｍａｐｓ列出了不同ＰＩＤ号进程的 ＶＭＡ映射。当我们需要获得非ａｎｏｎｙｍｏｕｓ页面的虚地址时， 可以通过ａｄｄｒｅｓｓ—ｓｐａｃｅ和ＶＭＡ结构找到对应的页表项。 ｔｉｏｎ ｆｏｒ Ｍｕｌｔｉｐｒｏｇｒａｍｍｅｄ ＤＳＭ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒｓ． Ｉｎ Ｊｏｕｒｎａｌ ｏｆ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ，２００２ ３ Ｌａｕｄｏｎ Ｊ，Ｌｅｎｏｓｋｉ Ｄ．Ｔｈｅ ＳＧＩ Ｏｒｉｇｉｎ：Ａ ｃｃＮＵＭＡ Ｈｉｇｈｌｙ Ｓｃａｌ— 虽然这种方法比直接查找反向页表要花费更多的时间， 但是，因为可以不用维护非ａｎｏｎｙｍｏｕｓ页面的反向页表结 构，所以能够节省大量空间开销 我们考虑在今后的实现中将 ａｂｌｅ Ｓｅｒｖｅｒ［Ａ］．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ ２４ Ａｎｎｕａｌ Ｉｎｔ’１ Ｓｙｍｐ ｏｎ Ｃｏｍ— ｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ［ｃ］．１ ９９７ ４ ｖａｎ Ｒｉｅｌ Ｒ．Ｔｏｗａｒｄｓ ａｎ Ｏ（１）ＶＭ：Ｍａｋｉｎｇ Ｌｉｎｕｘ ｖｉｒｔｕａｌ ｍｅｍｏｒｙ ｍａｎａｇｅｍｅｎｔ ｓｃａｌｅ ｔｏｗａｒｄｓ ｌａｒｇｅ ａｍｏｕｎｔｓ ｏｆ ｐｈｙｓｉｃａｌ ｍｅｍｏｒｙ．Ｉｎ Ｌｉｎｕｘ Ｓｙｍｐｏｓｉｕｍ ２００３ 两种反向映射方法结合起来，并在不同的情况下使用不同的 （上接第２０９页） ５ ＬＷＮ Ｔｈｅ ｏｂｊｅｃｔ—ｂａｓｅｄ ｒｅｖｅｒｓｅ—ｍａｐｐｉｎｇ ＶＭ．ｈｔｔｐ：／／１ｗｎ．ｎｅｔ／ Ａｒｔｉｃｌｅｓ／２３７３２／？ｆｏｒｍａｔ—ｐｒｉｎｔａｂｌｅ 结论和未来的工作本文提出了一种新的分布式协作冗 蠢 五 ≈６２．９倍；而使用完全复制的方法，只能将 ≈７．ｏ１倍。由此可见，在增加同样的存储空 Ａ 余复制存储机制ＤＣＲ Ｓ，这种机制通过校验文件实现了多个 文件之间的相互协作，不仅可以提高单个文件的容错性能，更 论的概念准确地描述了ＤＣＲ Ｓ的容错性质，定量地分析了链 单点容错性能和整体容错性能分别提高｛ 一１ｏ倍和 可以使得一组文件的整体容错性能得到大大提高 本文用图 形和环形ＤＣＲ Ｓ结构的容错性能，并给出了这两种特殊结构 的单点和整体可得概率的计算公式。通过计算比较，环形 ＤＣＲ Ｓ结构在占用同样存储空间的条件下，可以实现比完全 间的情况下，环形ＤＣＲ Ｓ可以比完全复制更加有效地增加一 组文件的单点和整体容错性能 Ｏ Ｅｎ 复制更高的容错性能，证明了ＤＣＲ Ｓ是一种十分有效的分布 ｏＢ 式文件容错机制 如前所述，ＤＣＲ Ｓ有多种结构，而本文只分析了链形和 环形两种，在以后的工作中将对其他一些ＤＣＲ Ｓ结构的容错 Ｄｏ ｏｃ 分布在不同主机上的五个文件 性能进行进一步的分析，找出容错效率最高、最易于实现的 ＤＣＲ Ｓ单元结构，并通过实验给予验证。 参考文献 ８８ ８８ 完全复制容错 环形ＤＣＲ２Ｓ容错 １ Ｄｉｎｇｌｅｄｉｎｅ Ｒ．Ｆｒｅｅｄｍａｎ Ｍ．Ｍｏｌｎａｒ Ｄ．Ｔｈｅ ｆｒｅｅｈａｖｅｎ ｐｒｏｊｅｃｔ：Ｄｉｓ— ｔｒｉｂｕｔｅｄ ａｎｏｎｙｍｏｕｓ ｓｔｏｒａｇｅ ｓｅｒｖｉｃｅ．Ｉｎ：Ｐｒｏｃ．ｏｆ ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｄｅｓｉｇｎ Ｉｓｓｕｅｓ ｉｎ Ａｎｏｎｙｍｉｔｙ ａｎｄ Ｕｎｏｂｓｅｒｖａｂｉ１ｉｔｙ．Ｊｕｌｙ ２０００ ２ Ｂｏｌｏｓｋｙ Ｗｔ Ｄｏｕｃｅｕｒ Ｊ．Ｅｌｙ Ｄ．Ｔｈｅｉｍｅｒ Ｍ．Ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ａ ｓｅｒｖｅｒ一 １ｅｓｓ ｄｉｓｔｒｉｂｕｔｅｄ ｆｉｌｅ ｓｙｓｔｅｍ ｄｅｐｌｏｙｅｄ ｏｎ ａｎ ｅｘｉｓｔｉｎｇ ｓｅｔ ｏｆ ｄｅｓｋｔｏｐ 图６环形ＤＣＲ Ｓ容错和完全复制容错 以上的分析是基于 一１的假设，即环形ＤＣＲ Ｓ单元中 ＰＣｓ．Ｉｎ：Ｐｒｏｃ．ｏｆ ＳｉｇｍｅｔｒｉｃＳ．Ｊｕｎｅ ２０００ ３ Ｋｕｂｉａｔｏｗｉｃｚ Ｊ．ｅｔ ａ１．０ｃｅａｎｓｔｏｒｅ：Ａｎ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｇｌｏｂａｌ—ｓｃａｌｅ ｐｅｒｓｉｓｔｅｎｔ ｓｔｏｒａｇｅ．Ｉｎ：Ｐｒｏｃ．ｏｆ ＡＳＰＬ０Ｓ．ＮＯＶ．２０００，ＡＣＭ ４魏青松，卢显良，雷宇．ＦＴＤＳＳ：高容错分布式共享存储机制．计 算机科学，２００３，３０（８）：１７２～１７５ ５ Ｄｒｕｓｃｈｅ１ Ｐ．Ｒｏｗｓｔｒｏｎ Ａ．Ｓｔｏｒａｇｅ ｍａｎａｇｅｍｅｎｔ ａｎｄ ｃａｃｈｉｎｇ ｉｎ ＰＡＳＴ，ａ ｌａｒｇｅ—ｓｃａｌｅ．ｐｅｒｓｉｓｔｅｎｔ ｐｅｅｒｔｏ—ｐｅｅｒ ｓｔｏｒａｇｅ ｕｔｉｌｉｔｙ．Ｉｎ： Ｐｒｏｃ．ｏｆ ＡＣＭ Ｓ０ＳＰ（２００１） 每个点对应的文件复本只有一个。当 ＞ｌ时，根据公式计算 可知环形ＤＣＲ Ｓ结构的容错性能仍然高于完全复制，且提高 的幅度比 ＝ｌ时更大。由此可知，一组分散的文件在结成环 形ＤＣＲ Ｓ单元后，若还想进一步提高单个文件和整体的容错 性能，只需为每个文件增加复本，就可以获得比占用同样存储 空间的完全复制方法更好的容错性能 ６ Ｂ１ｏｍｅｒ Ｊ，Ｋａｌｆａｎｅ Ｍ，Ｋａｒｐ Ｒ，Ｋａｒｐｉｎｓｋｉ Ｍ．Ｌｕｂｙ Ｍ，Ｚｕｃｋｅｒｍａｎ Ｄ．Ａｎ ｘｏｒ—ｂａｓｅｄ ｅｒａｓｕｒｅ—ｒｅｓｉｌｉｅｎｔ ｃｏｄｉｎｇ ｓｃｈｅｍｅ．Ｔｅｃｈｎｉｃａ１ ｒｅ— ｐｏｒｔ．Ｉｎｔ１．Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｉｎｓｔｉｔｕｔｅ．Ｂｅｒｋｅｌｅｙ，Ｃａｌｉｆｏｒｎｉａ，１９９５ ７ Ｗｅａｔｈｅｒｓｐｏｏｎ Ｈ．Ｋｕｂｉａｔｏｗｉｃｚ Ｊ Ｄ．Ｅ Ｃ ＶＳ．Ｒｅｐｌｉｃａｔｉｏｎ：Ａ Ｑｕａｎ— ｔｉｔａｔｉｖｅ Ｃｏｍｐａｒｉｓｏｎ．ＩＰＴＰＳ’０２ ２１３·
