單個節點的緩存容量達到上限 Hash算法一致性

場景

單個節點的緩存容量達到上限，無法繼續單點增加內存，如何解決？

單個節點支撐的QPS達到上限，如何解決？?

初步方案

增加N個緩存節點，為了保證緩存數據的均勻，一般情況會采用對key值hash，然后取模的方式，然后根據結果，確認數據落到哪臺節點上：如下：

hash(key)%N?

很好，這個的確解決了上面的問題，實現了初步的分布式緩存，數據均勻分散到了各個節點上，流量請求也均勻的分散到了各個節點。

但是如果出現以下情況，會帶來什么問題？

1、某臺服務器突然宕機。緩存服務器從N變為N-1臺。

2、緩存容量達到上限或者請求處理達到上限，需要增加緩存服務器，假定增加1臺，則緩存服務器從N變為N+1

上面的情況帶來的問題：

增加或者刪除緩存服務器的時候，意味著大部分的緩存都會失效。這個是比較致命的一點，緩存失效，如果業務為緩存不命中，查詢DB的話，會導致一瞬間DB的壓力陡增。可能會導致整個服務不可用。?

換種描述方式，我們需要解決怎么樣的問題？或者需求是怎樣的？

?????增刪機器時，希望大部分key依舊在原有的緩存服務器上保持不變。舉例來說：key1,key2,key3原先再Cache1機器上，現在增加一臺緩存服務器，希望key1,key2,key3依舊在Cache1機器上，而不是在Cache2機器上。?

改進方案（一致性Hash）

一致性哈希算法的簡單背景介紹（此段內容來自網絡）

一致性哈希算法在1997年由麻省理工學院提出的一種分布式哈希（DHT）實現算法，設計目標是為了解決因特網中的熱點(Hot spot)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡單哈希算法帶來的問題，使得分布式哈希（DHT）可以在P2P環境中真正得到應用。?

一致性hash算法提出了在動態變化的Cache環境中，判定哈希算法好壞的四個定義：（來自百度百科）

平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。
單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。?
分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。?
負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那么對于一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。

所以通過上面的定義可以看到，簡單的hash(key)%N的方式，違背了?單調性?的這個原則。原因如上面提到的，增刪機器的時候，原有的緩存大部分會失效，也就違背了單調性的原則。

介紹：

? ? 大部分文章都提到環形的hash空間，但是沒有講為什么是環形的。后面我會聊下我的想法。?

? ? 使用常見的hash算法可以把一個key值哈希到一個具有2^32個桶的空間中。也可以理解成，將key值哈希到 [0, 2^32) 的一個數字空間中。我們假設這個是個首尾連接的環形空間。如下圖：

? 假設我們現在有key1,key2,key3,key4 4個key值，我們通過一定的hash算法，將其對應到上面的環形hash空間中。

? ?k1=hash(key1);

? ?k2=hash(key2);

? ?k3=hash(key3);

? ?k4=hash(key4);

同樣的，假設我們有3臺cache服務器，把緩存服務器通過hash算法，加入到上述的環中。一般情況下是根據機器的IP地址或者唯一的計算機別名進行哈希。

c1=hash(cache1);

c2=hash(cache2);

c3=hash(cache3);

接下來就是數據如何存儲到cache服務器上了，key值哈希之后的結果順時針找上述環形hash空間中，距離自己最近的機器節點，然后將數據存儲到上面，如上圖所示，k1 存儲到 c3 服務器上， k4,k3存儲到c1服務器上， k2存儲在c2服務器上。用圖表示如下：

增刪機器的情況

假設cache3服務器宕機，這時候需要從集群中將其摘除。那么，之前存儲再c3上的k1，將會順時針尋找距離它最近的一個節點，也就是c1節點，這樣，k1就會存儲到c1上了，看一看下下面的圖，比較清晰。

摘除c3節點之后，只影響到了原先存儲再c3上的k1，而k3、k4、k2都沒有受到影響，也就意味著解決了最開始的解決方案（hash(key)%N）中可能帶來的雪崩問題。

增加節點原理和刪除時差不多~

新增C4節點之后，原先存儲到C1的k4，遷移到了C4，分擔了C1上的存儲壓力和流量壓力。

幾個問題：

1、為什么需要想象成環形？

? ? 為了保證節點宕機摘除之后，原先存儲在當前節點的key能找到可存儲的位置。舉個極端的例子，在不是環狀hash空間下，剛好緩存的服務器處于0這個位置，那么0之后是沒有任何節點信息的，那么當緩存服務器摘除的時候，以前存儲在這臺機器上的key便找不到順時針距離它最近的一個節點了。但如果是環形空間，0之后的最近的一個節點信息有可能是2^32-1這個位置，他可以找到0之后的節點。如下圖描述可能清晰一點。