一緻性哈希環
傳統的hash算法在節點數量變化的時候會出現映射關系前後不一緻的現象，如果每個節點提供的服務不一緻，映射關系的改變将是緻命的，比如無法找到已經映射了的資料。以哈希取模算法為例子，其公式是：node_index = hash(key) % N 。
節點減少的前後對比：對于新的key來說，映射沒有問題，但是對于舊的key來說，映射關系發生了變化，本來如果hash(key)==3，那麼會映射到編号為0的節點上，節點數量變化之後，卻将映射到編号為1的節點上。這時去1節點取資料将通路不到，出現錯誤，對于分布式緩存系統而言，可能出現“緩存雪崩”。節點增加的情況同理。這成為簡單雜湊演算法在分布式哈希表中存在的動态伸縮問題。
要解決映射不一緻的問題，直覺的方法是通過重新配置設定已有的key來迎合新的映射關系，但這代價昂貴。更好的方法是使用一緻性雜湊演算法。
一緻性雜湊演算法是一種特殊的雜湊演算法，在移除或者添加一個伺服器的時候能夠盡可能小地改變已經存在的服務請求和處理請求的伺服器之間的映射關系。
一緻性雜湊演算法通過一個叫作一緻性哈希環的資料結構實作，一緻性哈希環的主要思想是減少需要移動的已映射資料。原先的mod函數将key映射到一個特定的值上，并且為這個值提供一個伺服器，一緻性雜湊演算法首先将key映射到一個很大的範圍内，并且為每個範圍内的值提供一個伺服器。如果負責某一範圍的資料的伺服器被删除，其上存儲的資料将順時針遷移到下一台伺服器上，下一台伺服器将負責映射到這兩個連續範圍内請求的處理。增加節點同理進行資料遷移。通過這種方式，節點數量發生變化時也不會改變其他範圍的資料映射關系，盡可能地減少了需要遷移的資料數量。
如圖所示，橙色節點表示資料映射到的環上的位置，藍色節點表示伺服器。初始時刻K1和K2由B伺服器負責，如果B伺服器被删除，K1和K2将遷移到C伺服器上。
當然，這種方法也存在問題。當删除了一系列連續的節點之後，這些被删除節點的負載将交由環上的下一台機器統一處理。這台機器将承載大量的負載，可能是以崩潰，由此循環下去，造成雪崩，整個叢集最後可能完全崩潰。
為了解決這一問題，引入虛拟節點的概念。資料的存儲首先根據映射關系在環上找到對應的虛拟節點，每個虛拟節點都會關聯到一個真實節點。例如下圖中的A1、A2關聯到真實節點A，資料都在A上存儲，B1、B2關聯到真實節點B，資料都在B上存儲。由于節點數量很多，分布均勻，即使在連續範圍内有機器崩潰，也不會給同一台機器增加負載，是以不容易造成雪崩。
【參考】
https://segmentfault.com/a/1190000021199728
https://zhuanlan.zhihu.com/p/379724672