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 的映射关系都调整一遍。这就需要一种方法，在哈希项发生变化是，不需要调整所有的节点，而达到继续维护哈希映射的关系。下面来看下一致性的定义。](http://en.wikipedia.org/wiki/Consistent_hashing)%E7%9A%84%E5%AE%9A%E4%B9%89%E3%80%82)

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 受影响，需要满足下面几个条件：

  • 平衡性(Balance)：就是指哈希算法要均匀分布，不能有明显的映射规律，这对一般的哈希实现也是必须的；
  • 单调性(Monotonicity)：就是指有新节点加入时，已经存在的映射关系不能发生变化；
  • 分散性(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 类维护了一致性哈希后的物理机器和虚拟节点的映射关系。image.png

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> resources 维护了虚拟节点和真正的存储位置的映射关系。
也是说，hash(key) → virtual node → real node;
jedis 划分虚拟节点的逻辑代码，在 Sharded 类中，方法是 initialize。这是在实例化对象池 ShardedJedisPool 过程中执行的划分虚拟节点。
其中 ShardedJedis、BinaryShardedJedis 和 Sharded 的关系如下图所示。
image.png

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> 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 的哈希一致性。

https://alicharles.oss-cn-hangzhou.aliyuncs.com/static/images/mp_qrcode.jpg
文章目录
  1. 1、非一致性哈希
  2. 2、一致性哈希
  3. 3、ShardedJedis 一致性哈希
    1. 3.1 Sharded 的实现定义
    2. 3.2 ShardedJedis 初始化
    3. 3.3 ShardedJedis 中的 set 和 get 操作
Charles ©2022   浙ICP备14035515号-1