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)

参考