存在一个问题，假设当前有一组键和值，还有一些用于键值存储的服务器。这些服务器可能是 memcached、Redis、MySQL 等等。我们想将这些键分布到服务器上，然后不需要存储一个全局目录就可以再次找到它们，那么这要如何实现。

一种解决方案叫做模-N 哈希。

首先，选择一个哈希函数将一个键（字符串）映射到一个整数。哈希函数需要很快速，所以这往往排除掉像 SHA-1 或 MD5 这样的加密哈希函数。虽然它们分布良好，但计算成本太高。像 MurmurHash 这样的哈希函数就比较好，还有一些稍微更好的选择，比如非加密哈希函数 xxHash、MetroHash 或 SipHash1-3 都是不错的替代品。

如果有 N 台服务器，我们可以使用哈希函数对键进行哈希，然后将得到的整数对 N 取模。

 server := serverList[hash(key) % N]

这种设置有许多优点。首先，它非常容易解释。计算成本也很低。虽然取模运算可能开销比较大，但几乎肯定比哈希键好。如果N是二的幂，那么可以只屏蔽掉低位。（这是分片一组锁或其他内存数据结构的一个好方法。）

这种方法有哪些缺点呢？首先，如果我们改变服务器的数量，几乎每个键都会映射到不同的位置。这是很糟糕的。

让我们考虑一下“最佳”函数在这里应该做什么。

在添加或删除服务器时，只有1/n的键应该移动。 不移动任何不需要移动的键。 为了进一步说明第一个要点，如果我们从9台服务器增加到10台，那么新服务器应该填充所有键的1/10。这些键应从9台“旧”服务器中均匀选择。并且键只应移动到新服务器，而不是在两台旧服务器之间移动。同样，如果我们需要移除一台服务器（例如因为它崩溃了），那么这些键应该均匀分布在剩下的可用服务器上。

环哈希

幸运的是，有一篇论文解决了这个问题。1997年发布的论文“Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”描述了Akamai在其分布式内容传递网络中使用的方法。

直到2007年，这些想法才逐渐被大众所熟知。那一年有两篇重要的作品发表：

• last.fm’s Ketama memcached client.
• Dynamo: Amazon’s Highly Available Key-value Store

这些作品确立了一致性哈希作为标准扩展技术的地位。现在Cassandra、Riak和几乎所有需要在服务器间分配负载的分布式系统都使用这种算法。

这种算法是流行的基于环的一致性哈希。你可能见过一个“圆圈上的点”的图。当你搜索“一致性哈希”的图片时，这就是你会看到的：

我们可以将圆视为所有整数 0 ..232-1。基本思想是，每个服务器都通过哈希函数映射到圆上的一个点。要查找给定键的服务器，我们需要对键进行哈希处理，然后找到圆上的该点。然后向前扫描，直到找到任何服务器的第一个哈希值。

实际上，每个服务器都会在圆上出现多次。这些额外的点称为“虚拟节点”或“vnode”。这减少了服务器之间的负载差异。如果 vnode 数量较少，则不同的服务器可能会分配到截然不同的键数量。

（关于术语的简要说明。最初一致性哈希论文将服务器称为“节点”。论文通常会讨论“节点”、“服务器”或“分片”。本文将交替使用这三个词。）

环形哈希的另一个优点是算法简单易懂。下面是取自groupcache 的简单实现（为清晰起见略作修改）：

要将列表添加nodes到环哈希中，每个列表都会m.replicas使用略有不同的名称进行哈希处理（0 node1、1 node1、2 node1、...）。将哈希值添加到m.nodes切片中，并将从哈希值返回到节点的映射存储在 中m.hashMap。最后m.nodes对切片进行排序，以便我们可以在查找期间使用二分搜索。

func (m *Map) Add(nodes ...string) {
    for _, n := range nodes {
        for i := 0; i < m.replicas; i++ {
            hash := int(m.hash([]byte(strconv.Itoa(i) + " " + n)))
            m.nodes = append(m.nodes, hash)
            m.hashMap[hash] = n
        }
    }
    sort.Ints(m.nodes)
}

要查看给定值key存储在哪个节点上，需要将其哈希化为整数。nodes搜索已排序的切片，以查找大于键哈希的最小节点哈希值（如果我们需要绕回圆的起点，则为特殊情况）。然后在映射中查找该节点哈希，以确定它来自哪个节点。

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))
    idx := sort.Search(len(m.keys),
        func(i int) bool { return m.keys[i] >= hash }
    )
    if idx == len(m.keys) {
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}

问题

环哈希算法为我们最初的问题提供了一个解决方案，但是仍然存在一些问题。

首先，节点之间的负载分布仍然可能不均匀。每台服务器有 100 个副本（“vnode”），负载的标准偏差约为 10%。存储桶大小的 99% 置信区间是平均负载（即总键/服务器数量）的 0.76 到 1.28。这种变化使容量规划变得棘手。将副本数量增加到每台服务器 1000 个点会将标准偏差降低到约 3.2%，99% 置信区间会小得多，为 0.92 到 1.09。

这会带来巨大的内存成本。对于 1000 个节点，这是 4MB 的数据，搜索次数为 O(log n)（n=1e6），所有搜索都是处理器缓存未命中，即使没有其他内容争夺缓存。

跳跃哈希

2014 年，谷歌发布了一篇论文《A Fast, Minimal Memory, Consistent Hash Algorithm》，被称为“Jump Hash”。该算法实际上包含在2011 年发布的 Guava 库中，表明它是从 C++ 代码库移植而来的。

Jump Hash 解决了环形哈希的两个缺点：它没有内存开销，并且密钥分布几乎完美。（桶的标准差为 0.000000764%，99% 置信区间为 0.99999998 至 1.00000002）。

Jump Hash 也很快。循环执行 O(ln n) 次，比 Ring Hash 的 O(log n) 二分查找快一个常数，而且由于计算完全在几个寄存器中完成，并且不产生缓存未命中的开销，因此速度更快。

这是从github.com/dgryski/go-jump摘录的代码，由论文中的 C++ 翻译而来。该算法的工作原理是使用密钥的哈希值作为随机数生成器的种子。然后，它使用随机数在存储桶列表中“向前跳跃”，直到它落到末尾。它落入的最后一个存储桶就是结果。论文对其工作原理进行了更完整的解释，并推导了这个优化循环。

func Hash(key uint64, numBuckets int) int32 {
  var b int64 = -1
  var j int64
  for j < int64(numBuckets) {
    b = j
    key = key*2862933555777941757 + 1
    j = int64(float64(b+1) *
      (float64(int64(1)<<31) / float64((key>>33)+1)))
  }
  return int32(b)
}

Jump Hash 看起来很棒。它速度快，并且能均匀地分担负载。有什么问题呢？主要的限制是它只返回范围内的整数0..numBuckets-1。它不支持任意的存储桶名称。（使用环形哈希，即使两个不同的实例以不同的顺序接收它们的服务器列表，生成的键映射仍然相同。）理解 Jump Hash 的更好方法是提供分片号，而不是服务器名称。其次，我们只能正确地添加和删除范围上限的节点。这意味着它不支持任意节点删除。我们不能使用它在一组 memcached 实例之间分发键，其中一个实例可能会崩溃——无法从可能的目的地列表中删除崩溃的节点。

这些因素结合起来使 Jump Hash 更适合数据存储应用，在这些应用中，我们可以使用复制来缓解节点故障。使用节点权重时，它也可能会比较棘手。

问题

环形哈希允许任意添加和删除存储桶，但代价是内存占用较高，从而减少负载差异。跳跃哈希可以有效实现完美的负载分割，但代价是更改分片计数时的灵活性降低。

有没有一种方法可以灵活地调整环大小并降低方差而又不增加内存开销？

多探测一致性哈希

Google 的另一篇论文“Multi-Probe Consistent Hashing”（2015 年）试图解决这一问题。MPCH 提供 O(n) 空间（每个节点一个条目），以及 O(1) 节点添加和删除。问题是什么？查找速度变慢了。

基本思想是，不再对节点进行多次哈希处理并增加内存使用量，而是只对节点进行一次哈希处理，但在查找时对键进行k次哈希处理，并返回所有查询中最接近的节点。 k的值由所需的方差决定。对于峰值与均值比为 1.05（意味着负载最重的节点最多比平均值高 5%），k为 21。使用一个巧妙的数据结构，我们可以将总查找成本从 O(k log n) 降低到 O(k)。

作为比较，要使 Ring Hash 的峰值与均值比达到 1.05，700 ln n每个节点都需要副本。对于 100 个节点，这相当于超过 1 兆字节的内存。

汇合哈希

解决一致性哈希问题的另一个早期尝试称为汇合哈希或“最高随机权重哈希”。它也于 1997 年首次发布。

其思想是将节点和密钥一起进行哈希处理，并使用提供最高哈希值的节点。缺点是很难避免遍历所有节点的 O(n) 查找成本。

这是取自github.com/dgryski/go-rendezvous的实现。也可以通过对节点进行预哈希处理并使用 xorshift 随机数生成器作为廉价的整数哈希函数来优化多重哈希处理。

func (r *Rendezvous) Lookup(k string) string {
	khash := r.hash(k)

	var midx int
	var mhash = xorshiftMult64(khash ^ r.nhash[0])

	for i, nhash := range r.nhash[1:] {
		if h := xorshiftMult64(khash ^ nhash); h > mhash {
			midx = i + 1
			mhash = h
		}
	}

	return r.nstr[midx]
}

尽管汇合散列是 O(n) 查找，但内循环开销并不大。根据节点数量，计算比较快。请参阅最后的基准测试。

磁悬浮（Maglev）哈希

2016 年，谷歌发布了Maglev：一款快速可靠的软件网络负载均衡器。论文中有一节描述了一种新的一致性哈希算法，也就是后来的“磁悬浮哈希”。

与环形哈希或汇合哈希相比，主要目标之一是查找速度快和内存使用率低。该算法有效地生成一个查找表，允许在恒定时间内找到节点。两个缺点是，在节点故障时生成新表的速度很慢（本文假设后端故障很少发生），这也有效地限制了后端节点的最大数量。磁悬浮哈希还旨在在添加和删除节点时“最小化中断”，而不是最佳。对于 Maglev 作为软件负载平衡器的用例，这已经足够了。

该表实际上是节点的随机排列。查找会散列键并检查该位置的条目。这是 O(1)，带有一个小常数（恰好是散列键的时间）。

副本

副本使用一致性哈希来为给定的键选择次要（或更多）节点。这可以用于防止节点故障，也可以仅作为查询的第二个节点以减少尾部延迟。一些策略使用全节点副本（即每个服务器有两个完整副本），而其他策略则跨服务器复制键。

我们始终可以用可预测的方式改变键或键哈希，并进行完整的第二次查找，但需要小心，避免副本键也落在同一节点上。

一些算法有直接的方法来选择多个节点进行回退或复制。对于环哈希，我们可以使用在环上传递的下一个节点；对于多探测，我们可以使用下一个最近的节点。汇合哈希时，我们将选择下一个最高（或最低）节点。跳跃哈希有点棘手，但可以做到。

和这篇文章中的其他内容一样，选择副本策略需要权衡利弊。Vladimir Smirnov在 Booking.com 上谈论Graphite Metrics Storage时谈到了副本策略中的一些不同权衡。

加权主机

一致性哈希算法在添加具有不同权重的服务器的难易程度和有效性方面有所不同。也就是说，向一台服务器发送比其余服务器更多（或更少）的负载。使用环形哈希，我们可以根据所需的负载缩放副本数量。这会大大增加内存使用量。跳跃哈希和多探测一致性哈希的使用和维护其现有的性能保证更加棘手。虽然我们始终可以添加第二个引用原始节点的“影子”节点，但当负载倍数不是整数时，这种方法会失败。一种方法是将所有节点数缩放一定量，但这会增加内存和查找时间。

磁悬浮散列通过改变表构建过程来处理权重，以便权重更大的节点更频繁地选择查找表中的条目。

加权汇合哈希是一种单行修复方法，用于向汇合添加权重：选择按比例缩放的最高组合哈希-weight / math.Log(h)。

负载均衡

使用一致性哈希实现负载平衡似乎是一个很有吸引力的想法。但根据算法的不同，最终可能并不比随机分配更好，从而导致分布不均衡。

幸运的是（同样来自谷歌），除了 Maglev 之外，我们还有两种用于负载平衡的一致性哈希方法。

第一篇是 2016 年的《有界负载的一致性哈希》。由于键分布在各个服务器上，因此会检查负载，如果某个节点的负载过重，则会跳过该节点。Vimeo上有一篇详细的文章详细介绍了它是如何添加到 HAProxy 的。它也可以作为独立包使用。

对于需要选择连接哪组后端的客户端，Google 的SRE Book概述了一种称为“确定性子集”的算法。

负载平衡是一个很大的话题，可以单独写一本书。有关两个概述，请参阅

• Load Balancing Is Impossible by Tyler McMullen
• Predictive Load-Balancing: Unfair But Faster & More Robust by Steve Gury

基准测试

基准测试只是一个权衡点，在做选择时，不能忽略每个一致性哈希函数的所有注意事项和权衡。

结论

如你所见，没有完美的一致性哈希算法。它们都有权衡。还有很多其他算法我没有在这里介绍。但就像上面一样，它们都在努力平衡分布、内存使用、查找时间和构造时间（包括节点添加和删除成本）。