提取jedis源码的一致性hash代码作为通用工具类

时间:2024-01-21 15:12:32

一致性Hash热点

一致性Hash算法是来解决热点问题,如果虚拟节点设置过小热点问题仍旧存在。
关于一致性Hash算法的原理我就不说了,网上有很多人提供自己编写的一致性Hash算法的代码示例,我在跑网上的代码示例发现还是有热点问题。为此我翻阅了Jedis的ShardedJedis类的源码把它的一致性Hash算法提取出来,作为自己的一个工具类,以后自己工程开发中用起来也放心些,毕竟jedis的代码经受了大家的验证。

提取jedis的一致性hash代码作为通用工具类

看看人家码神写的代码,这泛型,这继承,这多态用的,写的真是好,代码通用性真是没话说。
在Sharded方法中:
1 ,定义了一个TreeMap ,TreeMap 用于存储虚拟节点(在初始化方法中,将每台服务器节点采用hash算法划分为160个(默认的,DEFAULT_WEIGHT)虚拟节点(当然也可以配置划分权重)
2 ,定义一个LinkedHashMap,用于存储每一个Redis服务器的物理连接,其中shardInfo的createResource就是物理连接信息 。
3,对于key采用与初始化时同样的hash(MurmurHash或者MD5)算法,然后从TreeMap获取大于等于键hash值得节点,取最邻近节点;
4,当key的hash值大于虚拟节点hash值得最大值时(也就是tail为空),取第一个虚拟节点。
相关完整的源码可以查看我的github的intsmaze-hash这个model,传送点https://github.com/intsmaze/intsmaze。

package cn.intsmaze.hash.shard;
public class Sharded<R, S extends ShardInfo<R>> {

    public static final int DEFAULT_WEIGHT = 1;

    private TreeMap<Long, S> nodes;

    private final Hashing algo;

    private final Map<ShardInfo<R>, R> resources = new LinkedHashMap<ShardInfo<R>, R>();


    public Sharded(List<S> shards) {
        this(shards, Hashing.MURMUR_HASH); // MD5 is really not good as we works
        // with 64-bits not 128
    }

    public Sharded(List<S> shards, Hashing algo) {
        this.algo = algo;
        this.shards=shards;
        initialize(shards);
    }

    private void initialize(List<S> shards) {
        nodes = new TreeMap<Long, S>();

        for (int i = 0; i != shards.size(); ++i) {
            final S shardInfo = shards.get(i);
            if (shardInfo.getTableName() == null) for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
                nodes.put(this.algo.hash("SHARD-" + i + "-NODE-" + n), shardInfo);
            }
            else for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
                nodes.put(this.algo.hash(shardInfo.getTableName() + "*" + shardInfo.getWeight() + n), shardInfo);
            }
            resources.put(shardInfo, shardInfo.createResource());//调用IntsmazeShardInfo的createResource()方法 如果我们的实现不需要控制远程的连接,那么这个方法就不没什么用
        }
    }

    /**
     * 这个是找到key对应的节点后,不是仅仅返回属于的节点名称而是返回对应的实例连接
     * @param key
     * @return
     */
    public R getShardByResources(String key) {
        return resources.get(getShardInfo(key));
    }

    /**
     * 这个是找到key对应的节点后,返回属于的节点名称
     * @param key
     * @return
     */
    public S getShard(String key) {
        return getShardInfo(key);
    }

    public S getShardInfo(byte[] key) {
        SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
        if (tail.isEmpty()) {
            return nodes.get(nodes.firstKey());
        }
        return tail.get(tail.firstKey());
    }

    public S getShardInfo(String key) {
        return getShardInfo(SafeEncoder.encode(key));
    }

}

package cn.intsmaze.hash.shard;
public class IntsmazeShardedConnection extends Sharded<Intsmaze, IntsmazeShardInfo>{

    public IntsmazeShardedConnection(List<IntsmazeShardInfo> shards) {
        super(shards);
    }

    public String getTable(String key) {
        IntsmazeShardInfo intsmazeShardInfo = getShard(key);
        return intsmazeShardInfo.getTableName();
    }
}

package cn.intsmaze.hash.shard;
public class IntsmazeShardInfo extends ShardInfo<Intsmaze> {

    private String host;

    private int port;

    public IntsmazeShardInfo(String host, String tableName) {
        super(Sharded.DEFAULT_WEIGHT, tableName);
        URI uri = URI.create(host);
        this.host = uri.getHost();
        this.port = uri.getPort();
    }


    @Override
    public Intsmaze createResource() {
        return new Intsmaze(this);
    }

}

package cn.intsmaze.hash.shard;
public abstract class ShardInfo<T> {
    private int weight;

    private String tableName;

    public ShardInfo() {
    }

    public ShardInfo(int weight,String tableName) {
        this.weight = weight;
        this.tableName=tableName;
    }

    protected abstract T createResource();

}



package cn.intsmaze.hash.shard;
public class Test {

    private static IntsmazeShardedConnection sharding;

    public static void setUpBeforeClass() throws Exception {
        List<IntsmazeShardInfo> shards = Arrays.asList(
                new IntsmazeShardInfo("localhost:6379", "intsmaze-A"),
                new IntsmazeShardInfo("localhost::6379", "intsmaze-B"),
                new IntsmazeShardInfo("localhost::6379", "intsmaze-C"),
                new IntsmazeShardInfo("localhost::6379", "intsmaze-D"),
                new IntsmazeShardInfo("localhost::6379", "intsmaze-E"));
        sharding = new IntsmazeShardedConnection(shards);
    }

    public void shardNormal() {
        Map<String,Long> map=new HashMap<String,Long>();
        for (int i = 0; i < 10000000; i++) {

            String result = sharding.getTable("sn" + i);

            Long num=map.get(result);
            if(num==null)
            {
                map.put(result,1L);
            }
            else
            {
                num=num+1;
                map.put(result,num);
            }
        }
        Set<Map.Entry<String, Long>> entries = map.entrySet();
        Iterator<Map.Entry<String, Long>> iterator = entries.iterator();
        while(iterator.hasNext())
        {
            Map.Entry<String, Long> next = iterator.next();
            System.out.println(next.getKey()+"--->>>"+next.getValue());
        }
    }

    public static void main(String[] args) throws Exception {
        Test t=new Test();
        t.setUpBeforeClass();
        t.shardNormal();
    }

}

没有热点问题

把jedis的源码提取出来后,跑了一下,发现没有热点问题,原理不是采用算法的问题,而是一个物理节点对应的虚拟节点的数量的问题导致使用hash算法后,还是有热点问题。jedis源码物理节点对应虚拟节点时160,而网上大部分代码都是10以下,所以导致了热点问题,这也告诉我们,实现一致性Hash算法时,不要太吝啬,虚拟节点设置的大点,热点问题就不会再有。

相关完整的源码可以查看我的github的intsmaze-hash这个model,传送点https://github.com/intsmaze/intsmaze。