一致性Hash存在的意義

在微服務(wù)領(lǐng)域，使用Redis做緩存可并不是一件容易的事情膜蠢。
像新浪堪藐、推特這樣的應(yīng)用，許許多多的熱點(diǎn)數(shù)據(jù)全都存放在Redis這一層挑围，打到DB層的請求并不多礁竞，可以說非常依賴緩存了。如果緩存掛掉杉辙，流量全部穿透到DB層模捂，其必然不堪其重，整個(gè)系統(tǒng)也會(huì)隨之癱瘓蜘矢，后果非常嚴(yán)重狂男。
由于緩存數(shù)據(jù)量很大，Redis快正是快在其基于內(nèi)存的快速存取品腹，而計(jì)算機(jī)的內(nèi)存資源又是十分有限的岖食，故分布式緩存集群面臨著伸縮性的要求。

問題就在這時(shí)出現(xiàn)了舞吭，所有的緩存數(shù)據(jù)是分散存放在各個(gè)Redis節(jié)點(diǎn)上的泡垃，通過客戶端實(shí)現(xiàn)路由算法，來將某個(gè)key路由到某個(gè)具體的節(jié)點(diǎn)镣典。
這個(gè)路由算法是分布式緩存伸縮性能否成功的關(guān)鍵兔毙。
它的職責(zé)不僅僅是由key算出一個(gè)Redis的地址，而且必須讓新上線的緩存服務(wù)器對整個(gè)分布式緩存集群影響最小兄春，使得擴(kuò)容后澎剥，整個(gè)緩存服務(wù)器集群中已經(jīng)緩存的數(shù)據(jù)盡可能還被訪問到。

這里可以舉一個(gè)例子，比如用取余數(shù)(hash(key)%serverNum)做為該算法哑姚，Redis需要由3個(gè)節(jié)點(diǎn)祭饭，擴(kuò)大到4個(gè)節(jié)點(diǎn)，會(huì)有75%的key無法命中叙量，如下圖：

這種效果非常糟糕倡蝙，當(dāng)服務(wù)器數(shù)量為100臺(tái)時(shí)，再增加一臺(tái)新服務(wù)器绞佩，不能命中率將達(dá)到99%寺鸥，這和整個(gè)緩存服務(wù)掛了一個(gè)效果。

而一致性Hash正是為了解決這個(gè)問題而出現(xiàn)的品山，該路由算法通過引入一個(gè)一致性Hash環(huán)胆建，以及進(jìn)一步增加虛擬節(jié)點(diǎn)層，來實(shí)現(xiàn)盡可能高的命中率肘交。
關(guān)于該算法的具體原理與網(wǎng)上已經(jīng)有一些說得很透徹的文章笆载，本文不再贅述。

本機(jī)部署多個(gè)Redis節(jié)點(diǎn)

要對一致性Hash進(jìn)行驗(yàn)證涯呻，要做好準(zhǔn)備工作凉驻，最直接地，首先要有一個(gè)Redis集群复罐。這里我通過使用在本機(jī)上部署多個(gè)Redis實(shí)例指向不同端口來模擬這一形態(tài)涝登。

建立項(xiàng)目目錄：$ mkdir redis-conf
之后將redis的配置copy一份過來并復(fù)制為5份，分別命名為redis-6379.conf~redis-6383.conf市栗。

需要對其內(nèi)容進(jìn)行一些修改才能正常啟動(dòng)缀拭，分別找到配置文件中的如下兩行并對數(shù)字進(jìn)行相應(yīng)修改。

port 6379
pidfile /var/run/redis_6379.pid

然后就可以分別啟動(dòng)了：redis-server ./redis-6379 &
可以使用redis-cli -p 6379來指定連接的redis-server填帽。
不妨進(jìn)行一次嘗試蛛淋，比如在6379設(shè)置key 1 2，而到6380 get 1只能得到nil篡腌，說明它們是各自工作的褐荷，已經(jīng)滿足可以測試的條件。

不同的節(jié)點(diǎn)展示

代碼實(shí)現(xiàn)

先說一下思路嘹悼。
部署4個(gè)節(jié)點(diǎn)叛甫，從6379到6382，通過一致性Hash算法，將key: 0~99999共100000個(gè)key分別set到這4個(gè)服務(wù)器上，然后再部署一個(gè)節(jié)點(diǎn)6383剔桨，這時(shí)再從0到99999開始get一遍，統(tǒng)計(jì)get到的次數(shù)來驗(yàn)證命中率是否為期望的80%(4/5)抖苦。

一致性Hash算法的實(shí)現(xiàn)嚴(yán)重借鑒了這篇文章，使用紅黑樹來做數(shù)據(jù)結(jié)構(gòu)，來實(shí)現(xiàn)log(n)的查找時(shí)間復(fù)雜度锌历，使用FNV1_32_HASH哈希算法來盡可能使key與節(jié)點(diǎn)分布得更加均勻贮庞，引入了虛擬節(jié)點(diǎn)，來做負(fù)載均衡究西。
建議讀者詳細(xì)看下這篇文章窗慎，里面的講解非常詳細(xì)易懂。

下面是我改寫過后的代碼：

package org.guerbai.io.jedistry;

import redis.clients.jedis.Jedis;
import java.util.*;

class JedisProxy {

   private static String[][] redisNodeList = {
           {"localhost", "6379"},
           {"localhost", "6380"},
           {"localhost", "6381"},
           {"localhost", "6382"},
   };

   private static Map<String, Jedis> serverConnectMap = new HashMap<>();

   private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();

   private static final int VIRTUAL_NODES = 100;

   static
   {
       for (String[] str: redisNodeList)
       {
           addServer(str[0], str[1]);
       }
       System.out.println();
   }

   private static int getHash(String str)
   {
       final int p = 16777619;
       int hash = (int)2166136261L;
       for (int i = 0; i < str.length(); i++)
           hash = (hash ^ str.charAt(i)) * p;
       hash += hash << 13;
       hash ^= hash >> 7;
       hash += hash << 3;
       hash ^= hash >> 17;
       hash += hash << 5;

       // 如果算出來的值為負(fù)數(shù)則取其絕對值
       if (hash < 0)
           hash = Math.abs(hash);
       return hash;
   }

   private static String getServer(String node)
   {
       // 得到帶路由的結(jié)點(diǎn)的Hash值
       int hash = getHash(node);
       // 得到大于該Hash值的所有Map
       SortedMap<Integer, String> subMap =
               virtualNodes.tailMap(hash);
       // 第一個(gè)Key就是順時(shí)針過去離node最近的那個(gè)結(jié)點(diǎn)
       if (subMap.isEmpty()) {
           subMap = virtualNodes.tailMap(0);
       }
       Integer i = subMap.firstKey();
       // 返回對應(yīng)的虛擬節(jié)點(diǎn)名稱卤材，這里字符串稍微截取一下
       String virtualNode = subMap.get(i);
       return virtualNode.substring(0, virtualNode.indexOf("&&"));
   }

   public static void addServer(String ip, String port) {
       for (int i = 0; i < VIRTUAL_NODES; i++)
       {
           String virtualNodeName = ip + ":" + port + "&&VN" + String.valueOf(i);
           int hash = getHash(virtualNodeName);
           System.out.println("虛擬節(jié)點(diǎn)[" + virtualNodeName + "]被添加, hash值為" + hash);
           virtualNodes.put(hash, virtualNodeName);
       }
       serverConnectMap.put(ip+":"+port, new Jedis(ip, Integer.parseInt(port)));
   }

   public String get(String key) {
       String server = getServer(key);
       Jedis serverConnector = serverConnectMap.get(server);
       if (serverConnector.get(key) == null) {
           System.out.println(key + "not in host: " + server);
       }
       return serverConnector.get(key);
   }

   public void set(String key, String value) {
       String server = getServer(key);
       Jedis serverConnector = serverConnectMap.get(server);
       serverConnector.set(key, value);
       System.out.println("set " + key + " into host: " + server);
   }

   public void flushdb() {
       for (String str: serverConnectMap.keySet()) {
           System.out.println("清空host: " + str);
           serverConnectMap.get(str).flushDB();
       }
   }

   public float targetPercent(List<String> keyList) {
       int mingzhong = 0;
       for (String key: keyList) {
           String server = getServer(key);
           Jedis serverConnector = serverConnectMap.get(server);
           if (serverConnector.get(key) != null) {
               mingzhong++;
           }
       }
       return (float) mingzhong / keyList.size();
   }

}

public class ConsistencyHashDemo {

   public static void main(String[] args) {
       JedisProxy jedis = new JedisProxy();
       jedis.flushdb();
       List<String> keyList = new ArrayList<>();
       for (int i=0; i<100000; i++) {
           keyList.add(Integer.toString(i));
           jedis.set(Integer.toString(i), "value");
       }
       System.out.println("target percent before add a server node: " + jedis.targetPercent(keyList));
       JedisProxy.addServer("localhost", "6383");
       System.out.println("target percent after add a server node: " + jedis.targetPercent(keyList));
   }
}

首先遮斥，他的getServer方法會(huì)有些問題，當(dāng)key大于最大的虛擬節(jié)點(diǎn)hash值時(shí)tailMap方法會(huì)返回空商膊，找不到節(jié)點(diǎn)會(huì)報(bào)錯(cuò)伏伐，其實(shí)這時(shí)應(yīng)該去找hash值最小的一個(gè)虛擬節(jié)點(diǎn)。我加了處理晕拆，把這個(gè)環(huán)連上了。
getHash方法為FNV1_32_HASH算法材蹬，可以不用太在意实幕。
VIRTUAL_NODES的值比較重要，當(dāng)節(jié)點(diǎn)數(shù)目較少時(shí)堤器，虛擬節(jié)點(diǎn)數(shù)目越大昆庇，命中率越高。

在程序設(shè)計(jì)上也有很大的不同闸溃，我寫了JedisProxy類整吆，來做為client訪問Redis的中間層，在該類的static塊中利用服務(wù)器節(jié)點(diǎn)生成虛擬節(jié)點(diǎn)構(gòu)造好紅黑樹辉川，getServer里根據(jù)tailMap方法取出實(shí)際節(jié)點(diǎn)的地址表蝙，再由實(shí)際節(jié)點(diǎn)的地址直接拿到j(luò)edis對象，提供簡單的get與set方法乓旗，先根據(jù)key拿特定的jedis對象府蛇，再進(jìn)行g(shù)et, set操作。

addServer靜態(tài)方法給了其動(dòng)態(tài)擴(kuò)容的能力屿愚，可以看到在main方法中汇跨，通過調(diào)用JedisProxy.addServer("localhost", "6383")便直接增加了節(jié)點(diǎn)，不用停應(yīng)用妆距。
targetPercent方法是用來統(tǒng)計(jì)命中率用穷遂。

當(dāng)虛擬節(jié)點(diǎn)為5時(shí)，命中率約為60%左右娱据，把它加大到100后蚪黑，可以到達(dá)預(yù)期的80%的命中率。

測試結(jié)果

好的，完美祠锣。