Redis(二)ShardedJedis一致性哈希

本文主要介绍一致性哈希的概念,以及在Redis中的ShardedJedis一致性哈希实现原理

1、非一致性哈希

在讨论一致性哈希之前,先认识下”非一致性哈希”,例如HashMap。
当使用HashMap时,key被均匀地映射到数组之上,映射方法就是利用key的hash与数组长度取模(通过&运算)。
当put的数据超过负载因子loadFactor×2Len时,HashMap会按照2被的容量扩容。
新put进来的数据会通过与新数组的长度取模的方式进行映射。那之前已经映射的数据该怎么办?
通过查看HashMap代码的resize方法会发现,每次扩容都会把之前的key重新映射。
所以对HashMap而言要想获得较好的性能必须要提前估计所放数据集合的大小,以设计合适的初始化容量和负载因子。
2、一致性哈希
不是每个场景都像HashMap这么简单,比如在大型的P2P网络中存在上百万台Server,资源与Server的关系是以Key的形式映射而成,也就是说是一个大的HashMap,维护着每个Key在哪个Server之上,如果有新的节点加入或退出P2P网络,跟HashMap一样,也会导致映射关系的变化,显然不可能把所有的Key与Server的映射关系都调整一遍。这就需要一种方法,在哈希项发生变化是,不需要调整所有的节点,而达到继续维护哈希映射的关系。下面来看下一致性的定义。

Consistent hashing is a special kind of hashing such that when a hash table is resized, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation.

一致性哈希是一种特殊类型的的哈希,当哈希表改变大小的时候,平均只有K/n的keys需要被重新映射,其中k为keys的数量,n为槽slots的数量。相比之下,在传统的哈希表中,因为key和slot的映射是通过取模操作定义的,槽slot的数量改变会引起几乎所有的key都被重新映射。一致性哈希当节点加入、退出时,只影响加入退出的节点和其邻居节点或者其他节点只有少量的Key受影响,需要满足下面几个条件:
1. 平衡性(Balance):就是指哈希算法要均匀分布,不能有明显的映射规律,这对一般的哈希实现也是必须的;
2. 单调性(Monotonicity):就是指有新节点加入时,已经存在的映射关系不能发生变化;
3. 分散性(Spread):就是避免不同的内容映射到相同的位置和相同的内容映射到不同的位置。
其实一致性哈希(哈希)有个明显的优点就是负载均衡,只要哈希函数设计得当,每个点就是对等的可以均匀地分布系统负载。

3、ShardedJedis一致性哈希
Shared一致性哈希采用以下方案:
1. Redis服务器节点划分:将每台服务器节点采用hash算法划分为160个虚拟节点(可以配置划分权重)
2. 将划分虚拟节点采用TreeMap存储
3. 对每个Redis服务器的物理连接采用LinkedHashMap存储
4. 对Key or KeyTag 采用同样的hash算法,然后从TreeMap获取大于等于键hash值得节点,取最邻近节点存储;
当key的hash值大于虚拟节点hash值得最大值时,存入第一个虚拟节点。
Sharded采用的hash算法:MD5 和 MurmurHash两种;默认采用64位的MurmurHash算法,
Sharded类维护了一致性哈希后的物理机器和虚拟节点的映射关系。

3.1 Sharded的实现定义

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>();

    /**
     * The default pattern used for extracting a key tag. The pattern must have a group (between
     * parenthesis), which delimits the tag to be hashed. A null pattern avoids applying the regular
     * expression for each lookup, improving performance a little bit is key tags aren't being used.
     */
    private Pattern tagPattern = null;
    // the tag is anything between {}
    public static final Pattern DEFAULT_KEY_TAG_PATTERN = Pattern.compile("\\{(.+?)\\}");
    ......
    
}

其中TreeMap<Long, S> nodes,存储的是虚拟节点和key的映射关系。有了虚拟节点,还要找到真正的存储位置。
Map<ShardInfo<R>, R> resources维护了虚拟节点和真正的存储位置的映射关系。
也是说,hash(key) -> virtual node -> real node;
jedis划分虚拟节点的逻辑代码,在Sharded类中,方法是initialize。这是在实例化对象池ShardedJedisPool过程中执行的划分虚拟节点。
其中ShardedJedis、BinaryShardedJedis和Sharded的关系如下图所示。

 3.2 ShardedJedis初始化

public ShardedJedis(List<JedisShardInfo> shards) {
    super(shards);
}

public BinaryShardedJedis(List<JedisShardInfo> shards, Hashing algo) {
    super(shards, algo);
}

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;
    initialize(shards);
}

通过initialize来看,节点的划分和初始化

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.getName() == 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.getName() + "*" + shardInfo.getWeight() + n), shardInfo);
        }
        resources.put(shardInfo, shardInfo.createResource());
    }
}

以上代码就是Sharded划分虚拟节点的逻辑,初始化TreeMap<Long, S> nodes虚拟节点和key的映射关系,以及Map<ShardInfo<R>, R> resources虚拟节点和真正的存储位置的映射关系。

 3.3 ShardedJedis中的set和get操作
先看ShardedJedis的set操作(get操作类似)

public String set(String key, String value) {
    // 1、获取ShardedJedis的实例
    Jedis j = getShard(key);
    return j.set(key, value);
}


public R getShard(String key) {
    // 2、首先需要通过getShardInfo(key)的获取到JedisShardInfo信息,通过resources.get获取到ShardedJedis实例
    return resources.get(getShardInfo(key));
}

public S getShardInfo(String key) {
    // 3、SafeEncoder.encode(getKeyTag(key))获取hash后的byte[]
    // 4、通过getShardInfo(byte[] key)获取到JedisShardInfo信息
    return getShardInfo(SafeEncoder.encode(getKeyTag(key)));
}

public S getShardInfo(byte[] key) {
    // 5、获取大于等于当前algo.hash(key)的升序SortedMap
    SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
    if (tail.isEmpty()) {
        // 6、为空,说明当前的hash值比所有的都大,返回nodes的第一个ShardInfo
        return nodes.get(nodes.firstKey());
    }
    // 7、否则返回大于等于当前hash值的第一个ShardInfo
    return tail.get(tail.firstKey());
}

上面的代码中大体的逻辑,首先通过key得到ShardInfo,然后通过ShardInfo得到泛型Jedis客户端实例,进行set和get操作。
通过上面的代码保证了redis的哈希一致性。