分散式資料快取中的一致性雜湊演算法
一致性雜湊演算法在分散式快取領域的 MemCache，負載均衡領域的 Nginx 以及各類 RPC 框架中都有廣泛的應用，它主要是為了解決傳統雜湊函式新增雜湊表槽位數後要將關鍵字重新對映的問題。
本文會介紹一致性雜湊演算法的原理及其實現，並給出其不同雜湊函式實現的效能資料對比，探討Redis 叢集的資料分片實現等，文末會給出實現的具體 github 地址。
Memcached 與客戶端分散式快取
Memcached 是一個高效能的分散式快取系統，然而服務端沒有分散式功能，各個伺服器不會相互通訊。它的分散式實現依賴於客戶端的程式庫，這也是 Memcached 的一大特點。比如第三方的 spymemcached 客戶端就基於一致性雜湊演算法實現了其分散式快取的功能。
其具體步驟如下:
- 向 Memcached 新增資料，首先客戶端的演算法根據 key 值計算出該 key 對應的伺服器。
- 伺服器選定後，儲存快取資料。
- 獲取資料時，對於相同的 key ，客戶端的演算法可以定位到相同的伺服器，從而獲取資料。
在這個過程中，客戶端的演算法首先要保證快取的資料儘量均勻地分佈在各個伺服器上，其次是當個別伺服器下線或者上線時，會出現資料遷移，應該儘量減少需要遷移的資料量。
客戶端演算法是客戶端分散式快取效能優劣的關鍵。
普通的雜湊表演算法一般都是計算出雜湊值後，通過取餘操作將 key 值對映到不同的伺服器上，但是當伺服器數量發生變化時，取餘操作的除數發生變化，所有 key 所對映的伺服器幾乎都會改變，這對分散式快取系統來說是不可以接收的。
一致性雜湊演算法能儘可能減少了伺服器數量變化所導致的快取遷移。
雜湊演算法
首先，一致性雜湊演算法依賴於普通的雜湊演算法。大多數同學對雜湊演算法的理解可能都停留在 JDK 的 hashCode 函式上。其實雜湊演算法有很多種實現，它們在不同方面都各有優劣，針對不同的場景可以使用不同的雜湊演算法實現。
下面，我們會介紹一下幾款比較常見的雜湊演算法，並且瞭解一下它們在分佈均勻程度，雜湊碰撞概率和效能等方面的優劣。
MD5 演算法：全稱為 Message-Digest Algorithm 5，用於確保資訊傳輸完整一致。是計算機廣泛使用的雜湊演算法之一，主流程式語言普遍已有 MD5 實現。MD5 的作用是把大容量資訊壓縮成一種保密的格式（就是把一個任意長度的位元組串變換成定長的16進位制數字串）。常見的檔案完整性校驗就是使用 MD5。
CRC 演算法：全稱為 CyclicRedundancyCheck，中文名稱為迴圈冗餘校驗。它是一類重要的，編碼和解碼方法簡單，檢錯和糾錯能力強的雜湊演算法，在通訊領域廣泛地用於實現差錯控制。
MurmurHash 演算法：高運算效能，低碰撞率，由 Austin Appleby 創建於 2008 年，現已應用到 Hadoop、libstdc++、nginx、libmemcached 等開源系統。Java 界中 Redis，Memcached，Cassandra，HBase，Lucene和Guava 都在使用它。
FNV 演算法：全稱為 Fowler-Noll-Vo 演算法，是以三位發明人 Glenn Fowler，Landon Curt Noll，Phong Vo 的名字來命名的，最早在 1991 年提出。 FNV 能快速 hash 大量資料並保持較小的衝突率，它的高度分散使它適用於 hash 一些非常相近的字串，比如 URL，hostname，檔名，text 和 IP 地址等。
Ketama 演算法：一致性雜湊演算法的實現之一，其他的雜湊演算法有通用的一致性雜湊演算法實現，只不過是替換了雜湊對映函式而已，但 Ketama 是一整套的流程，我們將在後面介紹。
一致性雜湊演算法
下面，我們以分散式快取場景為例，分析一下一致性雜湊演算法環的原理。
首先將快取伺服器（ ip + 埠號）進行雜湊，對映成環上的一個節點，計算出快取資料 key 值的 hash key，同樣對映到環上，並順時針選取最近的一個伺服器節點作為該快取應該儲存的伺服器。具體實現見後續的章節。
比如說，當存在 A，B，C，D 四個快取伺服器時，它們及其 key 值為1的快取資料在一致性雜湊環上的位置如下圖所示，根據順時針取最近一個伺服器節點的規則，該快取資料應該儲存在伺服器 B 上。
當要儲存一個 key 值為4的快取資料時，它在一致性雜湊環上的位置如下所示，所以它應該儲存在伺服器 C 上。
類似的，key 值為5，6的資料應該存在服務 D 上，key 值為7，8的資料應該儲存在服務 A 上。
此時，伺服器 B 宕機下線，伺服器 B 中儲存的快取資料要進行遷移，但由於一致性雜湊環的存在，只需要遷移key 值為1的資料，其他的資料的儲存伺服器不會發生變化。這也是一致性雜湊演算法比取餘映射演算法出色的地方。
由於伺服器 B 下線，key 值為1的資料順時針最近的伺服器是 C ，所以資料存遷移到伺服器 C 上。
現實情況下，伺服器在一致性雜湊環上的位置不可能分佈的這麼均勻，導致了每個節點實際佔據環上的區間大小不一。
這種情況下，可以增加虛節點來解決。通過增加虛節點，使得每個節點在環上所“管轄”的區域更加均勻。這樣就既保證了在節點變化時，儘可能小的影響資料分佈的變化，而同時又保證了資料分佈的均勻。
具體實現
下面我們實現 Memcached 分散式快取場景下的一致性雜湊演算法，並給出具體的測試效能資料。該實現借鑑了 kiritomoe 博文中的實現和 spymemcached 客戶端程式碼。具體實現請看我的github，地址為 github.com/ztelur/cons…
NodeLocator 是分散式快取場景下一致性雜湊演算法的抽象，它有一個 getPrimary 函式，接收一個快取資料的 key 值，輸出儲存該快取資料的伺服器例項。
public interface NodeLocator {
MemcachedNode getPrimary(String k);
}
複製程式碼
下面是通用的一致性雜湊演算法的實現，它使用 TreeMap 作為一致性雜湊環的資料結構，其 ceilingEntry 函式可以獲取環上最近的一個節點。 buildConsistentHashRing 函式中包含了構建一致性雜湊環的過程，預設加入了 12 個虛擬節點。
public class ConsistentHashNodeLocator implements NodeLocator {
private final static int VIRTUAL_NODE_SIZE = 12;
private final static String VIRTUAL_NODE_SUFFIX = "-";
private volatile TreeMap<Long, MemcachedNode> hashRing;
private final HashAlgorithm hashAlg;
public ConsistentHashNodeLocator(List<MemcachedNode> nodes, HashAlgorithm hashAlg) {
this.hashAlg = hashAlg;
this.hashRing = buildConsistentHashRing(hashAlg, nodes);
}
@Override
public MemcachedNode getPrimary(String k) {
long hash = hashAlg.hash(k);
return getNodeForKey(hashRing, hash);
}
private MemcachedNode getNodeForKey(TreeMap<Long, MemcachedNode> hashRing, long hash) {
/* 向右找到第一個key */
Map.Entry<Long, MemcachedNode> locatedNode = hashRing.ceilingEntry(hash);
/* 想象成為一個環，超出尾部取出第一個 */
if (locatedNode == null) {
locatedNode = hashRing.firstEntry();
}
return locatedNode.getValue();
}
private TreeMap<Long, MemcachedNode> buildConsistentHashRing(HashAlgorithm hashAlgorithm, List<MemcachedNode> nodes) {
TreeMap<Long, MemcachedNode> virtualNodeRing = new TreeMap<>();
for (MemcachedNode node : nodes) {
for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) {
// 新增虛擬節點的方式如果有影響，也可以抽象出一個由物理節點擴充套件虛擬節點的類
virtualNodeRing.put(hashAlgorithm.hash(node.getSocketAddress().toString() + VIRTUAL_NODE_SUFFIX + i), node);
}
}
return virtualNodeRing;
}
}
複製程式碼
在 getPrimary 函式中，首先使用 HashAlgorithm 計算出 key 值對應的雜湊值，然後呼叫 getNodeForKey 函式從 TreeMap 中獲取對應的最近的伺服器節點例項。
HashAlgorithm 是對雜湊演算法的抽象，一致性雜湊演算法可以使用各種普通的雜湊演算法，比如說 CRC ，MurmurHash 和 FNV 等。下面，我們將會對比各種雜湊演算法給該實現帶來的效能差異性。
效能測試
測試資料是評價一個演算法好壞的最為真實有效的方法，量化的思維模式一定要有，這也是程式設計師進階的法寶之一。我們以下面四個量化的指標對基於不同雜湊函式的一致性雜湊演算法進行評測。
- 統計每個伺服器節點儲存的快取數量，計算方差和標準差。測量快取分佈均勻情況，我們可以模擬 50000個快取資料，分配到100 個伺服器，測試最後個節點儲存快取資料量的方差和標準差。
- 隨機 下線10%的伺服器，重新分配快取，統計快取遷移比率。測量節點上下線的情況，我們可以模擬 50000 個快取資料，分配到100 個指定伺服器，之後 隨機 下線 10 個伺服器並重新分配這50000個數據，統計快取分配到不同伺服器的比例，也就是遷移比率。
- 使用JMH對不同雜湊演算法的執行效率進行對比。
具體評測演算法如下。
public class NodeLocatorTest {
/**
* 測試分佈的離散情況
*/
@Test
public void testDistribution() {
List<MemcachedNode> servers = new ArrayList<>();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
// 使用不同的DefaultHashAlgorithm進行測試，得出不同的資料
NodeLocator nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH);
// 構造 50000 隨機請求
List<String> keys = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
keys.add(UUID.randomUUID().toString());
}
// 統計分佈
AtomicLongMap<MemcachedNode> atomicLongMap = AtomicLongMap.create();
for (MemcachedNode server : servers) {
atomicLongMap.put(server, 0);
}
for (String key : keys) {
MemcachedNode node = nodeLocator.getPrimary(key);
atomicLongMap.getAndIncrement(node);
}
System.out.println(StatisticsUtil.variance(atomicLongMap.asMap().values().toArray(new Long[]{})));
System.out.println(StatisticsUtil.standardDeviation(atomicLongMap.asMap().values().toArray(new Long[]{})));
}
/**
* 測試節點新增刪除後的變化程度
*/
@Test
public void testNodeAddAndRemove() {
List<MemcachedNode> servers = new ArrayList<>();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
//隨機下線10個伺服器, 先shuffle，然後選擇0到90，簡單模仿隨機計算。
Collections.shuffle(servers);
List<MemcachedNode> serverChanged = servers.subList(0, 90);
NodeLocator loadBalance = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.NATIVE_HASH);
NodeLocator changedLoadBalance = new ConsistentHashNodeLocator(serverChanged, DefaultHashAlgorithm.NATIVE_HASH);
// 構造 50000 隨機請求
List<String> keys = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
keys.add(UUID.randomUUID().toString());
}
int count = 0;
for (String invocation : keys) {
MemcachedNode origin = loadBalance.getPrimary(invocation);
MemcachedNode changed = changedLoadBalance.getPrimary(invocation);
// 統計發生變化的數值
if (!origin.getSocketAddress().equals(changed.getSocketAddress())) count++;
}
System.out.println(count / 50000D);
}
static String[] ips = {...};
}
複製程式碼
JMH的測試指令碼如下所示。
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Thread)
public class JMHBenchmark {
private NodeLocator nodeLocator;
private List<String> keys;
@Benchmark
public void test() {
for (String key : keys) {
MemcachedNode node = nodeLocator.getPrimary(key);
}
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(JMHBenchmark.class.getSimpleName())
.forks(1)
.warmupIterations(5)
.measurementIterations(5)
.build();
new Runner(opt).run();
}
@Setup
public void prepare() {
List<MemcachedNode> servers = new ArrayList<>();
for (String ip : ips) {
servers.add(new MemcachedNode(new InetSocketAddress(ip, 8080)));
}
nodeLocator = new ConsistentHashNodeLocator(servers, DefaultHashAlgorithm.MURMUR_HASH);
// 構造 50000 隨機請求
keys = new ArrayList<>();
for (int i = 0; i < 50000; i++) {
keys.add(UUID.randomUUID().toString());
}
}
@TearDown
public void shutdown() {
}
static String[] ips = {...};
}
複製程式碼
分別測試了 JDK 雜湊演算法，FNV132 演算法，CRC 演算法，MurmurHash 演算法和Ketama 演算法，分別對應 DefaultHashAlgorithm 的 NATIVE_HASH ， FNV1_32_HASH ， CRC_HASH ， MURMUR_HASH 和 KETAMA_HASH 。具體資料如下所示。
虛擬槽分割槽
有些文章說，Redis 叢集並沒有使用一致性雜湊演算法，而是使用虛擬槽分割槽演算法。但是外網（地址見文末）上都說 Redis 使用的虛擬槽分割槽只是一致性雜湊演算法的變種，虛擬槽可以允許 Redis 動態擴容。
或許只有去了解一下Redis的原始碼才能對這個問題作出準確的回答。請了解的同學積極留言解答，謝謝。
github 地址： github.com/ztelur/cons… redis分散式討論的地址： www.reddit.com/r/redis/com…
個人部落格地址:remcarpediem