今天，洪爵來跟大家聊聊一緻性哈希。大概從以下幾個角度去進行什麼是一緻性哈希？為什麼會出現這種算法？它是為了解決什麼樣的問題。
我們先來列舉個例子：
請求的處理流程
我們知道前台的一個請求發送到了背景，背景會先從緩存中去取資料，如果取到了對應的資料就将結果傳回，否則會去查詢資料庫，然後将擷取到的資料放進緩存中，再傳回結果(圖1)：
為了減少查詢資料庫所帶來的的磁盤IO，有許多中間件應運而生，比如說幾乎所有招聘背景開發工程師的崗位要求中都寫有需要掌握Redis。通過把資料放入記憶體中，例如以形式存儲資料，以達到能快速的傳回使用者所需要的資訊。
假設一開始這個系統的使用者量并不大，用來當做緩存的伺服器隻有一台；但是當使用者的體量上來的時候，一台緩存伺服器是不足以支撐處理使用者的請求的，發生當機的情況也是常有，進而連鎖反應的導緻緩存伺服器當機，使用者的請求全部壓到了磁盤資料庫層面上，毫無疑問的資料庫支撐不了多久也會挂掉。
這個時候你可能會想到使用多個緩存伺服器嘛，通過負載均衡把請求均勻的打在每一個伺服器上，但是這樣的話，每一個緩存伺服器上的資料都是一樣的，而且當我們想要緩存的資料比伺服器的記憶體還要大的時候，可能是因為實時性要求比較高的場景之類，我們需要存每個使用者的一些資訊。如果使用者體量非常大，無疑一台伺服器的記憶體根本容不下。
簡單哈希
那我們有沒有一種辦法，就是讓每台伺服器都儲存不一樣的資料，然後我請求的時候就找特定的一個伺服器進行通路呢？(最暴力的就是每個緩存伺服器都去通路一遍，看看想要查找的key是不是為null，但是無疑增加了網絡傳輸的時間，并且每次都這樣輪詢，那麼其實和單台伺服器沒什麼差别)
通過簡單的雜湊演算法，我們能夠實作這一點，和Java中的HashMap類似，例如現在有3台緩存伺服器，我們取名為C0，C1，C2。現在我們把需要緩存的資料的key通過雜湊演算法拿到它的哈希值，然後對這個哈希值進行取模，有幾台伺服器就取幾台，那麼現在是有三台伺服器，那麼我們就把哈希值模3，即
key.hashValue % 3
得到的值如果是0，那麼我們就把資料放到C0伺服器，如果是為1則把資料放到C1伺服器，以此類推(圖2)：
看到這裡，你可能眼前一亮，這是個好辦法呀！但是如果我現在新添加一台伺服器呢？
那麼我們就需要對key的哈希值和4進行取模操作，并且之前的key和3進行取模而映射到了C0，C1，C2伺服器上，但是現在
key.hashValue % 3 和 key.hashValue % 4
這兩個值很大機率是不會一樣的，也就是說，我們需要對所有的key進行取模，重新映射到每一台機器上，但是以後我要新增一台伺服器，或者減少一台伺服器都需要大動幹戈的進行資料移動，這代價無疑非常高，是以一緻性雜湊演算法就應運而生啦。
一緻性雜湊演算法
我們考慮能不能設計一種算法，在你新增加或者删除一個伺服器節點的時候，絕大多數的記錄原來配置設定在哪一個節點，現在還是應該被配置設定到那一個節點，這樣的話，我們就能将資料的移動數量降到最低，這就是一緻性雜湊演算法的思想。
我們之前的簡單雜湊演算法是對伺服器節點的數量進行取模，但是一緻性雜湊演算法跳出了這個思想，它是對
2^32
這個數字進行取模，可能你還不是很明白，我們簡單畫一個圖你就了解了(圖3)。
對
2^32
進行取模，我們的取值範圍是：0 - 2^32-1，每一個數代表了一個個節點，我們把這個環叫做哈希環。
現在我們把伺服器節點也進行哈希，按照自定義的規則也好，或者單單對伺服器的ip位址進行哈希也好，得出來的哈希值取模會落在哈希環的節點上，例如我們得到了這樣的一個哈希環(圖4)：
接下來我們把要緩存資料的key進行哈希，哈希取模過後的值我們也映射到哈希環上的節點上，如果剛好落在了伺服器所在的節點上，那麼就讓這個伺服器存儲該資料；如果不是落在伺服器的節點上，那麼我們就讓該資料落在順時針方向碰到的第一台伺服器節點上。例如說，現在有4台伺服器C0，C1，C2，C3，有5個需要存儲的資料：V，W，X，Y，Z。
如圖所示(圖5)：
一共有4個伺服器節點分布在哈希環上，我們把V資料的key進行哈希取模過後，發現和C0伺服器算出來的值一樣，剛好打在了這個點上，那麼就由伺服器C0儲存這個資料，W落在了伺服器C0和C1之間，那麼按照原則，順時針遇到的第一個伺服器節點就儲存它的資料，那麼是由C1進行儲存的，以此類推(圖6)：(黑線為實際落環位置，紅線為該資料節點映射到的伺服器節點)
新增節點
這樣的哈希環有什麼好處呢，我們來看一下，當我們需要新增一個伺服器節點的時候：例如在C3節點和C0節點處添加一個新的伺服器會發生什麼事情(圖7)。
我們驚訝的發現，當我們新增了一個節點後，對于資料V,W,X,Y來說映射到的伺服器節點位置是沒有發生變化的，變化的隻有新增節點逆時針遇到的第一個伺服器節點這一段區間的資料，即
( C3節點 , C4節點 ]
這一段哈希環需要對資料進行遷移，從原本映射到C0伺服器節點轉為映射到C4新節點上。而
( C4節點 , C0節點 ]
這一段區間還是映射到C0節點，這就大大降低了新增伺服器節點時候資料的遷移量。
删除節點
如果是删除一個節點呢？會不會導緻資料的大量移動呢？我們來看看(圖8)。
假設現在C3節點挂掉了，那麼在
( C2節點 , C3節點]
這段的資料就需要重新映射到C0節點上，即挂掉節點逆時針遇到的第一個伺服器節點的這一段哈希環，那麼因為C3的當機，Y這個資料就會重新存儲在C0這個節點。
總的來說，無論是新增一個節點或者是删除一個節點所影響的都隻是逆時針遇到第一個節點的這段區間的資料。相比簡單哈希所帶來的全盤資料移動，一緻性雜湊演算法帶來的效率無疑是有着本質的提升。
資料傾斜問題
一緻性雜湊演算法介紹到這裡，其實還沒有結束，我們仔細看上面這張圖，其實還是存在有問題的。因為現在隻有C0，C1，C2三個節點，如果我們把C0和C2節點所在位置連起來(相當于圓環的直徑)，左上半部分的節點相當于都落在了C0節點上，也就是說幾乎有一半的資料節點都落在C0伺服器上，這是因為伺服器節點分布不均勻或者數量過少導緻的資料傾斜問題。
虛拟節點
為了避免資料傾斜問題的發生，引入虛拟節點進行解決。我們需要對伺服器節點進行多次哈希運算，使得一個伺服器節點有多個節點在環上與之對應，這樣就可以進一步削弱或者避免資料傾斜問題。一緻性雜湊演算法的本質不需要改變，我們隻需要多添加從虛拟節點到真實節點的映射關系就行了，如圖(圖9)：
至于一緻性雜湊演算法的建立人，哪一年建立的。大家可以百度搜尋一緻性哈希，檢視相關的百度百科哈。
願每個人都能帶着懷疑的态度去閱讀文章并探究其中原理。
道阻且長，往事作序，來日為章。
期待我們下一次相遇！