基于平衡结构的对等网络存储系统研究

何亚农， 宋 玮， 赵跃龙

(1.华南理工大学机械与汽车工程学院，广东广州510640；2.华南理工大学计算机科学与工程学院，广东广州510640)

0 引 言

目前，随着信息量的迅速增长，用户对海量的存储需求越来越大，通过构建对等网络、聚集对等节点空闲或者自愿提供的存储服务来扩大用户的存储能力已成为存储系统的热点研究问题。当前对等网络存储系统的研究，主要涉及两方面的内容：一是底层覆盖网络的确定；二是建立在其上的数据存储管理。本文提出的对等网络存储系统将以提高系统的可用性为目标，以平衡为出发点，从节点空间均衡和文件在节点间均衡分布的两个方面保证系统的平衡性。论文介绍了P-Grid系统虚拟二叉树结构和路由算法；给出了平衡树覆盖网络的形式化描述和改进节点的加入以及退出方式来保证树的平衡性；最后给出了实验分析和结论。

1 P-Grid覆盖网络

P-Grid是一个P2P平台[1-2]，其中数据对象的索引值是通过保持原字母顺序的散列函数得到，内部各个节点之间随机相遇，整个搜索空间被动态的划分并被各对等节点管理。

P-Grid的虚拟二叉树的构建过程和其它以树为基础的覆盖网相比，具有下列优点：

(1)不存在根节点。从图1可以看出在不断划分的过程中，各节点都最终位于树的底端。根节点并不对应实际的对等节点。文献[3]提出的MPPBTree，BATON都需要一个初始节点为根节点，这往往成为树的瓶颈。

(2)不需存储大量的父亲，儿子，兄弟指针。在树的结构中，设置大量的父亲，儿子，兄弟节点会带来搜索的便利，但同时这些指针的建立和维护是一个很大的问题。

图1 P-Grid实例

当然P-Grid也存在下列问题：

(1)未考虑树的平衡问题。有可能出现空间划分的不对称，如1*空间被4个节点划分为100*,101*,110*,111*的4个子空间，而0*则未被划分。此时必然导致负责0*空间的节点的负载大于1*空间。

(2)节点的频繁加入和退出对路由信息的维护仍然很大。

2 基于平衡树结构的对等网络存储的思想

根据文献[4-5]得知，在P2P系统中只有20%的节点具有高可用性(93%)，而30%的节点具有中等可用性。文献0指出节点的可用性分为两种一种是几乎长期在线的，一种是周期在线的。根据这个思想，本文对P-Grid中的虚拟二叉树进行改造。包括两个方面：一是引入树的平衡机制；二是对节点按照周期性质分级。最终形成一棵主体为平衡二叉树，底层为多叉树的结构。

采用虚拟二叉树构建整个模型的主体部分。模型中存在3类节点：长期节点(longtermpeer，LTPeer)、周期节点(periodical node，PPeer)，普通节点(normalpeer，NPeer)。图 2 中大圈部分是长期节点采用P-Grid算法构造的虚拟二叉树。小圈是某长期节点管理的周期节点。最底部为普通节点。长期节点和周期节点具有管理系统、贡献存储力和消费存储力的作用。普通节点也能提供存储力但以消费存储力为主。以树的形式组织资源，符合自然层次组织关系，容易实现系统的层次化管理，有利于减轻中心节点的负载和实现大规模应用的负载平衡，提高资源的查找效率[7-15]。

图2 虚拟二叉平衡树实例

3 基于平衡树的对等网络存储的形式化描述

3.1 平衡P-Grid形式化描述

定义1 一个树是平衡树，当且仅当对于树中的节点其子树的高度之差不超过1。在本文中，我们只考虑主干是一棵平衡二叉树。这样考虑的原因是，周期节点的加入和退出相对频繁，若要时刻保持平衡，对系统的性能有一定的影响。

定义2 长期节点(LTPeer)为可靠的，高性能的节点，几乎长期在线，可由研究中心，公共机构或大企业提供，在受控的环境中运行。也可来自一般用户提供的高性能资源，由其自愿加入。长期节点管理依据P-Grid构建算法加入的周期节点和相关数据存储索引信息。与P-Grid类似，长期节点具有路径值(Path)，由其在虚拟树中的位置决定，随着树动态变化而变化，其初始值表示为*，说明初始负责整个搜索区间。长期节点维护4张表。

(1)长期节点路由表。该表形成于虚拟二叉树的构建过程，其中每一项指向二叉树同层中一个与该节点在某位路径上具有相反值的节点。每个LTPeer由一个属性的多元组ninf描述。该多元组记录LTPeer的唯一ID号、主机名、IP地址、负载状态、在线周期等信息。对于每一个LTPeer具有node(id)=LTPeer iff getinf(LTPeer)=id。路由表项可以组织成一个序列的集合 (l1,Ninf1)(l2,Ninf2)…(ln,Ninfn),li∈{0,1}，其中 Ninfi是 ninf的集合。定义 path(LTPeer)=l1…ln,prefix(i,LTPeer)=l1…li1≤i≤n，refs(i,LTPeer)=Ninfi.集合 Ninfi,1≤i≤n 是满足下列性质的节点属性集合

(2)周期节点路由表。记录所管理的周期节点的信息。为每个长期节点设置最大管理周期节点数2PPeerMaxLen。每个表项是一个三元组(PPeer,KeyPPeer,ninfPPeer)。KeyPPeer代表PPeer的路径值。ninfPPeer代表PPeer的属性。

(3)复制节点表。复制节点是该长期节点的冗余节点。

(4)数据对象表。记录本地管理的数据对象信息。每一项是指向该数据对象实际所在位置节点的指针(KeyDataObject,Keypeer,AttrDataObject)。KeyDataObject表示逻辑文件名的散列值，AttrDataObject表示文件的属性。Keypeer是数据文件实际所在的位置节点。谓词exist_longest_common_prefix(a,b)表示字符串a和b有最大共同前缀；谓词Store(a,b)表示对象b存储在节点z上；谓词Manage(a,b)表示节点a管理对象b。

定义3 周期节点(PPeer)为固定时间段在线的节点。该节点具有路径值，初始值为空，加入到树中后，值为其管理节点的路径值连上其在管理节点中位置的编码。每个周期节点在长期节点中的编码为长度PPeerMaxLen二进制串。每个周期节点维护3张表：

(1)普通节点路由表。每一项是一个二元组(NPeer,ninfNPeer)记录其管理的普通节点信息。

(2)普通节点数据文件表。每一项是一个三元组(DataObject,NPeer,AttrDataObject)。

(3)本地数据文件表。记录存放在本地的数据文件信息。

定义4 普通节点(NGPeer)：性能一般的节点，提供一定的存储力，并使用网格中的存储力，在线行为无周期特征。含有一张本地数据文件表，并知道其管理节点。

证明：长期节点路径中的每一位代表树的层数。路径的长度说明节点所处的层数。比节点路径少两位的节点意味着比该节点高两层。若存在这样的节点则说明树不平衡。

推论1 当新节点加入，入口节点entry需要向下划分时，从entry的路由表中获得集合pset=refs(length(path(entry))-1,entry)，找到pset中路径值最短的节点p，若length(path(p))≥length(path(a))则说明可继续划分。

推论2 节点a离开，树向上缩减时，从路由表中获得集合pset=refs(length(path(a))-1,a)，查看相对层的下一层是否有节点，找到pset中路径值最长的节点p，若length(path(p))≥length(path(a))+1则说明a不可离开。

定理2 局部的平衡最终会导致全局的平衡。

证明：对于每一个新节点的加入，都保证被划分的入口节点entry，p∈ refs(length(path(entry))-1,entry)，length(path(p))≥length(path(LTPeer))成立。那么意味着加入对树的影响的效果仍然是每个节点满足定理1。每个节点的退出也同样保证树中每个节点满足定理1。

3.2 节点的加入

节点的加入和退出的灵活性体现了系统的灵活性和可扩展性。有两种加入方法：①入口点服务器(entrypointserver)；②带外(outofband)。入口服务器用于返回目前系统中任一已存在节点作为新加入节点的入口点，可以以网页的形式公布。带外方法通常在入口服务器不可用时，通过Email或人际直接交流。这里我们延用P-Grid的思想，即节点随机相遇，不管它们是什么原因相遇，只需考虑节点相遇后的处理。这意味着出现两种相遇情况：第一，系统之外的节点和系统内的节点相遇，即通常意义上的新节点加入；第二，系统内部节点的相遇，互相更新路由信息。为了保证主干二叉树是平衡树，则需对PGrid的构建算法做一些修改，以下节点主要是针对长期节点。

(1)系统内节点相遇且两节点原有路径值相同。如path(a1)=1001,path(a2)=1001。

①先做平衡考察。根据推论1，首先在各自路由表中找到一个节点集合，如pset=refs(length(path(a1))-1,a1)，即找到路径中第3位所对应的节点集，获得该节点集中路径最小的节点p，若该路径长度小于4，则说明若再继续划分则会出现不平衡。

②交换双方负载情况。

若load(a1)远大于load(a2)，或二者负载均大，并且可以向下划分，则继续向下划分空间。使a1负责10010空间，a2负责10011空间。

若load(a1)远大于load(a2)，或二者负载均大，但不可向下划分，则a1，a2互为冗余节点。a2分担一部分a1的负载。

若两者负载情况差别不大，且负载均小，并且可以向下划分，则继续向下划分空间。

若两者负载情况差别不大，且负载均小小，但不可向下划分，则将其中一个节点推荐到第一步中获得的节点p。如，a1将a2推荐给节点path(p)=100。此时将a2的负载转移到a1，a2和与p共同划分100*空间。

(2)两节点路径值是一个字串的关系。

若 load(a1)远大于 load(a2)，此时使 path(a1)=100，a2 分担101*空间的负载。

若load(a2)远大于load(a1)，此时使path(a1)=1011，将a1 上1000*，1001*，1010*转移到相应负责节点。

(3)没有路径值的节点和有路径值的节点相遇。将无路径节点的初始值赋为有路径节点的值。然后根据(1)来调整。

周期节点加入到系统，意味着被某个长期节点管理，路径值为其管理节点的路径值连上其在管理节点中位置的编码。每个周期节点在长期节点中的编码为长度PPeerMaxLen二进制串。用setPPeerPath(LTPeer,PPeer)来设置周期节点的路径：首先判断选定的长期节点的所管理的周期节点个数是否满，即≥2PPeerMaxLen。若满则在当前长期节点已知的信息中选择负载最轻的长期节点，做同样的判断。直到找到一个未满的，按照编码方案给PPeer设置路径。

3.3 节点的退出

这里主要考虑长期节点。一般来说长期节点是几乎长期在线的节点，但也不排除主动退出系统的情况。此时需要考虑节点退出对平衡的影响，以及节点上相关信息的转移。

(1)根据推论2做平衡考察。设节点a1要退出，则a1路径的长度len=(length(path(a1))，字符串sub=prefix(len-1,path(a1))，字符p表示a1路径在第len位值，加号表示字符串连接，可构造路径path=sub+P～+*,*表示0或1。若存在具有这样路径的节点则，说明a1删掉会导致不平衡。

(2)若可以删除，且节点无子节点，则可以删除

(3)若可以删除，但有子节点，则将数据交与冗余节点。或从子节点中选择状态好的节点替代。

(4)若不平衡，同(3)。

表1给出了根据平衡策略进行数据查找的部分实验结果。

表1 各种平衡策略进行数据查找的成功概率

4 结束语

本文提出了一种将长期在线的节点构建为主体平衡虚拟二叉树的方法，采用该方法能够提高对等网络中节点的空间均衡以及可用性，所构建的系统具有的特征是：①可扩展性好：由于系统建立在P-Grid的基础之上，所以对等节点的加入和退出由相应的构建算法保证，具有较高的灵活性。②可靠性高：按照节点可用性的周期特性进行分类，将高可用性的节点组织成树的主体，数据的存储信息总是放置在高可用性的节点上。③负载均衡性好：平衡二叉树保证了系统中对等节点在划分负责空间的均衡性。目前，我们正在实现相关的算法和协议，同时也在开发平衡树的原型系统。

[1]Song W,Zhao Y L,Zeng W Y,et al.Data grid model based on structured p2p overlay network[C].Proceedings of APPT,2007:282-291.

[2]孙知信,杨熙,宫婧.一种基于信任度推荐的P2P-Grid模型[J].吉林大学学报(工学版),2008,38(1):127-130.

[3]Xu L B,Wu G X,You F Q.A structured p2p system with match path and probability balance tree[C].Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences.Washington,DC,USA:IEEE Computer Society,2006:167-174.

[4]刘志忠,王怀民,周斌.一种双层P2P结构的语义服务发现模型[J].软件学报,2007,18(8):1922-1932.

[5]刘德辉,周宁,尹刚,等.QFMA:一种支持负载均衡的多属性资源定位方法[J].计算机学报,2008,31(8):1376-1382.

[6]Chandy,John A.Storage allocation inunreliable peer-to-peer systems[C].Proceedings of the International Conference on Dependable Systems and Networks,2006:227-236.

[7]齐德昱,林伟伟.一种新的网格环境模型——T Grid Model[J].计算机科学,2006,33(12):6-9.

[8]Houssem Jarraya,Maryline Laurent.A secure peer-to-peer backup service keeping great autonomy while under the supervision of a provider[J].Computers&Security,2010,29(2):180-195.

[9]JariVeijalainen.Autonomyheterogeneityand trust inmobile p2p environments[C].International Conference on Multimedia and Ubiquitous Engineering.United States:IEEE Computer Society,2007:41-47.

[10]Lipo Chan,Shanika Karunaseker.CAESAR:Middleware for complex service-oriented peer-to-peer applications[C].Proceedings of the 2nd Workshop on Middleware for Service Oriented Computing,the ACM/IFIP/USENIX International Middleware Conference.USA:ACM,2007:12-17.

[11]田敬,代亚非.P2P持久存储研究[J].软件学报,2007,18(6):1379-1399.

[12]LI Hongxing,Chen Guihai.Data persistence in structured p2p networks with redundancy schemes[C].Proceedings of the 6th International Conference on Grid and Cooperative Computing.United States:IEEE Computer Society,2007:542-549.

[13]Liu Zhiyu,Yuan Ruifeng,Li Zhenhua,et al.Survive under high churn in structured P2P systems:Evaluation and strategy[C].6th International Conference on Computational Science,LNCS 3994.Germany:Springer Verlag,2006:404-411.

[14]Chandy,John A.Storageallocation inunreliable peer-to-peer systems[C].Proceedings of International Conference on Dependable Systems and Networks.United States:IEEE Computer Society,2006:227-236.

[15]Chun B,DabekF,Haeberlen A,etal.Efficient replica maintenance for distributed storage systems[C].Proc of the 3rd Symp on Networked Systems Design and Implementation,2006:45-58.