手记

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

一致性Hash存在的意义

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

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

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

hash(key)hash(key)/3hash(key)/4是否命中
111
222
303
410
521
602
713
820
901
1012
1123
1200

这种效果非常糟糕,当服务器数量为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%的命中率。

测试结果

好的,完美。



作者:古二白
链接:https://www.jianshu.com/p/ed83515cb46c


0人推荐
随时随地看视频
慕课网APP