Chord：一个用于网络应用的可扩展的P2P查询服务（上） - sparkliang的专栏 - 博客频道 - CSDN.NET
P2P系统和应用都是没有中心控制节点或者层次化组织结构的分布式系统，系统中的节点在功能上都是相同的。近来，许多P2P应用都具有冗余存储（redundant storage）、持久化（permanence）、临近服务器选择（selection of nearby servers）、匿名访问（anonymity）、搜索（search）、认证（ authentication）和分级命名（hierarchical naming）等许多特征。然而绝大部分P2P系统中，最核心的操作是高效的数据定位。本文的贡献就在于提出了一个能为节点频繁加入、离开的动态P2P系统提供有效查询操作的可扩展协议。【译注：数据定位（data location）、查询（query、lookup）都是一回事】
实际上Chord协议仅支持一种操作：把一个给定的key映射到一个节点（node）上。 依据基于Chord协议的应用而定，目标节点可能负责存储关联到key的一组数据。Chord使用了一致性hash算法[11]（consistent hashing）的变体把Chord网络中的节点关联到特定而唯一的key上。一致性hash算法可以解决负载平衡（load balance）问题，因为它能保证系统中的每个节点都能接收到数量相当的key，并且当节点加入、离开系统时，减少数据的迁移。【译注：实际上一致性hash算法可以保证：当节点离开时，仅需要迁移离开节点上的数据；当节点加入时，仅将加入节点的后继节点的部分数据迁移到新节点上；而不涉及到其它的节点和数据，这在理论上已经是最小化的数据迁移了】
【译注：一致性hash算法的快速入门可以参见我的另一篇blog――一致性Hash算法 ，浅显易懂】
在以前对一致性hash算法的研究中，都假设每个节点都关注系统中的大多数节点，因此难以扩展应用到有很多节点的大规模系统中。相反，在Chord系统中，节点仅需要路由信息（routing information），关注少数其它节点。因为路由表是分布式的，一个节点执行查询时，需要和少数的其它节点通讯，稳定状态下，在一个有N个节点的系统中，每个节点仅需要维护O(logN)的节点信息，并且执行查询时仅需要和其它节点交互O(logN)的信息。当有节点加入、离开系统时，为了维护路由信息，Chord保证系统中节点之间的交互消息不会超过O(logN*logN)个。
Chord具有区别于其它P2P查找协议的3个特征：简单、正确性已经被证明和性能已经被证明。Chord简单有效，将key传递到目的节点仅需要路由O(logN)个节点。为了实现有效的路由，每个节点仅需要维护系统中O(logN)个节点的信息，并且在路由信息过期时，性能会优雅降级。这在实际中是很重要的，因为节点会随意的加入、离开系统，很难维持在O(logN) 的事件状态一致性。Chord协议中，每个节点仅有部分数据正确就能保证查询路由的正确性（尽管会变慢）。Chord具有简单的算法，能在动态的环境中维护路由信息。
文章其余部分的结构：第二节比较了Chord和其它的相关研究，第三节介绍了促进Chord协议的系统模型。第四节介绍了基本的Chord协议，并且证明了Chord协议的几个性质，第五节描述了能够处理多个节点同时加入、离开系统的扩展协议。第六节仿真和在实际部署的原型上的实验，论证了我们关于Chord性能的声明。最后，第七节列举了将来的工作，并在第八节总结了本文的成果。
Read full article from Chord：一个用于网络应用的可扩展的P2P查询服务（上） - sparkliang的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment