一致性哈希算法原理是什么

本篇內(nèi)容主要講解“一致性哈希算法原理是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“一致性哈希算法原理是什么”吧!

【哈希算法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨后的哈希都將產(chǎn)生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的，所以數(shù)據(jù)的哈希值可以檢驗數(shù)據(jù)的完整性。一般用于快速查找和加密算法。[1] 】

理解起來稍稍有些吃力，沒關(guān)系，用一個簡單的hash算法來理解以下上面那段話：

  int plusHash(String key, int cnt)
 {
  int hash, i;
  for (hash = key.length(), i = 0; i < key.length(); i++)
   hash += key.charAt(i);
  return (hash % cnt );
 }

上面這段算法，通常稱之為加法hash，輸入：key=zhuganglie，cnt=23，輸出：22

看看這段代碼，基本上上面那段不太好理解的內(nèi)容就相對容易一些了。

一致性哈希提出了在動態(tài)變化的Cache環(huán)境中，重點解決單調(diào)性的問題，單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應(yīng)的緩沖中，又有新的緩沖區(qū)加入到系統(tǒng)中，那么哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖區(qū)中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。 （請注意，以上是網(wǎng)上大多數(shù)技術(shù)文的說法，也不知道是來自于哪位大神的翻譯，按照我的理解，所謂單調(diào)性應(yīng)該指的是，當有新的緩沖區(qū)加入系統(tǒng)中的情況下，應(yīng)該盡量保證原有已分配內(nèi)容，不會被重新映射到新的緩沖區(qū)中去）

實際場景：現(xiàn)有n臺服務(wù)器，構(gòu)成一個服務(wù)器集群，現(xiàn)有算法是通過hash(obj) % n，來找到某一個請求對應(yīng)的服務(wù)器，如果某一臺服務(wù)器宕機了，就變成了 hash(obj) % n-1 ，顯而易見，這時候會發(fā)生大量的訪問錯誤，如果避免這種情況。

所謂一致性哈希，一致性究竟體現(xiàn)在什么地方，假設(shè)我們目前有4個對象和4個cache server，對這8個對象，采用統(tǒng)一的hash值空間，假定為1024。將此1024個值空間，想象成為一個環(huán)形結(jié)構(gòu)。而4個對象和4個cache server，分別落在這1024個值當中的不同位置。

如上圖所示，圓環(huán)是一個1024的值空間，我們把s1~s4這4臺server和obj1~obj4這4個對象，分別落入這個值空間當中去，然后按照順時針方向，為每一個obj，找到它所在的cache server。

對應(yīng)結(jié)果是obj1~s2，obj2~s3，obj3~s4，obj4~s1。

考慮幾種情況：

1、移除：s3發(fā)生了故障，上圖變成了下面這個樣子，新的對應(yīng)關(guān)系變成了下面這個樣子：

obj1~s2，obj2~s4，obj3~s4，obj4~s1。 我們看到，只有obj2的映射關(guān)系發(fā)生了變化。

2、添加：新增一個s5，新的結(jié)構(gòu)如下所示，在這種情況下，映射關(guān)系甚至不會發(fā)生任何變化，如果s3和s5之間，有obj存在，也只是這一部分obj的映射關(guān)系發(fā)生了變化。

看到這里，單調(diào)性的問題，已經(jīng)有了很好的解決方式。

下一步，還需要解決數(shù)據(jù)傾斜的問題，上面我們有了5臺真實服務(wù)器，再把這個情況進一步極端化，我們只有2臺真實服務(wù)器，我們是無法保證所有數(shù)據(jù)對象的hash值在環(huán)上均勻分布的，這樣就會出現(xiàn)數(shù)據(jù)傾斜的問題。為了解決這一問題，我們還需要里另一個概念，虛擬節(jié)點。

首先是一個只有2臺真實服務(wù)器的圖，我們看到數(shù)據(jù)傾斜是比較嚴重的。

然后我們把2臺真實服務(wù)器從環(huán)形結(jié)構(gòu)當中拿掉，換成8個虛擬服務(wù)器，這8個虛擬服務(wù)器，交替的屬于2臺真實服務(wù)器，這樣的話，數(shù)據(jù)傾斜問題，得到了極大地緩解。

到此，相信大家對“一致性哈希算法原理是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！