Consistent Hash

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 网络中如何理想地做到这一点有很大的难度。

  • 本文作者: Wafer Li
  • 本文链接: https://wafer.li/DHT/Consistent Hash/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!