如何優雅擴縮容，一致性哈希算法

- 背景 -

此外，在擴縮容前後，都需要負載均衡來維持各節點上的負載壓力，從而使得擴縮容變得更加 “優雅”。負載均衡技術中常用的算法模型就會涉及到一致性哈希算法。

服務集羣中每個節點都有個 “哈希地址” 作爲唯一標識，其計算公式簡寫如下：

add = hash(object) mod Nadd=hash(object)modN

當發生擴縮容導致增加或減少一個節點時，剩餘節點的地址映射都會發生改變

add = hash(object) mod (N±1)add=hash(object)mod(N±1)

進而導致所有節點的數據需要遷移，代價太大

一致性哈希將哈希值空間設計成 “環狀”，值域爲 [0,2^32-1]，定義域可以使用節點的 IP 或主機名來計算。

假設我們有 3 個節點和 4 個數據，其地址在哈希值空間的分佈如下：

按照一致性哈希算法，每個數據按順時針方向，綁定到距離它最近的節點，例如數據 A 綁定 01 節點，數據 D 綁定 02 節點，數據 B、C 綁定 03 節點。

假設 03 節點被縮減掉，數據 B 和 C 就需要綁定到 01 節點，其餘數據和節點不需要遷移。

假設增加一個節點 04，如下圖，按照一致性哈希算法，只需要將數據 B 重新遷移到節點 04 即可。

一致性哈希算法，因爲其特殊的數據結構和數據綁定算法，使得在節點增加和減少時，可發生的數據遷移量大大減少，數據遷移減少，帶來的應用價值就是減少動態擴縮容的時間。

目前市面上 “秒級” 的擴縮容產品非常少，大部分都在“分鐘級”，當擴縮容反應越靈敏，在業務運營大型活動時，發生服務宕機或者雪崩的概率就會大大降低！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/iVLtOuBvwFULAYA7FYFREQ