?

背景

?

09 年初，我們做了一個 memcached 的智能客戶端庫，業務只要將這個庫鏈上，就能跟 memcached 服務器通信。并且實現了一致性哈希的分布式算法，后端 memcached 服務器可以無限制擴展，而且客戶端能對 memcached 做自動故障轉移以及恢復。

我們知道，在沒有對數據做冗余存儲的情況下，無論是一致性哈希還是求余數分布式算法，在新增或刪除 memcached 節點時，命中率都會不同程度的降低。本文旨在解決當新增 memcached 節點時，如何保證命中率不變。

?

?

基本原理

?

當 新增一個 memcached 節點時，將該新節點的下一個節點的且屬于該新節點的數據遷移過來。

?

上面的這個基本原理讀起來可能會比較拗口，容我下面詳細說明。

?

?

原理描述

?

如圖 1 所示，假設當前哈希環上有 n 個 memcached 節點，記為 M 1 ~M n ，存儲到這些節點上的數據的有效期都是一致的，記為 T e 。因此從圖 1 可以看出，從 M 1 到 M k 區間的數據均從 M k 上存取。比如數據 K 1 ， K 2 ， K n 。

?????????
??????????????????
????

???????????????????????????????????????????????????????????? ?????????????? 圖1

當新增節點 M x 時，如圖 2 所示。

??????????????????
?????????????????????
????????????????? ?

????????????????????????????????????????????????????????????????????????????? 圖2

此時數據 K 1 ， K 2 從新節點 M x 讀取不到的，但節點 M k 存儲了這些數據，我們需要做的就是將這些數據遷移到新節點 M x 。

?

具體做法是：將新加入的節點 M x 標記為 N （ New ）狀態，表示該節點是新增的。在 N 狀態下讀取數據 K 1 的步驟為：

1） 從 M x 讀取數據，如果讀取得到，則返回，否則進行 2 ）；

2） 從 M k 讀取數據，如果讀取不到，則返回，否則進行 3 ）；

3） 將讀取到的數據 K 1 寫入 M x ；

4） 將 K 1 從 M k 刪除；

?

在 N 狀態下，不斷進行上面的 4 個步驟

?

因為數據的有效期是 T e ，所以在經過 T e 時間后， M k 上的數據隨之自動失效了，此時將 M x 標記為 O （ Old ）狀態，在 O 狀態下，如果讀取不到數據也立即返回，無需再次到它下一個節點嘗試讀取。