第３７卷第１期 计算机科学 ＶｏＩ．３７ Ｎｏ．１ ２０１０年１月 一Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ Ｊａｎ ２０１０ 种基于分组管理的混合式Ｐ２Ｐ存储系统 杨磊黄浩李仁发李肯立 （湖南大学计算机与通信学院 长沙４１００８２） 摘要利用Ｐ２Ｐ的方法建立了一个Ｐ２Ｐ存储系统。以预测的网络距离对参与节点进行分组，形成由超节点维护管 理的覆盖网络。使用覆盖网络拓扑结构保持机制、ＤＨＴ数据存储机制，依据数据访问率不同的数据备份机制和数据 修复机制，提高了系统的可靠性和数据存储效率。在仿真实验基础上，验证了该存储系统的性能。 关键词Ｐ２Ｐ存储系统，网络距离，分组，副本，带宽 Ｃｏｍｐｏｓｉｔｅ Ｐ２Ｐ Ｓｔｏｒａｇｅ Ｓｙｓｔｅｍ Ｂａｓｅｄ ｏｎ Ｇｒｏｕｐ Ｍａｎａｇｅｍｅｎｔ ＹＡＮＧ Ｌｅｉ ＨＵＡＮＧ Ｈａｏ ＬＩ Ｒｅｎ－ｆａ ＬＩ Ｋｅ １ｉ （Ｃｏｌｌｉｅ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｈｕ’ｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｂａ ４１００８２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ Ｂｙ ｕｓｉｎｇ ｔｈｅ ｗａｙ ｏｆ Ｐ２Ｐ，ａ Ｐ２Ｐ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ ｗａｓ ｂｕｉｌｔ．Ｔｈｅ ｎｏｄｅｓ ｉｎｖｏｌｖｅｄ ｉｎ ｔｈｅ ｓｙｓｔｅｍ ｗｅｒｅ ｇｒｏｕｐｅｄ ｂｙ ｔｈｅ ｐｒｅｄｉｃｔｅｄ ｎｅｔｗｏｒｋ ｄｉｓｔａｎｃｅ，ａｎｄ ｔｈｅｎ ａｎ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ ｗｈｉｃｈ ｉｓ ｍａｉｎｔａｉｎｅｄ ｂｙ ｓｕｐｅｒ ｎｏｄｅｓ ｗａｓ ｆｏｒｍｅｄ．Ｂｙ ｕｓｉｎｇ ｔｈｅ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｉｃａｌ ｓｔｒｕｃｔｕｒｅ ｍｅｃｈａｎｉｓｍ ｏｆ ｍａｉｎｔｅｎａｎｃｅ，ＤＨＴ ｄａｔａ ｓｔｏｒａｇｅ ｍｅｃｈａｎｉｓｍ，ｄａｔａ ｒｅｐｌｉｃａｔｉｏｎ ｍｅｃｈａｎｉｓｍ ｂａｓｅｄ ｏｎ ｄｉｆｆｅｒｅｎｔ ｆｒｅｑｕｅｎｃｙ ｏｆ ｄａｔａ ａｃｃｅｓｓ ａｎｄ ｄａｔａ ｒｅｓｔｏｒａｔｉｏｎ ｍｅｃｈａｎｉｓｍ，ｔｈｅ ｒｅｌｉａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｓｙｓｔｅｍ ａｎｄ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｄａｔａ ｓｔｏｒａｇｅ ｉｎ ｓｙｓｔｅｍ ｗｅｒｅ ｐｒｏｍｏｔｅｄ．Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ ｗａｓ ｔｅｓｔｉｆｉｅｄ ０ｎ ｔｈｅ ｂａｓｉｓ ０ｆ ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｓｉｍｕｌａｔｉｏｎ ｅｘｐｅｒｉｍｅｎｔ， Ｋｅｙｗｏｒｄｓ Ｐ２Ｐ ｓｔｏｒａｇｅ ｓｙｓｔｅｍ，Ｎｅｔｗｏｒｋ ｄｉｓｔａｎｃｅ，Ｇｒｏｕｐｉｎｇ，Ｒｅｐｌｉｃａｔｉｏｎ，Ｂａｎｄｗｉｄｔｈ Ｐ２Ｐ存储系统已成为当前一个重要的研究领域。在Ｐ２Ｐ 网络上构建存储系统能有效利用节点间网络带宽、存储空间 和数据资源，系统具有良好的可扩展性、数据可用性和可靠 管理的方法以期取得更好的性能。文献［４３在网络坐标算法 ｃＮＰ［ ］和Ｖｉｖａｌｄｉ［ ］及ＤＨＴ算法的基础上，利用等距同心圆 簇，对节点二维网络坐标平面进行等面积划分，并根据节点所 处区域进行多层命名空间中区间的一一映射，提出了一种分 布式的拓扑感知节点聚集算法ＴＡＮＲＡ，从而有效地保持了 性。Ｐ２Ｐ存储系统的目标是有效组织系统中的节点来存储数 据。因此，系统的拓扑结构及其存储数据的可用性和可靠性， 与Ｐ２Ｐ存储系统中节点组织及数据存储备份方式有着极大 的关系。 Ｐ２Ｐ存储系统网络拓扑匹配，并降低了节点加入时延，但其应 用大多针对流媒体数据。文献Ｅ７３和文献Ｅ８－１分别采用用户行 为语义和基于主题划分Ｐ２Ｐ存储系统的方式改进数据存储 方式，提高了Ｐ２Ｐ存储系统搜索的效率。文献Ｅ９３提出了一 种基于ＯＰＥＮＤＨＴ的节点聚集算法ＲｅＤＩＲ，利用抽象出的原 语接口ｐｕｔ（）／ｇｅｔ（）为上层应用在多层节点命名空间中进行 节点分组，但算法没有考虑节点邻近度问题，导致节点间拓扑 匹配较差。 为了对系统节点进行有效的管理，提高系统数据存储的 效率及可靠性，提出了一种以预测的网络距离对系统节点进 行分组，再使用ＤＨＴ方法存储数据，最终建立一个覆盖分层 的混合式Ｐ２Ｐ存储系统的设计方案。 １相关工作 当前基于Ｐ２Ｐ的存储系统节点组织主要分为两种方式： 集中式（ｃｅｎｔｒａｉｌｉｚｅｄ）和非集中式（ｄｅｃｅｎｔｒａｉｌｉｚｅｄ）。 ２ Ｐ２Ｐ存储系统节点分组与分层算法 本文将Ｐ２Ｐ网络中网络距离相近的节点划分到同一分 组，以实现对Ｐ２Ｐ存储系统节点的分组和有效管理。为此， 先提出预测系统节点间网络距离的算法。 ２．１ 网络距离预测算法 Ｐ２Ｐ系统中两节点间网络距离的测算可通过计算系统中 数据传输时延、网络最小带宽和数据传输所经路由跳数等方 法获得。对于Ｐ２Ｐ存储系统中存储数据的可用性和可靠性 来说，数据传输时延是一个很重要的因素，而数据传输时延最 ＮａｐｓｔｅｒＥｊ］是典型的集中式系统，其利用服务器负责目录 管理的服务常受服务器的，存在单点崩溃导致系统拓扑 结构被破坏和由此引起的节点存储数据可用性不高、节点存 储数据可靠性下降等问题；Ｇｎｕｔｅｌｌａｌ２ 和ＦｒｅｅｎｅｔＥ３］是典型的 非集中式系统，由于没有服务器，查询数据时以ｆｌｏｏｄｉｎｇ 方式将消息传播到网络上，存在占用大量系统带宽、消息泛滥 和系统可扩展性差等问题。 针对上述问题，很多研究者采用了对网络节点进行分组 到稿日期：２００９—０３—０２返修日期：２００９—０６—１７ 杨本文受国家自然科学研究基金项目（９０７１５０２９）资助。 浩（１９８１一），男，硕士研究生，研究领域为分布式存储；李仁发（１９５７一）， 磊（１９７６一），男，博士生，讲师，研究领域为分布式系统及网络；黄男，教授，博士生导师，研究领域为嵌入式系统与网络；李肯立（１９７１一），男，博士后，教授，研究领域为并行处理、科学可视化。 ・６４・ 主要的影响因子是传输两节点问的可用带宽。在大规模Ｐ２Ｐ 网络中，由于网络节点频繁加入或退出系统导致的高动态性， ｆｏｒ（ｉ＝０； ＜ｇ； ＋＋） ／／每次循环得到一个分组，共分ｇ组 ｛从初始网络中选取一个节点 ； ／／以此节点为圆心进行分组 ｆｏｒ（； ∈Ｓ，ｊ＝／－ｎ；；） 使得综合考虑数据传输时延、网络最小带宽和数据传输所经 路由跳数等因素时，测算网络距离代价过高且难以实现，并且 计算系统所有节点的数据传输时延所需代价也是无法承受 的。因此，本文决定采用数理统计中随机抽样的方法，通过采 ／／以预测的网络距离为半径分组 （ｉｆ（Ｔ（ｎ， ）≤ｄｉｓ） 集的有限样本信息来预测网络数据传输时延，再利用预测到 的较合理的网络数据传输时延对系统节点进行分组。 算法如下：在大规模网络中随机取一节点ｋ，判断与其相 （添加节点Ｊ到分组ｃ［ｎ］； Ｓ—Ｓ－－｛Ｊ｝； ｝ ｌ ｌ 邻节点间网络数据传输时延。假设其有 个相邻节点，节点 ｋ与这ｎ个相邻节点间网络可用带宽分别为ＢＩＴ ，ＢＩＴ２，…， ＢＩＴｏ，假设传输数据块大小为ＤＡＴＡ （肠），ｒｉ（ 一１，２，…， ） 在分组中选取超节点； 为影响因子，可简单取Ｆｉ一１。则可测得节点ｋ与这 个相邻 节点问网络数据传输时延分别为Ｔ 一ｒｉＤＡＴＡ ／ＢＩ （ 一１， ２，…， ），再取其网络数据传输时延平均值为 Ｄ１一（∑７－１ ）／ 一（∑ ｒｉＤＡＴＡ女／ＢＪ ）／ 依此类推，可取得ｍ个随机节点的网络数据传输时延的 平均值Ｄ ，Ｄ２，…，Ｄ ，假定网络距离的预测值为将所得各采 样节点网络数据传输时延的平均值再取平均值，即预测网络 距离ｄｉｓ＝（∑ １Ｄｉ）／ｍ。 ２．２网络节点分组算法 该算法的思想是依次从初始网络中随机选取一个节点， 以该节点为圆心，预测网络距离为半径，其内的所有节点都划 入一个分组，再将获得分组的节点从初始网络中移除。以此 方法循环划分，可将初始网络中大部分节点划入分组。此时， 可在各分组节点中选取若干在线时间长、存储容量及网络可 用带宽较大的节点作为超节点，考虑到在大规模网络中节点 存储容量很难准确判断，故本文中超节点的选取主要考虑节 点在线时间的长短及网络的可用带宽。具体方法如下：为确 定某分组中超节点，在该分组中随机选取若干样本节点（不少 于５０个），采用定期心跳的方法（让该分组中选中的每个样本 节点定期向其对应的目录节点（已指定好）报告自己的存在状 态，如果对应的目录节点一段时间没有收到心跳，则认为该样 本节点下线，并记录下该样本节点上次在线时的时间ｔｉｍｅｉ）确 定节点在线时间长短；确定各样本节点的网络可用带宽的方法 为：假设某样本节点有 个相邻节点，样本节点与这 个相邻 节点间网络可用带宽分别为ＢＩＴ１，ＢＩＴｅ，…，ＢＩＴ，，，则取该样 本节点的平均网络可用带宽Ｂｉ一（∑ ＢＪ ）／ｎ为该样本节 点网络可用带宽。设节点在线时间长短及网络可用带宽对其 被选为超节点的影响因子分别为ｍ 和ｍ２（其中ｍｌ＋ｍ２— １，Ｏ＜ｍ１＜１，０＜ｍ２＜１），则Ｓｎｏｄｅ 一ｍ１×ｔｉｍｅ ＋ｍ２×Ｂ 中 Ｓｎｏｄｅ 较大即可确定其为该分组超节点。以此方法，在各个 分组中选取若干次，可在每个分组确定若干个超节点，各分组 中超节点负责将该分组中其附近普通节点组织起来。在初始 化分组算法中，圆心节点选取的随机性必然导致少量剩余节 点未划入分组，因此，考虑剩余节点到各分组超节点间的网络 距离平均值，将取值最小的分组加入并连接到该分组网络距 离最小的超节点下。至此，整个初始网络中全部节点分组完 毕。 算法如下：假设Ｓ为当前初始网络中所有节点的集合， ｄｉｓ为预测的网络距离，ｇ为分组个数，Ｔ（ｎ， ）为节点 和节 点 之间的网络数据传输时延，Ｃ［ ］为一个分组。 ｗｈｉｌｅ（Ｓ非空） ／／对未加入分组的剩余节点添加到网络距离最近的分组 ｛ ｆｏｒ（ｋ∈Ｓ，ｉ＝０； ＜ｇ；Ｈ一十） ｛ 计算节点ｋ到各分组超节点的网络距离； ｝ 计算节点ｋ到各分组超节点的网络平均距离； 添加节点ｋ到网络平均距离最小的分组； ｝ ２．３覆盖网络分层及拓扑结构保持机制 为更好地对已分组节点进行管理，利用了超节点来对已 分组的系统进行分层管理。首先，对每个分组内超节点采用 ｃｈｏｒｄＥ” 方式组织，形成一个环形拓扑结构，各超节点附近的 普通节点均与该超节点连接，各超节点所属普通节点之间采 用随机组合方式连接。为确保各分组间的连通性，从各分组 内的超节点中随机选取一个与其它分组的一个超节点连接， 形成环形拓扑后，这些超节点又彼此交互连接，最终形成一个 内部环结构。由此，将存储网络划分为一个三层覆盖网络，如 图１所示。 ・剩余节点 ・超节点 。普通节点 图１三层覆盖网络图 对于Ｐ２Ｐ存储覆盖网络，当网络拓扑结构发生变化时， 其分层的拓扑结构的保持对存储系统性能优劣非常重要。为 此，我们提出一种网络分层拓扑结构保持的策略。具体方法 是：对分组中形成ｃｈｏｒｄ环路的第二层超节点保存至少一个 备份节点（可从２．２节选取超节点方法中选取Ｓｎｏｄｅ 较大的 节点作为备份节点）；对于形成第三层内部环结构的超节点， 考虑到其对各个分组之间保持连通的重要性，为其保存至少 两个备份节点，如图２所示。其中每个超节点和其备份节点 均记录该超节点的２个前继超节点和后２个后继超节点的信 息。这样一旦该超节点失效，可立即启用其备份节点替代其 位置；一旦该超节点的前继或后继超节点失效，可立即使用失 效超节点的前继或后继超节点作为自己现在的前继或后继节 点，以保持环路拓扑结构的完整性。由理论分析可知，假设每 ・ ６５ ・ 个节点失效概率为１／２，仅当连续两个超节点及其备份节点同 时失效（概率至多为１／２ ）第二层拓扑结构才可能出现中断的 情况；仅当超节点及其备份节点同时失效（概率至多为１／２。） 第三层拓扑结构才可能出现中断的情况。可见使用该方法 属超节点信息索引表中注册其ＮｏｄｅＩＤ即可。 ３．２数据备份机制 数据备份的目的是为了提高存储系统数据的可用性和可 靠性，使系统不因某些节点失效而丢失其存储的数据。文献 后，覆盖网络拓扑结构完整性被破坏的概率很低。 ：≤ ．一～～ ， ， ：、 图２分组内覆盖网络拓扑保持图 ３数据存储与备份机制 将网络距离相近的节点分组并利用超节点管理的方法层 次化后，系统便可充分利用节点问网络距离的邻近性。为使 Ｐ２Ｐ存储系统存储数据具有更好可用性和可靠性，提出了数 据的存储和备份机制。 ３．１数据存储机制 本文采用ＤＨＴ方式进行数据存储。具体方法是：首先 将网络中各节点根据其标志（ＩＰ地址或域名）按规定的Ｈａｓｈ 算法映射成一长度为Ｍ位（ｂｉｔ）的全球唯一标志符ＮｏｄｅＩＤ， 并将其唯一分配给该节点；对系统中需要存储的数据根据其 标志（文件名）按规定的Ｈａｓｈ算法映射成一个长度为』Ⅵ位 （ｂｉｔ）的全球唯一标志符ＤａｔａＩＤ，再将每个数据对象都存储在 与该对象ＤａｔａＩＤ相近的ＮｏｄｅＩＤ节点上。为此，分组内各超 节点与其备份节点维持着一张与其相连普通节点ＮｏｄｅｌＤ相 关的信息索引表（为降低超节点负担，各超节点与其备份节点 不存储数据，仅维持一张普通节点ＮｏｄｅＩＤ信息索引表，当超 节点负担过重时，可使用备份节点作ａｇｅｎｔ），第三层超节点 ＮｏｄｅｌＤ设置为网络中已知成员节点，可为数据存储查询提供 其所知的信息。在数据存储查询时，只要知道所查询数据的 ＤａｔａＩＤ及第三层超节点ＮｏｄｅＩＤ的位置，查询超节点中与其 相连节点ＮｏｄｅＩＤ信息索引表就可找到存储该数据的节点。 具体方法是：先在该第三层超节点所在分组内进行路由查询， 如相近ＮｏｄｅｌＤ不在本分组内，此时可以通过第三层超节点 内部环结构将此数据ＤａｔａＩＤ广播到其它分组超节点之上，再 采用相同的组内查询方法，最后总能为需要存储的数据找到 相近ＮｏｄｅｌＤ的普通节点（假设网络节点总数为～，网络被划 分为ｇ个组，一个分组中节点数量大致为Ｎ／譬（Ｎ／ｇ＜＜Ｎ）， 且分组内各超节点均维持着各自相连普通节点ＮｏｄｅＩＤ，其数 据存储位置查询时延代价将非常小）。 考虑到各节点存储空间有限，当某节点存储的数据超过 设定的阈值ＴＨ１时，将其最近最少访问的数据转存到其它 存储空间未超过阀值ＴＨ１的相连普通节点上，并将此消息 通知与其相连的超节点。分组内，各超节点采用定期心跳机 制确认其所连普通节点是否失效，当某普通节点失效时，删除 其在超节点和备份节点中的ＮｏｄｅｌＤ索引项；如超节点失效， 备份节点将立刻取代其位置。当有新节点需加入系统时，先 为其确定一个全球唯一标志符ＮｏｄｅｌＤ，再按剩余节点选择分 组的方法确认其加入的分组及所连超节点，加入成功后，在所 ・ ６６ ・ ［ｎ］的统计分析表明，在特定分组子网中，数据查询过程的重 复率很高，这是因为网络存在一些存储着热点数据的高访问 率节点。这些高访问率的热点数据的备份，对整个系统数据 可用性和可靠性的提高起着重要作用。因此，本文按数据访 问率的高低采用不同的数据备份机制。当系统节点上数据存 储成功且运行一段时间后，对于访问率低于设定阈值ＴＨ２ 的数据，考虑到备份数据时所需带宽和路由开销对整个系统 数据可用性和可靠性的影响，采用组内备份的方式。具体方 法是：需备份数据节点随机均匀的选择ｎ个（该参数为创建副 本的数目，需用户预先设定）相连组内节点，在这些节点上创 建该数据的副本，并将此信息写入与其相连的超节点信息索 引表中；对访问率高于设定阈值ＴＨ２的数据，采用组内备份 和组间备份的方式，即对访问率高的数据有选择的备份到其 它的分组节点中，再将其备份信息写入与其相连的超节点信 息索引表。由于存储网络采用的是覆盖分层的超节点管理拓 扑结构，当有节点存储数据失效时，系统可通过查询信息索引 表的方式在组内或组间快速找到所需备份数据信息，且组间 备份方式较组内备份方式容灾性更强，更适合于大规模存储 系统中重要数据信息的备份。 ３．３数据修复机制 由于Ｐ２Ｐ存储网络的高动态性，当系统节点频繁加入和 退出时，节点存储数据及其副本可能部分丢失甚至因受损而 无法还原，从而降低系统存储数据的可用性及可靠性。为保 证数据的可靠性并使其始终存在一定数目的副本，我们设计 的Ｐ２Ｐ存储系统将周期性地检测并修复丢失的数据及其副 本。检测过程由系统各分组的超节点周期性地检测其所属普 通节点所存数据及其备份的副本数目（为降低超节点负担，也 可考虑由各普通节点周期性地读取保存其数据副本的节点中 其备份的副本，看其是否存在）。修复分为两种情况：存储数 据的修复和备份副本的修复。存储数据的修复是当检测出某 普通节点的存储数据丢失或受损后，立即启用其副本备份节 点来修复其丢失或受损的数据；为降低因立即修复副本而增 大网络流量使系统开销增加，当节点存储数据保存完好，其备 份副本因受损减少的修复，仅当备份副本数目减少到一半时 才进行副本的修复。 ４仿真实验和性能分析 ＭＩＴ的ｃｈｏｒｄ算法采用一维环形空间结构组织节点，该 算法思路简洁清晰，性能较好，具有很高的应用价值。但在 ｃｈｏｒｄ系统中，逻辑相邻的节点物理位置未必相邻（逻辑相邻 节点之间物理位置可能很远），从而导致在大规模网络系统 中，当有节点频繁加入退出系统时，系统路由效率降低，节点 存储数据的一致性和可靠性下降，节点单位时间内处理消息 数过多等问题。本文设计算法将系统中网络距离相近的节点 划分到同一分组由超节点管理，使逻辑位置相邻的节点物理 位置（节点网络距离）也相近。因此，对ｃｈｏｒｄ系统与本文算 法从数据存储定位的路由查询跳数和节点加入退出系统时系 统平均处理消息数这两个指标进行对比分析。 在Ｉｎｔｅｌ Ｃｏｒｅ ２ Ｄｕｏ １．７３Ｇ处理器和Ｌｉｎｕｘ Ｒｅｄｈａｔ ９．０ 处理消息数略低。分析认为，这是因为在系统分组和选取各 环境下，使用ＮＳ－２网络仿真器对实际网络情况进行模拟，通 分组的超节点阶段，较好的样本节点采样，能更真实地反映系 统的实际情况，因此构建的混合系统在处理节点加入或退出 系统时的开销降低。 总之，上述实验结果有效证实了随着系统规模的增大，本 过０ｔｃｌ和Ｃ＋＋程序设计分别实现了Ｃｈｏｒｄ和本文算法，并 使用ＧＴ－ＩＴＭ拓扑发生器生成了网络拓扑图。为了尽可能 模拟实际网络情况，结合文献Ｅ１２，１３］结论和当今网络实际情 况将节点所拥有带宽设置为４个等级。其中约５ 的节点模 拟高级用户拥有１００Ｌｅｖｅｔ带宽，１５ 的节点拥有１０Ｌｅｖｅｌ带 文设计系统的数据存储定位的路由查询跳数较ｃｈｏｒｄ系统有 了较大改进，而本文算法所带来的系统维护开销却与ｃｈｏｒｄ 系统维护开销相差不大，在可接收范围之内。 宽，６Ｏ 的节点模拟大部分用户使用的ＤＳＬ上网方式拥有 １Ｌｅｖｅｌ带宽，２Ｏ 的节点模拟拨号上网的用户拥有０．１Ｌｅｖｅｌ带 宽；各等级节点在线时间随机取值，其在线时间单位为小时。 分别考虑１０００，２０００，３０００，４０００，５０００，６０００，７０００，８０００， ９０００，１００００个节点的网络，取影响因子和数据块大小ｒｉ一１， ＤＡＴＡ —ｌＯ０００（ｋｂ）进行分组，分组后，每个分组取５０个节点 按影响因子 Ｉ—Ｏ．５，ｍ２一Ｏ．５按公式Ｓｎｏｄｅｉ—ｅｌ×ｔｉｍｅｉ＋ｍ２ ×Ｂ（Ｂｆ取Ｌｅｖｅｌ值）选取超节点及其备份节点。为得到更准 确的仿真结果，对不同节点个数的系统各重复进行２Ｏ次实验 再取平均值。 本文算法与ｃｈｏｒｄ系统数据存储定位路由查询跳数实验 结果如图３所示。由图３可以看出，本文算法对数据存储定 位的路由查询跳数比ｃｈｏｒｄ算法有了较大改进。分析认为， 本文设计的系统中，各分组内节点个数远小于ｃｈｏｒｄ系统中 节点个数，且节点问网络距离较近，在超节点管理下进行查找 必然能有效提高找到目标节点的效率。 ８ ７萋： ４ 萎 节点个数 图３平均路由查询跳数对比 １加 ７０ 节点个数 图４节点加入系统平均发送消息个数对比 ６０ 帕ｌ５０ 罄１４０ １３０ １２ ０ ０ 节点个数 图５节点退出系统平均发送消息个数对比 本文算法与ｃｈｏｒｄ系统节点加入和退出系统时系统平均 处理消息数实验的结果如图４和图５所示。由此可见，随着 网络节点数量的增加，本文设计的算法在节点加入和退出系 统时系统平均处理消息数有时较ｃｈｏｒｄ系统略大，特别是节 点规模为５０００和９０００时，节点加入系统时平均处理消息个 数增幅较大。分析认为，这是由于本文算法较ｃｈｏｒｄ算法在 维护系统拓扑结构时更加严密，节点加入系统时在超节点的 注册及其备份比ｃｈｏｒｄ系统更加频繁且复杂而导致的结果。 在节点规模为３０００和８０００时，本文算法较ｃｈｏｒｄ系统平均 结束语本文详细描述了一种建立在Ｐ２Ｐ上的分布式 存储系统设计方案。提出了一种按预测网络距离对节点进行 分组，在超节点管理下建立三层覆盖网络的机制，并给出了有 效保持这种拓扑结构的方法。在此基础上，给出了一种按 ＤＨＴ方式的数据存储机制，并为之设计了详尽的数据副本备 份和修复方法，为存储数据的可用性和可靠性提供了有效保 障。在后续工作中，我们将对Ｐ２Ｐ存储系统中副本和纠删 码ｌ】叫相结合的备份机制的运用、节点问Ｂｙｚａｎｔｉｎｅ 错误的 处理及系统各影响因子、阈值的更优化组合做进一步研究。 参考文献 ［１］＆ＮＥＴ ＮＥＷＳ．Ｎａｐｓｔｅｒ ａｍｏｎｇ ｆａｓｔｅｓｔ—ｇｒｏｗｉｎｇ Ｎｅｔ ｔｅｃｈｎｏｌｏ ｇｉｅｓ．２０００ ［２］Ｇｎｕｔｅｌｌａ．ｈｔｔｐ：／／ｗｗｗ．ｇｎｕｔｅｌｌａ．ｃｏｒｎ／２００３ ［３］Ｃｌａｒｋｅ Ｉ，Ｓａｎｄｂｅｒｇ Ｏ，Ｗｉｌｅｙ Ｂ，ｅｔ ａ１．Ｆｒｅｅｎｅｔ：Ａ ｄｉｓｔｒｉｂｕｔｅｄ ａ ｎｏｎｙｍｏｕｓ ｉｎｆｏｒｍａｔｉｏｎ ｓｔｏｒａｇｅ ａｎｄ ｒｅｔｒｉｅｖａｌ ｓｙｓｔｅｍ［Ｃ］／／Ｗｏｒｋ— ｓｈｏｐ ｏｎ Ｄｅｓｉｇｎ Ｉｓｓｕｅｓ ｉｎ Ａｎｏｎｙｍｉｔｙ ａｎｄ Ｕｎｏｂｓｅｒｖａｂｉｌｉｔｙ．２０００： ２５ ３１ ［４］段翰聪，卢显良，唐晖，等．基于ＤＨＴ的拓扑感知节点聚集算法 【Ｊ］．计算机研究与发展，２００７，４４（９）：１５５７—１５６５ ［５］Ｃｅｃｃａｎｔｉ Ａ，Ｊｅｓｉ Ｇ Ｐ．Ｂｕｉｌｄｉｎｇ ｌａｔｅｎｃｙ－ａｗａｒｅ ｏｖｅｒｌａｙ ｔｏｐｏｌｏｇｉｅｓ ｗｉｔｈ ｑｕｉｃｋＰｅｅｒ［Ｃ］ｆ Ｊｏｉｎｔ Ｉｎｔ 、Ｃｏｎｆ ｏｎ Ａｕｔｏｎｏｍｉｃ ａｎｄ Ａｕｔｏｎｃ＞ ｍｏｕｓ Ｓｙｓｔｅｍｓ ａｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｔｗｏｒｋｉｎｇ Ｓｅｒｖｉｃｅｓ．Ｐａｐｅｅｔｅ，Ｔａｈｉｔｉ，２００５ ［６］Ｎａｋａｏ Ａ，Ｐｅｔｅｒｓｏｎ Ｌ，Ｂａｖｉｅｒ Ａ Ａ ｒｏｕｔｉｎｇ ｕｎｄｅｒｌａｙ ｆｏｒ ｏｖｅｒｌａｙ ｎｅｔｗｏｒｋｓ［Ｃ］／／ＩＥＥＥ ＳＩＧＣＯＭＭ．ｋａｒｌｓｒｕｈｅ，Ｇｅｒｍａｎｙ，２００３ ［７］邱志欢，肖明忠，代亚非．一种基于Ｐ２Ｐ环境下的基于用户行为 的语义检索方案＿Ｊ］．软件学报，２００７，１８（９） ［８］傅向华，冯博琴，马兆丰，等．基于主题划分的有组织Ｐ２Ｐ搜索 算法【ｌＪ］．西安交通大学学报，２００５，３９（１２） ［９］Ｒｈｅａ Ｓ，Ｇｏｄｆｒｅｙ Ｂ，Ｋａｒｐ Ｂ，ｅｔ ａ１．ＯｐｅｎＤＨＴ：Ａ ｐｕｂｌｉｃ ＤＨＴ ｓｅｒｖｉｃｅ ａｎｄ ｉｔｓ ｕｓｅｓ［（＝］／／ＩＥＥＥ ＳＩＣ，ＣＯＭＭ．Ｐｈｉｌａｄｅｌｐｈｉａ，ＵＳＡ，２００５ ［１ｏ３ Ｓｔｏｉｃａ Ｉ，Ｍｏｒｒｉｓ Ｒ，Ｋａｒｇｅｒ Ｄ，ｅｔ ａ１．Ｃｈｏｒｄ：Ａ ｓｃａｌａｂｌｅ ｐｅｅｒ－ｔｏ－ ｐｅｅｒ ｌｏｏｋｕｐ ｓｅｒｖｉｃｅ ｆｏｒ Ｉｎｔｅｒｎｅｔ ａ ｐｐｌｉｃａｔｉｏｎｓ［Ｃ］ｆ Ａｎｎｕａｌ Ｃｏｎｆ． ｏｆ ｔｈｅ Ｓｐｅｃｉａｌ Ｉｎｔｅｒｅｓｔ Ｇｒｏｕｐ ｏｎ Ｄａｔａ Ｃｏｍｍｕｎｉｃａｔｉｏｎ（ＳＩＧ— Ｃ０ＭＭ ２００１）．２００１：１２４—１３７ ［１１］Ｒａｍａｓａｍｙ Ｓ，Ｓｈｅｎｋｅｒ Ｓ，Ｓｔｏｉｃａ Ｉ．Ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｈｔｓ： Ｓｏｍｅ ｏｐｅｎ ｑｕｅｓｔｉｏｎｓ［ ｝Ｐｒｏｃ，ｏｆ ｔｈｅ ｉｇｒｉ￣２，Ｃａｍｂｒｉｄｇｅ，２００２ ［１２］Ｃｈａｗａｔｈｅ Ｙ，Ｒａｔｎａｓａｍｙ Ｓ，Ｂｒｅｓｌａｕ Ｌ，ｅｔ ａ１．Ｍａｋｉｎｇ ｇｎｕｔｅｌｌａ－ｌｉｋｅ Ｐ２Ｐ ｓｙｓｔｅｍ Ｓ ｓｅａｌａｂｌｅ［Ｊ￣．ＡＣＭ ＳＩＧＣＯＭＭ，２００３ ［１３］Ｓａｒｏｉｕ Ｓ，Ｇｕｍｍａｄｉ Ｐ Ｋ，Ｇｒｉｂｂｌｅ Ｓ ｎ Ａ Ｍｅａｓｕｒｅｍｅｎｔ Ｓｔｕｄｙ ｏｆ Ｐｅｅｒ－ｔｏ－Ｐｅｅｒ Ｆｉｌｅ Ｓｈａｒｉｎｇ Ｓｙｓｔｅｍｓ［ｃ３／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｍｕｌｔｉ— ｍｅｄｉａ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ ２００２（ＭＭＣＮ’０２）．Ｓａｎ Ｊｏ— ｓｅ，ＣＡ，Ｊａｎ．２００２ ［１４］田敬，代亚非．Ｐ２Ｐ持久存储研究综述［Ｊ］．软件学报，２００７，１８ （６）：１３７９—１３９９ ［１５］杨磊，黄浩，李仁发，等．Ｐ２Ｐ存储系统拜占庭容错机制研究［Ｊ］． 计算机应用研究，２００９，２６（１） ・ ６７ ・
