自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

什么是好的一致性 Hash 實(shí)現(xiàn)

作者：董澤潤
開發(fā) 開發(fā)工具
看到微信群有人問 prd 用什么一致性 hash 算法好，就想起了這篇文章。這是以前做的測試。那么什么是好的一致性 hash 算法呢?除了性能還要考慮哪些因素呢?根據(jù)我自己的經(jīng)驗(yàn)簡單聊一下，有不正確的請大家指正。

[[400551]]

本文轉(zhuǎn)載自微信公眾號「董澤潤的技術(shù)筆記」，作者董澤潤 。轉(zhuǎn)載本文請聯(lián)系董澤潤的技術(shù)筆記公眾號。

看到微信群有人問 prd 用什么一致性 hash 算法好，就想起了這篇文章。這是以前做的測試。

那么什么是好的一致性 hash 算法呢?除了性能還要考慮哪些因素呢?根據(jù)我自己的經(jīng)驗(yàn)簡單聊一下，有不正確的請大家指正 ^^

背景

關(guān)于什么是 Consistent Hashing 網(wǎng)上很多，一般用于對于數(shù)據(jù)狀態(tài)有一定要求的緩存場景，比如 web session 數(shù)據(jù)

節(jié)點(diǎn)根據(jù)算法，映射到環(huán)中。用戶請求時(shí)，根據(jù) id 求出 hash 值，按順(逆)時(shí)針找到的第一個(gè)節(jié)點(diǎn)，就是存儲數(shù)據(jù)節(jié)點(diǎn)。一般為了更加均勻些，同時(shí)防止一個(gè)節(jié)點(diǎn)下線，導(dǎo)致過多數(shù)據(jù)移動，會將節(jié)點(diǎn)按 replica (weight) 復(fù)制多個(gè)虛擬節(jié)點(diǎn)映射到環(huán)中。

數(shù)據(jù)不均勻問題

了解 LB 的都知道，lvs 這些負(fù)載均衡設(shè)備能做到請求均勻，但經(jīng)典實(shí)現(xiàn)的一致性 hash 是做不到的。具體場景，可能差別更大。測試腳本放到了 consistenthash balance test github[1]，感興趣的可以看下，測試場景如下：

  1. 節(jié)點(diǎn)數(shù)量：10 
  2. 虛擬系數(shù)：3, 10, 50, 100, 200, 400, 600, 800, 1000 
  3. 測試算法：MurMurHash, Crc32, Fnv1, CityHash 
  4. 請求數(shù)量：50w 

方差可以很好的衡量數(shù)據(jù)分布程度，可以看到，Crc32 是最差的，F(xiàn)nv1 在數(shù)量很少時(shí)也差，MurMurHash 和 CityHash 在虛擬節(jié)點(diǎn)超過 100 個(gè)后迅速收斂。

diff ratio 指數(shù)據(jù)分布最多的與最小的差值，除以平均值。從數(shù)據(jù)分布可以看到， MurMurHash, CityHash 首選的 hash 算法。replica 虛節(jié)點(diǎn)數(shù)量可以調(diào)大一些，畢竟動態(tài)增減節(jié)點(diǎn)不是常態(tài)

另一種方案

冒泡哥提到了一種實(shí)現(xiàn)，提前預(yù)計(jì)算好節(jié)點(diǎn)順序，可以減少分布 diff ratio. 他在生產(chǎn)環(huán)境，只用 20 replica 就降低到了 5% 當(dāng)然了前提是，增加減節(jié)點(diǎn)，必須符合一致性 hash 的思想，數(shù)據(jù)盡可能少的移動。

測試數(shù)據(jù)

  1. MurMur replica:3 var:43930 max:72370 min:35411 diff:36959 ratio:73.918000 
  2. MurMur replica:10 var:69441 max:85238 min:19257 diff:65981 ratio:131.962000 
  3. MurMur replica:50 var:20520 max:59708 min:40669 diff:19039 ratio:38.078000 
  4. MurMur replica:100 var:12556 max:57515 min:42045 diff:15470 ratio:30.940000 
  5. MurMur replica:200 var:11539 max:55858 min:41998 diff:13860 ratio:27.720000 
  6. MurMur replica:400 var:7161 max:53385 min:45323 diff:8062 ratio:16.124000 
  7. MurMur replica:600 var:5586 max:51697 min:45913 diff:5784 ratio:11.568000 
  8. MurMur replica:800 var:4101 max:52118 min:48041 diff:4077 ratio:8.154000 
  9. MurMur replica:1000 var:4369 max:52888 min:48356 diff:4532 ratio:9.064000 
  10. Crc32 replica:3 var:76353 max:97097 min:23872 diff:73225 ratio:146.450000 
  11. Crc32 replica:10 var:30219 max:61334 min:31891 diff:29443 ratio:58.886000 
  12. Crc32 replica:50 var:12231 max:55475 min:43926 diff:11549 ratio:23.098000 
  13. Crc32 replica:100 var:22105 max:58828 min:37776 diff:21052 ratio:42.104000 
  14. Crc32 replica:200 var:28465 max:59481 min:35807 diff:23674 ratio:47.348000 
  15. Crc32 replica:400 var:25440 max:58781 min:37059 diff:21722 ratio:43.444000 
  16. Crc32 replica:600 var:33926 max:61694 min:35887 diff:25807 ratio:51.614000 
  17. Crc32 replica:800 var:33978 max:61327 min:36914 diff:24413 ratio:48.826000 
  18. Crc32 replica:1000 var:27789 max:60515 min:37709 diff:22806 ratio:45.612000 
  19. Fnv1 replica:3 var:348461 max:377986 min:5997 diff:371989 ratio:743.978000 
  20. Fnv1 replica:10 var:200673 max:231641 min:14451 diff:217190 ratio:434.380000 
  21. Fnv1 replica:50 var:41072 max:84924 min:38135 diff:46789 ratio:93.578000 
  22. Fnv1 replica:100 var:11567 max:59547 min:47254 diff:12293 ratio:24.586000 
  23. Fnv1 replica:200 var:6465 max:53451 min:46127 diff:7324 ratio:14.648000 
  24. Fnv1 replica:400 var:5126 max:52454 min:47757 diff:4697 ratio:9.394000 
  25. Fnv1 replica:600 var:3748 max:52520 min:48394 diff:4126 ratio:8.252000 
  26. Fnv1 replica:800 var:6089 max:52003 min:46211 diff:5792 ratio:11.584000 
  27. Fnv1 replica:1000 var:5881 max:53028 min:46902 diff:6126 ratio:12.252000 
  28. Cityhash replica:3 var:77979 max:99378 min:11576 diff:87802 ratio:175.604000 
  29. Cityhash replica:10 var:60194 max:84045 min:25002 diff:59043 ratio:118.086000 
  30. Cityhash replica:50 var:26496 max:67141 min:38121 diff:29020 ratio:58.040000 
  31. Cityhash replica:100 var:11862 max:56008 min:44075 diff:11933 ratio:23.866000 
  32. Cityhash replica:200 var:9921 max:54711 min:44592 diff:10119 ratio:20.238000 
  33. Cityhash replica:400 var:5542 max:53629 min:47391 diff:6238 ratio:12.476000 
  34. Cityhash replica:600 var:6823 max:53417 min:46261 diff:7156 ratio:14.312000 
  35. Cityhash replica:800 var:5100 max:51615 min:46577 diff:5038 ratio:10.076000 
  36. Cityhash replica:1000 var:4884 max:52151 min:47166 diff:4985 ratio:9.970000 

小結(jié)

這次分享就這些，以后面還會分享更多的內(nèi)容，如果感興趣，可以關(guān)注并點(diǎn)擊左下角的分享轉(zhuǎn)發(fā)哦(:

參考資料

[1]

測試腳本: https://github.com/dongzerun/consistenthash_balance_test,

責(zé)任編輯：武曉燕 來源： 董澤潤的技術(shù)筆記
Hash算法測試
相關(guān)推薦

2022-11-10 07:49:09

hash算法代碼

2022-03-22 09:54:22

Hash算法

2020-07-20 08:30:37

算法哈希分布式系統(tǒng)

2021-07-27 08:57:10

算法一致性哈希哈希算法

2016-02-15 10:46:40

JavaHash算法

2018-08-08 15:51:44

Hash分布式算法

2017-07-25 14:38:56

數(shù)據(jù)庫一致性非鎖定讀一致性鎖定讀

2020-11-24 09:03:41

一致性MySQLMVCC

2019-11-01 09:13:37

算法哈希緩存

2021-12-26 00:48:05

一致性視圖數(shù)據(jù)庫

2022-12-14 08:23:30

2020-04-01 15:50:17

TiDBMySQL數(shù)據(jù)庫

2016-12-19 18:41:09

哈希算法Java數(shù)據(jù)

2021-02-05 08:00:48

哈希算法?機(jī)器

2021-02-02 12:40:50

哈希算法數(shù)據(jù)

2021-02-04 06:30:26

Python編程語言

2021-07-26 06:33:42

CRDT數(shù)據(jù)CAP

2021-06-22 10:22:08

業(yè)務(wù)IT一致性首席信息官

2020-05-12 10:43:22

Redis緩存數(shù)據(jù)庫

2024-05-28 00:50:00

RedisMySQL緩存
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號