QCon北京「鸿蒙专场」火热来袭!即刻报名,与创新同行~ 了解详情
写点什么

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

  • 2014-12-02
  • 本文字数:1062 字

    阅读完需:约 3 分钟

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 )关注我们,并与我们的编辑和其他读者朋友交流。

2014-12-02 05:4310205
用户头像

发布了 92 篇内容, 共 48.0 次阅读, 收获喜欢 5 次。

关注

评论

发布
暂无评论
发现更多内容

Sticky for mac 记录重要任务和事件、写下快速笔记

Rose

Mac平台上简单又好用的磁盘清理工具:BlueHarvest

Rose

Barcode for Mac(自定义创建视觉上完美的条形码/二维码)

Rose

云计算环境下云管平台选择哪家好?大家有推荐么?

行云管家

云计算 云服务 云管平台 云管理

人工智能与测试开发:新时代的黄金组合

霍格沃兹测试开发学社

FabFilter Total Bundle 2024 全套音频插件包

Rose

Terragen 4 mac渲染软件下载 Terragen 4安装教程

Rose

动态gif图片特效 Cinemagraph Pro for mac中文版

Rose

第39期 | GPTSecurity周报

云起无垠

iStat Menus for Mac CPU使用情况、内存用量、硬盘使用情况等一目了然!

Rose

mac视频转换器哪个好?Smart Converter Pro for Mac智能视频转换器专业版

Rose

Databend 开源周报第 132 期

Databend

BusyContacts for Mac:高效通讯录管理工具

Rose

云原生明星创业公司 Weaveworks 倒闭了,GitOps 该何去何从?

极狐GitLab

图像处理-Java-字深字浅

alexgaoyh

Java 图像处理 边缘检测 字深 字浅

There will be "7" later: Interpretation of next-generation Wi-Fi technology

wallysSK

听 GPT 讲 client-go 源代码 (8)

fliter

VMware Workstation 17安装教程:安装系统

小魏写代码

软件测试/人工智能|熟练使用web控件定位技巧,提升测试工作效率!

霍格沃兹测试开发学社

掌握web控件定位技巧,提升页面操作效率!

测吧(北京)科技有限公司

测试

Programming Abstractions in C阅读笔记:p283-p292

codists

radium市值机器人/刷量机器人/做市机器人

区块链技术

听 GPT 讲 client-go 源代码 (7)

fliter

业务开发自由之路:如何打破框架束缚,实现真正的框架中立性

canonical

低代码 架构设计 Nop平台 框架中立性

一文搞懂设计模式—工厂方法模式

Java随想录

Java 设计模式

全新且极易使用的视频延时制作软件Persecond for Mac

Rose

Chord:结构化P2P网络中的一个DHT算法_语言 & 开发_李士窑_InfoQ精选文章