Hash算法

Hash 算法在路由算法應用中，為了保證數據均勻的分布，例如有 3 個桶，分别是 0 号桶， 1 号桶和 2 号桶；現在有 12 個球，怎麼樣才能讓 12 個球平均分布到 3 個桶中呢？使用 Hash 算法的做法是，将 12 個球從 0 開始編号，得到這樣的一個序列： 0，1，2，3，4，5，6，7，8，9，10，11 。将這個序列中的每個值模3，不管數字是什麼，得到的結果都是 0,1,2 ，不會超過 3 ，将結果為 0 的數字放入 0 号桶，結果為 1 的數子放入 1 号桶，結果為 2 的數字放入2号桶，12個球就均勻的分布到 3 個桶中， 0,3,6,9,12 号球放入 0 号桶， 1,4,7,10 号球放入 1 号桶， 2,5,8,11 号球放入 2 号桶。

一緻性Hash算法

一緻性 Hash 算法在 1997 年由麻省理工學院提出的一種分布式哈希 （DHT） 實現算法，設計目标是為了解決因特網中的熱點 （Hot Spot） 問題，初衷和 CARP 十分相似。一緻性 Hash 修正了 CARP 使用的簡單哈希算法帶來的問題，使得分布式哈希 （DHT） 可以在 P2P 環境中真正得到應用。

一緻性 Hash 算法也是使用取模的方法，隻是，剛才描述的取模法是對服務器的數量進行取模，而一緻性Hash算法是對 2^32 取模，什麼意思呢？簡單來說，一緻性 Hash 算法将整個哈希值空間組織成一個虛拟的圓環，如假設某哈希函數H的值空間為 0-2^32-1 （即哈希值是一個32位無符号整形）。整個空間按 順時針方向組織 ，圓環的正上方的點代表 0，0 點右側的第一個點代表 1 ，以此類推， 2、3、4、5、6 ……直到 2^32-1 ，也就是說 0 點左側的第一個點代表 2^32-1 ， 0 和 2^32-1 在零點中方向重合，我們把這個由 2^32 個點組成的圓環稱為 Hash環 。

特性定義

一緻性 Hash 算法提出了在動态變化的 Cache 環境中，判定哈希算法好壞的四個定義：

1、平衡性（Balance）：平衡性是指哈希的結果能夠盡可能分布在所有的緩沖 (Cache) 中去，這樣可以使得所有的緩沖空間得到利用。很多哈希算法都能夠滿足這一條件。

2、單調性（Monotonicity）：單調性是指如果已經有一些内容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應該能夠保證原有已分配的内容可以被映射到原有的或者新的緩沖中去，而不會映射到舊的緩沖集合中的其他緩沖區。

3、分散性（Spread）：在分布式環境中，終端有可能看不到所有的緩沖，而隻能看到其中的一部分。當終端希望通過哈希過程将内容映射到緩沖上去，由于不同終端所見的緩沖範圍有可能不同，從而導緻哈希的結果不一緻，最終的結果是相同的内容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導緻相同内容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法應該能夠盡量避免不一緻的情況發生，也就是盡量降低分散性。

4、負載（Load）：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能将相同的内容映射到不同的緩沖區中，那麼對于一個特定的緩沖區而言，也可能被不同的用戶映射到不同的内容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。

下一步将各個服務器使用Hash進行一個哈希，具體可以選擇 服務器的IP或主機名 作為 關鍵字 進行哈希，這樣每台機器就能确定其在哈希環上的位置，這裡假設将上文中四台服務器使用IP地址哈希後在環空間的位置如下：

接下來使用如下算法定位數據訪問到相應服務器：将數據 key 使用相同的函數 Hash 計算出哈希值，并确定此數據在環上的位置，從此位置沿環順時針“行走”，第一台遇到的服務器就是其應該定位到的服務器！

例如我們有 Object A 、 Object B 、 Object C 、 Object D 四個數據對象，經過哈希計算後，在環空間上的位置如下：

根據一緻性 Hash 算法，數據 A 會被定為到 Node A 上， B 被定為到 Node B 上， C 被定為到 Node C 上， D 被定為到 Node D 上。

容錯和可擴展

現假設 Node C 不幸宕機，可以看到此時對象 A、B、D 不會受到影響，隻有 C 對象被重定位到 Node D 。一般的，在一緻性 Hash 算法中，如果一台服務器不可用，則受影響的數據僅僅是此服務器到其環空間中前一台服務器（即沿着逆時針方向行走遇到的第一台服務器）之間數據，其它不會受到影響，如下所示：

下面考慮另外一種情況，如果在系統中增加一台服務器 Node X ，如下圖所示：

此時對象 Object A、B、D 不受影響，隻有對象 C 需要重定位到新的 Node X ！一般的，在一緻性 Hash 算法中，如果增加一台服務器，則受影響的數據僅僅是新服務器到其環空間中前一台服務器（即沿着逆時針方向行走遇到的第一台服務器）之間數據，其它數據也不會受到影響。

綜上所述，一緻性 Hash 算法對于節點的增減都隻需重定位環空間中的一小部分數據，具有較好的容錯性和可擴展性。

Hash環的數據傾斜問題

一緻性 Hash 算法在 服務節點太少時 ，容易因為節點分部不均勻而造成 數據傾斜 （被緩存的對象大部分集中緩存在某一台服務器上）問題，例如系統中隻有兩台服務器，其環分布如下：

此時必然造成大量數據集中到 Node A 上，而隻有極少量會定位到 Node B 上。為了解決這種數據傾斜問題，一緻性 Hash 算法引入了虛拟節點機制，即對每一個服務節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛拟節點。具體做法可以在 服務器IP 或 主機名 的後面增加編号來實現。

例如上面的情況，可以為每台服務器計算三個虛拟節點，于是可以分别計算 “ Node A#1 ”、“ Node A#2 ”、“ Node A#3 ”、“ Node B#1 ”、“ Node B#2 ”、“ Node B#3 ”的哈希值，于是形成六個虛拟節點：

同時數據定位算法不變，隻是多了一步虛拟節點到實際節點的映射，例如定位到“ Node A#1 ”、“ Node A#2 ”、“ Node A#3” 三個虛拟節點的數據均定位到 Node A 上。這樣就解決了服務節點少時數據傾斜的問題。在實際應用中，通常将虛拟節點數設置為 32 甚至更大，因此即使很少的服務節點也能做到相對均勻的數據分布。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!