Elixir 中的 Highest Random Weight

# Elixir 中的最高随机权重 来源：https://jola.dev/posts/highest-random-weight-in-elixir 一致性哈希是分布式 Elixir 的一个常见构建块，能够以较低的复杂度和较高的价值实现设计模式，比如分布式速率限制器或缓存。我之前写过相关文章。 将键分配给节点、确保集群中任何参与节点都能找出哪个节点拥有给定键的最常见方法，是 Discord 的 `ExHashRing`（https://github.com/discord/ex_hash_ring）。这是一个经过大量实战检验且非常可靠的库，性能特性极佳，我使用它的体验一直很好。 不过，它也有一个缺点：你需要启动并管理环进程。这倒不算大问题，你可以为它们指定全局名称，查找起来也很简单，但你仍然需要在监督树下设置它们，而且它们是有状态、持久存在的后台进程。这些状态需要管理。这完全不是什么大问题，但当我发现一个无状态的替代方案时，它立刻引起了我的注意。 ## 会合哈希（Rendezvous hashing） 根据 [Wikipedia 页面](https://en.wikipedia.org/wiki/Rendezvous_hashing) 的描述：*会合哈希比一致性哈希更简单、也更通用。* 它也被称为 HRW 或最高随机权重（Highest Random Weight）。在实践中，使用方式与 ExHashRing 非常相似。 `ExHashRing` 示例： ```elixir {:ok, ring} = ExHashRing.Ring.start_link() Ring.add_nodes(ring, ["a", "b", "c"]) Ring.find_node(ring, "key1") => "b" ``` HRW 示例： ```elixir HRW.owner("key1", ["a", "b", "c"]) => "b" ``` 就是这样。无需有状态进程，无需设置。纯函数式编程，只有输入和输出。在多台机器上保持一致。在更改节点列表时可以避免不必要的漂移。你明白为什么它吸引我了吧！ 当然，它也有缺点。`HRW.owner` 的大 O 表示法是线性的（O(n)），也就是说，当节点列表较大时性能不佳。在考虑使用它时，这绝对是需要考虑的因素。但老实说，回顾我使用 `ExHashRing` 的几次经历，我从未需要关注超过约 14 个节点。以下是在我的机器上针对 14 个节点两种算法的对比： ``` Name ips average deviation median 99th % ExHashRing.Ring.find_node 2.67 M 375.20 ns ±1375.85% 334 ns 500 ns HRW.owner 2.39 M 418.13 ns ±1317.18% 375 ns 541 ns Comparison: ExHashRing.Ring.find_node 2.67 M HRW.owner 2.39 M - 1.11x slower +42.93 ns ``` `ExHashRing` 非常快，而且随着节点数量的增加仍能保持高速。但在节点数量较少的情况下，即使在比较热的路径上，差异也不大。你可以自由选择哪一种阅读起来更好。 ## 基本 HRW 算法 我们更深入地了解一下会合哈希。基本实现实际上非常简单。你只需要对键和每个节点分别应用一个评分函数，然后返回最高值。这就是最高随机权重。评分函数可以用任何快速的哈希函数。在 BEAM 生态系统中，`:erlang.phash2` 是一个明显的候选。 实现如下： ```elixir defmodule HRW do def owner(key, nodes) do Enum.max_by(nodes, fn node -> :erlang.phash2({key, node}) end) end end ``` 相当巧妙！ ## 线性增长 为了展示性能如何随着 `nodes` 增加而受影响，这里是一个包含 10K 节点的基准测试。比 `ExHashRing` 慢 4200 倍。但换个角度看，在我的机器上仍然只需要约 2 毫秒。根据你的用例，这其实可能完全可以接受。纯函数的便利性很难被超越。 ``` ##### With input D: 10_000 ##### Name ips average deviation median 99th % ExHashRing.Ring.find_node 1.91 M 0.00052 ms ±1515.88% 0.00046 ms 0.00063 ms HRW.owner 0.00046 M 2.20 ms ±5.29% 2.17 ms 2.62 ms Comparison: ExHashRing.Ring.find_node 1.91 M HRW.owner 0.00046 M - 4204.94x slower +2.20 ms ``` 但让我们看看能不能做得更好。 ## HRW 骨架 我们基本的 HRW 实现虽然实际上相当快，但节点数量增加时表现不佳。这是因为每次查找都需要对每个节点进行哈希。同一个 Wikipedia 页面[描述](https://en.wikipedia.org/wiki/Rendezvous_hashing#O(log_n)_running_time_via_skeleton-based_hierarchical_rendezvous_hashing)了一种解决方法：将节点组织成一个高效的数据结构，使得 `owner` 的大 O 表示法降低到 O(log n)。 从非常（非常）高层次来看，我们要做的是对节点列表进行排序，然后将其分块成多个簇。每个簇有一个地址，现在我们不需要对每个节点进行哈希，而只需要计算簇的地址，然后对该簇内的节点进行哈希以找到正确的节点。这大大减少了工作量，带来了更友好的对数复杂度。 使用方式如下： ```elixir skeleton = HRW.build(nodes) HRW.owner(key, skeleton) ``` 与上面相同的基准测试，但骨架预先创建好（就像我们对 `ExHashRing` 所做的那样），结果如下： ``` ##### With input D: 10_000 ##### Name ips average deviation median 99th % ExHashRing.Ring.find_node 2.17 M 0.00046 ms ±1791.93% 0.00042 ms 0.00058 ms HRW.owner (skeleton) 0.71 M 0.00141 ms ±634.18% 0.00138 ms 0.00183 ms HRW.owner 0.00047 M 2.13 ms ±5.03% 2.10 ms 2.53 ms Comparison: ExHashRing.Ring.find_node 2.17 M HRW.owner (skeleton) 0.71 M - 3.06x slower +0.00095 ms HRW.owner 0.00047 M - 4615.43x slower +2.13 ms ``` 我们从每次查找 2 毫秒降到了 141 微秒，只比 `ExHashRing` 慢大约 3 倍，而且没有使用 NIF，也不需要启动有状态进程。不过我们确实需要传递一个结构体，而且添加和删除节点不再是稳定操作。添加一个节点会将排序列表中后面的所有节点移动一个位置。我猜生活中没有什么是免费的。尽管如此，对于许多用例来说，这是一个有趣的权衡。 ## 分布 你可能还想知道，对于一种将工作/键/负载分布到一组节点上的机制，它的分布效果如何。如果每个键都映射到同一个节点，那就没什么用了。下面是一个演示分布的小示例脚本： ```elixir defmodule Distribution do def run do keys = Enum.map(1..100_000, fn i -> "key-#{i}" end) for n <- [10, 100, 1000] do nodes = Enum.map(1..n, &"node#{&1}") ideal = div(length(keys), n) counts = keys |> Enum.map(&HRW.owner(&1, nodes)) |> Enum.frequencies() |> Map.values() min_c = Enum.min(counts) max_c = Enum.max(counts) avg = Enum.sum(counts) / length(counts) stddev = :math.sqrt(Enum.sum(Enum.map(counts, fn c -> (c - avg) ** 2 end)) / length(counts)) IO.puts("#{n} nodes, #{length(keys)} keys (ideal #{ideal} per node):") IO.puts(" min: #{min_c} max: #{max_c} stddev: #{Float.round(stddev, 1)} (#{Float.round(stddev/avg*100, 2)}% of mean)") end end end Distribution.run() ``` 我扩展了它，添加了使用 MurmurHash3 的 HRW、使用骨架的 HRW 以及 ExHashRing 进行对比。 ``` 10 nodes, 100000 keys (ideal 10000 per node): phash2 (HRW) min: 9691 max: 10639 stddev: 249.9 (2.5% of mean) murmur3 x86_32 (HRW) min: 9859 max: 10192 stddev: 112.2 (1.12% of mean) murmur3 x64_128 (HRW) min: 9864 max: 10170 stddev: 98.1 (0.98% of mean) HRW.Skeleton min: 9691 max: 10639 stddev: 249.9 (2.5% of mean) ExHashRing min: 9526 max: 10513 stddev: 338.5 (3.38% of mean) 100 nodes, 100000 keys (ideal 1000 per node): phash2 (HRW) min: 920 max: 1075 stddev: 29.7 (2.97% of mean) murmur3 x86_32 (HRW) min: 934 max: 1059 stddev: 27.0 (2.7% of mean) murmur3 x64_128 (HRW) min: 902 max: 1072 stddev: 29.2 (2.92% of mean) HRW.Skeleton min: 877 max: 1124 stddev: 46.6 (4.66% of mean) ExHashRing min: 105 max: 1229 stddev: 279.7 (27.97% of mean) 1000 nodes, 100000 keys (ideal 100 per node): phash2 (HRW) min: 69 max: 132 stddev: 9.9 (9.91% of mean) murmur3 x86_32 (HRW) min: 72 max: 132 stddev: 9.6 (9.65% of mean) murmur3 x64_128 (HRW) min: 67 max: 144 stddev: 9.8 (9.79% of mean) HRW.Skeleton min: 72 max: 141 stddev: 9.9 (9.85% of mean) ExHashRing min: 0 max: 147 stddev: 31.4 (31.42% of mean) ``` 如你所见，使用 `:erlang.phash2` 表现良好。Murmur3 在节点数量较少时可能略好一些，但这并不是重点。重点是 `ExHashRing` 在默认设置下节点数量较大时表现不佳。解决方案是增加更多 vnode，但这出乎我的意料！ ## 宣布 HRW 库 非常欢迎你试用 [hex.pm](http://hex.pm/) 上的 `hrw` 库，或者看看 [GitHub 仓库](https://github.com/joladev/hrw)。对于非常多的节点，你会想使用 `ExHashRing` 或 `HRW.Skeleton`；对于其他情况，为什么不坚持使用纯 `HRW.owner` 呢？ 该库还附带了本文未描述的其他策略，例如 `HRW.Weighted`，它允许你为特定节点分配更多的键空间，适用于某些机器更大的异构集群；以及 `HRW.Bounded`，当你知道键集时，它可以更精确地控制键的分布。 请告诉我你的使用感受。