什麼是一致性hash？
一致性hash
前言
說出來大家可能不相信，我昨天做夢夢到自己在面試，然後面試官問了我這個問題哈哈~然後我就打算按照自己的理解寫一寫。如果有寫的不對的歡迎大家指正！
直接開始
普通hash演算法
普通hash演算法就是把存儲的key取hash然後再對節點數取模之後判斷key所在節點的位置，
如上圖所示，假設現在有key1，key2，key3，key4四個key，通過上面說的方法均勻分布在了這4個節點上面。看上去非常nice~
但是如果現在我們集群需要擴容，增加一台機器會發生啥？
可以看到，由於現在增加了一台機器，所以現在我們取模的對象由3變成了4。
導致什麼現象呢？假設我們的數據現在沒有遷移，那原來的key3和key4本來是分別在node0和node1上的，現在通過hash取模運算之後卻是在node0和node3上，所以在數據不做遷移的情況下會導致原有的快取會大量失效。然後這種大面積的數據遷移是非常麻煩的！
這是擴容導致的問題，如果集群中的節點宕機呢？
現在node2掛了，集群節點數量變成了2，對應的key通過hash取模之後所在的節點也會變化。導致node2上面原有的key查詢不到，會直接查庫。其餘的key，除了key1能正常查詢外，其他key全都失效了。這時不僅涉及到數據遷移還會導致快取穿透。
一致性hash
一致性hash其實是普通取模hash演算法的改良版，其hash計算方法沒有變化，但是hash空間發生了變化，由原來的線性的變成了環。快取節點通過hash計算之後得到在hash環中的位置；key通過hash計算之後得到所在環的位置，然後順時針方向找到第一個節點，這個節點就是存放key的節點。
來看看一致性hash是如何解決普通取模hash中擴容和宕機的問題的。
假設現在我們增加了一個節點node3，原來的key1現在順時針找到了新增加node3，對其餘的節點沒有任何影響。只需要將node0到node3之間的key遷移到新的節點即可。
如果node2現在宕機了，那麼原來的key2順時針找到的節點會變成node0，其餘節點也沒有任何影響，只需要把node2上的key遷移到node0上即可。
那這個一致性hash難道就沒有啥毛病了嘛？
想一下，如果我們的節點數量很少，並且節點偏向一側會發生什麼事情？
可以看到很大一部分的key都會落在node0上，從而導致node0的壓力過大掛掉，node0掛掉之後數據同時又會向node1上轉移，node1又會掛掉，最終導致整個集群不可用！這就是數據傾斜的問題，會引起節點雪崩。可想而知這個問題會很嚴重。
一致性hash優化
數據傾斜的問題是通過虛擬節點來解決的。
就是在節點稀疏的hash環上對物理節點虛擬出一部分虛擬節點，key會打到虛擬節點上面，而虛擬節點上的key實際也是映射到物理節點上的，這樣就避免了數據傾斜導致單節點壓力過大導致節點雪崩的問題。
結語
做夢引起的一片博文。
介紹了普通取模hash的弊端，一致性hash如何解決，以及一致性hash優化的問題。
上面的介紹如果有什麼不對的地方希望各位能指正~我也會虛心接受。
