一致性哈希算法

我们希望构造一种函数 f(k,n)→m 把字符串映射到 n 个槽上：

  • 它的输入是随机到来的字符串 k 和 槽的个数 n.
  • 输出是映射到的槽的标号 m , m < n.

这个函数需要有这样的性质：

  • 映射均匀： 对随机到来的输入 k， 函数返回任一个 m 的概率都应该是 1/n 。
  • 一致性：
    • 相同的 k, n 输入， 一定会有相同的输出。
    • 当槽的数目增减时， 映射结果和之前不一致的字符串的数量要尽量少。

更严格的、维基百科的定义是：当添加一个槽时，只需要对k/n个字符串进行进行重新映射。

这个算法的关键特征在于,不要导致全局重新映射，而是要做增量的重新映射。

接下来将介绍三种一致性哈希算法：

  • 哈希环法
  • 跳跃一致性哈希法
  • Maglev一致性哈希法

三者对比如下:

均匀性 最小化重新映射 时间复杂度 加权映射 热扩容 & 容灾
哈希环 ⍻ ✔ $O(log(n))$ ✔ ✔
跳跃一致性哈希 ✔ ✔ $O(log(n))$ ✔ ✔
Maglev哈希 ✔ ✘ $O(1)$ ✔ ✘

一致性哈希算法的好坏定义

一致性哈希算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

  1. 平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
  2. 单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
  3. 分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
  4. 负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
  5. 平滑性(Smoothness)：缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

一致性哈希算法的用途

在分布式缓存系统中使用一致性哈希算法时，某个节点的添加和移除不会重新分配全部的缓存，而只会影响小部分的缓存系统，如果均衡性做的好的话，当添加一个节点时，会均匀地从其它节点移一部分缓存到新的节点上；当删除一个节点的时候，这个节点上的缓存会均匀地分配到其它活着的节点上。

一致性哈希缓存还被扩展到分布式存储系统上。数据被分成一组Shard,每个Shard由一个节点管理，当需要扩容时，我们可以添加新的节点，然后将其它Shard的一部分数据移动到这个节点上。比如我们有10个Shard的分布式存储系统，当前存储了120个数据，每个Shard存储了12个数据。当扩容成12个Shard时，我们从每个Shard上拿走2个数据，存入到新的两个Shard上,这样每个Shard都存储了10个数据，而整个过程中我们只移动了20/120=1/6的数据。

哈希环法

哈希环法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而哈希环法是对$2^{32}$取模，什么意思呢？简单来说，哈希环法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0~$2^{32}$-1（即哈希值是一个32位无符号整形），整个哈希环如下：

整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到$2^{32}$-1，也就是说0点左侧的第一个点代表$2^{32}$-1， 0和$2^{32}$-1在零点中方向重合，我们把这个由$2^{32}$个点组成的圆环称为Hash环。

下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用IP地址哈希后在环空间的位置如下：

接下来使用如下算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器！

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据哈希环法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

容错性和可扩展性

现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在哈希环法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响，如下所示：

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：

此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X ！一般的，在哈希环法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

综上所述，哈希环法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

哈希环做到了在槽位数量变化前后的增量式的重新映射， 避免了全量的重新映射。

假设整体的k的数量是K, 由于哈希映射的均匀性， 所以，添加或者删除一个槽位，总会只影响一个槽位的映射量，也就是1/K, 因此，哈希环做到了最小化重新映射(minimum disruption)，做到了完全的一致性。

复杂度分析

在技术实现上，实现哈希环的方法一般叫做 ketama 或 hash ring。 核心的逻辑在于如何在环上找一个和目标值 z相近的槽位， 我们把环拉开成一个自然数轴， 所有的槽位在环上的哈希值组成一个有序表。在有序表里做查找， 这是二分查找可以解决的事情， 所以希环的映射函数的时间复杂度是 O(logn)。

对于空间复杂度，显然是 O(n)。

带权重

实际应用中， 还可以对槽位（节点）添加权重。 大概的逻辑是构建很多指向真实节点的虚拟节点， 也叫虚拟节点。 虚拟节点之间是平权的，选中虚拟节点，就代表选中了背后的真实节点。 权重越大的节点，虚拟节点越多， 被选中的概率就越大。

下面的图6.2是一个例子， 其中 N0,N1,N2,N3 的权重比是 1:2:3:2。 选中一个虚拟节点如 V(N2) 就是选中了 N2。

但是需要注意的是， 权重的调整会带来数据迁移的工作。

数据倾斜问题

哈希环法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，例如系统中只有两台服务器，其环分布如下：

此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，哈希环法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。

例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。

实际应用中，即使节点之间是平权的， 也会采用虚拟节点。 比如，常用的ketama方法中，一般采用一个节点对应40个虚拟节点。 原因是，节点越多、映射的分布越均匀，采用虚拟节点可以减少真实节点之间的负载差异。

但是一致性哈希环算法的映射结果仍然不是很均匀:当有100个虚拟节点时，哈希环法的映射结果的分布的标准差大有 10%。 当虚拟节点增加到1000个时，这个标准差降到 3.2% 左右。

虚拟节点是一个绝妙的设计，不仅提高了映射结果的均匀性， 而且为实现加权映射提供了方式。 但是，虚拟节点增加了内存消耗和查找时间， 以常用的ketama为例， 每个节点都对应40个虚拟节点， 内存的消耗从 O(n)变为O(40n) ，查找时间从 O(logn) 变为 O(log(40n)) 。

虚节点这种靠数量取胜的策略增加了存储这些虚节点信息所需要的空间。还一种比较特殊的方法来解决分布不均的问题，改进了这些数据分布的算法，将环上的空间均匀的映射到一个线性空间，这样，就保证分布的均匀性。

扩散问题

大家使用一致性HASH的时候，可能都是只有一个路由KEY。但是对于批量请求的缓存服务，就涉及到一致性HASH扩散问题了。

比如我们的一个HASH环下有5个节点，业务一次请求批量拉取30个KEY，业务的请求是10W/s。此时我们该如何使用一致性HASH支持这个需求呢？

可能有些人没看出来问题是什么。

假设我们30个KEY分别一致性HASH向下拉取数据，那么对外路由层QPS是10W/S，对内缓存层QPS是300W/S。这么大的流量，网络操作等非业务操作就会消耗很多资源。所以批量请求需要在一致性HASH之后再聚合数据批量向下请求。

比如30个KEY平均的均摊在5个节点上，每个节点的6个KEY可以一次请求去拉数据，而不是6次请求。但是这样做对内的QPS也有50W/S，其实这个量也不小。此时，当负载过高时，我们增加一致性HASH节点无法解决问题。

为什么呢？

假设5台机器，对外QPS是10W/s，对内聚合请求QPS是50W/s（每个节点10W）。一致性HASH增加5个节点，这时对内的聚合请求QPS就是100W/S了，每台机器依旧是10W的QPS（单节点KEY量变少，负载会适当降低，但没有解决问题）。另外，这时候扩散更严重，意味着网络操作等额外操作会消耗更多的资源，

根据这个结论，我们可以反推出另一个结论：一致性HASH下应该有多少个节点？

答案是能够满足命中率指标的前提下（如储存下全量数据），节点数应该尽量的少。因为多余的节点不仅不能增加命中率，反而会因为扩散更严重而更消耗资源。

热点问题(有界一致性哈希)

有时候，我们已经将一致性HASH的虚拟节点调至最大了（假设有上限），发现流量依旧不均衡，甚至部分节点CPU跑满。 这时候甚至扩容都无法解决问题。

这种部分节点的流量总是比其他机器的流量高的问题，称为热KEY问题。这里面原因是多方面的，有可能确实是概率因素，但更多的是单KEY流量太高。此时我们无论怎么扩容或者增大虚拟节点个数都是无效的。因为一个KEY只会路由到一个机器，而这个KEY的量那台机器支持不住，那只能想其他办法了。

下面要介绍的有界一致性哈希就是一种解决这个问题的方法。

想象一下，在一个圆上覆盖了给定范围的数字。谷歌研究团队对球和进球箱分别应用不同的哈希函数，以获得与该圆上的位置对应范围内的数字。然后，我们开始以特定的顺序（假设根据它们的ID）分配球，而不考虑它们的哈希值。然后每个球顺时针移动，并分配到还有剩余容量的第一个箱子。

想象一下有6个球和3个箱子，使用2个哈希函数来随机循环地分配球进箱。设每个箱子的容量是2，然后按球的升序依次分配球（根据它们的ID），顺时针移动，1号球进入箱子C，2号球进入箱子A，3号球和4号球进入箱子B，5号球进入箱子C，然后6号球顺时针移动尝试进入箱子B，然而箱子B容量已达限制（箱子容量为2，箱子B已经装了3号球和4号球），所以6号球继续顺时针移动尝试进入箱子C，但是箱子C也已达容量，最后6号球进入了箱子A。

系统有任何更新（球或箱增加/删除）时，算法需要重新进行计算分配以保证均匀性。算法中巧妙的一点在于，确保小范围的更新（少量球或箱增加/删除）只引起细微的分配变化，以满足一致性。 在论文中，谷歌研究团队表明了增加和删除一个球引起其他球O（1 /ε2）的移动。最重要的一点是负载上界与系统中的球或箱的数量相对独立。 所以即使球或箱的数量加倍，负载的界限也不会改变。这一点增强了分配问题的可扩展性（即使扩大分配规模，也不影响一致性）。下图模拟了球或箱有更新时，移动次数（再分配）随更新的变化情况。

红色曲线显示平均移动次数，蓝色线条表示不同ε值的方差。 虚线曲线是基于理论研究建议的负载上界（通过预测实际运动次数能较好地拟合）。除此之外，对于任意值ε，谷歌研究团队知道每个箱子的负载上下界为平均负载的（1 +ε）倍。 下图表示不同值ε（ 0.1，0.3，0.9）对应的箱子的负载分布。

不同ε值的负载分布。 负载分布几乎均匀，覆盖了从0到（1 +ε）倍的平均负载，还有许多箱子的负载等于（1 +ε）倍的平均负载

从图中可以看出均匀性和一致性的一个折衷 - 较小的ε值增强了均匀性，降低了一致性；而较大的ε值增加了一致性而降低了均匀性。较低的ε值能确保许多箱子的负载等于（1 +ε）倍的平均负载，其余箱子的负载依次衰减。

有限负载一致性哈希（Consistent Hashing with Bounded Loads） 出自论文 Consistent Hashing with Bounded Loads ，主要思路是，根据当前负载情况对所有节点限制一个最大负载，在一致性哈希中对 hash 环进行查找时将跳过达到最大负载限制的节点，通过把过载的请求转移到其他节点上来解决热点和不均衡问题：

  • R: 当前所有节点的总负载（正在处理的总请求数）
  • T: 节点总个数
  • L: 当前所有节点的平均负载,L = R/T
  • ε: 一个参数用于表示在平均负载的基础上能够承受的额外负载上限，可以按照实际需求进行设置（根据 vimeo 分享的 经验 这个值推荐设置为 0.25~1）
  • M: 节点的最大负载上限,M = L*(1+ε) = R*(1+ε)/T

一致性哈希中进行节点查找时，增加检查匹配的节点的负载（正在处理的请求数）是否达到负载上限 M 的操作，如果达到了上限则跳过当前节点继续往后查找。

通过上面可以发现 Consistent Hashing with Bounded Loads 结合了 最少连接策略 和一致性哈希 策略各自的优点，即平衡了负载又兼顾了一致性哈希，并且还可以通过调整转化为最少请求策略或一致性哈希策略：

  • 当 ε 的值是 0 的时候，就实现了最少连接策略的效果
  • 当 ε 的值是无穷大的时候，就是传统的一致性哈希策略。

热扩容和容灾

对于增删节点的情况，哈希环法做到了增量式的重新映射，不再需要全量数据迁移的工作。 但仍然有部分数据出现了变更前后映射不一致， 技术运营上仍然存在如下问题：

  • 扩容：当增加节点时，新节点需要对齐下一节点的数据后才可以正常服务。
  • 缩容：当删除节点时，需要先把数据备份到下一节点才可以停服移除。
  • 故障：节点突然故障不得不移除时，面临数据丢失风险。

如果我们要实现动态扩容和缩容，即所谓的热扩容，不停止服务对系统进行增删节点,可以这样做：

  1. 数据备份(双写)： 数据写入到某个节点时，同时写一个备份(replica)到顺时针的邻居节点。
  2. 请求中继(代理)： 新节点刚加入后，数据没有同步完成时，对读取不到的数据，可以把请求中继(replay)到顺时针方向的邻居节点。

下面的图7.1中演示了这两种规则：

  1. 移除节点的情况： 每一个节点在执行写请求时，都会写一个备份到顺时针的邻居节点。 这样，当 N3 节点因故障需要踢除时，新的请求会交接给它的邻居节点 N2， N2 上有 k1 的备份数据，可以正常读到。
  2. 新增节点的情况： 对于新增节点的情况稍微复杂点， 当新增节点 N4 时， N4 需要从邻居节点 N1 上同步数据， 在同步仍未完成时，可能遇到的请求查不到数据， 此时可以先把请求中继给 N1 处理, 待两个节点数据对齐后，再结束中继机制。

就像细胞分裂一样， N4 刚加入时可以直接算作时 N3 的一部分， N3 算作一个大节点， 当数据对齐后， N4 再从 N3 中分裂出来，正式成为新节点。

另外，可以备份不止一份。下面图7.2中演示了备份两次情况， 每个写请求都将备份同步到顺时针方向的最近的两个节点上。 这样就可以容忍相邻的两节点损失的情况，进一步提高了系统的可用性。

同样的，中继也可以不止一次。 下面图7.3中演示了中继两次的情况， 如果一个节点上查不到数据，就中继给下一个节点，最多两次中继， 这样就可以满足同时添加”两个正好在环上相邻的”节点的情况了。

代码实现

https://github.com/lafikl/consistent

  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
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272

// An implementation of Consistent Hashing and
// Consistent Hashing With Bounded Loads.
//
// https://en.wikipedia.org/wiki/Consistent_hashing
//
// https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
package consistent

import (
	"encoding/binary"
	"errors"
	"fmt"
	"math"
	"sort"
	"sync"
	"sync/atomic"

	blake2b "github.com/minio/blake2b-simd"
)

const replicationFactor = 10

var ErrNoHosts = errors.New("no hosts added")

type Host struct {
	Name string
	Load int64
}
// Consistent为一致性哈希算法的核心数据结构，如下：
type Consistent struct {
	hosts     map[uint64]string   // 存储表格散列值-表格名kv对或主机散列值-主机名kv对等，
	sortedSet []uint64            // 表的哈希值列表，已经有序，当给一定key的哈希值，能直接用二分查找法快速检索出这个key所属表、主机的哈希值
	loadMap   map[string]*Host    // 存储表名-表的kv对、主机ip地址-Host的kv对等等
	totalLoad int64               // 记录所有机器的负载

	sync.RWMutex                 // 避免有多个goroutine同时修改Consistent导致冲突
}

func New() *Consistent {
	return &Consistent{
		hosts:     map[uint64]string{},
		sortedSet: []uint64{},
		loadMap:   map[string]*Host{},
	}
}
// 下面是往集群添加一台机器的代码：
func (c *Consistent) Add(host string) { // host可以表示任意对象，如主机ip地址127.0.0.1:8000或者表名1024
	c.Lock()                 // 加锁，避免并发修改导致的冲突
	defer c.Unlock()

	if _, ok := c.loadMap[host]; ok {    // 如果主机或表已经存在，直接返回
		return
	}

	c.loadMap[host] = &Host{Name: host, Load: 0}   // 初始化host主机或表的负载
	for i := 0; i < replicationFactor; i++ {       // 这里replicationFactor默认为10，也就是说1个表对应10个虚表、1台机器对应10台虚拟机器，提高机器负载的均衡性
		h := c.hash(fmt.Sprintf("%s%d", host, i))  // 求出每台虚拟机的地址或虚拟表的hash值，为uint64类型
		c.hosts[h] = host                          // uint64的哈希值-主机ip地址
		c.sortedSet = append(c.sortedSet, h)       // 把计算的哈希值添加到列表

	}
	// sort hashes ascendingly
	sort.Slice(c.sortedSet, func(i int, j int) bool {   // 对更新后的主机hash值列表进行排序
		if c.sortedSet[i] < c.sortedSet[j] {
			return true
		}
		return false
	})
}

// Returns the host that owns `key`.
//
// As described in https://en.wikipedia.org/wiki/Consistent_hashing
//
// It returns ErrNoHosts if the ring has no hosts in it.
// 下面是检索某个key对应的主机ip地址代码：
func (c *Consistent) Get(key string) (string, error) { // 计算某个key对应的表名或主机ip地址
	c.RLock()
	defer c.RUnlock()

	if len(c.hosts) == 0 {
		return "", ErrNoHosts
	}

	h := c.hash(key)       // 先算出key的哈希值
	idx := c.search(h)     // 通过二分查找出第一个等于或比key大的主机ip地址在列表的索引值，如果找不到，就用列表第1个主机，因为有序列表可以看作是一个环，列表尾部与头部是相接的
	return c.hosts[c.sortedSet[idx]], nil
}

// It uses Consistent Hashing With Bounded loads
//
// https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
//
// to pick the least loaded host that can serve the key
//
// It returns ErrNoHosts if the ring has no hosts in it.
//
func (c *Consistent) GetLeast(key string) (string, error) {
	c.RLock()
	defer c.RUnlock()

	if len(c.hosts) == 0 {
		return "", ErrNoHosts
	}

	h := c.hash(key)
	idx := c.search(h)

	i := idx
	for {
		host := c.hosts[c.sortedSet[i]]
		if c.loadOK(host) {
			return host, nil
		}
		i++
		if i >= len(c.hosts) {
			i = 0
		}
	}
}

func (c *Consistent) search(key uint64) int {
	idx := sort.Search(len(c.sortedSet), func(i int) bool {   // 使用sort包查找出第一个大于或等于key值的表或主机ip
		return c.sortedSet[i] >= key
	})

	if idx >= len(c.sortedSet) {  // 如果找不到，那么就用列表第1个元素
		idx = 0
	}
	return idx
}

// Sets the load of `host` to the given `load`
func (c *Consistent) UpdateLoad(host string, load int64) {
	c.Lock()
	defer c.Unlock()

	if _, ok := c.loadMap[host]; !ok {
		return
	}
	c.totalLoad -= c.loadMap[host].Load
	c.loadMap[host].Load = load
	c.totalLoad += load
}

// Increments the load of host by 1
//
// should only be used with if you obtained a host with GetLeast
func (c *Consistent) Inc(host string) {
	c.Lock()
	defer c.Unlock()

	atomic.AddInt64(&c.loadMap[host].Load, 1)
	atomic.AddInt64(&c.totalLoad, 1)
}

// Decrements the load of host by 1
//
// should only be used with if you obtained a host with GetLeast
func (c *Consistent) Done(host string) {
	c.Lock()
	defer c.Unlock()

	if _, ok := c.loadMap[host]; !ok {
		return
	}
	atomic.AddInt64(&c.loadMap[host].Load, -1)
	atomic.AddInt64(&c.totalLoad, -1)
}

// Deletes host from the ring
func (c *Consistent) Remove(host string) bool {
	c.Lock()
	defer c.Unlock()

	for i := 0; i < replicationFactor; i++ {           // 把表对应的10张虚拟表或主机对应的10台虚拟机器从列表中删除
		h := c.hash(fmt.Sprintf("%s%d", host, i))
		delete(c.hosts, h)
		c.delSlice(h)
	}
	delete(c.loadMap, host)                           // 同时把主机的负载信息删除
	return true
}

// Return the list of hosts in the ring
func (c *Consistent) Hosts() (hosts []string) {
	c.RLock()
	defer c.RUnlock()
	for k, _ := range c.loadMap {
		hosts = append(hosts, k)
	}
	return hosts
}

// Returns the loads of all the hosts
func (c *Consistent) GetLoads() map[string]int64 {
	loads := map[string]int64{}

	for k, v := range c.loadMap {
		loads[k] = v.Load
	}
	return loads
}

// Returns the maximum load of the single host
// which is:
// (total_load/number_of_hosts)*1.25
// total_load = is the total number of active requests served by hosts
// for more info:
// https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
func (c *Consistent) MaxLoad() int64 {
	if c.totalLoad == 0 {
		c.totalLoad = 1
	}
	var avgLoadPerNode float64
	avgLoadPerNode = float64(c.totalLoad / int64(len(c.loadMap)))
	if avgLoadPerNode == 0 {
		avgLoadPerNode = 1
	}
	avgLoadPerNode = math.Ceil(avgLoadPerNode * 1.25)
	return int64(avgLoadPerNode)
}

func (c *Consistent) loadOK(host string) bool {
	// a safety check if someone performed c.Done more than needed
	if c.totalLoad < 0 {
		c.totalLoad = 0
	}

	var avgLoadPerNode float64
	avgLoadPerNode = float64((c.totalLoad + 1) / int64(len(c.loadMap)))
	if avgLoadPerNode == 0 {
		avgLoadPerNode = 1
	}
	avgLoadPerNode = math.Ceil(avgLoadPerNode * 1.25)

	bhost, ok := c.loadMap[host]
	if !ok {
		panic(fmt.Sprintf("given host(%s) not in loadsMap", bhost.Name))
	}

	if float64(bhost.Load)+1 <= avgLoadPerNode {
		return true
	}

	return false
}

func (c *Consistent) delSlice(val uint64) {
	idx := -1
	l := 0
	r := len(c.sortedSet) - 1
	for l <= r {
		m := (l + r) / 2
		if c.sortedSet[m] == val {
			idx = m
			break
		} else if c.sortedSet[m] < val {
			l = m + 1
		} else if c.sortedSet[m] > val {
			r = m - 1
		}
	}
	if idx != -1 {
		c.sortedSet = append(c.sortedSet[:idx], c.sortedSet[idx+1:]...)
	}
}

func (c *Consistent) hash(key string) uint64 {
	out := blake2b.Sum512([]byte(key))
	return binary.LittleEndian.Uint64(out[:])
}

跳跃一致性哈希法

对于分布式存储系统，当一个节点失效时，我们并不期望它被移除，而是使用备份节点替换它，或者将它恢复起来，因为我们不期望丢掉它上面的数据。对于这种情况(节点可以扩容，但是不会移除节点)，Google的 John Lamping, Eric Veach提供一个高效的几乎不占用持久内存的算法： 跳跃一致性哈希。

go版本实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func JumpHash(key uint64, buckets int) int {
	var b, j int64
	if buckets <= 0 {
		buckets = 1
	}
	for j < int64(buckets) {
		b = j
		key = key*2862933555777941757 + 1
		j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
	}
	return int(b)
}

以上就是算法的全部代码，输入参数分别是64位的key，桶的数量（一般对应服务器的数量），输出是一个桶的编号（从0开始）。

算法原理

基础原理

一致性哈希算法有两个目标：

  • 平衡性。即把数据平均的分布在所有节点中。
  • 单调性。即节点的数量变化时，只需要把一部分数据从旧节点移动到新节点，不需要做其他的移动。

我们根据这个单调性可以推算出一些性质来。

这里先令f(key, n)为一致性哈希算法，输出的为[0,n)之间的数字，代表数据在对应的节点上。

  1. n=1 时，对于任意的key，输出应该都是0。
  2. n=2 时，为了保持均匀，应该有1/2的结果保持为0，1/2的结果输出为1。
  3. n=3 时，应该有1/3的结果保持为0，1/3的结果保持为1，1/3的结果保持为2。
  4. 依次递推，节点数由n变为n+1时，f(key, n)里面应该有n/(n+1)的结果不变，有1/(n+1)的结果变为n。

我们知道了每次需要重新映射多少份，才可以保证映射均匀。接下来的问题是：哪些 k 要被重新映射呢？ 就是说在新加槽位的时候，要让哪些 k 跳到新的槽位， 哪些 k 留在老地方不动呢？

Google 的办法是用随机数来决定一个 k 每次要不要跳到新槽位中去。 但是请注意，这里所说的「随机数」是指伪随机数，即只要种子不变，随机序列就不变。 我们程序语言中的随机数发生器都是伪随机的：

对每一个 k , 我们用这个 k 做随机数种子，就得到一个关于 k 的随机序列。 为了保证槽位数量由 j 变为 (j+1) 时有 1/(j+1) 占比的数据会跳到新槽位 (j+1)， 就可以用如下的条件来决定是否重新映射：如果random.next() < 1 / (j+1) 则跳，否则留。 那么，我得到了初步的一个 ch 函数：

1
2
3
4
5
6
7
8
9

int ch(int k, int num_buckets) {
    random.seed(k) ;
    int b = 0; // This will track ch(key, j +1) .
    for (int j = 1; j < num_buckets; j ++) {
        if (random.next() < 1.0/(j+1) ) b = j ;
    }
    return b;
}
//代码中的random.next()产生[0,1)的随机数，随机数序列只和key有关，key为随机种子。

下面的图8.2是对这个函数的一个演绎。 n 从 1 变化到 5 的过程中， k1 和 k2 每一次都要根据随机序列相应的值和目标分布 1/n 的比较， 来决定留在原来的槽位还是跳到新槽位。

需要注意的是， k 一旦确定， 随机序列就确定了， 每次计算 ch 函数，都会重新初始化随机数种子， 这样后面的 for 循环就是在遍历一个确定的序列而已。 并不是真正的随数。 就是说， k 一旦确定， 给定一个 n 时， k 的映射结果都是唯一确定的， 也就是一致的。

另一方面，虽然随机序列是由种子决定的， 但是随机序列足够均匀，这才能保证 ch 函数映射结果的均匀性。

ch 函数没有造成全量重新映射， 而是 1/(n+1) 份重新映射，这个函数已经达到了一致性哈希算法的定义标准。 可以说，跳跃一致性哈希做到了最小化重新映射(minimum disruption)， 做到了完全的一致性。

算法优化

很显然, 这个算法是O(n)的, 而且随着j越来越大, b=j需要执行的概率也越来越低. Google最终的算法叫跳跃一致性哈希, Jump指的是j是跳跃的, 那他们是怎么让j跳跃, 并保持结果正确呢?

上面的 ch 函数中， b 是用来记录 k 最后一次跳入的槽位标号。 假如我们现在处在 k 刚刚跳入最后一个槽位的时刻， 此时一定有 (b+1) 个槽位。 接下来的时刻， 我们要再新增一个槽位变为 b+2 个时， 易知 k 不换槽位的概率是 (b+1)/(b+2)。 假设我们要找的下一个 b 是 j， 就是说，假设当槽位数目到了 j+1 个时 k 跳入最新槽位， 那么， 在此期间， k 保持连续不换槽位的概率是(注意计算的终止项)：

化简得， k 连续不跳槽直到增加到 j+1 个槽位才跳的概率为 (b+1)/j。

下面图8.3 中， 虚线框内表示连续不变槽位， 其概率就是各次不变槽位的概率之积。

设 r=random.next() 要满足 r<(b+1)/j ， 就必须 j>(b+1)/r。 所以 j 至少移动到 (b+1)/r， 进一步改写 ch 函数如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int ch(int key, int num_buckets) {
    random.seed(key);
    int b = -1; // bucket number before the previous jump
    int j = 0; // bucket number before the current jump
    while (j < num_buckets) {
        b = j;
        r = random.next();
        j = floor((b + 1) / r);
    }
    return = b;
}

现在来分析下它的时间复杂度。 因为 r 的分布是均匀的， 在槽位数将变化为 i 的时候跳跃发生的概率是 1/i， 那么预期的跳跃次数就是 1/2+..+1/i+..+1/n , 调和级数和自然对数的差是收敛到一个小数的， 所以复杂度是 O(ln(n))。

跳跃一致性哈希算法的复杂度是比二分查找的复杂度 O(log(n)) 要快一些的，因为有一个常数。应该是这样的:

因为 log2e 是一个大于1的数， 所以， O(ln(n)) 虽然在复杂度上和 O(log(n)) 一样，都是对数级别复杂度， 但是，二分查找的复杂度是二分的，底是2， 跳跃一致性哈希的底是 e 跳的要更快。

线性同余

还是没有达到最终 Google 的函数呀？ 因为 Google 的 JumpConsistentHash 函数没有用语言自己的random , 而是自己做了一个64位的线性同余随机数生成器。

我们再看

1
2

key = key*2862933555777941757 + 1
j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))

和

1
2

r = random.next();
j = floor((b + 1) / r);

有什么关系。

第一个key=key*x+1算是一个伪随机生成器。而j=(b+1)*x/y则是上面的求上界的公式，其中y/x通过浮点数运算来产生(0,1)内的一个随机数。

(key>>33)+1是取key值的高31位的值再加1(因为key为64位,右移33位后剩余31位)，范围为(1,2^31+1),int64(1)<<31的值为2^31。

[(key>>33)+1]/int64(1)<<31的取值范围是(0,1],如果(key>>33)=2^31那么会大于1，由于是c的整数运算，大于1也会取证忽略掉小数部分。

自此，这个代码就可以看懂了。

算法分析

优点

跳跃一致性哈希算法的设计非常精妙， 我认为最美的部分是利用了伪随机数的一致性和分布均匀性。

根据试验数据来看，跳跃一致性哈希在执行速度、内存消耗、映射均匀性上都比经典的哈希环法要好。

下图是跳跃一致性哈希算法和哈希环法关于运行时间的对比， 可以看到红色的线（jump hash）是明显耗时更低的。

下图是跳跃一致性哈希算法和哈希环法关于映射分布的均匀性的对比， 其中 Standard Error是指分布的标准差， 标准差越小则分布越均匀。 可以看到跳跃一致性哈希的分布要比哈希环的方式均匀的多。 这一点也可以理解， 跳跃一致性哈希的算法设计就是源于对均匀性的推理。

关于内存消耗上的对比结果， 其实已然不言自明。 经典的一致性哈希环需要数据结构的支撑， 空间复杂度是 O(N) 的， 而跳跃一致性哈希算法几乎没有额外内存消耗。

缺点

无法自定义槽位标号

跳跃一致性哈希算法中， 因为我们没有存储任何数据结构， 所以我们无法自定义槽位标号， 标号是从0开始数过来的。

只能在尾部增删节点

下面图9.3， 假如我们在非尾部添加一个新的槽位， 会导致这个位置后续的槽位的标号全部发生变化。 所以在非尾部插入新槽位没有意义， 我们只能在尾部插入。

对于在非尾部删除一个槽位也是一样的, 我们只能在尾部删除。

如果导致后面的槽位全部重新标号，更提不上一致性映射。

带权重的跳跃一致性哈希

我们同样可以尝试虚拟节点(影子节点)的办法来做权重。

下面图11.1中， V(Ni) 表示 Ni 的影子节点， 可以看到 N0, N1, N2 的权重比是 3:2:1。 当我们把比重变成 3:3:1 时，和一致性哈希环一样， 可能会引起数据的重新映射，带来数据迁移工作。

热扩容和容灾

回到kvdb的例子上来， 我们讨论下如下问题：

  • 扩容： 新加一个节点， 如何做到不停服？
  • 容灾： 损失一个节点，如何做到影响最小？

先看第一个问题： 如何做热扩容。

新加一个全新的节点时， 必然要迁移数据才可以服务。 可以采用和一致性哈希环法类似的办法， 即请求中继： 新加入的节点对于读取不到的数据，可以把请求中继(relay)到老节点，并把这个数据迁移过来。

「老节点」是什么？ 假如此次扩容时，节点数目由 n 变为 n+1， 老节点的标号则可以由 ch(k,n) 计算得出， 即节点数量为 n 的时候的 k 的槽位标号。

下图10.1是一个示例， 当新加一个节点 Nn 时， k 被映射到新的槽位。 老节点标号是 Nold=ch(k,n)。 当一个查询 get(k) 到来， 因为 k 此时映射到的是新节点 Nn ， 所以可能会查不到数据， 接下来把请求中继到老节点 Nold ， 即可以查到结果。 同时 Nn 把 k 对齐到自己这里。

通过这种方式，可以做到整个系统不停服扩容。 关键在于如何找到老节点。

再看第二个问题： 如何做容灾。先看下，当我们移除一个节点时，会造成什么影响？

假如移除最后一个节点， 如下图10.2中， 尾部节点 N4 被移除后， 整体映射情况和节点数为 n 的时候是一致的。 一切看上去还好。 只要考虑如何备份 N4 上的数据就可以了。 参考上面如何扩容的玩法，可以把尾部节点的数据备份到老节点 (例如，图10.2中 k2 的老节点就是 N3)。

但是，移除一个非尾部节点的情况就不一样了。 下面的图10.3中，移除 N1 时，映射的整体结果会发生较大变化， 造成了大面积的映射右偏现象。 原因在于， 虽然跳跃一致性哈希映射到的点标号和节点数是 n 的情况是一致的， 但是，映射到的节点本身已经变化了。 在这种情况下，因为大量数据的重新映射， 跳跃一致性希已经不符合一致性哈希的定义标准， 带来的数据迁移的工作量也是巨大的。

现实中，节点故障是肯定有可能发生在非尾部节点的。一旦这种情况发生， 除了故障数据丢失的问题之外，还面临大积的映射偏移的问题。

至此，或许可以想到如何备份来容灾了，在执行数据写操作时，同时写一份数据到备份节点。 备份节点这样选定：

  • 尾部节点备份一份数据到老节点。
  • 非尾部节点备份一份数据到右侧邻居节点。

我们看下在这个容灾策略下的效果：

  • 当删除尾部节点时：

    • 下图10.4中， 删除了 N4 后， k2 被重新映射到 N3， 因为 N4 的数据在 N3 有备份， 因此正常。

  • 当删除非尾部节点时：

    • 下图10.5中， 删除了 N1 后， 由于 k， k1， k3 都在邻居节点上有备份， 所以此时映射右偏后并不会造成三个数据丢失， 而且查询也是正确的。

至此，跳跃一致性哈希下的热扩容和容灾的思路就讨论到这里。 虽然跳跃一致性哈希表现这么简单，思考起来比经典的哈希环法要复杂一些。

算法测试

我们可以写段代码测试它，看看它的分布是否均匀，在新增加一个节点的时候，是否只移动了一部分的数据：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

package main
import "fmt"
func main() {
	buckets := make(map[int]int, 10)
	count := 10
	for i := uint64(0); i < 120000; i++ {
		b := JumpHash(i, count)
		buckets[b] = buckets[b] + 1
	}
	fmt.Printf("buckets: %v\n", buckets)
	//add two buckets
	count = 12
	for i := uint64(0); i < 120000; i++ {
		oldBucket := JumpHash(i, count-2)
		newBucket := JumpHash(i, count)
		//如果对象需要移动到新的bucket中,则首先从原来的bucket删除，再移动
		if oldBucket != newBucket {
			buckets[oldBucket] = buckets[oldBucket] - 1
			buckets[newBucket] = buckets[newBucket] + 1
		}
	}
	fmt.Printf("buckets after add two servers: %v\n", buckets)
}

因为跳跃一致性哈希算法不使用节点挂掉，如果你真的有这种需求，比如你要做一个缓存系统，你可以考虑使用ketama算法，或者对跳跃一致性哈希算法改造一下：节点挂掉时我们不移除节点，只是标记这个节点不可用。当选择节点时，如果选择的节点不可用，则再一次Hash，尝试选择另外一个节点，比如下面的算法将key加1再进行选择。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func JumpHash(key uint64, buckets int, checkAlive func(int) bool) int {
	var b, j int64 = -1, 0
	if buckets <= 0 {
		buckets = 1
	}
	for j < int64(buckets) {
		b = j
		key = key*2862933555777941757 + 1
		j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
	}
	if checkAlive != nil && !checkAlive(int(b)) {
		return JumpHash(key+1, buckets, checkAlive) //最好设置深度，避免key+1一直返回当掉的服务器
	}
	return int(b)
}

上面的算法有一点问题，就是没有设定重试的测试，如果所有的节点都挂掉，则会进入死循环，所以最好设置一下重试次数(递归次数)，超过n次还没有选择到则返回失败。

小结

优点：

  • 无需存储虚拟节点
  • 性能强
  • 结果分布的均匀性与key分布无关，由伪随机数生成器的均匀性保证
  • 复杂度为log(n)

缺点:

  • 由于算法特性，后台节点id需要是有序的int，或者管理好节点id
  • 对于中间和多个节点剔除的情况，数据仍会落到原节点，需要额外处理（主备、doublehash或管理好节点id）

悬浮一致性哈希算法(Maglev哈希算法)

Maglev哈希算法来自 Google ， 在其2016年发布的一篇论文中[1]， 介绍了自2008年起服役的网络负载均衡器Maglev， 文中包括Maglev负载均衡器中所使用的一致性哈希算法，即Maglev一致性哈希 (Maglev Consistent Hashing)。

我们要设计一个一致性哈希算法，要求映射均匀，并尽力把槽位变化时的映射变化降到最小（避免全局重新映射）。

Maglev一致性哈希的思路是查表： 建立一个槽位的查找表(lookup table)， 对输入 k 做哈希再取余，即可映射到表中一个槽位。 下面的图1.1是一个示意图， 其中 entry 是查找表，里面记录了一个槽位序列， 查找表的长度为 M， 当输入一个 k 时，映射到目标槽位的过程就是 entry[hash(k)%M]。

如何查表很好理解。 接下来看，如何生成一张查找表。 先新建一张大小为 M 的待填充的空表 entry。 为每个槽位生成一个大小为 M 的序列 permutation， 叫做「偏好序列」吧。 然后， 按照偏好序列中数字的顺序，每个槽位轮流填充查找表。 将偏好序列中的数字当做查找表中的目标位置，把槽位标号填充到目标位置。 如果填充的目标位置已经被占用，则顺延该序列的下一个填。 这么简短地讲不大容易明白， 看一个例子就可以清楚了。 下面图1.2是演示填充查找表的原图：

我做了一张更容易理解的图来理解填表过程。 下面的图1.3中，左边的每一个纵列代表槽位的偏好序列， 右边是我们要填充的查找表。 我们看下整个的填充过程：

  1. B0 的偏好序列的第一个数字是 3， 所以填充 B0 到 entry[3]。
  2. 轮到 B1 填充了， B1 的偏好序列第一个是 0， 所以填充 B1 到 entry[0]。
  3. 轮到 B2 填充了，由于 entry[3]被占用， 所以向下看 B2 偏好序列的下一个数字，是 4， 因此填充 B2 到 entry[4]。
  4. 接下来， 又轮到 B0 填充了， 该看它的偏好序列的第2个数字了，是 0，但是 entry[0] 被占用了； 所以要继续看偏好序列的第3个数字，是 4， 同理， 这个也不能用，直到测试到 1 可以用， 则填充 B0 到 entry[1]。
  5. 如上面的玩法， 直到把整张查找表填充满。

还有一个问题没有解决：偏好序列是怎么生成的？取两个无关的哈希函数 $h_1$ 和 $h_2$， 假设一个槽位的名字是 $b$，先用这两个哈希函数算出一个 $offset$ 和 $skip$

$$ offset = h_1(b) % M \ skip = h_2(b) % (M - 1) + 1 $$

然后， 对每个 $j$，计算出 $permutation$ 中的所有数字，即为槽位 $b$ 生成了一个偏好序列：

$$ permutation\left[j\right] = (offset + j \times skip) % M $$

可以看到，这是一种类似二次哈希的方法，使用了两个独立无关的哈希函数来减少映射结果的碰撞次数，提高随机性。生成偏好序列的方法可以有很多种（比如直接采用一个随机序列等），不必须是 Google 的这个方法，

但是无论何种方式，目的都是一样的， 生成的偏好序列要随机、要均匀。

此外，查找表的长度 $M$ 必须是一个质数,和哈希表的槽位数量最好是质数是一个道理，这样可以减少哈希值的聚集和碰撞，让分布更均匀。

以上就是Maglev一致性哈希的算法的内容， 简单来说：

  1. 为每个槽位生成一个偏好序列， 尽量均匀随机。
  2. 建表：每个槽位轮流用自己的偏好序列填充查找表。
  3. 查表：哈希后取余数的方法做映射。

边缘情况

不过这个算法还存在一个边缘情况：假如所有的偏好序列都不包含某个数字呢？

下面的图1.4中，所有偏好序列都不包含 $2$，导致最终的查找表的 $entry\left[2\right]$ 是空的。

这种情况出现的概率非常低，但是并不是没有可能。论文中未对这种情况做出说明，不过还是可以想到解决办法的（当然，方法不止一种）：如果填充后的查找表有位置没有被填充，可以统计下哪个槽位的占比最小，把那个槽位填到这里。

上面的图1.4中，不巧的是三个槽位都占了2个位置，那么直接随意给标号最小的 $B_0$ 好啦。

槽位增删分析

我们接下来看下这个算法是否满足一致性哈希算法的定义标准:映射均匀和一致性。由于偏好序列中的数字分布是均匀的，查找表是所有偏好序列轮流填充的，容易知道，查找表也是分布均匀的,这样，映射也是均匀的。所以，下面着重分析下槽位增删对映射的干扰， 即分析槽位增删对查找表的填充的影响。

假如，槽位增删导致查找表的某个位置填充的槽位标号发生变化，我们称这是一种干扰.槽位增删必然导致填充干扰，我们的目的是追求这个干扰的最小化。

下面的图2.1中演示了删除槽位 $B_1$ 前后的填表情况。红色圆圈内标出了受干扰的填表结果， 可以看到，查找表7个位置中有3个被重新填充。其中两个位置(第 $0$，$2$行)是因为 $B_1$ 的移除导致被其他槽位接管，还有一个第 $6$ 行的 $B_0 \rightarrow B_2$ 的联动干扰（因为 $B_0$ 接管了 $B_1$ 的 $entry\left[2\right]$ 导致原本自己的 $entry\left[6\right]$ 被 $B_2$ 抢占）。

下面的图2.2中演示了新增槽位 $B_3$ 前后的填表情况。同样，红色圆圈内标记了受干扰的填表结果， 可以看到，7个位置中有3个被重新填充。其中两个位置(第 $1$，$5$行)是因为 $B_3$ 的加入抢占了其他槽位的填充机会，另一个第 $6$ 行的 $B_0 \rightarrow B_2$ 则是一种联动干扰。

在上面图2.2的基础上，我们继续删除一个槽位 $B_0$， 看下前后的变化。 从下面的图2.3可以看出，这一次的填表干扰更严重了， 7个里面出现了4个被重新填充其中两个（第 $3$，$4$ 行）是因为 $B_0$ 的移除导致位置被其他槽位接管，还有两个（第 $1$，$6$ 行， $B_3 \rightarrow B_1$ 和 $B_2 \rightarrow B_3$）都是属于联动干扰。

查找表的重填意味着查表时的重新映射。从上面的三个例子可以看出，Maglev一致性哈希虽然没有导致全量重新映射，但却没有做到最小化重新映射.不过，在 Google 的实际测试中总结出来，当查找表的长度越大时，Maglev哈希的一致性会越好.

复杂度分析

显然，查表的时间复杂度是 $O(1)$ 。

下面分析下建表的复杂度。

论文中给出了填表过程的伪代码实现。其中，$N$ 是槽位的总数目，$permutation[i]$ 是槽位 $i$ 的偏好序列。$next[i]$ 用来记录槽位 $i$ 的偏好序列将迭代的下一个位置（即这个序列该跑第几个了）。对于每一个槽位 $i$ , 我们从它的偏好序列中找出一个候选的、还没占用的位置数字 $c$ ,然后把槽位标号 $i$ 填入查找表 $entry$ 中。

先看下，最坏的时间复杂度是怎样的？那肯定是，在查找下一个合适的填充位置的时候，把所有已经被抢占的位置数字放在这个目标位置的前面，这样的尝试次数最多！ 这种情况发生在 $N = M$ 且 所有偏好序列完全一样的情况下。 下面的图3.2中描述了这种复杂度最高的情况， 有3个槽位、查找表的长度为3、而且所有偏好序列都一样，总共需要尝试 $4+3+2+1$ 个数字（也就是 ${((4+1)\times 4)} / {2}$），所以最坏复杂度是 $O(((M+1)\times M)/2)$， 即平方级别的 $O(M^2)$。

现在考虑下平均的时间复杂度，我们就要分析这个过程总共需要尝试多少个数字。一步一步来想：

  • 第一次填表的时候，由于查找表 $entry$ 还是空的，所以第一个数字一定合适， 只需要尝试 $1$ 次。
  • 第二次填表的时候，由于前面已经填了一个槽位到 $entry$ 中， 所以空余的空位还有 $M-1$ 个，所以每个空位被选中的概率是 $1/(M-1)$。 每次查找一个可以填充位置的过程，都是在一个偏好序列中尝试，而序列的长度是 $M$ ， 所以需要尝试 $M/(M-1)$ 次。
  • 依次类推， 当我们已经填充了查找表 $entry$ 的 $n$ 个位置的时候，我们下一步就需要尝试 $M/(M-n)$ 次来找到下一个可以填充的空位置。

计算下来，总共需要尝试的次数是： $M/M + M/(M-1) + … + M / (M - (M-1))$， 即 $\sum { n=1 }^{ M }{ \frac { M }{ n } }$，是 $1$ 到 $1/M$ 的倒数之和 与 $M$ 的乘积。调和级数和自然对数的差是收敛到一个小数的.所以，平均的时间复杂度是对数级别的 $O(Mln(M))$， 也就是 $O(Mlog(M))$ (注意到 $O(ln(n)) = O(\frac { log{2}{n} } { log_{2}{e} })$)。

一般选择 $M \gg N$ ($M$ 远大于 $N$) ，这样各个槽位的偏好序列更随机、均匀，也不容易发生不同槽位的偏好序列一样的情况。当然，也不是越大越好， 越大的 $M$ 意味着更高的内存消耗、更慢的建表时长。应该选择一个远大于 $N$ 的质数当做查找表的大小 $M$。

论文中提到，在 Google 的实践过程中，一般选择 $M$ 为一个大于 $100 \times N$ 的质数，这样各个槽位在查找表上的分布的差异就不会超过 $1%$。

测试表现

论文中对Maglev一致性哈希的测试关注在两个指标：映射的平均性和对槽位变化的适应能力。

下面图4.1对比了 Maglev哈希、 经典的哈希环算法和endezvous哈希环算法在不同槽位数量的情况下（对应的查找表大小分别是 $65537$ 和 $655373$ ），映射结果中占比最大和最小的槽位的占比。从图中可以看到，两种槽位数量的情况下，Maglev的映射结果中占比最大和占比最小的占比量都非常接近，也就是说，Maglev一致性哈希的映射平均性非常好。

关于槽位增删对映射一致性的干扰影响，由于哈希环算法实现了最小的重新映射所以当删除槽位时（比如节点故障时）哈希环算法可以保证剩余的槽位的映射不受影响。而我们前面有分析，对于Maglev算法来讲, 则并没有做到最小的重新映射。下面的图4.2中是 Google 对Maglev负载均衡器做的测试结果，演示了在相同数量的后端节点、但是不同大小的查找表的情况下(分别是 $65537$ 和 $655373$)，映射结果发生变化的节点的占比相对于节点故障占比的关系。可以看到，查找表越大，Maglev哈希对槽位增删的容忍能力更强，映射干扰也越小。

不过，即使这样，实际中 Google 仍然选择 $65537$ 作为查找表大小。论文中给出的说法是， 当他们把查找表大小从 $65537$ 调大到 $655373$ 时，查找表的生成时间从 $1.8ms$ 升高到了 $22.9ms$， 所以查找表的大小不是越大越好。

论文中同时提到：在 Google 的场景下， 并没有把后端槽位的变化带来的干扰看的太重要。实际上，工程中节点损失是低概率事件， 并且 Google 的设计中主要的保护手段是连接跟踪，而不是完全依赖一致性哈希。这样，也可以理解了，这个一致性哈希算法的设计上就没有做到最小化干扰的要求。

热扩容和容灾

对于Maglev哈希来讲，热扩容或许还可以做，容灾却无法依赖备份的方式进行。

回到kvdb的例子上来， 看一下我们的诉求：

  • 扩容： 新加一个节点， 如何做到不停服？
  • 容灾： 损失一个节点，如何做到影响最小？

先看第一个问题： 如何做热扩容。

新加一个全新的节点时， 必然要迁移数据才可以服务。还是采用类似的办法，即请求中继：

新加入的节点对于读取不到的数据，可以把请求中继(relay)到老节点，并把这个数据迁移过来。

老节点是什么呢？ 就是加入新节点之前，数据应该映射到的那个节点。举例子来说，观察前面的图2.2中，假设数据 $k$ 先前映射到的节点是 $B_0$， 后来因为新加入了节点 $B_3$，导致 $k$ 现在映射到 $B_3$， 那么 $B_0$ 就叫做 $k$ 的老节点。

要知道数据的老节点是什么，就要保存一份加入新节点之前的查找表。也就是节点要保存两份查找表。如果经最新的查找表映射到的节点上没有数据，再去经老查找表映射到老节点上去查。

然而第二个问题： 如何做容灾， 则没那么容易。

回顾下前面章节中的图2.2和图2.3。

图2.3演示了删除一个节点的情况，为了演示方便，这里直接把图2.3照搬下来：

图2.2中演示了新增节点前后的填表情况，如果我们从右往左看，它也可以演示删除节点的情况，就是下面图5.1的样子：

可以观察到两个图中都是从完全一样的状况、完全一样的表格，分别删除不同节点的情况。图2.3中，删除 $B_0$ 后，导致了一个 $B_3 \rightarrow B_1$ 的映射变化。所以， 我们需要把 $B_3$ 的数据备份到 $B_1$ 上，才可以应对这一变化，而不丢数据、不停服。图5.1中，删除 $B_3$ 后则导致了 $B_3 \rightarrow B_0$ 和 $B_3 \rightarrow B_2$的映射变化，意思是， 在损失节点 $B_3$ 之后，$B_3$ 中的数据一部分会映射到 $B_0$ 上， 一部分又会映射到 $B_2$ 上，我们除非把 $B_3$ 的数据全部备份一份到 $B_0$, $B_1$, $B_2$ 上，否则没有很好的办法做 $B_3$ 的数据备份。

这样，关于容灾这个话题，

我的结论是没有很好的办法做数据备份，所以无法做不停服的容灾处理。 (需要注意：这部分并不是论文中的内容，而是我个人的分析结论。)

论文中所讨论的Maglev哈希算法的应用场景是负载均衡，确切的说是弱状态化的后端的负载均衡。如果后端节点的数据是类似数据库性质的强状态化数据，那么就会有容灾设计的问题。如果后端节点是无状态的、或者是弱状态的（如缓存），Maglev哈希算法的一致性的特点还是有好处的：比如降低故障情况下的缓存击穿的比例、连接重新建立的比例等等。

带权重

Maglev哈希做到了尽量平均的映射分布，但是，如果槽位之间不是平权的呢？关于带权重的Maglev哈希，论文中只提了一句话：可以通过改变槽位间填表的相对频率来做加权。

就是不「轮流」填了，可以你填1次，我填3次。 填表越频繁的槽位，权重就越大。

最后我们再玩一次填表游戏。下面的图6.1中，假设 $B_0$ 的权重是 $2$， 其他的槽位的权重都是 $1$，也就是其他槽位每填表一次， $B_0$ 填表两次。可以观察到，填表的结果上， $B_0$ 的席位占比 $4/7$， 符合权重的设定。

小结

Maglev哈希是 Google 在自家的负载均衡器Maglev中使用的一致性哈希算法。槽位变化时，虽然避免了全局重新映射，但是没有做到最小化的重新映射,适合后端节点数万级的场景。映射的均匀性非常好。映射的时间复杂度是 $O(1)$， 建立查找表的时间复杂度是 $O(Mlog(M))$。可以通过改变填表的相对频率来实现加权。难以实现后端节点的数据备份逻辑，因此工程上更适合弱状态后端的场景。

参考

https://zhuanlan.zhihu.com/p/34985026

https://mp.weixin.qq.com/s/yyqEwfEgEWYwWoalFLcuSw

https://colobu.com/2016/03/22/jump-consistent-hash/

https://www.owenzhang.net/blog/tag/jump-consistent-hash

https://yikun.github.io/2016/06/09/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3%E4%B8%8E%E5%AE%9E%E8%B7%B5/

https://www.lanindex.com/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%EF%BC%88consistent-hash%EF%BC%89%E7%9A%84%E9%BB%91%E7%A7%91%E6%8A%80/

https://writings.sh/post/consistent-hashing-algorithms-part-1-the-problem-and-the-concept

https://writings.sh/post/consistent-hashing-algorithms-part-4-maglev-consistent-hash

负载均衡策略之有限负载一致性哈希

谷歌推出有界负载的一致性哈希算法，解决服务器负载均衡问题

具有有界负载的一致哈希