簡單hash演算法和一致性hash演算法

hash演算法常見的場景有：作為負載均衡策略、分散式緩存分區、資料庫分表分庫等，下面將兩種常見的演算法做一簡單的介紹及實現，（下面部分內容參考其他網站，記錄在此實為當做個人筆記）

1. 簡單hash演算法

簡單hash演算法在實現上為：目標 target = hash（key）/ 質數

此方法簡單java代碼實現如下:

public static void main(String[] args) { ArrayList<String> data = new ArrayList<String>();for(int i=0;i<200;i++){ IdWorker worker = new IdWorker(1,1,1); data.add(worker.nextId()+""); } HashMap<String,AtomicLong> target = new HashMap<String,AtomicLong>(); /** * 最簡單的hash演算法:targetServer = serverList[hash(key) % serverList.size] */ data.forEach(e->{long serv = new HashServiceImpl().hash(e)%5; System.out.println(serv); target.compute(Math.abs(serv)+"", (k,v)->{if(v==null){return new AtomicLong(); }else{ v.getAndIncrement();return v; } }); }); //列印分組結果 System.out.println(target.toString()); }/** * MurMurHash演算法，是非加密HASH演算法，性能很高，碰撞率低 */ @Override public Long hash(String key) { ByteBuffer buf = ByteBuffer.wrap(key.getBytes()); int seed = 0x1234ABCD; ByteOrder byteOrder = buf.order(); buf.order(ByteOrder.LITTLE_ENDIAN); long m = 0xc6a4a7935bd1e995L; int r = 47; long h = seed ^ (buf.remaining() * m); long k; while (buf.remaining() >= 8) { k = buf.getLong(); k *= m; k ^= k >>> r; k *= m; h ^= k; h *= m; } if (buf.remaining() > 0) { ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN); finish.put(buf).rewind(); h ^= finish.getLong(); h *= m; } h ^= h >>> r; h *= m; h ^= h >>> r; buf.order(byteOrder); return h; }

運行結果如下，可以看到hash的結果與取模的質數數量一致。

{0=24, 1=15, 2=8, 3=22, 4=126}

簡單Hash引起的問題

簡單hah演算法計算的值會依賴於質數。如果再加入一個分區則之前的hash映射都會失效，無法動態調整。解決此問題的辦法為使用一致性hash，一致性hash可以解決大部分hash引用失效的問題。在開始前先了解一下一致性hash演算法的原理及相關的特性。

1、一致性hash演算法原理

一致性哈希演算法是分散式系統中常用的演算法，比如有N台緩存伺服器，你需要將數據緩存到這N台伺服器上。一致性哈希演算法可以將數據儘可能平均的存儲到N台緩存伺服器上，提高系統的負載均衡，並且當有緩存伺服器加入或退出集群時，儘可能少的影響現有緩存伺服器的命中率，減少數據對後台服務的大量衝擊。

一致性哈希演算法的基本原理，把數據通過hash函數映射到一個很大的環形空間里，如下圖所示：

A、B、C、D 4台緩存伺服器通過hash函數映射環形空間上，數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如緩存數據:K1對應到了圖中所示的位置，然後沿順時針找到一個機器節點A，將K1存儲到A節點上，K2存儲到A節點上，K3、K4存儲到B節點上。

如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：

這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。

為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：

引入「虛擬節點」後，映射關係就從 {對象 ->節點 }轉換到了 {對象 ->虛擬節點 }。圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，提高了平衡性，因此不會造成「雪崩」現象。

2、一致性hash的特性

考慮到分散式系統每個節點都有可能失效，並且新的節點很可能動態的增加進來，如何保證當系統的節點數目發生變化時仍然能夠對外提供良好的服務，這是值得考慮的，尤其實在設計分散式緩存系統時，如果某台伺服器失效，對於整個系統來說如果不採用合適的演算法來保證一致性，那麼緩存於系統中的所有數據都可能會失效（即由於系統節點數目變少，客戶端在請求某一對象時需要重新計算其hash值（通常與系統中的節點數目有關），由於hash值已經改變，所以很可能找不到保存該對象的伺服器節點），因此一致性hash就顯得至關重要，良好的分散式cahce系統中的一致性hash演算法應該滿足以下幾個方面：

平衡性(Balance)

平衡性是指哈希的結果能夠儘可能分布到所有的緩衝中去，這樣可以使得所有的緩衝空間都得到利用。很多哈希演算法都能夠滿足這一條件。

單調性(Monotonicity)

單調性是指如果已經有一些內容通過哈希分派到了相應的緩衝中，又有新的緩衝區加入到系統中，那麼哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩衝區中去，而不會被映射到舊的緩衝集合中的其他緩衝區。簡單的哈希演算法往往不能滿足單調性的要求，如最簡單的線性哈希：x = (ax + b) mod (P)，在上式中，P表示全部緩衝的大小。不難看出，當緩衝大小發生變化時(從P1到P2)，原來所有的哈希結果均會發生變化，從而不滿足單調性的要求。哈希結果的變化意味著當緩衝空間發生變化時，所有的映射關係需要在系統內全部更新。而在P2P系統內，緩衝的變化等價於Peer加入或退出系統，這一情況在P2P系統中會頻繁發生，因此會帶來極大計算和傳輸負荷。單調性就是要求哈希演算法能夠應對這種情況。

分散性(Spread)

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

負載(Load)

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

平滑性(Smoothness)

平滑性是指緩存伺服器的數目平滑改變和緩存對象的平滑改變是一致。解解決了傳統hash演算法增加機器後緩存大量miss的問題

redis目前主從複製過程有個很不好的地方就是：當slave和master在同步過程中，網路出現問題，這時候slave要求master重傳而不是續傳（重新生成一份RDB文件然後傳輸）；這樣當master中數據很多的時候，影響會很大，所以一個master下掛多個slave穩定性會下降。

針對上述演算法做一個簡單的實現參考：http://sundoctor.iteye.com/blog/2104321

一致性Hash實現：