關(guān)于一致性哈希算法在游戲服務(wù)器端的思考

1. 需求分析

   • 后端有很多邏輯node節(jié)點(diǎn)（not-section binded），節(jié)點(diǎn)啟動(dòng)后注冊(cè)到注冊(cè)中心
     • node本身有狀態(tài)，有內(nèi)存cache，有過(guò)期時(shí)間
   • 客戶端登陸，需要從注冊(cè)中心分配一個(gè)node
     • a. 客戶端需要在一段時(shí)間內(nèi)連接固定節(jié)點(diǎn)（長(zhǎng)連接）。因?yàn)閮?nèi)存有狀態(tài)，最好支持客戶端斷線一段時(shí)間再次連接還是之前的節(jié)點(diǎn)
     • b. 節(jié)點(diǎn)最好是相對(duì)負(fù)載均勻的
     • 考慮新增/減少節(jié)點(diǎn)（宕機(jī)），最好保證a/b兩點(diǎn)

2. 引入一致性hash算法

   • 算法主要參考：dubbo ConsistentHashSelector 并做部分修改

   • 算法測(cè)試

     • a. 初始運(yùn)營(yíng)服5個(gè)，每個(gè)服10w注冊(cè)，即50w注冊(cè)。后端一個(gè)node承載1w，后端初始50個(gè)node

       算法步驟

       1. 初始化50w個(gè)rid，rid格式 serverId_id，shuffle
       2. build hash ring，replicaNumber（虛擬節(jié)點(diǎn)） = 160
       3. 依次遍歷shuffle后的rid list，從hash ring select
       4. 看node整體分布情況（最大、最小、平均、標(biāo)準(zhǔn)差）
       5. 不斷調(diào)整虛擬節(jié)點(diǎn)數(shù)目

       統(tǒng)計(jì)結(jié)果展示

       [7743, 8777, 8847, 8932, 8985, 9100, 9185, 9229, 9274, 9308, 9330, 9478, 9625, 9638, 9660, 9697, 9699, 9728, 9748, 9791, 9794, 9847, 9904, 10021, 10053, 10055, 10063, 10073, 10257, 10258, 10263, 10291, 10356, 10374, 10376, 10486, 10519, 10521, 10581, 10620, 10628, 10678, 10719, 10783, 10790, 10837, 10859, 11001, 11120, 12099]
       replica:160 |max:12099|min:7743|mean:10000.0|std:750.9|median:10054.0

       [9142, 9393, 9518, 9525, 9549, 9578, 9626, 9659, 9667, 9690, 9765, 9777, 9811, 9831, 9848, 9850, 9886, 9889, 9909, 9933, 9940, 9958, 9998, 10002, 10007, 10029, 10030, 10050, 10052, 10129, 10152, 10158, 10182, 10184, 10202, 10212, 10213, 10215, 10247, 10265, 10273, 10279, 10297, 10321, 10322, 10342, 10358, 10420, 10456, 10861]

       replica:1280 |max:10861|min:9142|mean:10000.0|std:317.2|median:10018.0

       結(jié)論

       1. 在節(jié)點(diǎn)不動(dòng)態(tài)變化的情況，算法可以保證同一個(gè)rid每次都select到同一個(gè)node
       2. 通過(guò)調(diào)整replicaNumber，可以讓node負(fù)載相對(duì)均勻
       3. 因?yàn)閞id樣本是可確定的，所以可以這種方式不斷調(diào)整hash ring的參數(shù)，來(lái)符合實(shí)際的負(fù)載情況，即是可預(yù)測(cè)的
          • 如果一個(gè)node負(fù)載是1w，那么目前會(huì)有node overloaded。實(shí)際可以考慮將node負(fù)載調(diào)整為9k

     • b. 從a的結(jié)果上看，看似很美好，比較好的滿足我們的需求，but 我們還要考慮新增/減少節(jié)點(diǎn)的情況

       假設(shè)

       1. 讓我們問(wèn)問(wèn)題先簡(jiǎn)化一下 因?yàn)槲覀儽旧硎情L(zhǎng)連接，所以假設(shè)之前的50w個(gè)rid全部連接到已知的50個(gè)node

       2. 需求：準(zhǔn)備開始開第6個(gè)服，在新增10個(gè)node，用來(lái)承載10w人，并重建hash ring

       測(cè)試輸出

       // 這個(gè)是已經(jīng)連接的50個(gè)node的數(shù)據(jù)分布情況，和a的結(jié)果一致，也驗(yàn)證了本身一致性hash算法的正確性

       [9142, 9393, 9518, 9525, 9549, 9578, 9626, 9659, 9667, 9690, 9765, 9777, 9811, 9831, 9848, 9850, 9886, 9889, 9909, 9933, 9940, 9958, 9998, 10002, 10007, 10029, 10030, 10050, 10052, 10129, 10152, 10158, 10182, 10184, 10202, 10212, 10213, 10215, 10247, 10265, 10273, 10279, 10297, 10321, 10322, 10342, 10358, 10420, 10456, 10861]

       replica:1280 |max:10861|min:9142|mean:10000.0|std:317.2|median:10018.0

       // 這個(gè)是新增10個(gè)node后的數(shù)據(jù)分布情況

       [1499, 1534, 1569, 1652, 1673, 1675, 1684, 1712, 1713, 1723, 10585, 10948, 11119, 11162, 11173, 11177, 11223, 11267, 11270, 11324, 11348, 11404, 11504, 11511, 11530, 11546, 11547, 11569, 11570, 11610, 11631, 11635, 11674, 11681, 11684, 11706, 11742, 11750, 11758, 11769, 11796, 11815, 11842, 11855, 11878, 11908, 11912, 11921, 11933, 11952, 11991, 11996, 12019, 12068, 12068, 12077, 12089, 12157, 12215, 12657]

       replica:1280 |max:12657|min:1499|mean:10000.0|std:3783.8|median:11620.5

       結(jié)論

       1. 我們?cè)诩僭O(shè)條件成立的情況下，我們期望新增的10w客戶端全部負(fù)載到新的10個(gè)node上。但是從結(jié)果上看，其實(shí)是負(fù)載了整個(gè)的60個(gè)node上（這個(gè)其實(shí)也是相對(duì)均勻的）。這個(gè)和我們預(yù)期完全不相符
       2. 從一致性hash的算法實(shí)現(xiàn)上看，對(duì)于新增/減少節(jié)點(diǎn)來(lái)說(shuō)，一定是會(huì)有一部分客戶端重新分配節(jié)點(diǎn)，這個(gè)是由算法本身決定的

3. 繼續(xù)沿著一致性hash的思路走

   • 主要問(wèn)題
     • a. 如何解決新增/減少節(jié)點(diǎn)，部分客戶端select節(jié)點(diǎn)變化的問(wèn)題？
     • b. 如何解決新增節(jié)點(diǎn)，整體的負(fù)載均勻問(wèn)題（甚至分配過(guò)程中的相對(duì)均勻，即不會(huì)出現(xiàn)分配過(guò)程中某一個(gè)node先達(dá)到上限，而是整體均衡）？
   • 一些擴(kuò)展思路
     • 對(duì)于a
       • 可以在客戶端select到一個(gè)節(jié)點(diǎn)后，將客戶端和節(jié)點(diǎn)的映射關(guān)系保存下來(lái)?？蛻舳藬嗑€再連接還是同一個(gè)節(jié)點(diǎn)。當(dāng)內(nèi)存數(shù)據(jù)過(guò)期后，下次再連接，可以再次重新映射
       • 可以在每次客戶端斷線時(shí)，強(qiáng)制刷新一下對(duì)應(yīng)的node內(nèi)存數(shù)據(jù)到外部緩存。這樣當(dāng)客戶端再次連接時(shí)，如果切到了其他的node也沒(méi)有關(guān)系，只不過(guò)額外走一次加載流程。不過(guò)如果是頻繁斷線重連的情況下則需要額外注意
     • 對(duì)于b
       • 可以引入有限負(fù)載一致性哈希，即node有負(fù)載的概念。首選還是按照正常的一致性hash算法選擇某一個(gè)node。不過(guò)區(qū)別是會(huì)判斷此node是否overloaded，如果overloaded，則繼續(xù)從hash ring尋找下一個(gè)node，直到未超過(guò)負(fù)載。引入該算法后，對(duì)于2b中的測(cè)試來(lái)說(shuō)，新的10w人會(huì)被主要分流到新增的10個(gè)node上
         • 我目前實(shí)現(xiàn)的一個(gè)版本是可以設(shè)置一個(gè)node的負(fù)載上限比如9000
         • 不過(guò)引入負(fù)載后，就需要額外維護(hù)負(fù)載這個(gè)指標(biāo)。比如客戶端內(nèi)存數(shù)據(jù)過(guò)期后，將客戶端所屬的node的負(fù)載-1
   • 思考
     • 如果我們按照一致性hash的思路實(shí)現(xiàn)需求，是可以做的，只不過(guò)有不少額外成本。那這樣的必要性大嗎？
     • 一致性hash最早的例子是用在如memcache，根據(jù)key hash到對(duì)應(yīng)的node。而這個(gè)應(yīng)用場(chǎng)合是緩存，即使key沒(méi)有命中的話（增/減），那么對(duì)于應(yīng)用層來(lái)是可以重新從數(shù)據(jù)庫(kù)加載的。所以其實(shí)應(yīng)用場(chǎng)合并一定特別適合
     • 對(duì)于我們的需求，我們手動(dòng)實(shí)現(xiàn)一個(gè)基于負(fù)載的類似輪詢算法，是不是更簡(jiǎn)單？

4. 再換一個(gè)思路 假如我們把連接和數(shù)據(jù)分開呢？

   • 假如我們讓客戶端不是直接連接后端的node，而是一個(gè)網(wǎng)關(guān)呢？
   • 網(wǎng)關(guān)負(fù)責(zé)連接，node負(fù)責(zé)數(shù)據(jù)
   • 我們有一組網(wǎng)關(guān)，網(wǎng)關(guān)的數(shù)量是固定的（當(dāng)然也可以在維護(hù)時(shí)間調(diào)整），先通過(guò)客戶端rid做hash運(yùn)算到對(duì)應(yīng)的網(wǎng)關(guān)（為保證均勻，可以考慮一致性hash）
   • 然后再通過(guò)網(wǎng)關(guān)和后端node的映射關(guān)系得出客戶端該路由到那個(gè)node上。這樣node節(jié)點(diǎn)動(dòng)態(tài)變化時(shí)，只需要修改路由表中網(wǎng)關(guān)和動(dòng)態(tài)node之前的關(guān)系即可
   • TODO
     • Consistent Hashing + Distributed Hash Table （Orleans）

5. ref

   • Improve consistent hashing load balancing with a new algorithm(patch for 3.0)
   • 螞蟻金服服務(wù)注冊(cè)中心如何實(shí)現(xiàn) DataServer 平滑擴(kuò)縮容
   • Dubbo 一致性Hash負(fù)載均衡實(shí)現(xiàn)剖析
   • Making The Case For Building Scalable Stateful Services In The Modern Era
   • {技術(shù)}某分布式應(yīng)用實(shí)踐一致性哈希的一些問(wèn)題