突破領導者的限制
問題
假設我們使用 Raft 算法實現了一個 KV 服務滔韵。雖然領導者簡化了共識協(xié)商，但是寫請求只能在領導者上處理（如果系統(tǒng)設計要求強一致性，那么讀請求也應該由領導者處理），所以集群的接入性能相當于單機伴榔。隨著業(yè)務的發(fā)展礁击，系統(tǒng)很容易到達性能瓶頸。
那么妖泄，怎么突破領導者的限制呢驹沿？方法就是數據分片，即每個集群只負責存儲一部分數據蹈胡。所有集群的數據合起來才是全部數據渊季。
為了方便，以下用節(jié)點來代替集群罚渐。
那怎么決定哪些數據由哪個節(jié)點存儲呢却汉？我們需要在客戶端和節(jié)點之間加一層 Proxy 層：Proxy 層接收客戶端的請求，通過對 key 哈希荷并，然后取模來決定由哪個節(jié)點來處理該請求合砂。
哈希算法
使用哈希算法，我們是這樣切分流量的：假設客戶端的請求中有一個 key源织，Proxy 層接收到請求后翩伪，根據下列公式，計算出處理該請求的節(jié)點：cluster_index = hash(key) % cluster_num谈息。
這種哈希算法優(yōu)點是簡單缘屹、快速。但是當節(jié)點的數量發(fā)生變更時侠仇，同一個 key 計算出的節(jié)點索引也會變化轻姿，導致無法定位到數據。這種情況下逻炊，我們就需要遷移數據互亮。遷移數據的成本非常高。例如余素，從 3 個節(jié)點變更為 4 個節(jié)點豹休，75% 的數據需要遷移，成本非常高桨吊。
一致性哈希算法
我們希望有一種哈希算法：在發(fā)生節(jié)點數量變更時慕爬，遷移盡量少的數據窑眯。一致性算法能滿足我們的要求。
算法原理
算法原理為：
將一個虛擬圓環(huán)分為 2^32 份医窿，按順時針方向磅甩，從 0 開始，直到 2^32 - 1姥卢。
使用某種哈希算法卷要，將各個節(jié)點映射到圓環(huán)上。
-
當需要對指定的 key 讀寫時独榴，需要
- 使用某種哈希算法僧叉，計算出 key 在圓環(huán)上的位置
- 沿著順時針方向找到的第一個節(jié)點，就是 key 對應的節(jié)點棺榔。
假設瓶堕，如果節(jié)點 C 故障了，那么只會影響故障節(jié)點與其前一個節(jié)點間的數據症歇，它們都會被路由到故障節(jié)點的下一個節(jié)點郎笆。
所以，相比哈希算法忘晤，如果使用一致性哈希算法宛蚓，從 3 個節(jié)點變更為 4 個節(jié)點，只有 25% 的數據需要遷移设塔，成本為原來的 1/3凄吏。
假設，如果新增一個節(jié)點 D闰蛔，那么只會影響新節(jié)點與其前一個節(jié)點間的數據痕钢，它們都會被路由到新節(jié)點。
[站外圖片上傳中...(image-58f87f-1590412658301)]
總的來說序六，一致哈希算法具有較好的容錯性和可擴展性任连。
虛擬節(jié)點
在哈希尋址中，經常會出現這樣的問題：客戶端請求的 key 比較集中难咕，有的機器負載高，有的機器負載低距辆，那有什么辦法使得訪問均勻分布嗎余佃？答案是虛擬節(jié)點。
其實跨算，每個節(jié)點有多個哈希值分布在虛擬圓環(huán)上爆土，并且同一個節(jié)點的多個哈希值是相鄰的，不會出現交叉的情況诸蚕。一個哈希值對應一個虛擬節(jié)點步势，并將虛擬節(jié)點映射到實際節(jié)點氧猬。
對比
當節(jié)點數量越多時，哈希算法的遷移數量越大坏瘩，一致性哈希算法的遷移數量越小盅抚。使用一致哈希實現哈希尋址時，可以通過增加節(jié)點數降低節(jié)點宕機對整個集群的影響倔矾，以及故障恢復時需要遷移的數據量妄均。
提高 Raft 集群的可用性
在多個 Raft 集群組成的 KV 系統(tǒng)中，如何設計一致哈希哪自，實現當某個集群的節(jié)點出現了故障時丰包，整個系統(tǒng)還能穩(wěn)定運行呢？
答：數據要同時寫入當前集群和下一個集群壤巷。某個Raft集群掛掉后邑彪，原本路由到這個集群的請求，現在都到下一個Raft集群去了胧华。只要下一個Raft集群保存了上一個集群的數據寄症，即使某個集群掛了，整個系統(tǒng)還能正常提供服務撑柔。只有兩個相鄰集群都同時掛掉時瘸爽，某個集群數據才不能訪問。
