Kyle's Notebook

一致性哈希(译)

Word count: 1.4kReading time: 5 min
2021/06/19

原文链接:Consistent Hashing

一致性哈希

一致性哈希的需求源自于缓存服务器集群,比如 Web 缓存,一套由 n 台缓存服务器组成的集群,实现负载均衡最常用的做法是把对象 o 存放在序号为 hash(o) mod n 的服务器上。

这种策略效果良好,但如果出于某种原因需要从集群中增加或删除服务器,会导致所有的对象 hash 值都被重新计算到新的地址上,其结果可能会很严重:就像缓存瞬间消失了,原本有缓存的服务器瞬间就被请求淹没。

因此需要使用一致性哈希来规避由于缓存失效、服务器承接大量请求的问题。

示例

从细节上来看,哈希函数是把对象及其缓存映射到一个数字范围上。

每位 Java 程序员都应该非常熟悉对象的 hashCode 方法会返回一个整型数(范围 [-2^32, 2^32-1]),可以试想一下将此范围映射到一个圆圈中,使得这些值可以被包含在内。

下图的圆圈中包含了对象 (1, 2, 3, 4),以及缓存 (A, B, C) 经过哈希计算得出的标记点(Web Caching with Consistent Hashing by David Karger et al)。

一致性哈希-1

为了找到一个对象在哪个缓存中,顺时针转动圆圈直到找到一个缓存点。

因此在上图中可见对象 1 和 4 属于缓存 A,对象 2 属于缓存 B,对象 3 属于缓存 C。

如果缓存 C 被删除了将会发生什么:对象 3 属于缓存 A,且其他所有的对象映射关系都不会被改变。

如果此时另一个缓存 D 被添加到标记的位置,对象 3 和 4 将会被划走,只剩下对象 1 还属于缓存 A。

一致性哈希-2

这种策略效果很好,只是存在一些问题:每个分配给缓存的间隔很难以命中。由于这种分配本质上是随机的,很可能导致缓存之间的对象分布很不均匀。

解决方法是 引入虚拟节点:即在圆圈中缓存点的副本。因此无论何时添加缓存,都会在圆圈中为其创建多个点。

在下面的图表(通过代码模拟将 10,000 个对象存储在 10 个缓存中)可以看到效果:x 轴是缓存点的副本数(对数刻度),当它的值很小时可见对象在整个缓存中的分布是很不平衡的,因为 标准偏差每个缓存中平均对象数 的百分比很高。随着副本数量增加,对象的分布会变得更平衡。

这个实验表明,一个包含 100 或 200 个副本的图即可达到可接受的平衡状态(标准偏差大约为平均值的 5% 至 10%)。

一致性哈希-3

实现

以下是基于 Java 的简单实现,用于完整呈现这种策略。

为了使一致性哈希更高效,hash 函数的混淆效果很重要。ObjecthashCode 方法的多数实现都不能起到良好的混淆效果,比如它们通常会产生数量有限的小整型值。因此使用一个允许自定义 hash 函数的 HashFunction 接口(此处建议使用 MD5 散列)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class ConsistentHash<T> {

private final HashFunction hashFunction;

private final int numberOfReplicas;

private final SortedMap<Integer, T> circle = new TreeMap<>();

public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
add(node);
}
}

public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.put(hashFunction.hash(node.toString() + i), node);
}
}

public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
circle.remove(hashFunction.hash(node.toString() + i));
}
}

public T get(Object key) {
if (circle.isEmpty()) {
return null;
}
int hash = hashFunction.hash(key.toString());
if (!circle.containsKey(hash)) {
SortedMap<Integer, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
}

圆圈用一个有序的整型 Map 表示(TreeMap,红黑树实现),代表了缓存的哈希值(此处为泛型 T)。

创建 ConsistentHash 时,每个节点都会多次添加到表示圆圈的 Map 中(次数由 numberOfReplicas 字段控制)。每个副本的位置由对节点名称和数字后缀的 hash 值决定,并将该节点存储在 Map 中。

要找到对象的节点(get 方法),应使用该对象的 hash 值在 Map 中查找。在大多数情况下都不会有节点存储在此 hash 值上(因为即使包括副本,hash 值范围通常比节点数大得多),因此在 Map 的尾部查找第一个 key 即可找到下一个节点。如果 Map 的尾部为空,则可以获取第一个 key 来环绕圆圈。

应用

很多库都有提供一致性哈希的功能,因此不需要自己编码来实现它。例如现在 Memcached(一种分布式内存对象缓存系统)就具有支持一致性哈希的客户端。第一个是 Richard Jones 的 Last.fm’s ketama ,Dustin Sallings 也有基于 Java 的实现。有趣的是只有客户端需要实现一致性哈希算法,Memcached 服务器不用改变。

其他采用一致性哈希的系统:包括 Chord(分布式哈希表实现)和 Amazon 的 Dynamo(键值存储,不对 Amazon 外部开放使用)。

CATALOG
  1. 1. 一致性哈希
    1. 1.1. 示例
    2. 1.2. 实现
    3. 1.3. 应用