Redis集群的一致性Hash及代码演示

一致性Hash存在的意义

在微服务领域，使用Redis做缓存可并不是一件容易的事情。
像新浪、推特这样的应用，许许多多的热点数据全都存放在Redis这一层，打到DB层的请求并不多，可以说非常依赖缓存了。假如缓存挂掉，流量一律穿透到DB层，其必然不堪其重，整个系统也会随之瘫痪，后果非常严重。
因为缓存数据量很大，Redis快正是快在其基于内存的快速存取，而计算机的内存资源又是十分有限的，故分布式缓存集群面临着伸缩性的要求。

问题就在这时出现了，所有的缓存数据是分散存放在各个Redis节点上的，通过用户端实现路由算法，来将某个key路由到某个具体的节点。
这个路由算法是分布式缓存伸缩性是否成功的关键。
它的职责不仅仅是由key算出一个Redis的地址，而且必需让新上线的缓存服务器对整个分布式缓存集群影响最小，使得扩容后，整个缓存服务器集群中已经缓存的数据尽可能还被访问到。

这里可以举一个例子，比方用取余数(hash(key)%serverNum)做为该算法，Redis需要由3个节点，扩大到4个节点，会有75%的key无法命中，如下图：

这种效果非常糟糕，当服务器数量为100台时，再添加一台新服务器，不能命中率将达到99%，这和整个缓存服务挂了一个效果。

而一致性Hash正是为理解决这个问题而出现的，该路由算法通过引入一个一致性Hash环，以及进一步添加虚拟节点层，来实现尽可能高的命中率。
关于该算法的具体原理与网上已经有少量说得很透彻的文章，本文不再赘述。

本机部署多个Redis节点

要对一致性Hash进行验证，要做好准备工作，最直接地，首先要有一个Redis集群。这里我通过使用在本机上部署多个Redis实例指向不同端口来模拟这一形态。

建立项目目录：$ mkdir redis-conf
之后将redis的配置copy一份过来并复制为5份，分别命名为redis-6379.conf~redis-6383.conf。

需要对其内容进行少量修改才能正常启动，分别找到配置文件中的如下两行并对数字进行相应修改。

port 6379pidfile /var/run/redis_6379.pid

而后即可以分别启动了：redis-server ./redis-6379 &
可以使用redis-cli -p 6379来指定连接的redis-server。
不妨进行一次尝试，比方在6379设置key 1 2，而到6380 get 1只能得到nil，说明它们是各自工作的，已经满足可以测试的条件。

代码实现

先说一下思路。
部署4个节点，从6379到6382，通过一致性Hash算法，将key: 0~99999共100000个key分别set到这4个服务器上，而后再部署一个节点6383，这时再从0到99999开始get一遍，统计get到的次数来验证命中率能否为期望的80%(4/5)。

一致性Hash算法的实现严重借鉴了这篇文章，使用红黑树来做数据结构，来实现log(n)的查找时间复杂度，使用FNV1_32_HASH哈希算法来尽可能使key与节点分布得更加均匀，引入了虚拟节点，来做负载均衡。
建议读者详细看下这篇文章，里面的讲解非常详细易懂。

下面是我改写过后的代码：

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;       // 假如算出来的值为负数则取其绝对值       if (hash < 0)           hash = Math.abs(hash);       return hash;   }   private static String getServer(String node)   {       // 得到带路由的结点的Hash值       int hash = getHash(node);       // 得到大于该Hash值的所有Map       SortedMap<Integer, String> subMap =               virtualNodes.tailMap(hash);       // 第一个Key就是顺时针过去离node最近的那个结点       if (subMap.isEmpty()) {           subMap = virtualNodes.tailMap(0);       }       Integer i = subMap.firstKey();       // 返回对应的虚拟节点名称，这里字符串略微截取一下       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("虚拟节点[" + 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方法会有些问题，当key大于最大的虚拟节点hash值时tailMap方法会返回空，找不到节点会报错，其实这时应该去找hash值最小的一个虚拟节点。我加了解决，把这个环连上了。
getHash方法为FNV1_32_HASH算法，可以不用太在意。
VIRTUAL_NODES的值比较重要，当节点数目较少时，虚拟节点数目越大，命中率越高。

在程序设计上也有很大的不同，我写了JedisProxy类，来做为client访问Redis的中间层，在该类的static块中利用服务器节点生成虚拟节点构造好红黑树，getServer里根据tailMap方法取出实际节点的地址，再由实际节点的地址直接拿到jedis对象，提供简单的get与set方法，先根据key拿特定的jedis对象，再进行get, set操作。

addServer静态方法给了其动态扩容的能力，可以看到在main方法中，通过调用JedisProxy.addServer("localhost", "6383")便直接添加了节点，不用停应用。
targetPercent方法是用来统计命中率用。

当虚拟节点为5时，命中率约为60%左右，把它加大到100后，可以到达预期的80%的命中率。

好的，完美。