基於分歧性hash算法(consistent hashing)的應用詳解。本站提示廣大學習愛好者：（基於分歧性hash算法(consistent hashing)的應用詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是基於分歧性hash算法(consistent hashing)的應用詳解正文
1 根本場景
好比你有 N 個 cache 辦事器（前面簡稱 cache ），那末若何將一個對象 object 映照到 N 個 cache 上呢，你極可能會采取相似上面的通用辦法盤算 object 的 hash 值，然後平均的映照到到 N 個 cache ；
hash(object)%N
一切都運轉正常，再斟酌以下的兩種情形；
1 一個 cache 辦事器 m down 失落了（在現實運用中必需要斟酌這類情形），如許一切映照到 cache m 的對象都邑掉效，怎樣辦，須要把 cache m 從 cache 中移除，這時候候 cache 是 N-1 台，映照公式釀成了 hash(object)%(N-1) ；
2 因為拜訪減輕，須要添加 cache ，這時候候 cache 是 N+1 台，映照公式釀成了 hash(object)%(N+1) ；
1 和 2 意味著甚麼？這意味著忽然之間簡直一切的 cache 都掉效了。關於辦事器而言，這是一場災害，洪水般的拜訪都邑直接沖向後台辦事器；
再來斟酌第三個成績，因為硬件才能愈來愈強，你能夠想讓前面添加的節點多做點活，明顯下面的 hash 算法也做不到。
有甚麼辦法可以轉變這個狀態呢，這就是 consistent hashing...
2 hash 算法和單調性
Hash 算法的一個權衡目標是單調性（ Monotonicity ），界說以下：
單調性是指假如曾經有一些內容經由過程哈希分配到了響應的緩沖中，又有新的緩沖參加到體系中。哈希的成果應可以或許包管原有已分派的內容可以被映照到新的緩沖中去，而不會被映照到舊的緩沖聚集中的其他緩沖區。
輕易看到，下面的簡略 hash 算法 hash(object)%N 難以知足單調性請求。
3 consistent hashing 算法的道理
consistent hashing 是一種 hash 算法，簡略的說，在移除 / 添加一個 cache 時，它可以或許盡量小的轉變已存在 key 映照關系，盡量的知足單調性的請求。
上面就來依照 5 個步調簡略講講 consistent hashing 算法的根本道理。
3.1 環形hash 空間
斟酌平日的 hash 算法都是將 value 映照到一個 32 為的 key 值，也等於 0~2^32-1 次方的數值空間；我們可以將這個空間想象成一個首（ 0 ）尾（ 2^32-1 ）相接的圓環，以下面圖 1 所示的那樣。
圖 1 環形 hash 空間
3.2 把對象映照到hash 空間
接上去斟酌 4 個對象 object1~object4 ，經由過程 hash 函數盤算出的 hash 值 key 在環上的散布如圖 2 所示。
hash(object1) = key1;
… …
hash(object4) = key4;
圖 2 4 個對象的 key 值散布
3.3 把cache 映照到hash 空間
Consistent hashing 的根本思惟就是將對象和 cache 都映照到統一個 hash 數值空間中，而且應用雷同的 hash 算法。
假定以後有 A,B 和 C 共 3 台 cache ，那末其映照成果將如圖 3 所示，他們在 hash 空間中，以對應的 hash 值分列。
hash(cache A) = key A;
… …
hash(cache C) = key C;
圖 3 cache 和對象的 key 值散布
說到這裡，趁便提一下 cache 的 hash 盤算，普通的辦法可使用 cache 機械的 IP 地址或許機械名作為 hash 輸出。
3.4 把對象映照到cache
如今 cache 和對象都曾經經由過程統一個 hash 算法映照到 hash 數值空間中了，接上去要斟酌的就是若何將對象映照到 cache 下面了。
在這個環形空間中，假如沿著順時針偏向從對象的 key 值動身，直到碰見一個 cache ，那末就將該對象存儲在這個 cache 上，由於對象和 cache 的 hash 值是固定的，是以這個 cache 必定是獨一和肯定的。如許不就找到了對象和 cache 的映照辦法了嗎？！
仍然持續下面的例子（拜見圖 3 ），那末依據下面的辦法，對象 object1 將被存儲到 cache A 上； object2 和 object3 對應到 cache C ； object4 對應到 cache B ；
3.5 考核cache 的更改
後面講過，經由過程 hash 然後求余的辦法帶來的最年夜成績就在於不克不及知足單調性，當 cache 有所更改時， cache 會掉效，進而對後台辦事器形成偉大的沖擊，如今就來剖析剖析 consistent hashing 算法。
3.5.1 移除 cache
斟酌假定 cache B 掛失落了，依據下面講到的映照辦法，這時候受影響的將僅是那些沿 cache B 逆時針遍歷直到下一個 cache （ cache C ）之間的對象，也等於原來映照到 cache B 上的那些對象。
是以這裡僅須要更改對象 object4 ，將其從新映照到 cache C 上便可；拜見圖 4 。
圖 4 Cache B 被移除後的 cache 映照
3.5.2 添加 cache
再斟酌添加一台新的 cache D 的情形，假定在這個環形 hash 空間中， cache D 被映照在對象 object2 和 object3 之間。這時候受影響的將僅是那些沿 cache D 逆時針遍歷直到下一個 cache （ cache B ）之間的對象（它們是也原來映照到 cache C 上對象的一部門），將這些對象從新映照到 cache D 上便可。
是以這裡僅須要更改對象 object2 ，將其從新映照到 cache D 上；拜見圖 5 。
圖 5 添加 cache D 後的映照關系
4 虛擬節點
考量 Hash 算法的另外一個目標是均衡性 (Balance) ，界說以下：
均衡性
均衡性是指哈希的成果可以或許盡量散布到一切的緩沖中去，如許可使得一切的緩沖空間都獲得應用。
hash 算法其實不是包管相對的均衡，假如 cache 較少的話，對象其實不能被平均的映照到 cache 上，好比在下面的例子中，僅安排 cache A 和 cache C 的情形下，在 4 個對象中， cache A 僅存儲了 object1 ，而 cache C 則存儲了 object2 、 object3 和 object4 ；散布是很不平衡的。
為懂得決這類情形， consistent hashing 引入了“虛擬節點”的概念，它可以以下界說：
“虛擬節點”（ virtual node ）是現實節點在 hash 空間的復成品（ replica ），一現實個節點對應了若干個“虛擬節點”，這個對應個數同樣成為“復制個數”，“虛擬節點”在 hash 空間中以 hash 值分列。
仍以僅安排 cache A 和 cache C 的情形為例，在圖 4 中我們曾經看到， cache 散布其實不平均。如今我們引入虛擬節點，並設置“復制個數”為 2 ，這就意味著一共會存在 4 個“虛擬節點”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假定一種比擬幻想的情形，拜見圖 6 。
圖 6 引入“虛擬節點”後的映照關系
此時，對象到“虛擬節點”的映照關系為：
objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；
是以對象 object1 和 object2 都被映照到了 cache A 上，而 object3 和 object4 映照到了 cache C 上；均衡性有了很年夜進步。
引入“虛擬節點”後，映照關系就從 { 對象 -> 節點 } 轉換到了 { 對象 -> 虛擬節點 } 。查詢物體地點 cache 時的映照關系如圖 7 所示。
圖 7 查詢對象地點 cache
“虛擬節點”的 hash 盤算可以采取對應節點的 IP 地址加數字後綴的方法。例如假定 cache A 的 IP 地址為 202.168.14.241 。
引入“虛擬節點”前，盤算 cache A 的 hash 值：
Hash(“202.168.14.241”);
引入“虛擬節點”後，盤算“虛擬節”點 cache A1 和 cache A2 的 hash 值：
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2
