一致性哈希和分布式哈希表

一致性哈希(consistent hashing)和分布式哈希表(DHT: Distributed Hash Table)在最近的学习中经常用到,但是两个概念经常纠缠在一起,不容易分清楚。有时候就不明白这里为什么说的是consistent hashing,而不是用DHT。

从字面的意思来区分:consistent hashing 是一种满足特殊需求的哈希;DHT 是通过哈希实现的分布式的表,归根到底是一个分布式系统。consistent hashing 是理论上节点变化最少数据迁移的哈希方法,而DHT 在实现上更加具体,DHT 把传统的单个K-V 表在分布式多个节点中进行划分,既可以采用consistent hashing 实现,也可以采用其他哈希方法。

一致性哈希   consistent hashing

一种特殊的哈希。在传统的哈希表中,当划分哈希区域的分组数量发生变化时,几乎所有的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=2^{32}$ 。并使用同样哈希函数和模数R 对所有的节点进行同样的计算hash(node.id) mod R。这样就把节点和对象都哈希到同一个大小为R 的环(Ring)上了。每个节点管理、存储它和它环上前驱节点之间范围的对象,当有新的节点加入或者退出时,遵循同样规则。这样的好处是剥离了对象分布和节点的关系,节点个数发生变化时对象在环上的分布不发生变化,最大限度减少了对象在节点上的迁移。

下面图示了consistent hashing 节点加入、退出过程(图片来源):

consistent-hashing-1

在只有两个节点node 1 和node 2 ,哈希结果为Key1 和key2 ,每个节点存储前驱节点(如key2>key1)和自己之间范围的对象(values)。在节点个数比较少的时候就可能存在负载不均衡的情况,这个可用通过引入虚拟节点来解决。

consistent-hashing-2

添加一个节点node3 (key3)的情形。根据每个节点管理、存储它和它环上前驱节点之间范围的对象的原则,node3(key3)分担了key2 的空间。

consistent-hashing-3

删除一个节点node1(key1)的情形。key1 的空间被node3(key3)接管了。

consistent-hashing-4

引入虚拟节点后的结果。为了避免因为节点空间不均衡导致负载不平衡,每个节点引入等量的虚拟节点分布在环上,虚拟节点使用同样的方法划分空间。采用v1_key1=hash(node1.id.v1) ……vn_key1=hash(node1.id.vn)  的方法可以得到节点node1 的n 个虚拟节点vi_key1。

consistent hashing 具有以下性质:

  1. Spread: 发散性指的是对象分发到各个节点上,每个节点只需要存储所有对象的一部分
  2. Load: 负载指的是任何一个节点都不会保存过多的对象数据
  3. Smothness: 平滑性指的是节点改变带来的对象迁移是平缓的。不会因为节点的加入、退出导致大量数据迁移
  4. Balance: 平衡性指的是每个对象随机分配到节点
  5. Monotonic: 单调性指的是当一个节点加入时,只有分配到该节点的对象发生了重排

 

分布式哈希表   Distributed Hash Table

分布式哈希表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($\sqrt{n}$) O(1)

DHT 具有三点性质:

  1. Decentralization: 去中心化,节点之间相互配合形成整个系统,而不需要一种中心节点协调
  2. Fault tolerance: 容错,即使不断有节点加入、退出或者失效,也要能够保证系统稳定
  3. Scalability: 扩展性,系统在成千上万个节点时也能够有效地运行

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据