p12-stoica.pdf下载

and involves relatively little movement of keys when nodes join and leave the system. A fundamental problem that confronts peer-to-peer applications is Previous work on consistent hashing assumed that nodes were to efficiently locate the node that stores a particular data item. This aware of most other nodes in the system, making it impractical to paper presents Chord, a distributed lookup protocol that addresses scale to large number of nodes. In contrast, each Chord node needs this problem. Chord provides support for just one operation: given “routing” information about only a few other nodes. Because the a key, it maps the key onto a node. Data location can be easily routing table is distributed, a node resolves the hash function by implemented on top of Chord by associating a key with each data communicating with a few other nodes. In the steady state, in item, and storing the key/data item pair at the node to which the an Æ -node system, each node maintains information only about key maps. Chord adapts efficiently as nodes join and leave the Ç ́ÐÓ Æ μ other nodes, and resolves all lookups via Ç ́ÐÓ Æ μ mes- system, and can answer queries even if the system is continuously sages to other nodes. Chord maintains its routing information as changing. Results from theoretical analysis, simulations, and ex- nodes join and leave the system; with high probability each such event results in no more than Ç ́ÐÓ 3⁄4 Æ μ messages. periments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with Three features that distinguish Chord from many other peer-to- the number of Chord nodes. peer lookup protocols are its simplicity, provable correctness, and provable performance. Chord is simple, routing a key through a se- quence of Ç ́ÐÓ Æ μ other nodes toward the destination. A Chord node requires information about Ç ́ÐÓ Æ μ other nodes for efficient routing, but performance degrades gracefully when that informa- tion is out of date. This is important in practice because nodes will join and leave arbitrarily, and consistency of even Ç ́ÐÓ Æ μ state may be hard to maintain. Only one piece information per node need be correct in order for Chord to guarantee correct (though slow) routing of queries; Chord has a simple algorithm for maintaining this information in a dynamic environment. The rest of this paper is structured as follows. Section 2 com- pares Chord to related work. Section 3 presents the system model that motivates the Chord protocol. Section 4 presents the base Chord protocol and proves several of its properties, while Section 5 presents extensions to handle concurrent joins and failures. Sec- tion 6 demonstrates our claims about Chord’s performance through simulation and experiments on a deployed prototype. Finally, we outline items for future work in Section 7 and summarize our con- tributions in Section 8.