分布式數據緩存中的一致性哈希算法

一致性哈希算法在分布式緩存領域的 MemCached，負載均衡領域的 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，地址為 https://github.com/ztelur/consistent-hash-algorithm。

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的源碼才能對這個問題作出準確的回答。請了解的同學積極留言解答，謝謝。

個人微信公眾號: remcarpediem

個人博客地址:

github 地址： https://github.com/ztelur/consistent-hash-algorithm

redis分布式討論的地址： https://www.reddit.com/r/redis/comments/4yztxi/whichoneisbetterhashslotor_consistent/

參考

• https://jistol.github.io/software%20engineering/2018/07/07/consistent-hashing-sample/
• https://mp.weixin.qq.com/s/oe3EPu5DxB0bWheBImMsHg