open-courses
Search…
Consistent Hashing and Random Trees (1997)
Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web*
论文作者的贡献主要包含两部分:Consistent Hashing 和 Random Trees。Consistent Hashing 主要用于解决分布式哈希表 (Distributed Hash Table, DHT) 的桶增减带来的重新哈希问题;Random Trees 主要用于分布式缓存中的热点问题,它利用了 Consistent Hashing。下文主要关注 Consistent Hashing。

Contribution

在分布式环境下,单台机器的负载有限,我们需要将请求散列到不同的机器上,利用更多的机器实现服务的横向扩容。这时候就需要 Hash Function,好的 Hash Function 能够帮我们均匀地分布到不同的机器上。但传统的 Hash Function 通常是静态的,桶的数量固定。在多台机器组成的服务中,每台机器就是一个桶,但机器在运行的过程中很可能出现崩溃,在请求数量波动较大时,需要动态地增减机器。如果每次桶的数量发生变化时都需要重新散列所有请求,可能造成多方面影响:
  • 来自于同一个用户的请求在桶发生变化时将被打到不同的节点,可能导致数据不一致 (考虑monotonic consistency)
  • 所有的 Client 都需要知道当前最新的 Hash Function 配置,在网络中传播这个配置需要时间
Consistent Hashing 的提出就是希望能够缓解/解决这个问题,使得每次桶数量发生变化时不需要重新散列桶内的所有元素,而是将受影响的数量控制在很小的范围内。

Definitions

作者从四个方面讨论了好的 Consistent Hash Function 应该满足的性质:
  • Balance:元素应当尽量均匀地分布到不同的桶内 (with high probability)
  • Monotonicity:当增加新的桶时,元素只可能从旧桶移动到新桶,而不可能从旧桶移动到其它旧桶
  • Spread:在不同的用户眼里,相同的元素可能被散列到不同的桶中,我们称之为不同的观点。Spread 要求总的观点数量必须有一个上限。好的 Consistent Hash Function 应当让 spread 尽量小。
  • Load:类似 spread,Load 性质是针对不同的用户,但它规定的是单个桶中不同元素数量的上限,即每个桶中的,至少有一个用户认为其中含有的,元素数量存在上限。好的 Consitent Hash Function 应当让这个上限尽量小。

Construction

作者提出一种构建好的 Consistent Hash Function 的方法:
假设我们有两个随机的函数
rBr_{B}
rIr_{I}
  • rBr_{B}
    将 buckets 映射到区间
    [0,1][0, 1]
  • rIr_{I}
    将 items 映射到区间
    [0,1][0, 1]
那么一个好的 Consistent Hash Function 可以定义为
fV(i)=min(rB(b)rI(i))f_{V}(i) = min(|r_B(b) - r_{I}(i)|)
,即将 item 放在距离它最近的 bucket 中。这里的 V 代表着不同的观点,由于观点数量会随着 buckets 的增减而增加,每个观点的内容会随着 buckets 的增减而变化,因此这个 Consistent Hash Function 并不是一个静态的、固定的函数。
这里还有一点,
rBr_{B}
通常需要将每个 bucket 映射到
[0,1][0, 1]
区间的多个点上。假设整个区间上的 bucket 数量上限为
CC
,那么
rBr_{B}
需要将每个 bucket 映射到
klogCk\log{C}
个点上,其中
kk
为常数,且
rBr_{B}
在映射单个 bucket 的不同点时,是相互独立的。
接着论文证明了上述函数满足 Monotonicity、Balance、Spread 和 Load 四个特性,这里简要说明一下证明的直觉:
  • Monotonicity:新增 bucket 时,新的 bucket 会被映射到
    klogCk\log{C}
    个随机的点上,而这些点周围的 items 可能会被新的 bucket 抢过来,因为新的 bucket 离它们更近,但绝不会出现 items 被旧的 bucket 抢走的情况,因此 Monotonicity 被满足。
  • Balance:因为每个 bucket 的
    klogCk\log{C}
    个点会随机分布在
    [0,1][0, 1]
    上,因此每个 bucket 将管辖不超过
    O(1)V\frac{O(1)}{V}
    长度的区间 (with high probability)。由于 items 会被随机地、均匀地分布在整个区间上,因此 Balance 被满足。
  • Spread:假设某个 item 被
    rIr_{I}
    映射到
    [0,1][0, 1]
    上的某个点,那么每个观点
    VV
    中,最接近 item 的 bucket 只有一个。由于 buckets 会被
    rBr_{B}
    随机、均匀地映射到整个区间,因此即使随着 buckets 数量的增减,观点的数量会增加,但可以想象,不可能所有新 bucket 对应的映射点都在 item 周围,位于它周围的 bucket 映射点数量应当有个上限。因此 Spread 被满足。
  • Load:类似 spread 的推理,把 item 和 bucket 位置对调即可。即对于每个 bucket 来说,映射到它附近的 items 数量应当有个上限。因此 Load 被满足。

Implementation

Consistent Hashing 在许多场景下都有应用,比如:
  • 负载均衡
  • P2P 系统
  • 数据库分片
  • ...
尽管场景很多,但它们对 DHT 的要求不一样:

负载均衡

在云原生环境下,为了保证服务的扩展性和可用性,通常会同时启动一个服务的多个实例。如何把不同的请求合理地反向代理到不同实例,是负载均衡器需要解决的问题。
为了保证服务的数据单调一致性,一些服务要求同一个用户的请求必须被路由到同一个实例。这时候就需要对用户的身份标识数据做一次哈希操作,找到固定的实例。但在云原生环境下,同一个服务的实例数量以及地址可能常常发生变化,为使得因实例变动影响到的用户数量最小,就需要使用 Consistent Hashing。
和其它场景不同,Consistent Hashing 在负载均衡场景下,实例数量发生变化时,实际上没有主动重新哈希已有数据的过程,因为它不需要保持对应关系数据。

实现思路

材料:哈希函数:
H(x)string[0,max]H(x):string \to [0, max]
方案:将每个节点哈希到区间
[0,max][0, max]
上随机的
kk
个点,将所有节点的所有哈希值排序后保存在一个数组
AA
中。每次新来一个请求,就将请求的 ID 哈希到区间 [0, max] 上的某个点,然后利用二分查找找到比 k 大的最小点,后者对应的节点就是目标实例。
算法复杂度分析:
操作
时间复杂度
AddNode
O(klog(n))O(klog(n))
DelNode
O(klog(n))O(klog(n))
Get
O(logkn)O(logkn)

实现示例

P2P 系统

Pastry

数据库分片

(TODO)

参考