分散式的一致性hash問題？

01-14

我們在使用memchache做分散式緩存時，通常採用一致性hash演算法加虛擬節點的策略，但我有幾個疑問，不太明白，如下：
先說明一下應用場景：分別在兩台機器上部署了memchache的一個實例，為簡化描述，標記為a，b，其中每個實例分配兩個虛擬節點，a1，a2；b1，b2；
我的問題是：

1. 在memchache客戶端，會採用某種hash演算法將各節點分布到hash環上，如計算各memchache的ip地址 + 編號等等，但是如果某幾個節點的hash值相同怎麼辦？特別是當memchache的節點很多時，除非類似於算md5，否則很難保證不碰撞。大家是怎麼處理這種情況的？
2. memchache客戶端會維護一個node列表，如 a，a1, a2，b，b1，b2，根據要訪問的key，計算hash（key）來確定訪問哪個node。這就意味著memchache客戶端與各memchache實例之間需要建立長連接。一旦memchache客戶端檢測到某個node不可用（比如連接斷開了），則根據一致性hash演算法，自動選擇另一個node。我的問題是：我有多個自己的業務伺服器，各自通過memchache客戶端來訪問memchache，也就是說，存在多個memchache客戶端訪問同一個memchache集群，那就存在一種不可避免的情況： memchache客戶端1與node a連接正常，但是memchache客戶端2與node a卻斷開了...總而言之，沒法保證各memchache客戶端之間維護的node列表是完全一致的，當然，這種情況並不常見，但如果出現了，該怎麼處理？是否有好的解決辦法？

第一次在知乎提問，謝謝

問題1，很少會出現這個問題的，一個是ip地址不一樣，編號不一樣，也可以用人起的名字代替IP地址，另一個是選取好的哈希演算法，甚至選取好的種子。

另外兩個節點，四個虛擬節點不覺得少了點嗎？任一節點宕機，都會導致50%數據搬家，是否用一致性哈希意義不大啊。

ip地址 + 編號會重？那至少說明你的網路已經出問題了吧。

再說「cache」這個詞的意思就是說你不一定在裡面能找到你想要的東西，斷了重連之後你就假裝自己面對的是一個剛啟動的什麼都沒有的cache，然後該咋辦咋辦。

特別是當memchache的節點很多時，除非類似於算md5，否則很難保證不碰撞。

不衝突的hash演算法是不存在的，只要虛擬節點夠多，保證在概率上每個真實節點的負載是相等的就好了。

存在多個memchache客戶端訪問同一個memchache集群，那就存在一種不可避免的情況： memchache客戶端1與node
a連接正常，但是memchache客戶端2與node
a卻斷開了...總而言之，沒法保證各memchache客戶端之間維護的node列表是完全一致的，

這個是經典的分散式中的partition的問題， 一致性hash演算法本身就要解決這個問題，而且得到了證明(具體證明可以去google一下一致性hash最早的論文). 這個性質叫分散性 (Spread) : 當上游的機器看到不同的下游列表時(在上線時及不穩定的網路中比較常見), 同一個請求盡量映射到少量的節點中。

另外說句題外話，這個問題和 分散式一致性 沒有任何關係. 分散式一致性英文叫做 distributed consensus. 一致性hash叫做 consistent hashing. 完全是兩回事情，不能混為一談，一致性hash保證不了任何的分散式一致性，只是一種降低cachemiss的負載均衡而已。

比較贊同 @陳章義的回答，補充一下個人見解。

問題的關鍵點在於「節點很多」，「hash碰撞」，「心跳」，「失效處理」。

1. 首先說節點不會很多

實際使用中，不只資料庫需要垂直切分，緩存也需要垂直切分，以避免在資源緊張的情況下不同業務對資源的爭搶。MC是不知道你的業務哪個最重要，也沒法屏蔽垃圾代碼。

如果你確實有如此大的業務模塊，那我覺得你其它地方早已經產生瓶頸了。

2. 其次說hash碰撞

綜上一個C段好了把，200+機器，hash碰撞概率極小了。

3. 然後是心跳

200+機器規模下，就算長連接也可接受，當然有些浪費。

一般的處理邏輯是發現節點失效，使用下一節點。

4. 失效處理

一致性哈希失效處理是有些問題，但和問題中描述的不太相同。

應該盡量確保服務組件和MC集群之間網路的穩定性。緩存肯定是就近部署的，要不然還有啥用。

而且可以這麼理解，如果你集群內部網路都出問題了，那對外提供的服務。。。

其實比較容易出現的問題是漂移的問題：某個節點失效了，緩存都漂到下個節點了；然後一會它又恢復了，這時候它就有臟數據了。

解決辦法一是每個節點引入集群。

不用集群想徹底解決這個問題，可能需要引入第三方健康檢查組件，如Consul，發現節點不穩定立即刪除下線。

5. 緩存命中率及單一熱點問題

一致性哈希解決的是某節點宕機後緩存失效的問題，只會導致相鄰節點負載增加。但是因為宕機後需要重新從資料庫讀取，會導致此時緩存命中率下降及db壓力增加。

也無法避免單一熱點問題。某一數據被海量請求，不論怎麼哈希，哈希環多大，數據只存在一個節點，早晚有被打垮的時候。

此時的解決策略是每個節點主備或主主集群。