Consistent Hash

Wafer Li ... 2016-11-07 DHT
  • DHT
  • 旧文仓库
大约 7 分钟

# 1. 概述

大多数 DHT 使用稳定散列方法(consistent hash)来将关键值对应到节点。

在使用稳定散列算法后,哈希表槽位数(大小)的改变平均只需要对 K/nK/n 个关键字重新映射,其中 KK 是关键字的数量, nn 是槽位数量。而不需要对整个哈希表进行重新映射。

下面就来介绍几种主流的 DHT 稳定散列协议算法。

# 2. Chord 算法

Chord 在 2001 年由 MIT 提出,它不关心资源是如何存储的,只关心资源的快速取得。

# 2.1 散列计算方法

Chord 使用 SHA-1 作为散列计算函数,保证了散列值的非重复性。SHA-1 会产生一个 21602^{160} 的整数空间,每项为一个 160 bit 的大整数,它们首尾相连,形成 Chord 环。

# 2.2 查找算法

显然任何查找只需要绕 Chord 环一圈即可完成,此时时间复杂度为 O(N)O(N),这对于一个上百万节点,而且节点随时处于动态变化中的 P2P 网络是不可承受的,所以 Chord 提出如下的非线性查找算法:

  1. 每个节点维护一个 mm 个其他节点信息的查询表,(mm 为位数,Chord 中为 160,表格中的节点的 ID 间距为 2i2^i,这样实际形成了一个二分查找所需要的查找关系表
  2. 查询时,查询节点将请求发送到与键值最接近的节点上,收到请求的节点如果存储了信息,则返回;否则,按照查询表将请求转发到与键值最接近的节点上;直到找到相应节点为止。

由于节点的查询表采用的是二分查找式的分布方式,不难看出,查询过程实际上就是二分查找的过程。

经过优化,Chord 查询所需的跳数由 O(N)O(N) 下降为 O(logN)O(logN)

# 2.3 优点

  1. 负载均衡

    所有的节点都以同样的几率负担系统负荷,从而可以避免某些节点负载过大。

  2. 分布性

    所有的节点平等的完成同样的工作,所以 Chord 具有比较高的健壮性,能抵御 DoS 攻击

  3. 可扩展性

    Chord 的系统开销按照 O(logN)O(logN) 增加,增加比例不大,因此它可以用于较大规模的系统

  4. 可用性

    Chord 可以根据网络的变化更新查询表,及时恢复查找关系,使得查询可以可靠进行

  5. 灵活性

    Chord 并未限制查询的内容结构,因此应用层可以灵活的将内容映射到键值空间,而不用受到协议的限制。

# 3. CAN 算法

CAN 是 2001 年由加州大学伯克利分校提出的。与 Chord 一样,也是 DHT 的一种实现形式。

# 3.1 哈希算法

在 CAN 中,每个节点自身的 ID 经过哈希后,能得到一个 d 维向量,所以整个 P2P 系统将被映射到一个 d 维的笛卡尔空间去。而 Chord 使用的 SHA-1 算法生成的结果是一维的。

其中 d 为一个系统决定的常量

# 3.2 查找算法

CAN 的节点通过维护一个相邻节点表来进行非线性搜索。 与 Chord 不同的是,CAN 不要求查询表的邻居节点保持 2i2^i 的关系,而采用笛卡尔空间的相邻定义:

dd 维笛卡尔空间中,2个节点的 dd 维坐标中有 d1d-1 维是相等的,剩余的一维是相邻的节点称之为相邻节点。

在查询的过程中,查询节点首先计算出被查询内容的键值 (d 维向量),然后在节点列表中查找与之最近的相邻节点,向其发送查询请求;如果被查询节点包含资源,则返回;否则,被查询节点就根据查询表转发到相应最近节点,直到查询完毕为止。

如果相邻节点表中没有可用的下一跳节点,则开始进行扩展环搜索(从最近的n个节点开始,层层转发直到找到目标或超出了跳数的上限为止),直到找到可用节点。

经过CAN的优化后,查询需要的跳数由 O(N)O (N) 减少到均值为(d/4)(n1/d)(d/4)(n1/d) 的随机制,考虑到 dd 为常数,这一值可以表示为O(n1/d)O(n1/ d)

# 3.3 比较

CAN 和 Chord 的主要区别在于查找算法不同。

相比之下,在节点数量非常大时,CAN 的平均查询跳数要比 Chord 增加得更快。

而且 CAN 查询过程中需要的运算量也要高于 Chord 。但 CAN 使用的 dd 为预先设置的常量,因此并不假设系统节点数量。

但是在节点总数动态变化范围很大的系统中,CAN 的相邻节点表结构保持稳定,这在 P2P 这一时常在变化的网络系统中有很大优点。

# 4. Pastry

Pastry 于 2001 年位于英国剑桥的微软研究院和莱斯(Rice)大学提出。

# 4.1 哈希算法

在 Pastry 中,每个节点拥有一个 128 bit 的标识,为了保证 ID 的一致性,一般采用节点的 IP 地址进行哈希计算。

Pastry 并没有规定应该使用何种哈希算法,而只规定了哈希键值为一维。(实际上则是使用了 128 bit 的整数空间)

# 4.2 查找算法

在 Pastry 中,每个节点拥有一个路由表 RR,一个邻居节点表 MM,和一个叶子节点表 LL,它们一起构成了节点的状态表。

路由表 RR 共有 logBNlogBN 行,其中,B=2bB = 2b 为系统参数,NN 为节点的总数。每行包括 B1B - 1 个项,每个项记录了一个邻居节点的信息。

叶子节点表存放的是在空间中与当前节点最近的 L|L| 个节点的信息; 其中,一半节点的标识大于当前节点,另一半小于当前节点。 一般取 L=2b|L| = 2b 或者 4b4b

邻居节点存放着在 真实网络 中与当前节点最近的 M|M| 个相邻节点的信息。距离在这里的定义指的是由多种因素综合得到的转发开销。

Pastry 并未提供距离节点的获取方法,而是由应用层来进行相邻节点的配置。

enter image description here

具体的查找过程如下:

  1. 首先,节点获取到被查询对象的 ID 后,检查 ID 是否在叶子节点的范围内
  2. 如果不在,则从路由表中按照最长前缀优先原则查找一个转发节点
  3. 如果不存在这样的节点,则从所有邻居节点集合(包括路由表中的子叶子表和邻居节点表)选择最近的节点进行消息转发,直到查询完毕为止。

从过程中看,如果路由表不为空,则每步查找至少能夠增加一個前綴匹配数位,所以在路由表始终有效时,步数最多为 logBNlogBN

# 4.3 比较

Pastry的查找利用了成熟的最大掩码匹配算法,因此实现时可以利用很多现成的软件算法和硬件框架,可以获得很好的效率。

与 Chord 和 CAN 相比,Pastry 引入了叶子节点和邻居节点集合的概念。

在应用层能够及时准确地获得这两个集合的节点信息时,可以大大加快查找查找的速度,同时降低因查找引起的网络传输开销;

不过在动态变化的 P2P 网络中如何理想地做到这一点有很大的难度。