何亚农， 宋 玮， 赵跃龙

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

0 引 言

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

1 P-Grid覆盖网络

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

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

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

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