本文主要介绍一致性哈希的概念,以及在 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 一致性哈希采用以下方案:
- Redis 服务器节点划分:将每台服务器节点采用 hash 算法划分为 160 个虚拟节点(可以配置划分权重)
- 将划分虚拟节点采用 TreeMap 存储
- 对每个 Redis 服务器的物理连接采用 LinkedHashMap 存储
- 对 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
也是说,hash(key) → virtual node → real node;
jedis 划分虚拟节点的逻辑代码,在 Sharded 类中,方法是 initialize。这是在实例化对象池 ShardedJedisPool 过程中执行的划分虚拟节点。
其中 ShardedJedis、BinaryShardedJedis 和 Sharded 的关系如下图所示。