写点什么

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:4310473
用户头像

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

关注

评论

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

Wireshark的捕获过滤器

小魏写代码

macbook屏幕亮度调整工具:Lunar Pro for Mac破解版 附Lunar Pro注册机

Rose

Mac屏幕亮度调整工具 Lunar Pro破解版 Lunar Pro注册机 Lunar Pro下载

【代码可视化实践】代码变更影响分析 | 京东云技术团队

京东科技开发者

代码可视化 企业号11月PK榜 代码变更

IBM SPSS Statistics v27.0.1中文破解版 spss详细图文安装教程

Rose

spss数据统计 IBM SPSS Statistics 27

Mac文本对比工具UltraCompare中文版 支持M/intel

Rose

文件对比工具 UltraCompare 中文版 UltraCompare 下载

文心一言 VS 讯飞星火 VS chatgpt (142)-- 算法导论12.1 2题

福大大架构师每日一题

福大大架构师每日一题

自然环境渲染工具Terragen 4 for mac破解版 附Terragen永久证书

Rose

Terragen 4破解 自然景观生成工具 Terragen 4下载 Terragen许可证书

IBM SPSS Statistics 27 Mac(spss统计分析软件)

展初云

Mac mac数据分析统计软件 IBM SPSS Statistics 27

手游APP被攻击了我们如何用游戏盾防御

Geek_f19a80

服务器

强大的鼠标增强软件BetterMouse 激活版最新中文

胖墩儿不胖y

Mac软件 鼠标增强工具 鼠标管理工具

「智造」第9期:一招砍成本、四档提效率,“智造”下半场如何仗剑破局?

用友BIP

智能制造

平台工程时代的 Kubernetes 揭秘:2023年生产状况报告深度剖析

SEAL安全

Kubernetes k8s 平台工程 企业号11月PK榜

Mac云电视:CloudTV mac破解版 能够接通全球400多个电视频道

Rose

Mac破解软件 CloudTV for Mac Mac云电视播放 CloudTV破解版

GitKraken for Mac(Git客户端) v9.10中文版

展初云

git Mac软件 GitKraken

Comsol Multiphysics for Mac(建模仿真软件) v6.2中文版

展初云

Mac COMSOL Multiphysics 物理场仿真软件

使用SpringDataJPA(Hibernate)动态更新数据的正确姿势

WuXiaoYuan

Java hibernate Spring JPA

FonesGo iPhone Unlocker for Mac(iPhone解锁工具)

Rose

iPhone解锁 FonesGo iPhone Unlocker Mac解锁软件

数智化赋能公立医院干部管理 激发组织活力

用友BIP

干部管理

财务共享中心建设项目的变革管理与沟通机制

用友BIP

财务共享

BetterMouse for Mac(鼠标增强软件)

展初云

Mac BetterMouse Mac鼠标辅助软件

macbook翻译软件就用Translatium for Mac

Rose

翻译软件 Translatium中文版 Translatium下载 Translatium Mac Mac翻译工具

​🔒 一文带你了解多文件混淆加密

分布式基础概念-选举算法

派大星

分布式 Java 面试题

万能蓝光播放器:Apeaksoft Blu-ray Player for Mac

Rose

Mac蓝光播放软件 Apeaksoft Blu-ray Player

天翼云以科技硬实力亮相第八届IDC中国数字化转型年度盛典

极客天地

项目管理体系文件代码评审规范

金陵老街

软件开发文档

Moho Pro 14 for Mac(2D动画制作软件)附注册机v14.1激活版

Rose

Moho Pro 14下载 Moho Pro 14中文版 Moho Pro 14破解 二维动画制作

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