一致性哈希(consistent hashing)和分布式哈希表(DHT: Distributed Hash Table)在最近的学习中经常用到,但是两个概念经常纠缠在一起,不容易分清楚。有时候就不明白这里为什么说的是consistent hashing,而不是用DHT。
从字面的意思来区分:consistent hashing 是一种满足特殊需求的哈希;DHT 是通过哈希实现的分布式的表,归根到底是一个分布式系统。consistent hashing 是理论上节点变化最少数据迁移的哈希方法,而DHT 在实现上更加具体,DHT 把传统的单个K-V 表在分布式多个节点中进行划分,既可以采用consistent hashing 实现,也可以采用其他哈希方法。
一致性哈希 consistent hashing
DHT的一种实现。本质还是一个哈希算法。回想平时我们做负载均衡,按querystring签名对后端节点取模是最简单也是最常用的算法,但节点的增删所造成的问题显而易见:原有的请求几乎都落不到同一台机器上。优化一点的是carp算法,只让1/n的数据受到影响。
一致性哈希,似乎最早提出是在分布式缓存里面的,让节点震荡的时候,影响最小。不过现在已经应用在分布式存储和p2p系统里面。
在传统的哈希表中,当划分哈希区域的分组数量发生变化时,几乎所有的keys 都需要重新排列到不同的分组。但如果使用一致性哈希,平均只需要k/n 个keys 重排,k 是keys 的个数,n 是分组的个数。基于这点性质,可以在DHT 中使用consistent hashing 。
hash(o) mod n 是传统的哈希用于确定对象分组位置方法,o 是对象,n 是分组个数,对应分布式系统节点个数,计算的结果即是存储该对象的节点编号。当节点个数n 发生变化时,而对象的哈希结果不变,这样几乎所有的对象位置都需要重排,造成分布式系统网络流量的严重颠簸(churn)。而一致性哈希很好的解决了这个问题。
consistent hashing 使用一个固定的模数R 对对象的哈希结果取模hash(o) mod R。R 可以表示哈希结果的范围,也可以表示对应哈希环(Ring)的范围,在chord 中。并使用同样哈希函数和模数R
对所有的节点进行同样的计算hash(node.id) mod R。这样就把节点和对象都哈希到同一个大小为R 的环(Ring)上了。每个节点管理、存储它和它环上前驱节点之间范围的对象,当有新的节点加入或者退出时,遵循同样规则。这样的好处是剥离了对象分布和节点的关系,节点个数发生变化时对象在环上的分布不发生变化,最大限度减少了对象在节点上的迁移。
下面图示了consistent hashing 节点加入、退出过程(图片来源):
在只有两个节点node 1 和node 2 ,哈希结果为Key1 和key2 ,每个节点存储前驱节点(如key2>key1)和自己之间范围的对象(values)。在节点个数比较少的时候就可能存在负载不均衡的情况,这个可用通过引入虚拟节点来解决。
添加一个节点node3 (key3)的情形。根据每个节点管理、存储它和它环上前驱节点之间范围的对象的原则,node3(key3)分担了key2
的空间。
删除一个节点node1(key1)的情形。key1 的空间被node3(key3)接管了。
引入虚拟节点后的结果。为了避免因为节点空间不均衡导致负载不平衡,每个节点引入等量的虚拟节点分布在环上,虚拟节点使用同样的方法划分空间。采用v1_key1=hash(node1.id.v1) ……vn_key1=hash(node1.id.vn) 的方法可以得到节点node1 的n 个虚拟节点vi_key1。
consistent hashing 具有以下性质:
-
Spread: 发散性指的是对象分发到各个节点上,每个节点只需要存储所有对象的一部分
-
Load: 负载指的是任何一个节点都不会保存过多的对象数据
-
Smothness: 平滑性指的是节点改变带来的对象迁移是平缓的。不会因为节点的加入、退出导致大量数据迁移
-
Balance: 平衡性指的是每个对象随机分配到节点
-
Monotonic: 单调性指的是当一个节点加入时,只有分配到该节点的对象发生了重排
分布式哈希表 Distributed Hash Table
两个key point:每个节点只维护一部分路由;每个节点只存储一部分数据。从而实现整个网络中的寻址和存储。
DHT只是一个概念,提出了这样一种网络模型。并且说明它是对分布式存储很有好处的。但具体怎么实现,并不是DHT的范畴。
分布式哈希表DHT 是一种去中心化的分布式系统,提供一种类似于哈希表的查询功能。
DHT 的研究最初是因为P2P 系统的兴起,如Napster,Gnutella 和Freenet。
Napster 是最早的P2P 服务的代表作,有一个中心index server 保存资源的index(key),当有节点加入、退出和查询时,与index server 进行交互,获取资源信息,存在单点故障,在遇到法律纠纷时,这个index server 很容就被关闭了。
Gnutella 去中心化得松散布局,当节点发起查询时,通过洪泛(flooding)的方式查询:每个收到查询命令的节点向其所有其他邻居节点发送类似请求。并通过TTL 控制洪泛的区域。
Freenet 首先采用了DHT,每个对象(文件)都关联一个key,具有相似的key 的文件保存在相似的节点上,并通过一个基于key 的启发式的路由进行查询。
DHT 可以认为是由keyspace(key 空间)、keyspace partition(key 空间划分)、overlay network(覆盖网)组成。keyspace 很好理解,是所有定长字符串的空间。keyspace partition 方案将keyspace 上不同区域划分到不同的参与节点上。overlay network(覆盖网)将节点连接起来,使得网络中节点通过这个网络可以找到保存指定key 的节点。consistent hashing 对比DHT 更多的是提供了一种keyspace 的划分方法,各种consistent
hashing 的也用在了DHT 中进行空间划分。为了更好的理解overlay network 的组成,有这么一段话:
Each node maintains a set of links to other nodes, these links forms the overlay network.
【译】每个节点维持到其他节点的链接,这些链接形成了覆盖网。
可以看出overlay network 已经从物理层的网络抽象成逻辑层上链接各个节点、各个节点保存的路由信息以及路由协议的集合。在overlay network 有两个重要参数:邻居节点数/度数(Degree)和跳数/路由长度(Route length)。度数衡量每个节点保存邻居节点信息的多少,度数越大每个节点邻居越多,保存和维持的信息就更多,需要的路由长度就越短。跳数指的是从该节点到保存特定key 的对象的节点的平均路由长度。他们的关系有下表:
度数
|
路由长度
|
备注
|
O(1) |
O(n) |
|
O(log n) |
O(log n/log(log n)) |
|
O(log n) |
O(log n) |
最常见(比如 chord),但不是最优的解 |
O(1) |
O(log n) |
|
O() |
O(1) |
|
DHT 具有三点性质:
-
Decentralization: 去中心化,节点之间相互配合形成整个系统,而不需要一种中心节点协调
-
Fault tolerance: 容错,即使不断有节点加入、退出或者失效,也要能够保证系统稳定
-
Scalability: 扩展性,系统在成千上万个节点时也能够有效地运行
Chord算法:
一致性哈希有多种实现算法,最关键的问题在于如何定义数据分割策略和节点快速查询。
chord算是最为经典的实现。cassandra中的DHT,基本是chord的简化版。
网络中每个节点分配一个唯一id,可以通过机器的mac地址做sha1,是网络发现的基础。
假设整个网络有N 个节点,并且网络是呈环状。两个节点间的距离定义为每个节点会存储一张路由表(finger表),表内顺时针按照离本节点2、4、8、16、32.……2i的距离选定log2N个其他节点的ip信息来记录。
存储方面:数据被按一定规则切割,每一份数据也有一个独立id(查询key),并且和节点id的值域是一样的。然后查找节点,如果存在和数据id一样的节点id,则将这份数据存在该节点上;如果不存在,则存储到离该数据id距离最近的节点上。同时,为了保证数据的可靠性,会顺时针往下找K个冗余节点,存储这份数据。一般认为K=3是必须的。
查询方面:先从自己的路由表中,找一个和数据id距离最近、并且存活在网络中的节点next。如果该节点的id巧合和数据id相等,那么恭喜你。如果不相等,则到next进行递归查找。一般或需要经过多次查询才能找到数据所在的节点,而这个次数是可以被证明小于等于log2N的。
在这个查询的过程中就体现了路由表的选取优势了,其实是实现了一个二分查找,从每个节点来观察网络,都是将网络分成了log2N块,最大一块里面有N/2个节点。路由表里面其实是记录了每一块的第一个节点。这样每一次查询,最少排除了一半的节点。保证在log2N次内找到目标节点。
新增一个节点i,需要预先知道网络中已经存活的一个节点j,然后通过和节点j交互,更新自己和其他节点的路由表。并且,需要将离自己距离最近的节点中的数据copy过来,以提供数据服务。
损失一个节点,路由算法会自动跳过这个节点,并且依靠数据的冗余来持续提供服务。
KAD算法(Kademlia)
个人觉得,kad算法其实是在chord上做的优化。主要是两个点:
1、用二进制(32/64/128)表示一个节点的id,两节点的id异或运算得到节点间的距离。
2、 每个节点保持的路由信息更丰富,同样是将整个网络按照划分成log2N份,在chord中,是保持log2N个路由节点,但在kad里面,是保存了 log2N个队列。每个队列长度为配置值K,记录网络中对应节点区域的多个节点,并且根据活跃时间对这些节点进行换入换出。
第一点是方便进行网络划分,节点按照二进制中每一bit的0或1建成一棵二叉树。
第二点是使得节点查询更迅速。从分割情况我们就可以得知,最坏情况不会差于chord,但保存更多的节点使得命中概率更高。另外队列中根据活跃时间进行换入换出,更有利于在p2p这种节点变更频繁的网络中快速找到有效的节点。
关于kad的介绍,这篇文章讲的比较详细wenku.baidu.com/view/ee91580216fc700abb68fcae.html
分享到:
相关推荐
博文链接:https://windshg.iteye.com/blog/1216914
关于分布式散列表DHT的前世今生的故事:包括单机hash、分布式一致性hash
Client.py:此文件使用弦环和n元树实现分布式哈希表(DHT)的两层覆盖网络。 它负责与其他节点进行通信。 使用以下代码在执行代码之前安装pyqt4:sudo apt-get install python-qt4 执行命令:索引服务器:python ...
算法特性:包括输入、输出、有穷性、确定性和可行性。即一个有效的算法必须能在有限步骤内结束,并且对于给定的输入产生唯一的确定输出。 算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序...
原子性操作:Redis支持原子性操作,能够保证多个操作的执行顺序和一致性,支持事务和流水线操作。 发布/订阅:Redis提供了发布/订阅功能,能够实现消息的异步发布和订阅,适用于实时通知、事件驱动等场景。 分布式...
根据标准的一致性哈希算法实现了hashRing,并加入数据服务器存储空间大小不同等权重来平衡各节点的虚拟多维数据集复制因子,对象读取请求均根据对象名进行哈希运算映射到虚拟多维数据集上,再由虚拟多维数据集映射到...
针对Chord模型在节点加入或离开时产生大量消息,不适用于动态网络的问题,提出一种基于分布式哈希表(Distribute Hash Table,DHT)的自适应Chord模型,即Self-adaptive Chord。方法是该模型在节点加入或离开的时候...
4.5.1 一致性哈希 81 4.5.2 对象版本 82 4.5.3 闲话协议和提示移交 83 4.6 小结 83 第5章 执行CRUD操作 84 5.1 创建记录 84 5.1.1 在以文档为中心的数据库中创建记录 85 5.1.2 面向列数据库的创建操作 91 ...
为解决分布式协同设计系统中的异地编辑一致性及多副本同步等问题,提出基于分布式哈希表(DHT)的分布式互斥算法,给出该算法的实现方法。通过采用DHT化的优先队列解决了异地编辑一致性操作问题。将传统的“锁”算法...
chapin blog微服务架构 & DevOpsK8SService Mesh苏槐系列文章如何快速搭建一个微服务架构微服务架构中...什么是一致性哈希?无序数组排序后的最大相邻差值数据库数据库是如何工作的?高效sql性能优化极简教程Mongo高级
什么是一致性哈希? 它基本上是一种技术,用于专门基于基于ID或某些唯一代码创建的哈希值在不同服务器之间处理请求。 这几乎是用于负载分配的最简单算法之一,因为它在重定向请求之前不会考虑节点内部的工作量。 您...
leetcode 跳跃 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ Ⅵ Ⅶ Ⅷ ...五种数据类型、字典和跳跃表...缓存特征、缓存位置、缓存问题、数据分布、一致性哈希、LRU、CDN 消息处理模型、使用场景、可靠性 :hammer: 工具 一些 Git 的使用和概念。 正则
问题:哈希表通常意味着您需要将所有内容存储在内存中。 1.2 简单的解决方案:压缩数据并存储在磁盘中 1.3 解决方案:分布式Key-value存储 分片:假设我们要存储像 URL 这样的键,我们可以将它们除以第一个字符,...
系统中的参与者注册在一个由 Chord 算法支持的分布式哈希表中,因此系统中的保存和查找与参与客户端的数量成对数比例。Eclipse设置菜单 > 帮助 > 安装新软件 > 添加... 名称: M2Eclipse 位置: : 全选 > 下一步 > ...
布鲁尔的猜想和一致,可用,可分区容忍的网站的可行性 | BASE:替代酸| | 最终一致| 无冲突的复制数据类型 拜占庭将军问题 兼职议会| Paxos变得简单| 存储 Bitcask-用于快速键/值数据的日志结构哈希表| | Google文件...
分布式哈希表对于 Coursera 上的 UIUC 云计算概念课程第 1 部分:Gossip Membership Protocol:始终完整性(每个非故障进程检测每个节点的加入、故障和离开) 故障检测的准确性(当没有消息丢失且消息延迟很小时) ...
§10.10 表和索引的空间预分配 116 §10.11 确定数据库对象存储大小 117 §10.11.1 非簇表的大小计算 117 §10.11.2 索引大小计算 119 §10.11.3 簇表的大小计算 120 §10.11.4 位图索引的大小计算 122 §10.12 应用...
【算法】什么是一致性哈希?用来解决什么问题? 144 【性能优化】页面静态化 144 【设计模式】写一个单例(延迟加载,高性能) 144 【容器】Apache Http Server和Tomcat 区别 145 【版本控制】GIT与SVN的区别 146 【高...