一致性哈希算法是分布式系統(tǒng)中常用的算法进副。比如这揣，一個分布式的存儲系統(tǒng)，要將數(shù)據(jù)存儲到具體的節(jié)點上影斑，如果采用普通的hash方法给赞，將數(shù)據(jù)映射到具體的節(jié)點上，如key%N鸥昏，key是數(shù)據(jù)的key，N是機器節(jié)點數(shù)姐帚，如果有一個機器加入或退出這個集群吏垮，則所有的數(shù)據(jù)映射都無效了，這顯然不是一個最優(yōu)的算法。一致性哈希算法可以將這種影響降到最小膳汪。算法設計：
- 按照常用的hash算法來將對應的key哈希到一個具有232次方個桶的空間中唯蝶，即0~(232)-1的數(shù)字空間中。現(xiàn)在我們可以將這些數(shù)字頭尾相連遗嗽，想象成一個閉合的環(huán)形粘我。
閉合環(huán)形.png
- 利用hash函數(shù)將key算出hash值，對應到換上的某個位置痹换，然后順時針找到第一個機器節(jié)點征字，就是將數(shù)據(jù)存儲到這個節(jié)點上。
Paste_Image.png
- 如果B點宕機了娇豫，K1匙姜，K2數(shù)據(jù)會存儲到機器節(jié)點C上，影響了一臺節(jié)點C的數(shù)據(jù)冯痢，不會影響A,D氮昧，通過這種算法可以將增加刪除節(jié)點的影響降低到最小。
Paste_Image.png
- 但是這也有一個風險：比如說B點宕機了浦楣，原來存儲在B點的數(shù)據(jù)都會請求到C點袖肥，造成C節(jié)點負載變高，C節(jié)點也容易宕機振劳，這樣依次下去椎组，這樣造成整個集群都掛了，造成雪崩澎迎。
- 為了解決這個問題庐杨，我們引入了虛擬節(jié)點，即把想象在這個環(huán)上有很多“虛擬節(jié)點”夹供，數(shù)據(jù)的存儲是沿著環(huán)的順時針方向找一個虛擬節(jié)點灵份，每個虛擬節(jié)點都會關(guān)聯(lián)到一個真實節(jié)點，通過虛擬節(jié)點的引入哮洽，對象的分布就比較均衡了填渠，因此不會造成“雪崩”現(xiàn)象。
Paste_Image.png
首先利用數(shù)據(jù)的hash值定位到虛擬節(jié)點鸟辅，再找到物理節(jié)點進行存儲氛什。
參考文章：
