一致性哈希算法及其在分布式存儲中的應用
OStorage的老大李明宇隨手發了一個朋友圈，是該公司企業級對象存儲產品OStorage-EOS的監控界面截圖，感慨一個200多TB的集群很快被用戶用到了92%以上。
“外行看熱鬧，內行看門道”，一位做分布式存儲的同仁看到了說：接近93%的存儲利用率，還在不停寫數據進去，說明OStorage-EOS數據分布的均勻性很好，否則，如果數據分布不夠均勻，就有可能出現其他的節點或盤還有很多空間，但某一個盤或者某一個節點寫滿了，這時還繼續寫數據進去就會出問題。
那么OStorage-EOS分布式對象存儲是如何讓數據均勻分布到各個盤上的呢？原來是使用了一個算法叫做“一致性哈希（Consistent Hashing）”，并且在一致性哈希基礎上做了改進，增加了權重、副本、機柜感知、地域感知等機制。
一致性哈希算法也是分布式系統領域的經典算法，在很多地方都有應用，下面，我們就一起來了解一下它：
哈希函數
仔細研究一致性哈希之前，我們先來了解一下基本的哈希，舉個例子說明了我們如何使用哈希函數來確定對象存儲在哪里。
先看一個定位數據相對簡單的方法，使用MD5算法來得到對象的邏輯位置的哈希值，然后除以可用的磁盤數量，得到余數。***將余數值映射到驅動器ID。
例如，對象的存儲位置為 /accountA/container1/objectX ，并且使用四個磁盤來存儲數據，我們稱之為磁盤0到磁盤3。這里我們先計算MD5值:
- md5 -s /accountA/container1/objectX
- MD5 ("/account/container/object") =
- f9db0f833f1545be2e40f387d6c271de
然后我們用哈希值（十六進制數值）除以磁盤數，取余數（取模）。以上十六進制數值轉化為十進制為：
332115198597019796159838990710599741918
取模函數在大多數編程語言中用%運算符表示:
332115198597019796159838990710599741918 % 4 = 2
因為余數是2，所以對象將被存儲在磁盤2。
這種算法***的缺點是計算結果取決于除數也就是磁盤數量。任何時候添加或移除某個磁盤(除數變化了)，同一個對象可能得到不同的余數，從而映射到不同的磁盤。為了說明這一點，下面的表顯示了當添加磁盤時，哪一個磁盤將成為對象新的存儲位置。
注意，幾乎每次添加新磁盤，對象都必須移動到新的磁盤上，這僅僅一個對象的情況，將這種行為推廣開來，在增加或者移除節點、磁盤時，幾乎集群中的所有數據都需要進行移動。集群將不得不花費大量資源來進行這些遷移，還將產生繁重的網絡負載，以及數據不可讀取的情況。
一致性哈希算法
當從集群中的增加或者移除磁盤、節點時，一致性哈希（Consistent Hashing）可以減少移動的對象數量。一致性哈希不是將每個值直接映射到一個磁盤，而是通過將所有可能的哈希值建模為一個環。一致性哈希算法除了計算對象的哈希以外，還計算設備的哈希，根據磁盤的IP地址、盤符等計算哈希值，每個磁盤被映射到哈希環的某個點上，如圖所示。
當一個對象需要被存儲時，先計算對象的哈希值，然后定位到環上，如圖所示“hash of object”的位置。系統按順時針搜索環上面下一個磁盤的哈希然后定位該磁盤，用這個磁盤存儲數據。上圖中可以看到，對象將被存儲在磁盤4。按照這種算法，哈希環上某個區間的哈希值會被映射到一個磁盤上，如圖所示，我們用不同顏色表示不同區間和它們對應的磁盤，若某個對象的哈希值落在藍色的區間內，則它會被存儲在磁盤1上。
有了這樣的哈希環，當我們添加一塊新的磁盤時，比如磁盤5，那么圖中粉色部分將不再屬于磁盤4，因為這部分數據目前全部屬于新的磁盤5。所以這部分位于磁盤4上的對象將會被移動到磁盤5，而其他數據均不受影響。
使用這種方案，添加一個盤或者一個節點，只需要移動少量數據，比前面那種最基本的依靠計算哈希值并模除來確定數據存放位置的方案要好很多，在前面那種方案中需要移動很多數據。
在實際應用的一致性哈希算法中，每個實際的磁盤或節點會對在環上對應到多個標記，這些標記在一些文獻中也被成為“虛節點（Virtual Node）”，實際應用中，一個磁盤會對應很多標記/虛節點，甚至每個磁盤對應數百個標記。多個標記意味著每塊磁盤對應環的哈希值范圍從一個大區域切分成了數個小區域。這樣做有兩個效果，一個效果是一個新添加的磁盤可能從多個磁盤那里遷移對象數據，進一步降低了數據遷移的壓力，另一個效果是總體的數據分布更加的平均。
以上就是一致性哈希的基本原理，OStorage-EOS基于一致性哈希算法實現了數據的均勻分布，并加以改進，引入副本、權重、機柜感知、地域感知等機制，以滿足企業級用戶的需求。
