哈希 Hash 算法介紹

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

md5("123456") => "e10adc3949ba59abbe56e057f20f883e"

主要特點(diǎn)：

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

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

分布式存儲場景

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

場景描述:

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

實(shí)現(xiàn)思路:

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

缺點(diǎn):

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

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

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

一致性Hash算法

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

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

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

對應(yīng)的存儲節(jié)點(diǎn)和數(shù)組的映射可能如下：

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

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

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

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

那我們看看使用了這種方式, 當(dāng)存儲節(jié)點(diǎn)的增加和減少時(shí)會(huì)有什么影響？

節(jié)點(diǎn)增加場景

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

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

節(jié)點(diǎn)減少場景

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

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

節(jié)點(diǎn)分布不均勻

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

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

虛擬節(jié)點(diǎn)

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

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

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

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

增加節(jié)點(diǎn)

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

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

節(jié)點(diǎn)減少

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

總結(jié)

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

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

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

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

最新評論