一致性Hash算法

2018-11-25 本文已影响3人丫头可乐

最近在做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来实现

创建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
但是无论是新增一个节点或者删除一个节点。数据的命中率都会显著降低。