哈希 Hash 算法介紹

哈希算法也叫散列算法, 不過英文單詞都是 Hash, 簡單一句話概括, 就是可以把任意長度的輸入信息通過算法變換成固定長度的輸出信息, 輸出信息也就是哈希值, 通常哈希值的格式是16進制或者是10進制, 比如下面的使用 md5 哈希算法的示例

md5("123456") => "e10adc3949ba59abbe56e057f20f883e"

主要特點：

• 不可逆 從哈希值不能推導出原始數(shù)據(jù), 所以Hash算法廣泛應用在現(xiàn)代密碼體系中
• 無碰撞 不同的信息進行哈希后得到的值應該是不同的, 但是從理論上來說, 哈希算法其實是有可能發(fā)生碰撞的, 輸入的信息是無窮的, 而輸出的哈希值長度是固定的, 所以是有限的。好比要把10個蘋果放到9個抽屜里面, 肯定會有一個抽屜裝了多個蘋果, 只不過哈希算法的碰撞的概率是非常小的, 比如128位的哈希值, 就有2的128次方的空間。
• 效率高 在處理比較大的原生值時, 也能能快速的計算出哈希值
• 無規(guī)律 原始輸入信息修改一點信息, 得到的哈希值也是大不相同的

哈希算法的實現(xiàn)有很多, 常見的有 MD5, SHA-1, 還有像 C#, Java 一些語言都有直接的 GetHashCode(), hashCode() 函數(shù)可以直接來用。

分布式存儲場景

在互聯(lián)網(wǎng)場景中, 通常面對的都是海量的數(shù)據(jù),海量的用戶, 那為了要滿足大量數(shù)據(jù)的寫入和查詢, 以及高可用, 一臺單機的存儲服務器肯定是不能滿足需求的, 通常需要使用多臺服務器形成分布式存儲。

場景描述:

在本文中, 為了方便大家更好的理解, 這里列出了一個簡單的例子, 有三位用戶, 分別是 James、 Bob、 Lee, 我們需要把用戶的圖片寫入到存儲服務器節(jié)點, 這里有ABC三個節(jié)點, 而且當查詢用戶的圖片時, 還需要快速定位到這個用戶的圖片是在哪個節(jié)點存儲的, 然后直接從這個節(jié)點進行查詢, 需要滿足高效率的查詢。

實現(xiàn)思路:

首先,我們可以對用戶標識進行 Hash 計算, 這里我為了方便演示, 使用了用戶名作為Hash對象, 當然你還可以對用戶的IP或者是UserId 進行Hash計算, Hash計算后會生成一個int類型的數(shù)字, 然后再根據(jù)存儲節(jié)點的數(shù)量進行取模, 這里的公式就是 hash(name) % 3, 計算得出的結(jié)果只有三種情況, 分別是 0,1,2, 然后我們再把這三種結(jié)果和三個存儲節(jié)點做一個映射, 0 ==> A, 1 ==> B, 2 == C。 因為Hash算法對一個值多次計算后都會得到同樣的hash值, 所以上面的公式, 一個用戶的圖片每次都會固定的寫入的其中一個節(jié)點, 這樣做查詢的話, 也可以通過hash算法快速找到這個用戶的圖片所在的節(jié)點。

缺點:

上面我們使用Hash算法實現(xiàn)了負載均衡, 可以根據(jù)用戶名路由到圖片所在的節(jié)點, 但是上面的方法也有一個很大的缺點, 那就是當服務器的數(shù)量增加或者減少時, 我們通過Hash算法生成的路由規(guī)則就再不準確了。

試想一下, 如果新增或者減少一個節(jié)點, 上面的公式就會變成 hash(name) % 4 或者 hash(name) % 2, 這里的關鍵點是, 我們之前用3取模, 現(xiàn)在變成用4或者2取模, 結(jié)果當然大概率是不一樣了, 當然如果 Hash后是12的話,用3或者4取模得到的結(jié)果都是為0, 不過這種概率比較小。

這個問題帶來的影響是, 路由規(guī)則不再準確, 大部分的查詢請求都撲了空。那么如何解決這個問題呢？相信有的同學這時應該有了一些想法, 是的沒錯, 關鍵點就在于, 不管節(jié)點的數(shù)量怎么變化, 都應該使用一個固定的值來進行取模！ 只有這樣才能保證每次進行Hash計算后, 得出的結(jié)果是不變的!

一致性Hash算法

同樣的,一致性Hash算法也是利用取模的方式, 不過通常是用一個很大的數(shù)字進行求模, 你可以用整數(shù)的最大值 int.Max, 2的32次方, 當然這個并沒有要求, 不過越大的數(shù)字, 平均分配的概率就越大(后面會具體介紹這個問題)。

為了方便理解, 這里我用 1000 來取模, 我們可以用一個長度為1000的數(shù)組表示它,就像這樣

接下來, 我們先不對用戶的圖片進行Hash處理, 而是先對每個節(jié)點進行 Hash 處理和映射, 現(xiàn)在的公式分別是 hash(A) % 1000, hash(B) % 1000,hash(C) % 1000, 這樣得出的結(jié)果一定是在0-999 之間, 然后把這個值映射到數(shù)組中, 在代碼中, 你可以用一個字典集合來保存這個映射關系。

對應的存儲節(jié)點和數(shù)組的映射可能如下：

那現(xiàn)在用戶的圖片怎么和存儲節(jié)點對應呢？ 因為存儲節(jié)點已經(jīng)映射到了數(shù)組上, 我們現(xiàn)在可以通過范圍區(qū)間的方式, 來找到對應的節(jié)點, 映射在數(shù)組上的圖片可以向右查找, 找到了一個節(jié)點, 那么這個圖片就屬于這個節(jié)點, 當往右查找到最大值時,再回到最左邊從0開始。

我在圖中用不同的顏色標記了每個存儲服務器的范圍區(qū)間, 你可以理解一下

接下來, 我們就需要對用戶的圖片進行Hash計算取模,同樣的,計算結(jié)果一定還是在0-999的范圍內(nèi), 然后再把這些值映射到數(shù)組上, 映射的結(jié)果可能如下圖:

這樣就可以通過往右查找的方式, 找到用戶的圖片相對應的存儲節(jié)點! 總結(jié)下來上面做了幾件事情, 首先我們?nèi)∫粋€固定的并且比較大的整數(shù)進行求模, 然后在對每個節(jié)點進行Hash計算求模, 這樣可以找出每個節(jié)點所對應的范圍區(qū)間, 最后再把用戶的圖片進行Hash計算求模, 最后根據(jù)范圍區(qū)間確定圖片的所在的存儲節(jié)點。

那我們看看使用了這種方式, 當存儲節(jié)點的增加和減少時會有什么影響？

節(jié)點增加場景

這里我新增了一個存儲節(jié)點D, 經(jīng)過Hash計算后映射在數(shù)組上, 這樣的話, 用戶 James 本來是路由到C節(jié)點的,現(xiàn)在被路由到了D節(jié)點, 不過我們添加了D節(jié)點后, 受到影響的也只有C節(jié)點, 其實不管D節(jié)點映射到數(shù)組哪一個位置, 都只會有一個節(jié)點會受到影響, 其他的節(jié)點可以正常使用。

那么這種情況下, 如何做數(shù)據(jù)遷移? 我的思路是, 我們需要把C節(jié)點全部數(shù)據(jù)重新進行Hash計算, 然后根據(jù)計算結(jié)果, 一部分會移動到D節(jié)點, 一部分繼續(xù)保留在C節(jié)點。

節(jié)點減少場景

假如現(xiàn)在 A 節(jié)點在晚上20點宕機了, 那么本來應該路由到A節(jié)點的數(shù)據(jù), 現(xiàn)在就被路由到了節(jié)點C, 也就是圖中的 Bob的數(shù)據(jù), 但是這種情況下, 其他的節(jié)點是不會受到節(jié)點變動的影響, 等到晚上21點時, A節(jié)點又恢復了正常。

這種情況的數(shù)據(jù)遷移的思路是, 當A節(jié)點宕機后, 數(shù)據(jù)需要全部復制到C節(jié)點, 當A節(jié)點恢復正常后, 再把C節(jié)點20:00至21:00的數(shù)據(jù)重新Hash計算, 然后根據(jù)計算的結(jié)果, 一部分會移動到A節(jié)點, 一部分繼續(xù)保留在C節(jié)點。

節(jié)點分布不均勻

因為節(jié)點是隨機的散列分布在數(shù)組上,所以有的節(jié)點的范圍比較大, 而有的節(jié)點的范圍比較小, 這樣我們的數(shù)據(jù)分布就不均勻, 有的節(jié)點服務器會有比較大的請求壓力。

這種情況有的同學可能會說, 我可以根據(jù)數(shù)組的長度(1000)和節(jié)點(3)的個數(shù), 求出平均值, 然后就可以平均的把節(jié)點散列到數(shù)組上, 這樣每個節(jié)點的請求壓力都是一樣的, 這種方式看起來沒什么問題, 但是當添加節(jié)點或者移除節(jié)點的時候, 每個節(jié)點的覆蓋范圍都需要重新計算, 然后也需要遷移數(shù)據(jù), 影響的范圍還是挺大的。

虛擬節(jié)點

之前我們用了三個存儲節(jié)點, 發(fā)現(xiàn)有分布不均勻的情況, 上圖是我做了一個簡單的測試, x 軸是節(jié)點的數(shù)量, y 軸是標準偏差, 根據(jù)這個圖的趨勢得出的結(jié)論是, 節(jié)點越多的時候, 標準偏差也就越小, 節(jié)點分布的就越均勻。

實際中,服務器節(jié)點是有限的, 增加很多節(jié)點也肯定是不現(xiàn)實的, 那么就可以在服務器節(jié)點不變的情況下, 引入虛擬節(jié)點, 也叫做影子節(jié)點。

還記得我們之前是怎么對節(jié)點做hash映射的嗎?公式是 hash(node) / 1000, 我們現(xiàn)在可以給A節(jié)點創(chuàng)建10個虛擬節(jié)點, 分別是 A1, A2,A3..., A10, 對應的虛擬節(jié)點的公式就是 hash(A1) / 1000 等等。這些虛擬節(jié)點和真實節(jié)點存在映射關系, 當圖片映射到A節(jié)點的任意一個虛擬節(jié)點上時, 我們就把這個圖片路由到A存儲節(jié)點, 現(xiàn)在數(shù)組上已經(jīng)有了30個虛擬節(jié)點做映射, 分布也比之前更均勻了, 當然你也可以創(chuàng)建更多的虛擬節(jié)點, 這些真實節(jié)點和虛擬節(jié)點的映射關系要保存在內(nèi)存中或者是數(shù)據(jù)庫中, 現(xiàn)在我們的映射圖如下, 這里我給每個真實節(jié)點都添加了3個虛擬節(jié)點。

引入了虛擬節(jié)點后, 在數(shù)組的映射看起來平均很多了, 現(xiàn)在我們每個真實節(jié)點的請求壓力都是一樣的了, 接下來, 我們還要看下這個方案在節(jié)點的變動情況下應該怎么處理。

增加節(jié)點

現(xiàn)在增加了一個節(jié)點D,按照上面的規(guī)則, 實際上是要添加 D 的虛擬節(jié)點, D1,D2,D3,然后散列映射到數(shù)組上,如下圖所示:

先看最左邊, D1 插入到了 C2 和 A1 之間, 而A1和A節(jié)點對應, D1節(jié)點和D節(jié)點對應, 也就是說A節(jié)點的一部分數(shù)據(jù)要遷移到D節(jié)點, 這里我的思路是, 當在節(jié)點寫入數(shù)據(jù)時, 同時把虛擬節(jié)點的信息也記錄下來,這樣就很方便做數(shù)據(jù)遷移了, 我們可以在A節(jié)點中只找出A1虛擬節(jié)點的數(shù)據(jù), 而不是全部, 然后Hash計算映射后, 根據(jù)計算結(jié)果,一部分同步到D節(jié)點, 一部分保持不變。后邊的數(shù)據(jù)也可以按照這個思路進行數(shù)據(jù)遷移。

節(jié)點減少

當C節(jié)點下線的時候, 我們同時要移除和C節(jié)點對應的虛擬節(jié)點,C1,C2,C3, 然后就是數(shù)據(jù)遷移的工作了, 根據(jù)圖中的表示, 可以直接把 C節(jié)點中的C2節(jié)點的數(shù)據(jù)遷移到A1節(jié)點, C1遷移到B3,C3遷移到B1中, 完成！

總結(jié)

本文介紹了哈希和一致性哈希算法, 以及提供了一些數(shù)據(jù)遷移的思路, 回顧下這個方案, 首先需要定義一個比較大的固定值用于取模, 然后創(chuàng)建和真實節(jié)點對應的虛擬節(jié)點, 最后再把虛擬節(jié)點映射到數(shù)組上, 通過范圍區(qū)間的方法, 來確定圖片屬于哪一個存儲節(jié)點。

可能還有同學會說, 一致性hash也有緩存失效的時候,也需要手動遷移數(shù)據(jù)。 是的, 維基百科對一致性Hash的定義是, 當節(jié)點的數(shù)量變動時,可以允許少部分的數(shù)據(jù)進行遷移, 而大部分的數(shù)據(jù)還是不變的。

上面的一致性Hash算法其實是經(jīng)典的哈希環(huán)算法, 當然還有其他的算法, 比如跳躍一致性哈希法, 有興趣也可以看一下。

以上就是一篇文章讀懂哈希與一致性哈希算法的詳細內(nèi)容，更多關于Java哈希與一致性哈希算法的資料請關注腳本之家其它相關文章！