基于Chord网络模型的改进数据复制方法

2017-11-01 13:05刘立芳侯力元齐小刚

重庆邮电大学学报(自然科学版) 2017年5期

关键词：后继失败率副本

刘立芳，侯力元，齐小刚

(1.西安电子科技大学计算机学院，西安 710071；2.西安电子科技大学数学与统计学院，西安 710071)

基于Chord网络模型的改进数据复制方法

刘立芳1，侯力元1，齐小刚2

(1.西安电子科技大学计算机学院，西安 710071；2.西安电子科技大学数学与统计学院，西安 710071)

根据现有复制策略在局部节点故障时数据查找失败率高的缺点，提出一种针对Chord网络的数据复制方法——Rd-Chord(rearranged replication method based on Chord)。利用离散存储的方法，将数据复制到Chord覆盖网根节点前继相对分散的节点中，即使某个甚至几个区域节点全部故障，其他区域依然有数据副本可供使用。同时，为了维护网络结构和key迁移，针对Rd-Chord提出基础更新和定期更新2种更新策略。为了验证该方法的优越性，通过计算机仿真对前继复制、后继复制和Rd-Chord方法进行了大量的比较实验。实验结果表明，Rd-Chord方法能够解决节点区域性故障问题，在保证平均查找效率的前提下，查找失败率降低了近10%，明显优于其他方法。

P2P网络；Chord模型；数据复制；区域性故障

0 引言

近年来，对等(peer-to-peer，P2P)网络已经成为关注的焦点，成为构建大规模分布式应用的范例[1]。P2P网络是一种分布式网络，打破了传统的C/S(client/server)模式，网络中每个节点地位都是对等的，没有中心化的服务器，不存在系统瓶颈，每个节点既充当客户端又充当服务器，因而具有很高的资源利用率。P2P网络分为非结构化和结构化网络。以Gnutella为代表的非结构化P2P网络，不存在目录服务器，解决了单点瓶颈问题，不存在单一故障点。然而其缺点也是明显的：采用洪泛机制加重了网络通信负担，其查询机制在系统规模扩大时不具有可扩展性；另外，由于查询报文被限制在特定的范围内，所以并不能保证一定可以找到网络中存在的目的数据。

结构化P2P网络实现了节点之间在应用层的互连，然而当节点故障时，如何保证数据的可用性成为必须要解决的问题。在节点失效情况下，保证数据可用性最基本和必要的手段，就是要对存储的数据做一定的冗余。没有冗余的数据，节点故障后，其上的数据必然无法恢复。DHT(distributed hash table)网络中，需要找到一个最合适的节点集合来存放冗余数据，以达到最好的数据持久性。不适当的节点组合将可能极大地消耗系统带宽，甚至威胁系统中数据的持久性。例如，将数据的多个副本放在一个错误相关的节点集合上，即节点集合中的节点可能由于区域断网或断电而同时离线。这样即便有多个数据副本，也容易出现数据不可用的情况。

本文的主要贡献：①针对现有复制策略在局部节点故障时查找失败率高的缺点，在Chord模型基础上提出一种数据复制方法——Rd-Chord(rearranged replication method based on Chord)来保证数据可用性，并和现有主要数据复制方法进行比较。仿真结果显示，就解决节点区域性故障而言，Rd-Chord在保证平均查找效率的前提下，查找失败率降低了近10%，远远优于其他方法；②在Rd-Chord的基础上，为了维护网络结构和key迁移，提出基础更新和定期更新2种更新策略。基础更新在节点加入或离开网络时启用。定期更新机制被定期触发，目的在于在动荡环境下保持复制因子。

1 相关工作

文献[2]中对当前分布式系统的数据存储方式做了比较，针对目前分布式存储系统的不足，以发展相对比较成熟的P2P技术作为存储结构体系，对数据冗余容错技术、副本管理机制、资源的搜索算法做了详细的探索与研究。数据冗余存储问题中，在最小化副本数目和最大化副本命中率之间存在一个权衡。副本越多，复制成本越高，副本命中率也越高，反之亦然。理想的复制方法是以低成本给用户提供延迟较低的查询服务。现有复制方法可以被分为四类：随机复制、ServerEnd复制、路径复制和ClientEnd复制。随机复制，如文献[3]，将文件复制到随机选择的节点中；ServerEnd复制，如文献[4-6]，将文件复制到P2P网络中文件拥有者附近的节点；路径复制，如文献[7-8]，将文件复制到它查询路径路过的所有节点中。在随机复制、ServerEnd复制和路径复制中，文件查询直到到达文件持有者或者副本节点才停止转发。随机复制和路径复制由于副本数很多，其中一些副本没有被很好地利用，会导致开销很高。因此，文献[9]中提出了有效的自适应文件复制算法，该算法是基于路径复制改进的。在该算法中，某个文件的查询流量枢纽为该文件许多查询路径相交的节点。该算法选择某个文件查询流量枢纽和频繁的请求者为副本节点，在限制副本数的同时增加命中率；ClientEnd复制，如文献[10-11]，将文件复制到频繁请求的节点中，使它们可以不用对查询进行路由，直接存取文件。然而，由于其他请求者的查询消息有很低的可能性通过频繁请求者，ClientEnd不能保证高命中率。在以上副本放置的基础上，还有数据冗余度维护方法[12]、负载均衡技术[13-16]、数据一致性维护等策略[17-21]。

本文主要以ServerEnd复制[6]的前继复制方法为基础，在Chord模型中，将副本存储在标识符为(rid-2k-1)%·2m，k=1,2,…,r的节点中，其中，rid为根节点id，k为副本数目。

2 问题描述

本文根据现有的数据复制方法，在Chord模型基础上提出一种在局部节点故障时增加数据可用性的复制方法——Rd-Chord方法。

2.1 模型建立

图1是Chord模型的一个例子，有6个节点，每个节点存储一个资源集合。其中，keyk被分配给在标识符空间中标识符等于或者大于k的第1个节点。该节点称为k的后继，由successor(k)表示。例如，在图1中，successor(1)，successor(2)和successor(3)都是节点3，则key 1，2和3将会被存储在该节点。Chord用一致性散列，以更高的概率保证节点间的负载均衡。为了完成一次lookup(k)操作，查询沿着Chord环转发，寻找Finger table中节点标识符大于或等于k的，最接近节点标识符的节点。

图1 Chord模型Fig.1 Chord model

2.2 改进的数据复制方法——Rd-Chord方法

为了利用Chord的查询路由机制，前继复制方法将副本存储在持有节点连续前继节点中，副本存储较为集中，在节点区域性故障时不能保证数据可用性。Rd-Chord同样将复制数据到持有节点的前继节点中以减少定位被请求数据的跳数。不同的是，为了提高数据可用性，并克服数据副本存储集中的缺点，Rd-Chord采用离散存储的方式，将数据复制到Chord覆盖网(rid-2k-1)%·2m，k=1,2,…,r的节点中。这样，副本节点较为分散，并有规律可寻，当局部副本节点故障时，其他部分数据依然可用。

算法1描述了本文提出的数据复制机制。每个节点维护r-1个通过计算得出的副本节点replicateList。根节点n将数据复制到每个属于replicateList的节点中。复制程序通过旨在更新副本key值的updateReplicas过程实现。该算法每个节点在O(n)时间内完成对副本的复制。

算法1Rd-Chord复制方法。

1: n.improvementReplication(k)

2: fori=0 tor-2 do

3:nextReplica=n.replicateList[i];

4:nextReplica.replicatedKeys.put(k);

5: end for

为了更好地理解Rd-Chord，不失一般性，以key 2的复制为例来进一步阐述，如图2所示。假设节点2为根节点，当m=1，rid=2，k=4时，副本存储在(2-21-1)%·24，(2-22-1)%·24，(2-23-1)%·24，(2-24-1)%·24，也就是标识符为1，0，14和10的节点中。可以看出，副本节点分布较为分散，数据可用性较好。

图2 基于Chord模型的数据复制Fig.2 Data replication based on Chord model

更新算法用来解决复制时机的问题。有2种情况：①节点加入或者离开网络时，应用下面介绍的基础更新算法对数据进行迁移或复制。每个数据根据复制因子对副本进行编号，不能超过副本数目阈值；②为了应对节点故障，周期性出发定期更新策略对网络中的副本数进行探测，以保证每个数据的复制度。

为了定义一个有效的P2P数据复制方法，必须考虑到节点故障的情况。因此，本文会详述此后在实现不同复制方法时涉及到的稳定算法的不同策略。为了维护网络结构和key迁移，本文提出2种更新策略(算法2)，基础更新和定期更新。该算法同样在O(n)时间内完成对网络的更新操作。

基础更新策略在节点加入或离开网络时启用。比如说在节点n离开时，数据必须已经从节点n成功迁移到它的前继n′。这个过程在改进的复制方法中需要更新successorList。基础更新算法根据复制方法自适应的。比如说，在后继复制方法中，当节点n离开网络时，n的后继存储n负责的key并更新replicatedKeys列表。

算法2更新算法。

1: n.updateReplicas(k)

2: fori=0 tor-2 do

3: replicaNode = replicaList[i];

4: replicaNode.addReplica(myKeys);

5: end for

6: n.verifReplicas(k)

7: fori=0 toreplicatedKeys.lengthdo

8: root = successor(replicatedKeys[i]);

9: root.verifReplicas(n);

10: end for

11: n.addReplica(keys)

12: n.replicatedKeys.put(keys);

举一个简单的例子，如图3所示。在节点n加入系统时(见图3a)，节点n获取ns作为它的后继，此外，ns将自己负责的key分成2部分：kns和kn，kn为所有小于等于节点nID的key。n从ns复制，并不考虑副本(见图3b)。这时，节点ns收到节点n的通知，会把n作为自己的前继(见图3c)，然后np把n作为自己的后继，最后，np通知n，让n把自己作为n的前继(见图3d)。

图3 节点加入Fig.3 Node to join

节点离开如图4所示，假设节点n离开系统，它的ID在节点np和ns之间。在离开系统时，节点n先通知前继和后继ns自己即将离开，告诉np自己的后继ns的地址(见图4a)；然后，前继节点np断开与节点n的链接(见图4b)，后继节点ns从节点n复制所有节点n负责的数据和副本数据(见图4c)；最后，节点n退出系统，前继节点np将自己的后继指针指向ns，让ns作为自己的后继节点(见图4d)。此时，节点n的离开过程已经完成。

图4 节点离开Fig.4 Node to leave

定期更新机制被定期触发，目的在于在动荡环境下保持复制因子。有2个目标：①每个根节点定期联系它的所有副本节点来保证正确维护合适的副本(updateReplicas)；②每个节点保证只维护自己负责的key(verifReplicas)。因此，为了确保副本是最新的，它联系所有副本key的后继。

2.3 已有方法的故障情形分析与改进研究

为了更好地理解本文改进复制方法——Rd-Chord方法的优点，考虑图5中描述的lookup情景。节点11发起lookup(2)操作并由不同的复制策略处理，复制因子在该例中为4。根据标识符顺序，将Chord模型中的节点分为8个区域，假设故障区域数cn=3。

1)后继复制方法。图5描述了后继复制处理过程。假设节点11执行lookup(2)的请求，r=4。为了在使用后继复制的Chord网络中找到key 2，节点11由在Finger table中寻找2的前继开始，也就是节点15。根据Chord路由算法，在节点15执行相同的查找过程，在节点15的Finger table中查找2的前继，也就是节点1。节点1再转发请求给节点2，也就是存储被请求资源的节点。节点11发起的lookup(2)通过3跳到达successor(2)。

就跳数而言，在通常情况下后继复制并没有减少lookup的跳数，除非lookup(k)操作由复制k的后继发起。否则，lookup查询将会被路由到successor(k)。

就抗毁性来说，故障区域是随机挑选的，假设刚好是区域1、区域2和区域3，则存储资源2的节点全部故障，在该网络中资源2是不可用的。

2)前继复制方法。该方法和后继复制相比减少了2跳，如图6所示。这是由于节点2复将key 2复制到了节点15，lookup过程在并没有到达successor(2)时就已经完成。因此，节点11只需要一跳便能完成lookup(2)操作。就抗毁性而言，当有3个区域故障时，假设刚好是区域7、区域8和区域1，则存储资源2的节点全部故障，在该网络中资源2不可用。

图5 后继复制方法Fig.5 Successor replication method

图6 前继复制方法Fig.6 Predecessor replication method

3)Rd-Chord方法。如图7所示，Rd-Chord方法和后继复制相比减少了1跳，和前继复制相比增加了1跳。前2种复制方法副本存储比较集中，在同样数目副本的情况下，该方法副本分散在4个区域内，当任意3个区域发生故障时依然有数据可得。

3 仿真结果与算法比较

为了评估改进数据复制策略的好处和适用性，本文进行了仿真实验。实验包括2个方面：①调查在考虑一系列的性能度量时该方法的效率；②和现有几个数据复制策略进行比较，包括后继复制和前继复制方法。所有方法用omnet++仿真实现。

3.1 仿真环境设定

仿真基于omnet++，对不同副本数和故障区域数进行仿真，比较前继复制、后继复制和本文改进方法查找平均跳数和查找失败率。

平均跳数定义为

(1)

(1)式中：hi为第i条查找成功的消息经过的跳数；Lsuc为查找成功的消息数。

查找失败率定义为

(2)

假设系统初始由N个节点构成。每次实验由初始载入阶段开始。随后，在仿真阶段节点可以在系统中进行lookup查询。每个key被复制r(复制因子)次。在仿真期间，8个区域中不同区域的节点会随机故障。例如，当N=1 024个，故障区域数cn=2时，会有1 024×(2/8) = 256个节点故障。

本仿真实验共有5个参数：标识符长度m，表示标识符空间中标识符ID所占的比特数；节点数N，表示整个网络中的节点数目，即网络规模；副本数r，表示整个网络中的复制度，即副本数目阈值，该值比故障区域数多1；查询消息数L，表示网络中节点随机生成查询消息的总数目，每个节点发送100条查询消息，则整个网络有6 400条；故障区域数cn，表示将整个网络划分成8个区域，其中故障区域的总数，当故障区域数大于5时，整个网络瘫痪，因此，故障区域数最多为5。仿真过程中使用的参数如表1所示。

表1 仿真参数设置

3.2 算法比较

网络模型基于Chord模型，本文将模型中所有节点按标识符序号分为8个区域，统计在不同副本数下3种复制方法查找的平均跳数和不同故障区域数状况下查找失败率。本文解决的问题是在节点区域性故障时，怎样存储副本可以提高数据可用性。前继复制和后继复制并没有考虑到这个问题。

本文从查找速度和查找失败率2个维度来验证Rd-Chord的有效性。其中，查找速度由最后统计的参数平均跳数来反映，查找失败率即由最后统计的失败率来反映。平均跳数越少，失败率越低，表明算法效率越好。下面从查找成功平均跳数和查找失败率2个方面比较本文的Rd-Chord方法以及前继复制和后继复制算法。

1)平均跳数。图8为cn=3时，不同副本个数下查找平均跳数。可以看出，当副本数增加时，平均跳数减少，这是因为查找成功的概率和网络中可用的副本数是成正比的。Rd-Chord复制方法平均跳数居于前继复制和后继复制之间。

图8 cn=3时，不同副本个数下查找成功平均跳数Fig.8 cn=3, search successful average hops of different copies

2)查找失败率。图9为r=6时，不同个数区域节点失效的查找失败率。图9中，查找失败率随着失效区域数增加而增加，这是由于失效节点可能存储所查找的数据。前继复制和后继复制方法查找失败率曲线几乎重合，而本文的方法失败率远远低于这2种方法。仿真表明，在节点区域性故障的情况下，Rd-Chord数据复制方法在几乎没有增加查找代价的前提下，大大提高了网络中的数据可用性。

4 结束语

本文在Chord模型基础上提出一种在局部节点故障时增加数据可用性的复制方法——Rd-Chord。为了应对节点区域性故障，此方法将数据副本存储在根节点前继相对分散的节点集合上，这样即使某个区域节点全部故障，别的区域依然有数据副本可供使用。为了验证该方法的有用性，本文对现有的前继复制、后继复制和Rd-Chord方法进行了大量的比较实验。实验结果显示，就解决节点区域性故障而言，本文的数据复制方法远远优于其他方法，而且也有很好的查找效率(查找成功平均跳数和后继复制比并没有明显差距)。

图9 r=6时，不同个数区域节点失效的查找失败率Fig.9 r=6, failure rate when nodes in different number of areas are fail

[1] BLOND S L, LEGOUT A, DABBOUS W.Pushing bittorrent locality to the limit.[J].Computer Networks, 2010，55(3), 541-557.

[2] 张永福. 分布式数据存储关键技术研究[D]. 南京：南京邮电大学, 2016.

ZHANG Yongfu.Study on Key Technology of Distributed Data Storage[D].Nanjing：Nanjing University of Posts and Telecommunications, 2016.

[3] CHEN H, JIN H, LUO X, et al. BloomCast: Efficient and Effective Full-Text Retrieval in Unstructured P2P Networks[J].IEEE Transactions on Parallel & Distributed Systems, 2011, 23(2):232-241.

[4] LEGTCHENKO S，SENS P，MULLER G.RelaxDHT:A churn-resilient replication strategy for peer-to-peer distributed hash-tables[J]. ACM Transactions on Autonomous & Adaptive Systems，2012 , 7(2) :1-18.

[5] RAMASUBRAMANIAN V, SIRER E G.The Design and Implementation of a Next Generation Name Service for the Internet[C]//ACM. Summaries of Technical Papers of Meeting Architectural Institute of Japan. E-2, Architectural Planning and Design Ii, Dwelling Houses and Housing Sites, Rural Planning, Education. New York：ACM，Architectural Institute of Japan, 2004:331-342.

[6] GUIRAT F B, FILALI I. An efficient data replication approach for structured peer-to-peer systems[C]//IEEE.International Conference on Telecommunications. New York：IEEE Press, 2013:1-5.

[7] ROUSSOPOULOS M, BAKER M. CUP: Controlled Update Propagation in Peer-to-Peer Networks[J]. Computer Science, 2002, 21(6):1 -6.

[8] YIN L, CAO G. DUP: Dynamic-Tree Based Update Propagation in Peer-to-Peer Networks[C]//IEEE. International Conference on Data Engineering. Tokoyo：IEEE Computer Society, 2005:258-259.

[9] SHEN H. EAD: An Efficient and Adaptive Decentralized File Replication Algorithm in P2P File Sharing Systems[C]// Eighth International Conference on Peer-To-Peer Computing.[s.l.]: IEEE Computer Society, 2008:827-840.

[10] GOPALAKRISHNAN V, SILAGHI B, BHATTACHARJEE B, et al. Adaptive replication in peer-to-peer systems[C]// 2008 APS March Meeting.[s.l.]: American Physical Society, 2004:360-369.

[11] 孙新,李庆洲,赵璞,等.对等网络中一种优化的副本分布方法[J].计算机学报,2014, 37(6):1424-1434.

SUN Xin, LI Qqingzhou, ZHAO Pu, et al.An Optimized Copy Distribution Method in Peer-to-Peer Networks [J].Journal of Computers,2014,37(6): 1424-1434.

[12] YANG Z, TIAN J, ZHAO B Y, et al. Protector: A Probabilistic Failure Detector for Cost-Effective Peer-to-Peer Storage.[J]. IEEE Transactions on Parallel & Distributed Systems, 2010, 22(9):1514-1527.

[13] MUTHUSAMY V, JACOBSEN H A. Infrastructure-free content-based publish/subscribe[J].IEEE/ACM Transactions on Networking, 2014, 22(5):1516-1530.

[14] TU X, JIN H, CAO J, et al. An Efficient Data Scheduling Scheme for P2P Storage-Constrained IPTV System[J].IEEE Transactions on Systems Man & Cybernetics Systems, 2013, 43(2):379-389.

[15] KAWAKAMI T, ISHI Y, YOSHIHISA T, et al. A Study of Robustness Enhancement Technique on P2P Sensor Data Stream Delivery System Using Distributed Hashing[C]//IEEE.International Conference on P2P. New York：IEEE Press, 2014:591-596.

[16] ZHANG Y, GUO Y, CHEN Y. Optimized bandwidth allocation for maximizing user’s QoE in hybrid cloud P2P content distribution[J].Journal of China Universities of Posts & Telecommunications, 2015, 22(3):84-91.

[17] LAI C C, LIU C M. A mobility-aware approach for maintaining data consistency in unstructured mobile P2P systems[C]//IEEE.International Conference on Ubiquitous and Future Networks.New York：IEEE Press, 2015:695-700.

[18] HU Y, BHUYAN L N, FENG M. Maintaining Data Consistency in Structured P2P Systems[J].IEEE Transactions on Parallel & Distributed Systems, 2012, 23(11):2125-2137.

[19] SHEN H, LIU G.A Geographically Aware Poll-Based Distributed File Consistency Maintenance Method for P2P Systems[J].IEEE Transactions on Parallel & Distributed Systems, 2013, 24(11):2148-2159.

[20] NAKASHIMA T, FUJITA S.Tree-Based Consistency Maintenance Scheme for Peer-to-Peer File Sharing Systems[J]. Ieice Transactions on Information & Systems, 2013, 97 (12):187-193.

[21] NAKASHIMA T, FUJITA S. Scalable Tree-Based Consistency Maintenance in Heterogeneous P2P File Sharing Systems[C]//IEEE.International Conference on Parallel Processing Workshops.New York: IEEE Press, 2015:250-256.

(编辑：王敏琦)

ImproveddatareplicationapproachbasedonChordnetworkmodel

LIU Lifang1, HOU Liyuan1, QI Xiaogang2

(1. School of Computer Science and Technology, Xidian University, Xi’an 710071, P.R. China；2. School of Mathematics and Statistics, Xidian University, Xi’an 710071, P.R. China)

To solve the high failure rate in data search under the local node failure of the existing replication strategy, a new data replication mechanism called Rd-Chord is proposed. Discrete storage method is employed to deal with the data copies’ storage in the relatively decentralized nodes which are Pre-relay nodes of the root node in the Chord network, and thus there are still copies of data available in other regions even if all the nodes in one region or several regions are breakdown. Simultaneously, a basic update strategy and a periodic update strategy for Rd-Chord are presented to maintain the network structure and key migration. In order to verify the superiority of this method, the extensive comparative experiments on the existing predecessor replication, successor replication, and Rd-Chord are carried out, and the experiment results show that Rd-Chord is superior to the other methods in terms of the capability of solving the regional node failure, the searching failure rate of Rd-Chord is also cut down about 10% but the average searching efficiency is ensured.

P2P network; Chord model; data replication; regional fault

s：The National Natural Science Foundation of China (61572435, 61472305); The Natural Science Foundation of Shaanxi Province (2015JZ002, 2015JM6311); The Natural Science Foundation of Zhejiang Province (LZ16F020001); The Natural Science Foundation of Ningbo Province (2016A610035) ; The Space Measurement and Communication Innovation Fund (KJCK1608)

TP393

1673-825X(2017)05-0688-08