BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

Chord:结构化P2P网络中的一个DHT算法

| 作者 李士窑 关注 0 他的粉丝 发布于 2014年12月3日. 估计阅读时间: 3 分钟 | QCon上海2018 关注大数据平台技术选型、搭建、系统迁移和优化的经验。

DHT即分布式哈希表(Distributed Hash Table),它通常是为了拥有极大节点数量的系统,而且在系统的节点常常会加入或退出节点而设计的。DHT具有良好的扩展性、鲁棒性、结点ID分配的均匀性和自组织能力。DHT可以用以建立复杂的服务,例如分散式档案系统、点对点技术档案分享系统、网页快取、缓存系统、任意点传输、网域名称系统以及即时通讯等。Chord由麻省理工学院(MIT)在2001年提出,其目的是提供一种能在P2P网络快速定位资源的的算法,它并不关心资源是如何存储的,只是从算法层面研究资源的取得,因此,Chord的API就简单到只有一个set、get。Chord在一致性哈希的基础上提供了优化的路由算法,优化后的算法具有负载平衡、分布性、可扩展性、可用性、命名的灵活性等优点。它可用于全球文件系统、命名服务、数据库请求处理、互联网级别的数据结构、通信服务、事件通知、文件共享等应用中。

Chord要实现的其实就是给定一个关键字Key,并能够将其映射到某个节点。Chord采用一致性哈希为每个节点和关键字产生一个m位的ID,并按照ID的大小构成环形拓扑。另外,为了路由的需要,Chord还维护了一张最多m项的路由表即Finger表。如下图所示的就是m为 6的一个Chord拓扑环和Finger表。

对于节点的查询的处理,Chord采用了幂次逼近查询法;对于新节点加入的处理,Chord需要环形拓扑中的任意一个节点来协助完成,且加入过程包括新节点本身的Join操作和被其他节点发现两个阶段;对于节点失效的处理,Chord需要周期性对节点的前继节点和后继节点进行探测,并按照节点加入时的算法重建Finger表;对于节点退出的处理,Chord采取了将节点的退出当作为失效来处理的方式。有关Chord及Chord对节点的查询、加入、失效等具体是如何处理的,请读者参考论文《结构化P2P网络chord算法研究与分析》

另外,请读者们注意,DHT只是一个概念、一种网络模型,读者还可以阅读freedomlayer上的一篇介绍以加深对DHT的理解。除了Chord算法外,基于DHT实现的算法还包括加州大学伯克利分校提出的内容寻址网络算法CAN、英国剑桥的微软研究院和莱斯大学提出的Pastry、加州大学伯克利分校提出的一种新型P2P网络定位和路由算法Tapestry等。目前,DHT算法的发展方向非常多,且随着科学技术的发展以及人们的不断探索与研究,将会有新的改进算法不断被提出来。


感谢郭蕾对本文的审校。

给InfoQ中文站投稿或者参与内容翻译工作,请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博(@InfoQ)或者腾讯微博(@InfoQ)关注我们,并与我们的编辑和其他读者朋友交流。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT