本文參考 嗨客網 Redis面試題
一緻性Hash
什麼是一緻性Hash
一緻性雜湊演算法在 1997 年由麻省理工學院的 Karger 等人在解決分布式 Cache 中提出的，設計目标是為了解決網際網路中的熱點(Hot spot)問題，初衷和 CARP 十分類似。
一緻性哈希修正了 CARP 使用的簡單雜湊演算法帶來的問題，使得 DHT 可以在 P2P 環境中真正得到應用。
一緻性Hash
現在一緻性 hash 算法在分布式系統中也得到了廣泛應用，研究過 memcached 緩存資料庫的人都知道，memcached 伺服器端本身不提供分布式 cache 的一緻性，而是由用戶端來提供，具體在計算一緻性 hash 時采用如下步驟：
- 首先求出 memcached 伺服器（節點）的哈希值，并将其配置到 0～232 的圓（continuum）上。
- 然後采用同樣的方法求出存儲資料的鍵的哈希值，并映射到相同的圓上。
- 然後從資料映射到的位置開始順時針查找，将資料儲存到找到的第一個伺服器上。如果超過 0～232 仍然找不到伺服器，就會儲存到第一台 memcached 伺服器上。
從上圖的狀态中添加一台 memcached 伺服器。餘數分布式算法由于儲存鍵的伺服器會發生巨大變化而影響緩存的命中率，但 Consistent Hashing 中，隻有在圓（continuum）上增加伺服器的地點逆時針方向的第一台伺服器上的鍵會受到影響，如下圖所示：
一緻性Hash性質
考慮到分布式系統每個節點都有可能失效，并且新的節點很可能動态的增加進來，如何保證當系統的節點數目發生變化時仍然能夠對外提供良好的服務，這是值得考慮的，尤其實在設計分布式緩存系統時，如果某台伺服器失效，對于整個系統來說如果不采用合适的算法來保證一緻性，那麼緩存于系統中的所有資料都可能會失效（即由于系統節點數目變少，用戶端在請求某一對象時需要重新計算其 hash 值（通常與系統中的節點數目有關），由于 hash 值已經改變，是以很可能找不到儲存該對象的伺服器節點），是以一緻性 hash 就顯得至關重要，良好的分布式cahce 系統中的一緻性 hash 算法應該滿足以下幾個方面：
平衡性(Balance)
平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多雜湊演算法都能夠滿足這一條件。
單調性(Monotonicity)
單調性是指如果已經有一些内容通過哈希分派到了相應的緩沖中，又有新的緩沖區加入到系統中，那麼哈希的結果應能夠保證原有已配置設定的内容可以被映射到新的緩沖區中去，而不會被映射到舊的緩沖集合中的其他緩沖區。簡單的雜湊演算法往往不能滿足單調性的要求，如最簡單的線性哈希：x = (ax + b) mod §，在上式中，P 表示全部緩沖的大小。不難看出，當緩沖大小發生變化時(從 P1 到 P2)，原來所有的哈希結果均會發生變化，進而不滿足單調性的要求。哈希結果的變化意味着當緩沖空間發生變化時，所有的映射關系需要在系統内全部更新。而在 P2P 系統内，緩沖的變化等價于 Peer 加入或退出系統，這一情況在 P2P 系統中會頻繁發生，是以會帶來極大計算和傳輸負荷。單調性就是要求雜湊演算法能夠應對這種情況。
分散性(Spread)
在分布式環境中，終端有可能看不到所有的緩沖，而是隻能看到其中的一部分。當終端希望通過哈希過程将内容映射到緩沖上時，由于不同終端所見的緩沖範圍有可能不同，進而導緻哈希的結果不一緻，最終的結果是相同的内容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導緻相同内容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的雜湊演算法應能夠盡量避免不一緻的情況發生，也就是盡量降低分散性。
負載
負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能将相同的内容映射到不同的緩沖區中，那麼對于一個特定的緩沖區而言，也可能被不同的使用者映射為不同的内容。與分散性一樣，這種情況也是應當避免的，是以好的雜湊演算法應能夠盡量降低緩沖的負荷。
平滑性(Smoothness)
平滑性是指緩存伺服器的數目平滑改變和緩存對象的平滑改變是一緻的。
原理
一緻性雜湊演算法（Consistent Hashing）最早在論文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。簡單來說，一緻性哈希将整個哈希值空間組織成一個虛拟的圓環，如假設某哈希函數H的值空間為 0-232-1（即哈希值是一個 32 位無符号整形），整個哈希空間環如下：
整個空間按順時針方向組織。0 和 232-1 在零點中方向重合。
下一步将各個伺服器使用 Hash 進行一個哈希，具體可以選擇伺服器的 ip 或主機名作為關鍵字進行哈希，這樣每台機器就能确定其在哈希環上的位置，這裡假設将上文中四台伺服器使用 ip 位址哈希後在環空間的位置如下：
接下來使用如下算法定位資料通路到相應伺服器：将資料 key 使用相同的函數 Hash 計算出哈希值，并确定此資料在環上的位置，從此位置沿環順時針 “行走”，第一台遇到的伺服器就是其應該定位到的伺服器。
例如我們有 Object A、Object B、Object C、Object D 四個資料對象，經過哈希計算後，在環空間上的位置如下：
根據一緻性雜湊演算法，資料 A 會被定為到 Node A 上，B 被定為到 Node B 上，C 被定為到 Node C 上，D 被定為到 Node D 上。
下面分析一緻性雜湊演算法的容錯性和可擴充性。現假設 Node C 不幸當機，可以看到此時對象 A、B、D 不會受到影響，隻有 C 對象被重定位到 Node D。一般的，在一緻性雜湊演算法中，如果一台伺服器不可用，則受影響的資料僅僅是此伺服器到其環空間中前一台伺服器（即沿着逆時針方向行走遇到的第一台伺服器）之間資料，其它不會受到影響。
下面考慮另外一種情況，如果在系統中增加一台伺服器 Node X，如下圖所示：
此時對象 Object A、B、D 不受影響，隻有對象 C 需要重定位到新的 Node X 。一般的，在一緻性雜湊演算法中，如果增加一台伺服器，則受影響的資料僅僅是新伺服器到其環空間中前一台伺服器（即沿着逆時針方向行走遇到的第一台伺服器）之間資料，其它資料也不會受到影響。
綜上所述，一緻性雜湊演算法對于節點的增減都隻需重定位環空間中的一小部分資料，具有較好的容錯性和可擴充性。
另外，一緻性雜湊演算法在服務節點太少時，容易因為節點分部不均勻而造成資料傾斜問題。例如系統中隻有兩台伺服器，其環分布如下，
此時必然造成大量資料集中到 Node A 上，而隻有極少量會定位到 Node B 上。為了解決這種資料傾斜問題，一緻性雜湊演算法引入了虛拟節點機制，即對每一個服務節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛拟節點。具體做法可以在伺服器 ip 或主機名的後面增加編号來實作。例如上面的情況，可以為每台伺服器計算三個虛拟節點，于是可以分别計算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3” 的哈希值，于是形成六個虛拟節點：
同時資料定位算法不變，隻是多了一步虛拟節點到實際節點的映射，例如定位到 “Node A#1”、“Node A#2”、“Node A#3” 三個虛拟節點的資料均定位到 Node A 上。這樣就解決了服務節點少時資料傾斜的問題。在實際應用中，通常将虛拟節點數設定為 32 甚至更大，是以即使很少的服務節點也能做到相對均勻的資料分布。
更多
原文連結：連結
其他：目錄
更多文章，可以關注下方公衆号：