維基百科定義
一致哈希是一種特殊的哈希算法。在使用一致哈希算法后菜谣，哈希表槽位數(shù)（大小）的改變平均只需要對 K/n個關(guān)鍵字重新映射砍的，其中K是關(guān)鍵字的數(shù)量蹂喻， n是槽位數(shù)量。然而在傳統(tǒng)的哈希表中开泽，添加或刪除一個槽位的幾乎需要對所有關(guān)鍵字進行重新映射牡拇。
引出
我們在上文中已經(jīng)介紹了一致性Hash算法的基本優(yōu)勢，我們看到了該算法主要解決的問題是：當slot數(shù)發(fā)生變化時穆律，能夠盡量少的移動數(shù)據(jù)惠呼。那么，我們思考一下峦耘，普通的Hash算法是如何實現(xiàn)剔蹋？又存在什么問題呢？ 那么我們引出一個問題：
假設(shè)有1000w個數(shù)據(jù)項辅髓，100個存儲節(jié)點泣崩，請設(shè)計一種算法合理地將他們存儲在這些節(jié)點上少梁。
看一看普通Hash算法的原理：
算法的核心計算如下
for item in range(ITEMS):
k = md5(str(item)).digest()
h = unpack_from(">I", k)[0]
# 通過取余的方式進行映射
n = h % NODES
node_stat[n] += 1
從上述結(jié)果可以發(fā)現(xiàn)，普通的Hash算法均勻地將這些數(shù)據(jù)項打散到了這些節(jié)點上律想，并且分布最少和最多的存儲節(jié)點數(shù)據(jù)項數(shù)目小于1%猎莲。之所以分布均勻，主要是依賴Hash算法（實現(xiàn)使用的MD5算法）能夠比較隨機的分布技即。
然而著洼，我們看看存在一個問題，由于該算法使用節(jié)點數(shù)取余的方法而叼，強依賴node的數(shù)目身笤，因此，當是node數(shù)發(fā)生變化的時候葵陵，item所對應(yīng)的node發(fā)生劇烈變化液荸，而發(fā)生變化的成本就是我們需要在node數(shù)發(fā)生變化的時候，數(shù)據(jù)需要遷移脱篙，這對存儲產(chǎn)品來說顯然是不能忍的娇钱，我們觀察一下增加node后，數(shù)據(jù)項移動的情況：
如果有100個item绊困，當增加一個node文搂，之前99%的數(shù)據(jù)都需要重新移動。
這顯然是不能忍的秤朗，普通哈希算法的問題我們已經(jīng)發(fā)現(xiàn)了煤蹭，如何對其進行改進呢？沒錯取视，我們的一致性哈希算法閃亮登場硝皂。
那么，一個亟待解決的問題就變成了：當node數(shù)發(fā)生變化時作谭，如何保證盡量少引起遷移呢稽物？即當增加或者刪除節(jié)點時，對于大多數(shù)item折欠，保證原來分配到的某個node姨裸，現(xiàn)在仍然應(yīng)該分配到那個node，將數(shù)據(jù)遷移量的降到最低怨酝。
一致性Hash算法的原理是這樣的：
雖然一致性Hash算法解決了節(jié)點變化導(dǎo)致的數(shù)據(jù)遷移問題，但是那先，我們回過頭來再看看數(shù)據(jù)項分布的均勻性农猬， 但是引入一致性哈希算法后，為什么就不均勻呢售淡？數(shù)據(jù)項本身的哈希值并未發(fā)生變化斤葱，變化的是判斷數(shù)據(jù)項哈希應(yīng)該落到哪個節(jié)點的算法變了慷垮。
因此，主要是因為這100個節(jié)點Hash后揍堕，在環(huán)上分布不均勻料身，導(dǎo)致了每個節(jié)點實際占據(jù)環(huán)上的區(qū)間大小不一造成的。
改進-虛節(jié)點
當我們將node進行哈希后衩茸，這些值并沒有均勻地落在環(huán)上芹血，因此，最終會導(dǎo)致楞慈，這些節(jié)點所管轄的范圍并不均勻幔烛，最終導(dǎo)致了數(shù)據(jù)分布的不均勻。
因此囊蓝，通過增加虛節(jié)點的方法饿悬，使得每個節(jié)點在環(huán)上所“管轄”更加均勻。這樣就既保證了在節(jié)點變化時聚霜，盡可能小的影響數(shù)據(jù)分布的變化狡恬，而同時又保證了數(shù)據(jù)分布的均勻。也就是靠增加“節(jié)點數(shù)量”加強管轄區(qū)間的均勻蝎宇。
另一種改進
然而弟劲，虛節(jié)點這種靠數(shù)量取勝的策略增加了存儲這些虛節(jié)點信息所需要的空間。在OpenStack的Swift組件中夫啊，使用了一種比較特殊的方法來解決分布不均的問題函卒，改進了這些數(shù)據(jù)分布的算法，將環(huán)上的空間均勻的映射到一個線性空間撇眯，這樣报嵌，就保證分布的均勻性。
