第１２０１１年４月 ７ 第４ ＪＯＵＲＮＡＬ ＯＦ Ｊ江苏ＩＡＮ‘ＧＳ 。技术师ｒｒＥ工ＣＨ—ＥＲＳ范学。一ＵＮ‘Ｉｖ 院学报 ｒ Ｏ…ＦＴＥＣＨＮＯＬＯＧＹ ＶｏＩ．１７．Ｎｏ．４ ＡＤｒ．．２０１１ 分布式存储系统中混合数据布局算法 刘金芝 （江苏技术师范学院计算机科学与工程学院，江苏常州２１３００１） 摘要：数据布局算法是分布式存储系统的基础性算法，也是提高数据处理效率的关键。针对节点负载和通信 延迟等存储节点状态，提出了一种衡量存储节点可用性的通用方法，并在分析了已有算法的基础上，综合各种算 法的优点，提出了一种混合数据布局算法。该算法根据存储节点可用性不同而采取不同的数据冗余策略。通过对 比分析，证实该算法在存储量与通信量方面具有较大的优越性。 关键词：分布式存储系统；数据布局；纠删编码；数据冗余 中图分类号：Ｔｌｒ３０９ 文献标识码：Ａ 文章编号：１６７４—８５２２（２ｏ￣１）０４—００２１—０７ ０ 引 言 在信息时代，当人们越来越多地依赖于信息时，信息的存储以及对这些信息的可利用性、完整性和机 密性的服务支持是信息化社会的基础设施。一个生存力强的存储系统将在任何时候都能提供这些保证。 高可靠性和高可用性对大规模存储系统非常重要，因为在网络存储系统中随着存储节点数量的动态变 化，在增加了系统性能和灵活性的同时，也会出现存储节点失效、关键数据的丢失以及网络路由造成的延 时等。例如，在世界上最大的ＳＡＮ系统之一、金融巨头ＪＰＭｏｒｇａｎ公司的数据库系统，其总存储量达到１４ ＰＢ字节，每个存储节点的存储容量达到３００ ＧＢ以上，在世界各国的总节点数超过２ ０００个，一方面，根 据目前商用磁盘的平均无故障时间为１０５小时计算，磁盘失效的情况平均每天都可能发生；另一方面，根 据磁盘发生坏区等不可恢复读数据平均无错误率为１０ ，在由大量磁盘组成的存储系统中，即使在磁盘 没有完全失效的情况下，不可恢复的读取数据错误的情况也可能每小时都发生１次以上。如此频繁的丢 失数据对大规模存储系统是不能容忍的，并且由于容量的增加，导致磁盘失败时的重建磁盘数据时间更 长。以重构１００ ＧＢ的磁盘为例，若以在线１０ Ｍｂｐｓ的速度重构，需要的时间超过１天，在磁盘数据的修复 期问，同时发生另一个磁盘失效的概率依然很大。因此，在设计分布式存储系统时，简单地使用一种容错 技术不能有效保证数据的可用性，而必须采用相应的通用性强的数据冗余机制，以确保存储系统中数据 的一致性和可用性。 １ 冗余方式与数据布局 １．１ 对数据布局算法的要求 由于大型的分布式存储系统在运行过程中会面临各种各样的环境，相应的数据处理算法应该满足特 定的条件。在应用过程中数据布局算法存在以下最基本的要求［１】。 １．１．１ 安全性 收稿日期：２０１１－０３—１６；修回日期：２０１１－０３—３０ 作者简介：刘金芝（１９８０一），女，江苏溧阳人，讲师，研究方向为计算机存储、信息安全。 ２２ 江苏技术师范学院学报 第１７卷 安全性包括两方面：防止信息丢失和泄露。为防止信息丢失，系统中应该存在冗余，而密码技术则是防 止泄露的重要方法。两者结合的最佳典型是所谓“完备”的秘密共享方案，“完备”的意思是指当份额数量 小于某个门限值时，从信息论的角度来讲，将得不到关于原始数据的任何信息。 １．１．２ 高效性 在实现时，数据布局的过程应该具有可接受的时间复杂度，而布局后的数据占用空问也不应过大。对 于大规模数据，尤其应该保证这一点。另外，同一数据不宜分散到太多的节点，各个存储节点上保存的数据 量也应尽可能小。 １．１．３容错性 实现数据的容错性是分布式存储的主要优势之一，容错性主要通过两方面来实现：存储节点的冗余 和存储数据的冗余。前者依靠增加物理节点，通过多节点合作，增加系统的冗余；后者通过特定的数据布 局算法，对原数据进行复制、编码等方式增加冗余。 １．２ 相关工作 存储数据的可利用性是许多信息系统的首要指标。大多数系统通过完全复制来增强可用性；少数系 统利用占用较小空间的弹性擦除校正编码，即纠删编码来增强数据容错性。在分布式存储系统中，要将数 据分布到物理上的Ｉｔ个节点中保存，首先要有一个适当的算法将１份数据转化为Ｉｔ份，这个算法过 程我们称为数据布局。以上两种增强可用性的途径都统称为数据布局算法。常见的数据布局算法按技术 细节可划分为备份或数据镜像、数据分割或条带技术、纠删编码方式等。 １．２．１备份或数据镜像 备份是最直接也是最基本的方法，Ｈｉｔａｃｈｉ的存储系统Ｌｉｇｈｔｎｉｎｇ ９９００Ｖ和Ｔｈｕｎｄｅｒ ９５００Ｖ系列便采用 镜像来保证重要数据的安全。然而备份存在着信息易泄露和占用存储空问较大的缺点。 １．２．２数据分割或条带（Ｓｔｒｉｐｉｎｇ）技术 数据分割是将数据分为若干段，保存在不同的存储设备中。这方面最典型的例子是ＲＡＩＤ（Ｒｅｄｕｎｄａｎｔ Ａｒｒａｙ ｏｆ Ｉｎｅｘｐｅｎｓｉｖｅ Ｄｉｓｋ）ｔ２］系列，如ＲＡＩＤ０和ＲＡＩＤ５中的数据处理方法。ＲＡＩＤ０中的数据被存储在同一 张盘的连续扇区上，至少使用两个磁盘驱动器，并将数据分成从５１２ ｂｉｔｓ到数兆ｂｉｔｓ的若干块，这些数据 块被交替写到磁盘中。第１段被写到磁盘１中，第２段被写到磁盘２中，如此等等。ＲＡＩＤ５类似于 ＲＡＩＤ０，但它不是将数据分成块，而是将每个字节的位拆分到多个磁盘。这样会增加管理费用，但是，如果 一个磁盘出现故障，则可以更换该磁盘，数据通过奇偶校验和纠错码重建。数据分割将Ｉ／０负载平均分配 到所有的驱动器。由于驱动器可以同时写或读，所以性能得以显著提高。但是它却没有数据保护能力，如 果一个磁盘出故障，数据就会丢失。 １．２．３ 门限纠删编码 为了提高数据的可用性，一些分布式存储系统采用纠删码来布局数据，如ＯｃｅａｎＳｔｏｒｅ［３１中便同时采用 了ＲＳ码和Ｔｏｒｎａｄｏ码来保证档案数据的可用性。此外还有ＥＶＥＮＯＤＤｌ４码，Ｘ一码［５１，ＬＥＣ码阑等等。采用纠 删编码的目的主要是为了防止数据丢失，而并不能提供保密性。 门限秘密共享技术从实现方式上讲也是一类纠错码，其中所使用的（ ， ）门限方案，是保护重要信 息的常见手段，也是信息系统可生存性研究中较常用的方法。现有的针对可生存性而设计的存储系统，基 本上都利用该方法布局数据。文献［７１中总结了利用线性方程组构造（ ，１２，）门限方案的通用方法，并对如何 寻找存取结构进行了分析，其中介绍的通用线性门限方案如下所述。 设Ｆ为一个有限域，要保护的秘密信息为ｓ∈Ｆ，欲构造（Ｊ｝Ｉ， ）门限方案，首先要找到一个ｎｘｋ阶满秩 矩阵Ａ（秩为 ），并产生一个 维向量Ｘ＝（ ，ｘ２，… ），其中：劫－－－Ｓ，其余元素取自于Ｆｏ计算Ｉｔ维向量： Ｂ＝ＡＸＴ， 则生成的ｎ个份额为： Ｂ＝（ｂｌ，ｂ２，…，ｂ ）。 将Ａ公开，如果已知Ｉｔ个份额中的任意 个，则由于矩阵Ａ的任意ｋ行线性无关，故可以用解线性方程 组的方法求得秘密信息。 第４期 刘金芝－分布式存储系统中混合数据布局算法 ２３ 采用以上方法进行数据布局的有文献［８１中的分布式代理存储系统及Ｒａｂｉｎ提出的信息分散算法ＩＤＡ （Ｉｎｆｏｒｍａｔｉｏｎ Ｄｉｓｐｅｒｓａｌ Ａｌｇｏｒｉｔｈｍ）ｔｇｊ。ＩＤＡ的基本思想是将信息Ｄ分布到ｎ个服务器上保存，当系统中有ｔ个 服务器无法工作时，仍然能够恢复信息。Ｒａｂｉｎ的方案中，每个份额占用的空间为ｌ Ｄ Ｉ／（ｎ—ｆ）。在ＩＤＡ的基 础上，人们针对各种具体应用环境，又提出了ＳＩＤＡｔ砌，ＡＩＤＡｔ“等改进算法。 本文针对节点负载和通信延迟情况，提出了一种衡量存储节点可用性的通用方法，并在分析了已有 算法的基础上，综合各种算法的优点，提出了一种混合数据布局算法。该算法根据存储节点可用性不同而 采取不同的数据冗余策略。通过对比分析，本算法具有比较好的实用性。 ２ 系统模型及假设 ２＿１ 相关定义 ２．１．１ 节点可用性ａ 通过获取目标节点的负载与通信延迟并将数据映射到某个统一的函数Ｆ的值域内，从而获得的一个 变量，可理解为该节点能正常响应存取请求的概率。 ２．１．２ 节点集５的可用性鲫 定义为对该节点集内所有节点的可用性取平均值的结果，即： ａｖ＝２２ ａ，ｉ∈Ｓ 。 ２．１．３ 冗余性ｒ 对于一次存储操作，其冗余性可定义为加人数据冗余的程度，一般定义为： ｒ＝ 。 ２ １．４ 蛾数据Ｐ 指用户的原始数据Ｄ被分割加工成的大小固定的数据单元，若尾段长度不够要进行填充，然后依照 布局算法可以直接进行转存，也可以作为纠删编码输人。 ２．１．５段数据Ｆ 数据冗余的最小单元，直接按布局算法判定的目标节点或节点集合存储。 ２．２ 系统故障模型 把分布式系统看成存储节点的全集Ⅳ，每次存取操作的目标是Ⅳ的一个子集．ｓ，每个节点之间在存 取可用性上是相互的，其可用性可以用一个概率Ｐ表示。系统的用户是动态的，即随时可以加入和退 出系统的通信，也可以在任何时刻请求存取服务。对于每一个存储节点ｉ∈Ｎ，其可用性： ）＝ｐｒ ， 其中 表示事件第 个节点按照设定的程序完成用户所请求的任务的概率。在实际中，ａ是随着时问推 移而变化的，本文为简化存储过程，假定当前操作中使用的参考值为： Ⅱｏ 口 ， 其中： ，为本次操作前节点返回的可用性期望值。 ３ 混合数据布局算法 本节针对节点负载和通信延迟情况，提出了一种衡量存储节点可用性的通用方法，并以此为基础，提 出了一种混合数据布局算法，该算法根据存储节点可用性不同而采取不同的数据冗余策略。 ２４ 江苏技术师范学院学报 第１７卷 ３．１ 节点的可用性 通过第３节中的定义可知，要获得对目标节点可用性的准确评价就要尽量获得相关的信息进行分 析，将的变量简化成一维的变量，从而便于数据布局时的决策。本文将这个过程分为２个步骤：首先， 通过对网络状态的监测，初始化判定多项式Ｆ，并对其系数进行训练；其次，利用判定多项式Ｆ对目标节 点或节点集进行可用性区分，并对操作的历史数据进行分析，以调整多项式Ｆ，使之能对可用性进行准确 判定。 ３．２存在性证明 ３．２．１ 结论１ 设节点有ｍ个，节点状态为 维，在时间ｔ内存在关于目标状态 的二次多项式： 月［ ，Ｕ１，…， ， 使ＦＥ［０，１】，且具有概率完备性。 证明：设Ｅ是随机对节点可用性的抽样试验，样本空间为： ｎ＝｛ｃ， ， ，…， ｝， 且有： ＝ｆ ， ，…， ｝。 则明显存在系数向量Ｃ０ ， ，…，ｃｏ 使所有Ｆ≥０且对结果为全部可用的节点有 ０；又由于节点可用性 之间具有的性，且每次抽样为随机抽样，故不同Ｆ的值具有可加性。综上，存在系数ｃ０。，Ｃｏ ，…， 使多项式Ｆ具有概率完备性。 ３．２．２结论２ 对于给定的目标存储节点集合Ｓ和将要存储的原始数据Ｄ，所需的冗余性ｒ与目标可用性ａ反相 关。 证明： ｏ＝ 一ｌ 型 ． Ｉ二１．旦Ｌ ｌ 型 ． ．１＝１．旦Ｉ ． 一 ｌ Ｆｒａｇｍｅｎｔ同ｓ Ｉ Ｉ Ｆｒａｇｍｅｎｔ ｓ ｌ ’ 又由结论１以及在存储过程中，随着时间的推移，网络节点处于动态调整和维护中，有Ｆ接近期望 １， 故上式约等于零。由此可得，一次存储操作所需的冗余性ｒ与目标可用性ａ是反相关的。 ３．２．３推论１ 给定目标存储节点Ｉｓ和期望可用性 ，不同冗余方式的优化程度具有可比性，即存在算法Ａ对不同冗 余方式返回可区分性的结果。 证明：在期望相同的前提下，若比较冗余方式维护的复杂度，由结论２只需计算（１）式，比较取值小者 即可。 ３．２．４结论３ 在给定存储节点集合的前提下，存在算法 可以对复制与纠删编码两种冗余方式的数据维护进行 复杂度比较。 证明：由推论１可得。 ３．３ 算法流程 为了在实际应用中降低算法复杂度，算法中选取了两个有代表性的节点变量，ｌｏａｄ和ｚ孔用来表示 节点当前的状态。 令： Ｆ＝Ｃｏ。 ｍ ２十Ｃｏ 堡－－ ２， ｆ０ｎｄ２ ＹＴＬ 第４期 刘金芝：分布式存储系统中混合数据布局算法 ２５ 其中： 。，ｃ０ 为训练系数，用来修正Ｆ的值，使之满足结论１，经过多轮的交互，ｃ０ ｃｏ 的值可以确定。 又令： （１一Ｆ）×１００％ 作为节点的可用性变量。数据处理的基本流 如图１所示 ｓｔｏ嘲…ａｅ目国国目国 图１数据布局的流程 布局过程如下： Ｓｔ ｐ０：用户向所在网络发出一次节点可用性查询，根据返回的结果将目标节点集分为 和 两个集 合。 Ｓｔｅｐ１：用户将原始数据Ｄ分割成长度相同的片数据（Ｐｉｅｃｅ），并对末尾进行填充。随机将Ｐｉｅｃｅ分为 ｌ ｕ Ｉ＋Ｉ ’ｌ份。 Ｓｔｅｐ２：将Ｉ 个片数据复制为段数据，同时调用纠删编码算法计算Ｅ（１ ’Ｉ，１ １），产生 个段数 据。 Ｓｔｅｐ３：随机将 个片数据发送到节点集合 ，将 个段数据发送到节点集合 。 恢复过程如下： Ｓｔｅｐ０：用户向网络提交一次数据请求服务。 Ｓｔｅｐ１：集合 和 中的部分节点将请求的段数据返回给用户。 Ｓｔｅｐ２：用户调用纠删编码程序对来自 的数据进行解码。 ｓｔｅｐ３：用户用所有段数据恢复原始数据Ｄ。 该数据布局算法的基本思路是以结论３为依据，存储网络的用户在进行存储数据时，向网络发出询 问；网络根据用户的位置和数据的属性作出判断，向用户返回一个节点的集合；用户根据这个集合的属 性，进行数据布局与存储，决定将哪些数据片直接复制到节点，将哪些数据片采用纠删编码进行转化后存 储到节点。 主要的相关代码如下： Ｏｎｄａｔａ—．ｄｉｓｐｅｒｓａｌ（）｛ Ｔｈｒｅｓｈｏｌｄ＝Ｇｅｔａ（Ｎｏｄｃ…ｓｃｔ）； Ｉｆ（Ｔｈｒｅｓｈｏｌｄ＞Ｃ） Ｆｒａｇｍｅｎｔｓｃａｔｔｅｒ（Ｎｏｄｅｓｅｃ）； ＿—ｅｌｓｅ Ｐｉｅｃｅ＿ｒｅｐｌｉｃａｔｉｏｎ（Ｎｏｄｅｓｅｔ）； ——｝ Ｇｅｔａ（Ｎｏｄｅ＿ｓｅｔ）｛ Ｉｆ（！Ｎｏｄｅ—ｓｅｔ） Ｒｅｔｕｒｎ ａｖｅｒａｇｅ（Ｆ（１ｏａｄ，ＴＴＬ））； ｅｌｓｅ Ｒｅｔｕｒｎ Ｓｅ 点 ＲＲＯＲ； ｝ 江苏技术师范学院学报 第ｌ７卷 Ｆｒａｇｍｅｎｔ＿ｓｃａｔｔｅｒｆＮｏｄｅ＿ｓｅｔ）｛ Ｉｆ（！ｄａｔａ） Ｅｒａｓｕｒｅ＿ｅｎｃｏｄｅ（ＩＮｏｄｅ＿ｓｅｔＩ，｝ｅｉｅｃｅｌ，ｄａｔａ）； Ｒｅｔｕｒｎ Ｆ１‘ａｇｍｅｎｔ ｓｅｔ； ｅｌｓｅ Ｒｅｔｕｒｎ ＳｅｔＥＲＲＯＲ； 。＿Ｐｉｅｃｅ＿ｒｅｐｌｉｃａｔｉｏｎ（Ｎｏｄｅ＿ｓｅｔ）｛ Ｉｆ（！ｄａｔａ） ｒｅｐｌｉｃａ（１Ｎｏｄｅｓｅｔｔ，ｌＰｉｅｃｅｌ，ｄａｔａ）； ｅｌｓｅ Ｒｅｔｕｒｎ Ｓｅｔ ＥＲＲＯＲ； １ 一 ， ４ 性能分析 ４．１ 存储量 相比完全使用纠删编码的方案，本算法以一定的概率加入了数据片的复制机制，从而相对增加了节 点的存储量。但存储量的增加并不是绝对的，若二者都应用在网络相同且节点状态良好的存储系统中，因 为较少使用数据片的复制，本文算法所耗的存储量与单纯使用纠删编码的算法相当。由结论２可知，理想 情况下的数据存储不存在任何数据冗余，存储量也相应最小；当节点性能下降时，为了保证数据的可用 性，本算法会以较大概率采用数据片复制方式存储，从而增加了数据的存储量。以下对增加的存储量进行 计算。 设判定为状态不良的存储节点所占的比例为ｕ，所用的纠删编码为ｍｌ ｐｉｅｃｅ ｌ ｎ１． ｍ Ｉ，则增 加的存储量百分比为： Ｕ Ｉ ±１．臣 ｌ￣ｏｍｅｎｔ型Ｌ【 Ｉ Ｌ ｌ Ｓ ｌ【！二 ）二Ｉ． 型Ｕ ＝（ 一１）“×１００％。 ｍ ４．２通信量 本算法的主要优势在于可以减少单纯用纠删编码方式所造成的通信开销。当系统监测到节点状态不 良时，需要调用数据片修复协议对目标节点上的数据进行修复，则会在网络上产生ｎ个数据片的流量。而 本算法只需复制相应的数据片即可，从而大大减小了数据修复的通信开销。若节点集合处于良好状态，则 与纠删编码方式相同，而远小于采用复制的存储系统。故在节点的可用性不高时，本算法会节省用于数据 修复的通信开销。 ４．３计算量 由于采用纠删编码方式过程中会求解关于数据份额的线性方程组和矩阵相乘，故在编解码时会相应 增加系统的计算开销。本文采用了部分纠删编码的数据容错方式，当节点状况不稳定或负载过重时，算法 会自动减小采用纠删编码的比例，而提高采用稳定复制数据的比例，故本文算法平均计算量将小于ＩＤＡ 等单纯采用纠删编码方式的算法，但必将大于基于复制的冗余方式。最终计算量大小由具体网络状态所 决定，即本算法可以将具体存储系统中的优势资源充分利用，从而减小节点可用性不高等劣势对数据可 用性带来的影响。 第４期 刘金芝：分布式存储系统中混合数据布局算法 ２７ ５ 结 论 数据布局算法对网络存储系统的性能有很大的影响，是提高数据处理效率的关键。通常一种数据布 局算法只适合某一特定故障水平的存储系统。本文提出的算法可以针对节点负载和通信延迟情况，计算 节点或节点集合的可用性，为未来时刻数据布局存储采用的策略提供判断的依据，从而可以动态地调整 数据的冗余度。通过与完全复制和纠删编码方式的对比分析，证明了本算法在存储量、通信量与计算量方 面具有比较好的实用性。 参考文献： ［１］Ｚｈａｎｇ Ｗｅｉ，Ｍａ Ｊｉａｎ－ｆｅｎｇ．ＬＰＣＡ——ｄａｔａ ｄｉｓｔｒｉｂｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ．Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ， ２００７，２９（３）：４５３－－４５８． ［２］王沛，韩耀伟．Ｌｉｎｕｘ中ＳｏｆｔｗａｒｅＲＡＩＤ驱动程序的机制分析【Ｊ］－／Ｊ＼型微型计算机系统，２００１，２２（３）：３０５—３０８． ［３］Ｋｕｂｉａｔｏｗｉｃｚ Ｊｏｈｎ，Ｂｉｎｄｅｌ Ｄａｖｉｄ，Ｃｈｅｎ Ｙａｎ，ｅｔ ａ１．ＯｅｅａｎＳｔｏｒｅ：ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｇｌｏｂａｌ ｓｃａｌｅ ｐｅｒｓｉｓｔｅｎｔ ｓｔｏｒａｇｅ［Ｃ］／／Ｐｒｏ ｏｆ ｔｈｅ Ｎｉｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｃｈｉｔｅｃｔｕｒａｌ Ｓｕｐｐｏ￣ｆｏｒ Ｐｒｏｇｒａｍｍｉｎｇ Ｌａｎｇｕａｇｅｓ ａｎｄ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２０００：９０－ ２０１． Ｉ４】Ｂｌａｕｍ Ｍａｒｉｏ，Ｂｒａｄｙ Ｊｉｍ，Ｂｒｏｃｋ Ｊｅｈｏｓｈｕａ，ｅｔ ａ１．ＥＶＥＮＯＤＤ：ａｎ ｏｐｔｉｍａｌ ｓｃｈｅｍｅ ｏｆｒ ｔｏｌｅｒａｔｉｎｇ ｄｏｕｂｌｅ ｄｉｓｋ ｆａｉｌｕｒｅｓ ｉｎ ＲＡＩＤ ａｒｃｈｉ— ｔｅｃｔｕｒｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，１９９５，４４（２）：１９２－２０２． ［５］Ｘｕ Ｌｉｈａｏ，Ｂｒｎｃｋ Ｊｅｈｏｓｈｕａ．Ｈｉｇｈｌｙ ａｖａｉｌａｂｌｅ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍｓ［Ｃ］／／Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｎｔｒｏｌ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ． Ｂｅｒｌｉｎ：ＳｐｒｉｎｇｅｒＶｅｒｌａｇ，１９９９：１６６－１６７． ［６］Ｊｏｓｅｐｈ Ｃｏｏｌｅｙ，Ｊｅｒｅｍｙ Ｍｉｎｅｗｅａｓｅｒ，Ｌｅｓｌｉｅ Ｓｅｒｖｉ，ｅｔ １．Ｓｏｆａｔｗａｒｅ－ｂａｓｅｄ ｅｒａｓｕｒｅ ｃｏｄｅｓ ｏｆｒ ｓｅａｌａｂｌｅ ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒａｇｅ［Ｃ］／／Ｐｒｃ ｏｏｆ ｔｈｅ ２０ｔｈ ＩＥＥＥ／１ ｌｔｈ ＮＡＳＡ Ｇｏｄｄａｒｄ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｓｓ Ｓｔｏｒａｇｅ Ｓｙｓｔｅｍｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｉｅｓ．Ｎｅｗ Ｙｏｒｋ：ＩＥＥＥ，２００３：１５７－１６４． ［７］Ｊｏｓｈ Ｂｅｎａｌｏｈ．Ｇｅｎｅｒａｌ ｉｌｎｅａｒ ｓｅｃｒｅｔ ｓｈａｒｉｎｇ【ＥＢ／ＯＬ］．（２０１０－０３－１ １）［２０１ １－０１—１５］．ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｒｎ／ｃｒｙｐｔｏ． 【８］Ｇａｒｔｈ Ｇｏｏｄｓｏｎ，Ｊａｙ Ｗｙｌｉｅ，Ｇｒｅｇｏｒｙ Ｇａｎｇｅｒ，ｅｔ ａ１．Ａ ｐｒｏｔｃｏｌｏ ｆａｍｉｌｙ ｆｏｒ ｖｅｍａｔｉｌｅ ｓｕｒｖｉｖａｂｌｅ ｓｔｏｒｇｅａ ｉｎｆｒａｓｔｒｕｃｔｕｒｅｓ【Ｃ］／／Ｃａｒｎｅｇｉｅ Ｍｅｎｏｎ Ｕｎｉｖｅｒｓｉｔｙ Ｐａｒａｌｌｅｌ Ｄａｔａ Ｌａｂ Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏ￣ＣＭＵ—ＰＤＬ一０３—１０３．Ｎｅｗ Ｙｏｒｋ：Ｓｔｏｒｍｉｎｇ Ｍｅｄｉａ．２００３． 【９】Ｒａｂｉｎ Ｍｉｃｈａｅｌ，Ｅｆｆｉｃｉｅｎｔ ｄｉｓｐｅｒｓａｌ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｆｏｒ ｓｅｃｕｒｉｔｙ，ｌｏａｄ ｂａｌａｎｃｉｎｇ ａｎｄ ｆａｕｌｔ ｔｏｌｅｒｎｃｅ［ａＪ】．Ｊｏｕｒｎａｌ ｏｆ ＡＣＭ，１９８９（３６）： ３３５－３４８． ［１０］Ｋｒａｗｃｚｙｋ Ｈｕｇｏ．Ｄｉｓｔｒｉｂｕｔｅｄ ｉｆｎｇｅｒｐｒｉｎｔｓ ａｎｄ ｓｅｃｕｒｅ ｉｎｆｏｒｍａｔｉｏｎ ｄｉｓｐｅｒｓａｌ［Ｃ］＃Ｐｒｏｃ ｏｆ １３ｔｈ ＡＣＭ Ｓｙｍｐ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｏｍｐｕｔｉｎｇ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，１９９３：２０７—２１８． 【１ １］Ｂｌａｋｌｅｙ．Ｓａｆｅｇｕａｒｄｉｎｇ ｅｒｙｐｔｏｇｒａｐｈｉｅ ｋｅｙｓ【Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ Ｎａｔｉｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｃｏｎｆｅｒｅｎｃｅ ｏｆ Ａｍｅｒｉｃａｎ Ｆｅｄｅｒａｔｉｏｎ ｏｆ Ｉｆｏｒｎｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｏｃｉｅｔｉｅｓ．Ｎｅｗ Ｙｏｒｋ：ＩＥＥＥ，１９７９：３１３－３１７． Ｈｙｂｒｉｄ Ｄａｔａ Ｐｌａｃｅｍｅｎｔ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｔｏｒａｇｅ Ｓｙｓｔｅｍ ， ｎ－＝ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｓｕ Ｔｅａｃｈｅｒｓ Ｕｎｉｖｅｒｓｉｔｙ ｆ ｏＴｅｃｈｎｏｌｏｇｙ， Ｃｈａｎｇｚｈｏｕ ２１３００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄａｔａ ｐｌａｃｅｍｅｎｔ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｂａｓｉｃ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｔｈｅ ｋｅｙ ｔｏ ｅｎｈａｎｃｅ ｄａｔａ ｐｒｏｃｅｓｓｉｎｇ ｅｆｉｃｉｅｎｃｙ ｉｎ ｄｉｓｔｒｆｉｂｕｔｅｄ ｓｔｏｒａｇｅ ｓｙｓｔｅｍｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｅｄ ａ ｕｎｉｖｅｒｓａｌ ａｐｐｒｏａｃｈ ｔｏ ｍｅａｓｕｒｅ ｓｔｏｒａｇｅ ｎｏｄｅ ａｖａｉｌａｂｉｌｉｔｙ ｂａｓｅｄ ｏｎ ｓｔａｔｅ ｖａｒｉａｂｌｅｓ ｓｕｃｈ ａｓ ｌｏａｄ ｏｆ ｓｔｏｒａｇｅ ｎｏｄｅ ａｎｄ ｎｅｔｗｏｒｋ ｄｅｌａｙ．Ａｆｔｅｒ ａｎａｌｙｓｉｓ ｔｈｅ ｅｘｉｓｔｉｎｇ ｄａｔａ ｐｒｏｃｅｓｓｉｎｇ ａｌｇｏｒｉｔｈｍｓ，ｗｅ ｒａｉｓｅｄ ａ ｎｅｗ ｈｙｂｒｉｄ ｄａｔａ ｐｌａｃｅｍｅｎｔ ａｌｇｏｒｉｔｈｍ．Ｄｉｆｆｅｒｅｎｔ ｒｅｄｕｎｄａｎｃｙ ｐｏｌｉｃｉｅｓ ａｒｅ ａｐｐｌｉｅｄ ｔｏ ｓｔｏｒａｇｅ ｎｏｄｅ ｗｉｈ ｄｉｔｆｅｒｅｎｔ ｎｏｄｅ ａｖａｉｌａｂｉｌｉｔｙ． Ａｃｃｏｒｄｉｎｇ ｔｏ ｏｕｒ ａｎａｌｙｓｉｓ，ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｈａｓ ｉｔｓ ａｄｖａｎｔａｇｅｓ ｉｎ ｓｔｏｒｅ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｃｏｓｔｓ． Ｋｅｙ ｗｏｒｄｓ：ｄｉｓｔｒｉｂｕｔｅｄ ｓｔｏｒｇｅ ｓａｙｓｔｅｍ；ｄａｔａ ｐｌａｃｅｍｅｎｔ；ｅｒａｓｕｒｅ ｃｏｄｅ；ｄａｔａ ｒｅｄｕｎｄａｎｃｙ 责任编辑盛艳
