分布式存儲和一致性hash

本文我將對一致性算法作介紹，同時談談自己對一致性hash和一般意義上的hash算法的區別

hash是什么

hash即hash算法，又稱為散列算法，百度百科的定義是

哈希算法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。

1.這句話有幾個很重要的地方，首先是任意長度二進制，在java中，可以代表所有對象（序列化）

2.固定長度，使得hashmap等可以按照高低位進行位操作，同時能夠提供統一的方式（有種協議的感覺）

3.數據唯一的數值，使得hashcode可以作為查找的依據（快速查找的根本）

為什么hash

說為什么首先要說說如果沒有會怎么樣。

csdn 有這樣一篇文章講的很有意思，我們有一堆豬，怎么根據體重找到對應的一頭。如果沒有hash的思想，我們會比較每頭豬，但是如果有1000頭你也這樣做 么。引入hash，每頭豬的重量hash到一個hashcode，hashcode會映射到對應的豬圈，我們只要比較每個豬圈的豬就行了，而最理想的情況 就是每個豬圈的豬都一樣多（注：每個豬圈一個是好，但是空間消耗巨大）

（http://blog.csdn.net/ok7758521ok/article/details/4003476）

而java中，hash也是采用這樣的方式，通過hashcode與桶數取模的方式（當然時間是通過位操作，性能更高）自然映射到具體的桶中。

關于分布式存儲

當 hash遇上分布式，單臺機子的hashmap存儲已經不能滿足我們的key-value需求，怎么辦，我們需要把存儲內容分布到不同的實體機上，這時需 要一種把key映射到不同機器的方法，我們想起了hash，可以把實體機當做是桶，采用和hashmap實現一樣的思路，通過和實體機的數量取模，自然映 射到不同的機器。

ok，搞定，分布式確實可以實現。但現在問題來了，如果其中一臺機子掛了，或者又加了一臺機子怎么辦，這時出現兩種情況：

    1.不做任何改變，那么掛了的數據將無法得到恢復，新增的機子也無法得到利用

    2.rehash 這種情況，桶的數量將會改變，所有的值將重新映射，最終數據會得到存儲，這有兩個問題，rehash的時刻，所有key將重新映射，這時，對于大并發的情 形，是災難的，所有請求將不經過任何緩存，服務器面臨崩潰的風險，再者，老的數據依然還在，并且不會被用到，浪費存儲空間。

那么，怎么辦

引入一致性hash

consistent hashing 是這樣一種 hash 算法，簡單的說，在移除 / 添加一個 節點（機器，ip）時，它能夠盡可能小的改變已存在 key 映射關系，盡可能的滿足單調性（）的要求。

hash回環

任何的hash值都是固定長度的，因此可以通過一個回環來承載所有的hash值（為什么用環后面會說）

映射

hash最總要的一步就是把對象映射到對應的桶，而與通常的hash做法相比，一致性hash會比較特殊，一致性hash不會將key直接映射到桶，而將key和桶分別映射到回環的對應hash值節點

        映射key

        映射桶

接下來是最重要的一步，把key映射到對應的桶

尋桶

現在 cache 和對象都已經通過同一個 hash 算法映射到 hash 數值空間中了，接下來要考慮的就是如何將對象映射到 cache 上面了。

在這個環形空間中，如果沿著順時針方向從對象的 key 值出發，直到遇見一個 cache ，那么就將該對象存儲在這個 cache 上，因為對象和 cache 的 hash 值是固定的，因此這個 cache 必然是唯一和確定的。這樣不就找到了對象和 cache 的映射方法了嗎？！

依然繼續上面的例子（參見圖 3 ），那么根據上面的方法，對象 object1 將被存儲到 cache A 上； object2和 object3 對應到 cache C ； object4 對應到 cache B ；

好處

我們講了這么多一致性hash的算法，那么他究竟帶來了什么，我們分添加和刪除的情況考慮

    添加

我們添加一個新的節點D，按照順時針的方式，原先映射到C的object2會映射到D，而object3則還是映射到C，這樣添加只會影響到object2，事實上是B和D之間的對象，這種影響相比傳統的方式，影響是很小的

刪除

與添加類似，刪除也只會影響A和B之間的對象

虛擬節點（一下完全引自：http://my.oschina.net/jsan/blog/49702）

考量 Hash 算法的另一個指標是平衡性 (Balance) ，定義如下：

平衡性

平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

hash 算法并不是保證絕對的平衡，如果 cache 較少的話，對象并不能被均勻的映射到 cache 上，比如在上面的例子中，僅部署 cache A 和 cache C 的情況下，在 4 個對象中， cache A 僅存儲了 object1 ，而 cache C 則存儲了 object2 、 object3 和 object4 ；分布是很不均衡的。

為了解決這種情況， consistent hashing 引入了“虛擬節點”的概念，它可以如下定義：

“虛擬節點”（ virtual node ）是實際節點在 hash 空間的復制品（ replica ），一實際個節點對應了若干個“虛擬節點”，這個對應個數也成為“復制個數”，“虛擬節點”在 hash 空間中以 hash 值排列。

仍以僅部署 cache A 和 cache C 的情況為例，在圖 4 中我們已經看到， cache 分布并不均勻。現在我們引入虛擬節點，并設置“復制個數”為 2 ，這就意味著一共會存在 4 個“虛擬節點”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假設一種比較理想的情況，參見圖 6 。

圖 6 引入“虛擬節點”后的映射關系

此時，對象到“虛擬節點”的映射關系為：

objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；

因此對象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。

引入“虛擬節點”后，映射關系就從 { 對象 -> 節點 } 轉換到了 { 對象 -> 虛擬節點 } 。查詢物體所在 cache時的映射關系如圖 7 所示。

圖 7 查詢對象所在 cache

“虛擬節點”的 hash 計算可以采用對應節點的 IP 地址加數字后綴的方式。例如假設 cache A 的 IP 地址為202.168.14.241 。

引入“虛擬節點”前，計算 cache A 的 hash 值：

Hash(“202.168.14.241”);

引入“虛擬節點”后，計算“虛擬節”點 cache A1 和 cache A2 的 hash 值：

Hash(“202.168.14.241#1”);  // cache A1

Hash(“202.168.14.241#2”);  // cache A2

參考

http://my.oschina.net/u/1166485/blog/136663