一致性Hash算法

最近在做Redis方面的一些工作，其中Redis3.0以前的版本，服务器端没有提供集群的方式。需要在客户端做sharding。redis客户端做sharding的话，需要用到一致性Hash算法。

假设我们有3台redis服务器。


一、普通Hash算法

1、首先对3台redis服务器的ip地址，进行hash运算。得到一个int类型的值。hash算法如下：

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;
}

2、利用得到的hash值对3进行取模

getHash(192.168.7.1)=196713682%3=1
getHash(192.168.7.2)=467665103%3=2
getHash(192.168.7.3)=542751888%3=0

3、假如我们想要把键值对name=linlin。存入到redis中，因为有3台redis存在，所以必须要决定将键值对存入到哪一台中。对key值name进行hash，然后对3进行取模。

getHash("name")=117328155%3=0

所以键值对name=linlin会被路由到192.168.7.3这台服务器中。
4、使用Java来实现

  1. 创建RedisNode类
package com.lin.hash.redis;

import java.util.HashMap;
import java.util.Map;

public class RedisNode {
    private String ip;

    private Map<String,Object> data;

    public RedisNode(String ip) {
        this.ip = ip;
        data = new HashMap<>();
    }
    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public Map<String, Object> getData() {
        return data;
    }

    public void setData(Map<String, Object> data) {
        this.data = data;
    }

    public Object getNodeValue(String key){
        return data.get(key);
    }
}

2.创建抽象类

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public abstract class RedisCluster {
    protected List<RedisNode> redisNodes;


    public RedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public abstract void addRedisNode(RedisNode redisNode);

    public abstract RedisNode getRedisNode(String key);

    public abstract void removeRedisNode(RedisNode redisNode);
}

3.创建NormalRedisCluster类

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class NormalRedisCluster extends RedisCluster {
    private List<RedisNode> redisNodes;


    public NormalRedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public void addRedisNode(RedisNode redisNode){
        redisNodes.add(redisNode);
    }

    public RedisNode getRedisNode(String key){
        int hash = HashUtils.getHash(key);
        /**使用key的hash值对key进行取模*/
        RedisNode redisNode = redisNodes.get(hash % redisNodes.size());
        return redisNode;
    }
    public void removeRedisNode(RedisNode redisNode){
        Iterator<RedisNode> iterator = redisNodes.iterator();
        while (iterator.hasNext()){
            RedisNode next = iterator.next();
            if (next.getIp().equals(redisNode.getIp())){
                iterator.remove();
            }
        }
    }
}

4.创建HashUtils

package com.lin.hash.redis;

public class HashUtils {
    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
     */
    public 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;
    }
}

5.创建RedisHashTest类

package com.lin.hash.redis;

import com.alibaba.fastjson.JSONObject;

import java.util.List;
import java.util.Map;

public class RedisHashTest {
    public static void main(String[] args) {
        String[] servers = {"192.168.7.1","192.168.7.2","192.168.7.3"};

        /**
         * 添加redis节点
         */
        RedisCluster redisCluster = new NormalRedisCluster();
        for (String server:servers){
            redisCluster.addRedisNode(new RedisNode(server));
        }

        /**
         * 往redis集群中加入100条数据
         * */

        int dataCount = 100;

        for (int i=0;i<dataCount;i++){
            String key = "name"+i;
            String value = "linlin"+i;

            /**获取节点*/
            RedisNode redisNode = redisCluster.getRedisNode(key);
            Map<String, Object> data = redisNode.getData();
            data.put(key,value);
        }

        /**获取redis节点中的数据分布*/
        List<RedisNode> redisNodes = redisCluster.getRedisNodes();
        for (RedisNode redisNode:redisNodes){
            System.out.println(JSONObject.toJSONString(redisNode.getData()));
        }

        /**查看节点不变的情况下，redis数据的命中率*/
        int hitCount = 0;
        for (int i=0;i<dataCount;i++){
            String key = "name"+i;
            String value = "linlin"+i;
            Object nodeValue = redisCluster.getRedisNode(key).getNodeValue(key);
            if (nodeValue != null){
                hitCount++;
            }
        }

        System.out.println("数据命中率为："+hitCount*1.0/dataCount);

        /**新增一个节点的情况下数据的命中率*/
        redisCluster.addRedisNode(new RedisNode("192.168.7.4"));
        hitCount=0;
        for (int i=0;i<dataCount;i++){
            String key = "name"+i;
            String value = "linlin"+i;
            Object nodeValue = redisCluster.getRedisNode(key).getNodeValue(key);
            if (nodeValue != null){
                hitCount++;
            }
        }
        System.out.println("新增节点的情况下，redis数据的命中率:"+hitCount*1.0/dataCount);

//        /**删除一个节点的情况下数据的命中率*/
//        normalRedisCluster.removeRedisNode(new RedisNode("192.168.7.2"));
//        hitCount=0;
//        for (int i=0;i<dataCount;i++){
//            String key = "name"+i;
//            String value = "linlin"+i;
//            Object nodeValue = normalRedisCluster.getRedisNode(key).getNodeValue(key);
//            if (nodeValue != null){
//                hitCount++;
//            }
//        }
//        System.out.println("删除节点的情况下，redis数据的命中率:"+hitCount*1.0/dataCount);
    }
}

5.我们可以看到在节点保持不变的情况下，数据的命中率为1.0。
新增一个节点的命中率为：0.27
删除一个节点的命中率为：0.4
但是无论是新增一个节点或者删除一个节点。数据的命中率都会显著降低。

一致性Hash算法

关于一致性Hash算法的原理，网络上已经有很多非常棒的文章，我在这里就不解释了，为了文章的完整性，在这里将原理贴出来：

先构造一个长度为232的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 232-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。

一直性Hash算法会导致数据分布不均匀的情况产生。如下图所示


image.png

按照一致性Hash的原理，因为A-B区间占了圆环的绝大部分，所以大部分的数据都会落入到B节点上，这样就会导致数据不会均匀的分不到A-B两个节点中。从而导致负载不均衡。可以通过引入虚拟节点来解决这个问题。

不带虚拟节点的一致性Hash算法

下面是不带虚拟节点的ConsistentWithoutVirtualNodeRedisCluster

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentWithoutVirtualNodeRedisCluster extends RedisCluster{
    private List<RedisNode> redisNodes;

    private SortedMap<Integer,RedisNode> hashNodeMap = new TreeMap<>();

    public ConsistentWithoutVirtualNodeRedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public void addRedisNode(RedisNode redisNode){
        redisNodes.add(redisNode);
        int hash = HashUtils.getHash(redisNode.getIp());
        hashNodeMap.put(hash,redisNode);
    }

    public RedisNode getRedisNode(String key){
        int hash = HashUtils.getHash(key);
        SortedMap<Integer, RedisNode> subMap = hashNodeMap.tailMap(hash);
        int i = 0;
        if (subMap.size()==0){
            i = hashNodeMap.firstKey();
            return hashNodeMap.get(i);
        }else {
            i = subMap.firstKey();
            return subMap.get(i);
        }
    }
    public void removeRedisNode(RedisNode redisNode){
        Iterator<RedisNode> iterator = redisNodes.iterator();
        while (iterator.hasNext()){
            RedisNode next = iterator.next();
            if (next.getIp().equals(redisNode.getIp())){
                iterator.remove();
            }
        }
    }
}

如果要测试不带虚拟节点的一直性Hash算法的命中率，将

RedisCluster redisCluster = new NormalRedisCluster();
替换成
RedisCluster redisCluster = new ConsistentWithoutVirtualNodeRedisCluster();

就可以进行测试了

带虚拟节点的一致性Hash算法

假设我们将一个真实节点映射成10个虚拟节点。例如真正节点的ip是192.168.7.1。那么对应的十个虚拟ip分别是

真实：192.168.7.1
虚拟：
           192.168.7.1&&VN1
           192.168.7.1&&VN2
           192.168.7.1&&VN3
           192.168.7.1&&VN4
           192.168.7.1&&VN5
           192.168.7.1&&VN6
           192.168.7.1&&VN7
           192.168.7.1&&VN8
           192.168.7.1&&VN9
           192.168.7.1&&VN10

当真正进行数据存储的时候，我们根据虚拟节点的ip信息， 取出真正的ip，然后进行存储。
算法如下：

package com.lin.hash.redis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentWithVirtualNodeRedisCluster extends RedisCluster{
    private List<RedisNode> redisNodes;

    //定义每个真实节点对应10个虚拟节点
    private Integer virtualCount = 10;

    private SortedMap<Integer,RedisNode> virtualHashNodeMap = new TreeMap<>();


    public ConsistentWithVirtualNodeRedisCluster() {
        redisNodes = new ArrayList<>();
    }

    public List<RedisNode> getRedisNodes() {
        return redisNodes;
    }

    public void setRedisNodes(List<RedisNode> redisNodes) {
        this.redisNodes = redisNodes;
    }


    public void addRedisNode(RedisNode redisNode){
        redisNodes.add(redisNode);

        for (int i=0;i<10;i++){
            int hash = HashUtils.getHash(redisNode.getIp()+"&&VN"+(i+1));
            virtualHashNodeMap.put(hash,redisNode);
        }

    }

    public RedisNode getRedisNode(String key){
        int hash = HashUtils.getHash(key);
        SortedMap<Integer, RedisNode> subMap = virtualHashNodeMap.tailMap(hash);
        int i = 0;
        if (subMap.size()==0){
            i = virtualHashNodeMap.firstKey();
            return virtualHashNodeMap.get(i);
        }else {
            i = subMap.firstKey();
            return subMap.get(i);
        }
    }
    public void removeRedisNode(RedisNode redisNode){
        Iterator<RedisNode> iterator = redisNodes.iterator();
        while (iterator.hasNext()){
            RedisNode next = iterator.next();
            if (next.getIp().equals(redisNode.getIp())){
                iterator.remove();
            }
        }
    }
}

如果要测试带虚拟节点的一直性Hash算法的命中率，将

RedisCluster redisCluster = new NormalRedisCluster();
替换成
RedisCluster redisCluster = new ConsistentWithVirtualNodeRedisCluster();

就可以进行测试了
从测试结果中可以看到，无论是新增节点还是删除节点，带虚拟节点的一致性Hash算法的命中率都大大的提高了。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,445评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,889评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,047评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,760评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,745评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,638评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,011评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,669评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,923评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,655评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,740评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,406评论 4赞 320
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,995评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,961评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,023评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,483评论 2赞 342

推荐阅读更多精彩内容

  • 一致性Hash算法
    余数Hash 最简单、常用的Hash算法。hash(i) = i mod n缺点：伸缩性差，使用余数Hash的路由...
    萌妈码码阅读 201评论 0赞 0
  • 一致性Hash算法
    01.引入 在业务开发中，我们常把数据持久化到数据库中。如果需要读取这些数据，除了直接从数据库中读取外，为了减轻数...
    Java技术范阅读 586评论 0赞 7
  • 一致性hash算法
    consistent hashing算法早在1997年就在论文Consistent hashing and...
    北风第一支阅读 797评论 0赞 5
  • 一致性hash算法
    转载请说明出处：http://blog.csdn.net/cywosp/article/details/23397...
    码农也越野阅读 433评论 0赞 1
  • 《终身学习》
    10个你必须掌握的未来生存法则 将来为上，过往次之 学习为上，经历次之 付出为上，回报次之 表现为上，赞誉次之 感...
    tuanzifighting阅读 182评论 0赞 0