基于DHT的P2P系统中高可用数据冗余机制.doc

基于DHT的P2P系统中高可用数据冗余机制 陈贵海1 吴帆2 李宏兴1， 邱彤庆3 1 南京大学软件新技术国家重点实验室，南京210093 2 纽约州立大学计算机科学与工程系，纽约布法罗 14260 3 佐治亚理工大学计算机学院，佐治亚亚特兰大 30332 摘要：在基于DHT的P2P系统中需要采用冗余机制以保证数据的高可用性。本文基于用户下载行为来衡量数据存储与共享系统中的不同冗余机制。此外，我们提出了一种混合式的数据冗余策略，它兼具传统的复制策略和分片冗余策略的优点。实验表明，复制策略虽然比分片冗余策略需要更多的存储空间，但当节点平均可用性高于47%时，更节省网络维护带宽。混合式冗余策略在各种网络环境中均能较传统冗余策略更节省网络带宽，并且冗余因子适中。 关键字：分布式哈希表，对等计算，可用性，冗余，分片冗余，复制 Redundancy Schemes for High Availability in DHTs Guihai Chen 1, Fan Wu 2, Hongxing Li 1 and Tongqing Qiu 3 1 State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210093 2 Department of Computer Science and Engineering, SUNY at Buffalo, Buffalo, NY 14260 3 College of Computing, Georgia Institute of Technology, Atlanta, GA 30332 Abstract: High availability in peer-to-peer DHTs requires data redundancy. This paper takes user download behavior into account to evaluate redundancy schemes in data storage and share systems. Furthermore, we propose a hybrid redundancy scheme of replication and erasure coding. Experiment results show that replication scheme saves more bandwidth than erasure coding scheme, although it requires more storage space, when average node availability is higher than 47%. Our hybrid scheme saves more maintenance bandwidth with acceptable redundancy factor. Keywords：DHT, peer-to-peer, availability, redundancy, erasure-coding, replication 引言 随着互联网和网络计算技术的迅猛发展，一类基于分布式哈希表（DHT）的对等计算系统应运而生[1] [2] [3] 。 DHT能支持全局性的数据存储，提供确定性的定位服务，并已有诸多应用[4] [5] [6] [7] 。在不能保证节点100%可用的情况下，要实现数据文件的高可用性，即数据被成功访问到的概率，需要某种数据冗余策略。目前应用于基于DHT的P2P系统的数据冗余策略主要有两种：复制（replication）[4] [7] 和分片冗余（erasure coding）[4] [5] [6] 。 在数据存储方面，和复制相比，分片冗余既具有优势，也有不足。其的优势在于要达到相同的可用性水平，分片冗余比复制需要的存储空间和网络带宽少得多，甚至相差一个数量级（换言之，若使用相同的存储空间，或者通过网络传输的数据量相等的情况下，分片冗余比复制达到的可用性水平高得多）[5] [8] [9] 。但是分片冗余的优势有限，只有当节点平均可用性较低时分片冗余才明显优于复制[10] [11] 。而当节点平均可用性较高时，引入分片冗余往往不足以弥补引入它的代价，如额外的系统复杂度、异构环境中下载的延迟和不支持关键词检索等。 一方面，观察目前的P2P文件共享系统，发现热点文件的下载次数相当多，无需维护，其可用性自动保持在较高水平。这里，我们将用户下载使用的带宽与维持文件可用性水平所需的带宽区别开来，我们称前者为用户带宽，而后者为维护带宽。这表明了使用混合式的数据冗余策略（即结合用户主