一致性哈希簡(jiǎn)稱DHT,是麻省理工學(xué)院提出的一種算法卖哎，目前主要應(yīng)用于分布式緩存當(dāng)中鬼悠。
一致性哈下彩可以有效地解決分布式存儲(chǔ)結(jié)構(gòu)下動(dòng)態(tài)增加和刪除節(jié)點(diǎn)所帶來(lái)的問(wèn)題。我們簡(jiǎn)單舉例說(shuō)明一下：
1.首先厦章，我們把全量的緩存空間當(dāng)做一個(gè)環(huán)形存儲(chǔ)結(jié)構(gòu)镇匀。環(huán)形空間總共分成2^32個(gè)緩存區(qū)，在Redis中則是把緩存key分配到16384個(gè)slot袜啃。
2.每一個(gè)緩存key都可以通過(guò)Hash算法轉(zhuǎn)化為一個(gè)32位的二進(jìn)制數(shù)汗侵，也就對(duì)應(yīng)著環(huán)形空間的某一個(gè)緩存區(qū)。我們把所有的緩存key映射到環(huán)形空間的不同位置群发。
3.我們的每一個(gè)緩存節(jié)點(diǎn)（Shard）也遵循同樣的Hash算法晰韵，比如利用IP做Hash，映射到環(huán)形空間當(dāng)中熟妓。
4.如何讓key和節(jié)點(diǎn)對(duì)應(yīng)起來(lái)呢雪猪？很簡(jiǎn)單，每一個(gè)key的順時(shí)針?lè)较蜃罱?jié)點(diǎn)起愈，就是key所歸屬的存儲(chǔ)節(jié)點(diǎn)只恨。所以圖中key1存儲(chǔ)于node1，key2抬虽，key3存儲(chǔ)于node2官觅，key4存儲(chǔ)于node3。
當(dāng)緩存的節(jié)點(diǎn)有增加或刪除的時(shí)候阐污，一致性哈希的優(yōu)勢(shì)就顯現(xiàn)出來(lái)了休涤。讓我們來(lái)看看實(shí)現(xiàn)的細(xì)節(jié)：
1.增加節(jié)點(diǎn)
當(dāng)緩存集群的節(jié)點(diǎn)有所增加的時(shí)候，整個(gè)環(huán)形空間的映射仍然會(huì)保持一致性哈希的順時(shí)針規(guī)則笛辟，所以有一小部分key的歸屬會(huì)受到影響功氨。
有哪些key會(huì)受到影響呢？圖中加入了新節(jié)點(diǎn)node4手幢，處于node1和node2之間捷凄，按照順時(shí)針規(guī)則，從node1到node4之間的緩存不再歸屬于node2弯菊，而是歸屬于新節(jié)點(diǎn)node4纵势。因此受影響的key只有key2踱阿。
最終把key2的緩存數(shù)據(jù)從node2遷移到node4管钳，就形成了新的符合一致性哈希規(guī)則的緩存結(jié)構(gòu)。
2.刪除節(jié)點(diǎn)
當(dāng)緩存集群的節(jié)點(diǎn)需要?jiǎng)h除的時(shí)候（比如節(jié)點(diǎn)掛掉）软舌，整個(gè)環(huán)形空間的映射同樣會(huì)保持一致性哈希的順時(shí)針規(guī)則才漆，同樣有一小部分key的歸屬會(huì)受到影響。
有哪些key會(huì)受到影響呢佛点？圖中刪除了原節(jié)點(diǎn)node3醇滥，按照順時(shí)針規(guī)則黎比，原本node3所擁有的緩存數(shù)據(jù)就需要“托付”給node3的順時(shí)針后繼節(jié)點(diǎn)node1。因此受影響的key只有key4鸳玩。
最終把key4的緩存數(shù)據(jù)從node3遷移到node1阅虫，就形成了新的符合一致性哈希規(guī)則的緩存結(jié)構(gòu)。
說(shuō)明：這里所說(shuō)的遷移并不是直接的數(shù)據(jù)遷移不跟，而是在查找時(shí)去找順時(shí)針的后繼節(jié)點(diǎn)颓帝，因緩存未命中而刷新緩存。
如果出現(xiàn)分布不均勻的情況怎么辦窝革？比如下圖這樣购城，按順時(shí)針規(guī)則，所有的key都?xì)w屬于統(tǒng)一個(gè)節(jié)點(diǎn)虐译。
為了優(yōu)化這種節(jié)點(diǎn)太少而產(chǎn)生的不均衡情況瘪板。一致性哈希算法引入了 虛擬節(jié)點(diǎn) 的概念。
所謂虛擬節(jié)點(diǎn)漆诽，就是基于原來(lái)的物理節(jié)點(diǎn)映射出 N 個(gè)子節(jié)點(diǎn)侮攀，最后把所有的子節(jié)點(diǎn)映射到環(huán)形空間上。
如上圖所示厢拭，假如node1的ip是192.168.1.109魏身，那么原node1節(jié)點(diǎn)在環(huán)形空間的位置就是hash（“192.168.1.109”）。
我們基于node1構(gòu)建兩個(gè)虛擬節(jié)點(diǎn)蚪腐，node1-1 和 node1-2箭昵，虛擬節(jié)點(diǎn)在環(huán)形空間的位置可以利用（IP+后綴）計(jì)算，例如：
hash（“192.168.1.109#1”）回季，hash（“192.168.1.109#2”）
此時(shí)家制，環(huán)形空間中不再有物理節(jié)點(diǎn)node1，node2泡一，只有虛擬節(jié)點(diǎn)node1-1颤殴，node1-2，node2-1鼻忠，node2-2涵但。由于虛擬節(jié)點(diǎn)數(shù)量較多，緩存key與虛擬節(jié)點(diǎn)的映射關(guān)系也變得相對(duì)均衡了帖蔓。
