演算法一致性hash

『壹』 一致性hash演算法是什麼

一致性哈希演算法是在1997年由麻省理工學院提出的一種分布式哈希（DHT）演算法。其設計目標是為了解決網際網路中的熱點（Hot spot)問題，初衷和CARP十分類似。

一致性Hash是一種特殊的Hash演算法，由於其均衡性、持久性的映射特點，被廣泛的應用於負載均衡領域，如nginx和memcached都採用了一致性Hash來作為集群負載均衡的方案。

一致性哈希演算法的目標是，當K個請求key發起請求時。後台增減節點，只會引起K/N的key發生重新映射。即一致性哈希演算法，在後台節點穩定時，同一key的每次請求映射到的節點是一樣的。而當後台節點增減時，該演算法盡量將K個key映射到與之前相同的節點上。

優點

可擴展性。一致性哈希演算法保證了增加或減少伺服器時，數據存儲的改變最少，相比傳統哈希演算法大大節省了數據移動的開銷。

更好地適應數據的快速增長。採用一致性哈希演算法分布數據，當數據不斷增長時，部分虛擬節點中可能包含很多數據、造成數據在虛擬節點上分布不均衡，此時可以將包含數據多的虛擬節點分裂，這種分裂僅僅是將原有的虛擬節點一分為二、不需要對全部的數據進行重新哈希和劃分。

虛擬節點分裂後，如果物理伺服器的負載仍然不均衡，只需在伺服器之間調整部分虛擬節點的存儲分布。這樣可以隨數據的增長而動態的擴展物理伺服器的數量，且代價遠比傳統哈希演算法重新分布所有數據要小很多。

以上內容參考：網路-一致性哈希

『貳』 nginx 負載均衡之一致性hash，普通hash

哈希負載均衡原理
  ngx_http_upstream_hash_mole支持普通的hash及一致性hash兩種負載均衡演算法，默認的是普通的hash來進行負載均衡。
  nginx 普通的hash演算法支持配置http變數值作為hash值計算的key，通過hash計算得出的hash值和總權重的余數作為挑選server的依據；nginx的一致性hash(chash)演算法則要復雜一些。這里會對一致性hash的機制原理作詳細的說明。
一致性hash演算法的原理
一致性hash用於對hash演算法的改進，後端伺服器在配置的server的數量發生變化後，同一個upstream server接收到的請求會的數量和server數量變化之間會有變化。尤其是在負載均衡配置的upstream server數量發生增長後，造成產生的請求可能會在後端的upstream server中並不均勻，有的upstream server負載很低，有的upstream server負載較高，這樣的負載均衡的效果比較差，可能對upstream server造成不良的影響。由此，產生了一致性hash演算法來均衡。
   那麼為什麼一致性hash演算法能改善這種情況呢？這里引用網上資料的一致性hash演算法的圖例。
因為對於hash(k)的范圍在int范圍，所以我們將0~2^32作為一個環。其步驟為：
1，求出每個伺服器的hash（伺服器ip）值，將其配置到一個 0~2^n 的圓環上（n通常取32）。
2，用同樣的方法求出待存儲對象的主鍵 hash值，也將其配置到這個圓環上，然後從數據映射到的位置開始順時針查找，將數據分布到找到的第一個伺服器節點上。
其分布如圖：

除了上邊的優點，其實還有一個優點：對於熱點數據，如果發現node1訪問量明顯很大，負載高於其他節點，這就說明node1存儲的數據是熱點數據。這時候，為了減少node1的負載，我們可以在熱點數據位置再加入一個node，用來分擔熱點數據的壓力。
雪崩效應

接下來我們來看一下，當有節點宕機時會有什麼問題。如下圖：

如上圖，當B節點宕機後，原本存儲在B節點的k1，k2將會遷移到節點C上，這可能會導致很大的問題。如果B上存儲的是熱點數據，將數據遷移到C節點上，然後C需要承受B+C的數據，也承受不住，也掛了。。。。然後繼續CD都掛了。這就造成了雪崩效應。
上面會造成雪崩效應的原因分析：
如果不存在熱點數據的時候，每台機器的承受的壓力是M/2(假設每台機器的最高負載能力為M)，原本是不會有問題的，但是，這個時候A伺服器由於有熱點數據掛了，然後A的數據遷移至B，導致B所需要承受的壓力變為M（還不考慮熱點數據訪問的壓力），所以這個失敗B是必掛的，然後C至少需要承受1.5M的壓力。。。。然後大家一起掛。。。
所以我們通過上面可以看到，之所以會大家一起掛，原因在於如果一台機器掛了，那麼它的壓力全部被分配到一台機器上，導致雪崩。

怎麼解決雪崩問題呢，這時候需要引入虛擬節點來進行解決。
虛擬節點

虛擬節點，我們可以針對每個實際的節點，虛擬出多個虛擬節點，用來映射到圈上的位置，進行存儲對應的數據。如下圖：

如上圖：A節點對應A1，A2，BCD節點同理。這時候，如果A節點掛了，A節點的數據遷移情況是:A1數據會遷移到C2，A2數據遷移到D1。這就相當於A的數據被C和D分擔了，這就避免了雪崩效應的發送，而且虛擬節點我們可以自定義設置，使其適用於我們的應用。

ngx_http_upstream_consistent_hash
該模塊可以根據配置參數採取不同的方式將請求均勻映射到後端機器，比如：

指令
語法：consistent_hash variable_name
默認值：none
上下文：upstream

配置upstream採用一致性hash作為負載均衡演算法，並使用配置的變數名作為hash輸入。

參考文檔：
https://www.cnblogs.com/FengGeBlog/p/10615345.html
http://www.ttlsa.com/nginx/nginx-upstream-consistent-hash-mole/

『叄』 redis 數據分區--一致性hash&&虛擬槽分區

1.節點區域分區:
使用特定的數據,如redis的鍵或用戶ID,再根據節點數量N使用公式:hash(key)%N計算出hash值,用來決定數據映射到哪一個節點上.

這種方案的問題是:
當節點數量變化時,需要重新計算hash,會導致數據的重新遷移.

2.一致性hash演算法
一致性hash演算法實現思路是為系統中每一個節點分配一個token,范圍在0~2^32,這些token構成一個hash環.數據的讀寫執行節點查找操作時,先根據key計算hash值,然後順時針找到第一個大於等於該hash的token節點.

好處:
這種方式最大的好處就是,在加入或刪除節點時,隻影響hash環中相鄰的兩個節點,對其他節點無影響.

問題:

3.虛擬槽演算法

使用分散度較好的hash函數,將所有的數據映射到 比如0~16383(2^14)范圍的槽中(slot).這個槽的數量一般遠遠大於實例的數量.

槽是集群數據管理和遷移的基本單位.採用大范圍槽的主要目的是為了方便數據拆分和集群擴展.

每一個實例會映射一部分范圍的槽.

特點:
1.解耦數據和節點之間的關系,簡化擴容和鎖容的難度
2.節點自身維護槽的映射關系,不需要客戶端或代理服務維護槽分區的元數據.
3.支持節點,槽,鍵之間的映射查詢,用於數據路由,在線伸縮燈場景.

HashTags（面試）
Mset k1 v1 k2 v2 k3 v3
通過分片手段，可以將數據合理的劃分到不同的節點上，這本來是一件好事。但是有的時候，我們希望對相關聯的業務以原子性方式進行操作。舉個簡單的例子
我們在單節點上執行MSET （m表示多個，一次向redis設置多個key和值）, 它是一個原子性的操作，我們要求所有給定的key要在同一時間內被設置，不能出現某些指定的key被更新另一些指定的key沒有被更新的情況。但是在集群環境下，我們仍然可以執行MSET命令，但它的操作不在是原子操作，會存在某些指定的key被更新，而另外一些指定的key沒有改變，原因是多個key可能會被分配到不同的機器上。
所以，這里就會存在一個矛盾點，及要求key盡可能的分散在不同機器，又要求某些相關聯的key分配到相同機器。
這個也是在面試的時候會容易被問到的內容。怎麼解決呢？
從前面的分析中我們了解到，分片其實就是一個hash的過程，對key做hash取模然後劃分到不同的機器上。所以為了解決這個問題，我們需要考慮如何讓相關聯的key得到的hash值都相同呢？如果key全部相同是不現實的，所以怎麼解決呢？在redis中引入了HashTag的概念，可以使得數據分布演算法可以根據key的某一個部分進行計算，然後讓相關的key落到同一個數據分片；
舉個簡單的例子，假如對於用戶的信息進行存儲，
redis:store:1001、redis:store:1002
那麼通過hashtag的方式，
redis:{store}:1001、redis:{store}:1002; 表示
當一個key包含 {} 的時候，就不對整個key做hash，而僅對 {} 包括的字元串做hash。