一致性哈希证明

Lobsters Hottest 论文

摘要

本文推导出一致性哈希系统中误差分布的数学公式,有助于跨服务器的工作负载优化。这是一个技术推导,包括WebAssembly演示,并引用了Cloudflare的一篇博客文章。

<p><a href="https://lobste.rs/s/eplmed/consistent_hashing_proofs">评论</a></p>
查看原文
查看缓存全文

缓存时间: 2026/09/19 16:03

# 一致性哈希证明 来源:https://ch.terabyteoff.com/ *以及比你想知道的更多相关内容* 开源项目 (https://github.com/johnhurt/consistent-hash-math) 这是对描述使用一致性哈希分配工作负载系统中任务分布公式的推导。它部分是技术论文,部分是演示,部分是博客文章,因此包含大量数学公式、一些 WebAssembly,但也有一些笑话。我的期望是,无论读者背景如何,这篇文章都能做到完整、引人入胜且平易近要(并且有趣?)。 这是对我为 Cloudflare 撰写的这篇博客文章 (https://blog.cloudflare.com/saving-100-tb-of-ram-with-math) 的补充,所以如果你想了解完整故事以及我们如何利用这里的数学原理安全地回收边缘超过 100TB 的 RAM,请查看它。它还包含关于一致性哈希基本原理的入门介绍。 ## 动机 (https://ch.terabyteoff.com/#motivation) 我撰写本文的主要原因是为了帮助将来对此主题感兴趣的任何人。当我最初开始研究一致性哈希及其准确性如何随哈希次数变化的主题时,我对谷歌搜索出的资源感到沮丧。这些结果要么是详细(但对我来说完全晦涩难懂)的关于该主题的技术论文,要么是来自在线计算机科学课程资源的可理解但不完整的推导。这两种情况的结果都给出了一个关于一致性哈希任务分配均匀性误差的渐近、“大O”形式的上界 $O\left( \sqrt{\frac{1}{k} } \right)$,其中 $k$ 是每台服务器的哈希次数。不清楚实际误差与该极限有多接近,因此我决定自己推导实际公式并找出答案。我发现,要解析地解决这个问题,只需要一些高中数学和一点创造力。 ## 要点概括 (https://ch.terabyteoff.com/#tldr) 如果你是来寻求快速答案的,我不会让你久等。对于拥有 $N$ 台服务器、每台有 $k$ 个哈希的一致性哈希,误差公式为: $\text{Err}_k = \sqrt{\frac{N-1}{kN+1} }$ 当 $N$ 很大时,这*确实*非常接近 $\sqrt{\frac{1}{k} }$。在服务器数量为 50 台或更多的系统中,实际误差值与该近似值之间的差异约为 1%。这是一个有用的近似,但如果不了解其背后的推导过程,就不可能看清它的其他含义。例如,如果每台服务器拥有*不同*数量的哈希,情况会如何变化?我们将回答这个问题以及更多问题,所以现在让我们来证明它! 计算机科学就是数学 ## 第一部分 - 单个哈希 (https://ch.terabyteoff.com/#part-1---single-hashes) 为了得到上面的方程,我们需要从一个更简单的起点开始。在实践中使用一致性哈希时,我们处理的是整数(通常是 32 位或 64 位)。这使得计算更简单、更快捷,同时也让我们能够访问性能良好的哈希函数,但为了我们的目的,将哈希视为 0 到 1 之间的实数,而不是一个有界范围的整数会更容易。不幸的是,这确实意味着我上面已经陈述的结果*也*是一个近似值(因此我已经向你撒了谎 (https://x.com/ThePrimeagen/status/1861040630832742795)),但正如你将看到的,只要你的哈希数量和服务器数量不是*太*大,这就是一个很好的近似。 ### 初步尝试 (https://ch.terabyteoff.com/#baby-steps) 让我们循序渐进,从一些小规模开始。假设我们有一台服务器,它拥有一个哈希,属于一个至少还有一台服务器的一致性哈希设置。我们如何确定我们的服务器将处理的工作负载分布?一个简单的几何思考方式。回顾上文,我们将整数哈希空间重新映射到 0 和 1 之间的实数;在这种表示中,我们的服务器处理的工作份额等于分配给它的区间的长度(假设任务的哈希具有均匀分布)。下面是一个交互式演示,展示了与我们的服务器相关联的区域大小相对于平均大小的变化情况。误差百分比显示了我们服务器的区域与预期大小的偏差程度。 $\frac{L - 1/H}{1/H}$ 其中 $H$ 是总哈希次数。重新运行几次后,你可以看到与我们服务器相关联的区域大小变化*非常剧烈*,而且这种变化似乎并不依赖于总哈希次数。我们稍后将看到为什么是这样。 ### 循环展开 (https://ch.terabyteoff.com/#loop-unrolling) 我之前忽略的一个重要点是,第一个和最后一个哈希之间的区域是连接的,使得哈希域实际上是一个✨圆形✨。这就是为什么大多数关于一致性哈希的文章都包含像下面这样的图形,显示分配给每个服务器的不同颜色的角度范围。 一致性哈希环的圆形表示 像这样查看各个范围强化了我们已经使用过的一个事实。服务器哈希的绝对位置并不重要。只有它们之间的相对位置会影响分布。换句话说,哈希输出中没有“特殊”点,因此我们可以将“零点”设置在任何地方。为了简单起见,将零点设置为等于*我们的*服务器关联的哈希具有一个很好的特性,即我们不再需要考虑哈希环的圆形方面。这种哈希空间的重新定向意味着与我们服务器相关联的线段长度仅由所有其他哈希的最小值决定。 $L = min\left\{ h_2, h_3, ..., h_H \right\}$ *这*是我们可以为其计算统计分布的东西。 ### 一点统计学 (https://ch.terabyteoff.com/#a-little-statistics) 统计学是我在大学里唯一得过 C 的课程(如果课程不在早上8点,也许我会去上课),所以我觉得我没有权利对任何人说教……但我还是要说。最终,我们希望能够获得与我们服务器相关联的线段长度的均值和标准差,而这些是根据该长度的概率密度函数 (PDF) (https://en.wikipedia.org/wiki/Probability_density_function) 定义的。为了得到 PDF,我们将首先推导其累积分布函数 (CDF) (https://en.wikipedia.org/wiki/Cumulative_distribution_function)。考虑数线上 0 到 1 之间的某个点 $x$。我们线段长度的 CDF 是长度 $\le x$ 的概率。这个概率等于长度*不*大于 $x$ 的概率,即 $P \left( L \le x \right) = 1 - P \left( L > x \right)$。这是成立的,因为 $P \left( L \le x \right)$ 和 $P \left( L > x \right)$ 是“互斥事件” (https://en.wikipedia.org/wiki/Complementary_event),这只是一个花哨的说法,表示其中必有一个为真,但绝不会同时为真。我们进行这种变换是因为 $P \left( L > x \right)$ 与所有哈希 $\left\{ h_2, h_3, ..., h_H \right\}$ 都 $\ge x$ 的概率相同。由于每个哈希都是独立的 (https://en.wikipedia.org/wiki/Independence_(probability_theory))(意味着一个哈希的值不影响任何其他哈希),我们可以说所有哈希都满足条件的概率是每个哈希独立满足条件的概率的乘积。 $\begin{align*} P \left(L \ge x\right) &= P\left( \left\{ h_2, h_3, ... h_H \right\} > x\right) \\ &= \underbrace{ P\left(h_2 > x\right) \times P\left(h_3 > x\right) \times ... \times P\left(h_H > x\right) }_{H-1\text{ Terms}}\\end{align*}$ 确定单个哈希 $> x$ 的概率很简单,就是 $1 - x$。我们可以通过积分均匀分布的 PDF (https://en.wikipedia.org/wiki/Probability_density_function) 来证明这一点,但那有点无聊(而且我们最终会这样做)。相反,这里是另一个通过模拟经验性计算该概率的交互式演示。既然我们知道 $P \left(h_i > x\right) = 1 - x$,并且知道这个概率对每个哈希都相同,我们就可以将所有内容整合起来得到我们线段长度 $L$ 的 CDF。 $\begin{align*} \text{CDF}\left(L\right) &= P \left(L \le x\right) \\ &= 1 - P \left(L > x\right) \\ &= 1 - P\left(h_2 > x\right) \times P\left(h_3 > x\right) \times ... \times P\left(h_H > x\right) \\ &= 1 - P\left(h > x\right)^{H-1} \\ &= \boxed{1 - \left(1 - x\right)^{H - 1}} \end{align*}$ ### 一点微积分 😅 (https://ch.terabyteoff.com/#a-little-calculus-) 从 CDF 得到 PDF 就是对 $x$ 求导 CDF 的过程。所以请坐稳,微积分开始了。这里我们只需要用到分配律 (https://en.wikipedia.org/wiki/Linearity_of_differentiation) 和幂法则 (https://en.wikipedia.org/wiki/Power_rule)。 $\begin{align*} \text{PDF} \left(L\right) &= \frac{d}{dx}\text{CDF} \left( x \right) \\ &= \frac{d}{dx}\left( 1 - \left(1 - x\right)^{H - 1} \right) \\ &= \frac{d}{dx}\left( 1 \right) - \frac{d}{dx}\left(1 - x\right)^{H - 1} \\ &= 0 - \left(-\left( H - 1 \right)\right)\left(1-x\right)^{H-2} \\ &= \boxed{\left(H - 1 \right)\left(1-x\right)^{H-2}} \end{align*}$ 绘制出来,它看起来像这样。 ### 现实与概率 (https://ch.terabyteoff.com/#reality-vs-probability) 在使用上面的 PDF 计算期望值和标准差之前,让我们暂停一下,将内容拉回到现实。你可能已经注意到,PDF 的值*超过*了 1。这应该是一个很好的线索,表明 PDF 并*不*提供一种查找特定值概率的方法……那么它有什么用呢?……以及如何找出特定值的概率?这两个问题的答案都是**直方图**。作为一个纯粹数学问题的答案,这可能有点不尽如人意。直方图是极其实用的工具,我们通常在测量或可视化现实世界中的事物(如延迟或分贝水平)时使用。它们在这里出现的原因是因为我们在最开始做的简化。我们上面的 CDF 和 PDF 基于 0 和 1 之间的连续范围,而不是哈希输出中实际出现的离散长度。这种简化意味着每个特定长度具有无限精度,因此其自身的概率是无穷小的。为了获得可观/有用的概率值,我们必须查看特定长度范围内的概率。绘制不同范围之间的概率本质上就是直方图的定义,而我们使用 PDF(或 CDF)来计算该范围内的概率。$P\left(x_{min} \le x \le x_{max}\right) = \int_{x_{min}}^{x_{max}} \text{PDF}(x) dx = \text{CDF}(x_{max}) - \text{CDF}(x_{min})$。这个特定长度的区间概率由直方图的条形高度表示。 ### 求和多个哈希 (https://ch.terabyteoff.com/#summing-multiple-hashes) 现在我们有了一个可以用来描述单个哈希线段长度概率分布的 PDF,我们可以研究分配给同一服务器的多个连续哈希线段的总长度。我们使用之前的技巧,将第一个哈希固定在 0,但现在我们想要计算 $k$ 个线段的总长度,直到第 $(k+1)$ 个哈希。这个总长度 $L_k$ 就是从 0 到第 $(k+1)$ 个最小哈希的距离。从技术上讲,$L_k$ 是 $k$ 个连续线段的和:$L_k = \sum_{i=1}^{k}{L_i}$。这个随机变量 $L_k$ 的 CDF 为: $\begin{align*} \text{CDF}_k(x) &= P\left(\sum_{i=1}^{k}{L_i} \le x\right) \\ &= 1 - P\left(\sum_{i=1}^{k}{L_i} > x\right) \end{align*}$ 这显然算不上一个大的进步,但请听我解释。回想一下,我们可以将第一个哈希 $h_1$ 固定在 0,因此我们可以将前 $k$ 个哈希线段之和的表达式简化为第 $k+1$ 个最小哈希的位置:$\sum_{i=1}^{k}{L_i} = h_{k+1}$ 总哈希数:20 求和哈希数(k):3 # (https://ch.terabyteoff.com/#kth-hash-demo) 我们可以用它来重写 $k$ 个线段之和的 CDF: $\text{CDF}_k(x) = 1 - P \left( h_{k+1} > x \right)$ 虽然这个洞见没有直接给我们一组独立的概率,但它确实允许我们将长度测量问题简化为一个计数问题。因为如果第 $k+1$ 个最小哈希 $> x$,那么意味着小于 $x$ 的哈希总数必须小于 $k+1$。由于我们已将 $h_1$ 固定在 0,我们可以进一步说未固定的哈希数量(对我们分布而言唯一重要的哈希)必须小于 $k$。让我们为“计算小于等于 $x$ 的哈希数量”这个概念引入一些新符号。对于 $H$ 个随机哈希的集合,我们用 $C(x)$ 表示小于等于 $x$ 的哈希数量。那么,$P\left( h_{k+1} > x \right)$ 就是 $C(x) \le k$ 的概率。

相似文章

快速哈希函数的对抗样本

Lobsters Hottest

本篇博客文章深入分析了针对快速哈希函数的对抗样本,比较了它们的速度和抗碰撞性,并详细说明了多个实现中的漏洞。

哈希函数中的碰撞

Hacker News Top

zkSecurity 的 Collisions Atlas 对 MD4、MD5、SHA-0 和 SHA-1 等哈希函数已公开的碰撞对进行了编目与独立验证,并借助一个离线 Python 工具区分完全攻破与安全性降低或部分攻破的情况。