雜湊演算法與一致性雜湊演算法

語言: CN / TW / HK
時間 2023-01-27 03:15:13

theme: orange

雜湊演算法

雜湊函式，又稱為雜湊函式、雜湊演算法。雜湊函式把任意長度的訊息或資料通過演算法壓縮成固定長度的摘要資訊，也稱為雜湊值。使得資料量變小，把資料的格式固定下來，雜湊值的格式通常是16進位制或者是10進位制。常見的雜湊演算法有MD5、SHA-1 `````` func main() { TestString := "this is a test"

Md5Inst := md5.New() Md5Inst.Write([]byte(TestString)) Result := Md5Inst.Sum([]byte("")) fmt.Printf("%x\n\n", Result)

Sha1Inst := sha1.New() Sha1Inst.Write([]byte(TestString)) Result = Sha1Inst.Sum([]byte("")) fmt.Printf("%x\n\n", Result) } /* Output: 54b0c58c7ce9f2a8b551351102ee0938

fa26be19de6bff93f70bc2308434e4a440bbad02 */

``````

主要特點
  • 不可逆， 從雜湊值推匯出原始資料是不可行的，也就是隻有加密過程，沒有解密過程。所以Hash演算法廣泛應用在現代密碼體系中
  • 抗碰撞， 理想的雜湊函式，不同的資訊進行雜湊後得到的值應該是不同的，但是從實際上來說，雜湊演算法其實是有可能發生碰撞的， 輸入的資訊是無窮的，而輸出的雜湊值長度是固定的，所以是有限的。好比要把10個蘋果放到9個抽屜裡面，肯定會有一個抽屜裝了多個蘋果，只不過雜湊演算法的碰撞的概率是非常小的，比如128位的雜湊值，就有2的128次方的空間。
  • 效率高， 在處理比較大的原生值時，也能快速的計算出雜湊值
  • 無規律， 資料的任何改變都會導致雜湊值發生改變。即如果輸入有微小不同，雜湊運算後的輸出一定不同
主要應用場景
  • 檔案校驗，雜湊演算法可以校驗資訊是否是相同的，這樣的優勢可以在檔案接收通過對比雜湊值判斷檔案是否正確
  • 數字簽名，由於雜湊值加密是不可逆的，可以很大程度上實現安全
  • 鑑權協議

為什麼要引入一致性雜湊演算法？

在網際網路中，通常面對的都是海量的資料，海量的使用者，那為了要滿足大量資料的寫入和查詢，以及高可用， 一臺單機的儲存伺服器肯定是不能滿足需求的，通常需要使用多臺伺服器構建叢集，形成分散式儲存。

這個過程也就是實現負載均衡的過程，最簡單的方式是引入一箇中間的負載均衡層，讓他將外界的請求輪流的轉發給內部的伺服器叢集，比如叢集有3個節點，外界請求也有3 個，那麼每個節點處理1個請求，達到了平均分配的目的

image.png

既然如此，我們為什麼不能使用雜湊演算法呢？

這裡列出了一個簡單的例子，有三位使用者，分別是 James、 Bob、 Lee, 我們需要把使用者的圖片寫入到儲存伺服器節點， 這裡有ABC三個節點， 而且當查詢使用者的圖片時， 還需要快速定位到這個使用者的圖片是在哪個節點儲存的，然後直接從這個節點進行查詢， 需要滿足高效率的查詢。

image.png

實現過程：
首先，我們可以對使用者標識進行雜湊計算，我們可以根據使用者名稱、使用者ID或者是使用者IP進行計算，這裡採用使用者名稱作為物件進行計算，計算會生成一個int型別的數字，然後再根據儲存節點的數量進行取模，這裡的公式就是 hash(name) % 3， 計算得出的結果只有三種情況，分別是 0，1，2

然後我們再把這三種結果和三個儲存節點做一個對映， 0 ==> A， 1 ==> B， 2 == C。因為Hash演算法對一個值多次計算後都會得到同樣的hash值， 所以上面的公式， 一個使用者的圖片每次都會固定的寫入的其中一個節點，這樣做查詢的話， 也可以通過hash演算法快速找到這個使用者的圖片所在的節點。

image.png

缺點： 雖然上面我們使用Hash演算法實現了負載均衡， 可以根據使用者名稱路由到圖片所在的節點伺服器， 但是上面的方法也有一個很大的缺點， 那就是當伺服器的數量增加或者減少時， 我們通過Hash演算法生成的路由規則就再不準確了

如果新增或者減少一個伺服器節點，上面的公式就會變成 hash(name) % 4 或者 hash(name) % 2， 這裡的關鍵點是，我們之前用3取模，現在變成用4或者2取模，結果當然大概率是不一樣了，這個問題帶來的影響是，路由規則不再準確，大部分的查詢請求都撲了空，也就是說當伺服器數量發生改變時，所有快取在一定時間內是失效的，當應用無法從快取中獲取資料時，則會向後端伺服器請求資料；同理，假設突然有一臺快取伺服器出現了故障，那麼我們則需要將故障機器移除，那麼快取伺服器數量從3臺變為2臺，同樣會導致大量快取在同一時間失效，造成了快取的雪崩，後端伺服器將會承受巨大的壓力，整個系統很有可能被壓垮

那麼如何解決這個問題呢？相信有的同學這時應該有了一些想法，是的沒錯，關鍵點就在於，不管節點的數量怎麼變化，都應該使用一個固定的值來進行取模！只有這樣才能保證每次進行Hash計算後，得出的結果是不變的。一致性雜湊演算法就很好地解決了分散式系統在擴容或者縮容時，發生過多的資料遷移的問題

一致性雜湊演算法

一致雜湊演算法也採用了取模運算，但與雜湊演算法不同的是，雜湊演算法是對節點的數量進行取模運算，而一致雜湊演算法是對一個很大的數（這個數可以用2^32，越大的數，平均分配的概率就越大）進行取模運算，是一個固定的值

實現步驟：
  1. 一致性雜湊演算法將整個雜湊值空間（對2^32取模的結果集）按照順時針方向組織成一個虛擬的圓環，圓環的正上方的點代表0。0點右側的第一個點代表1，以此類推，2、3、4、5、6……直到2^32-1，也就是說0點左側的第一個點代表2^32-1，我們把這個由 2^32 個點組成的圓環稱為hash環。

image.png

  1. 確定伺服器節點在雜湊環上的位置，具體可以選擇伺服器的IP或主機名作為關鍵字進行雜湊：hash(伺服器ID) % 2^32，我們使用得到的雜湊值代表伺服器節點，假設我們有3臺伺服器，經過雜湊計算，對映到了如圖的位置：

image.png

  1. 將資料對映到雜湊環上，對映的結果值往順時針方向找到的第一個節點就是儲存該資料的節點。我們對要查詢的 key-01 進行雜湊計算，確定此  key-01 對映在雜湊環的位置，然後從這個位置往順時針的方向找到第一個節點，就是儲存該  key-01 資料的節點。下圖中的   key-01 對映的位置，往順時針的方向找到第一個節點就是節點 A。

image.png

上述就是一致性雜湊定址方式，我們來看看，如果增加一個節點或者減少一個節點會發生大量的資料遷移嗎？

假設節點數量從 3 增加到了 4，新的節點 D 經過雜湊計算後對映到了下圖中的位置：

image.png

可以看到，key-01、key-03 都不受影響，只有 key-02  需要被遷移節點 D。

假設節點數量從 3 減少到了 2，比如將節點 A 移除：

image.png

可以看到，key-02 和 key-03 不會受到影響，只有 key-01 需要被遷移節點 B。

因此，在一致雜湊演算法中，如果增加或者移除一個節點，僅影響該節點在雜湊環上順時針相鄰的後繼節點，其它資料也不會受到影響。

不足之處：

上面這些圖中 3 個節點對映在雜湊環還是比較分散的，所以看起來請求都會「均衡」到每個節點。但是一致性雜湊演算法並不保證節點能夠在雜湊環上分佈均勻，這樣就會帶來一個問題，會有大量的請求集中在一個節點上

image.png

從圖上我們可以看到，有一半以上的資料都會定址到節點A，也就是訪問主要集中在節點A上，違背了負載均衡平均分配的目的。另外，在這種節點分佈不均勻的情況下，進行容災與擴容時，雜湊環上的相鄰節點容易受到過大影響，容易發生雪崩式的連鎖反應。因此可以通過設定虛擬節點的方式提高均衡度

通過虛擬節點提高均衡度

要想解決節點能在雜湊環上分配不均勻的問題，就是要有大量的節點，節點數越多，雜湊環上的節點分佈的就越均勻。

但問題是，實際中我們沒有那麼多節點。所以這個時候我們就加入虛擬節點，也就是對一個真實節點做多個副本。

具體做法是，不再將真實節點對映到雜湊環上，而是將虛擬節點對映到雜湊環上，並將虛擬節點對映到實際節點，所以這裡有「兩層」對映關係。 比如對每個節點分別設定 3 個虛擬節點：

  • 對節點 A 加上編號來作為虛擬節點：A-01、A-02、A-03
  • 對節點 B 加上編號來作為虛擬節點：B-01、B-02、B-03
  • 對節點 C 加上編號來作為虛擬節點：C-01、C-02、C-03

引入虛擬節點後，原本雜湊環上只有 3 個節點的情況，就會變成有 9 個虛擬節點對映到雜湊環上，雜湊環上的節點數量多了 3 倍。

image.png

可以看到，節點數量多了之後，節點在雜湊環上的分佈就相對均勻了，這時候，如果有訪問請求定址到「A-01」這個虛擬節點，接著再通過「A-01」虛擬節點找到真實節點 A，這樣請求就能訪問到真實節點 A 了。另外，虛擬節點除了會提高節點的均衡度，還會提高系統的穩定性。當節點變化時，會有不同的節點共同分擔系統的變化，因此穩定性更高。有了虛擬節點後，還可以為硬體配置更好的節點增加權重，比如對權重更高的節點增加更多的虛擬機器節點即可。

因此，帶虛擬節點的一致性雜湊方法不僅適合硬體配置不同的節點的場景，而且適合節點規模會發生變化的場景。

文章參考：

https://www.cnblogs.com/aganippe/p/16009141.html https://blog.csdn.net/a745233700/article/details/120814088

「」
「」