前面描述了redis主从复制和redis sentinel以及redis cluster的适用场景和各自的原理。本文主要描述下它们的功能和作用以及异同点。文中图片大部分来自于网络。
(图片来源于网络) 原理说明见上一篇文章。
Sentinel为Redis提供高可用。利用Sentinel,在无人干预的情况下,可用让Redis服务抵御一定程度的故障。主要发挥以下几个方面的作用:
Redis Cluster集群架构,如果要存储更多的数据,可以直接增加新的Master + Slave来进行水平扩容。
假设有三台机,数据落在哪台机的算法为: node = hash(requestId) % 3 。这样进入的请求会被分布到三台redis节点上,如下图:
上面的方式看似能解决了我们将请求负载到多个节点的问题,实际上有一些问题:
为了解决上面的问题,我们引出了一致性hash算法
早在1997年就在论文《Consistent hashing and random trees》中提出,这个算法有一个环形hash空间的概念。
通常hash算法都是将value映射在一个32位的key值当中,那么把数轴首尾相接就会形成一个圆形,取值范围为0 ~ 2^32-1,这个圆形就是环形hash空间。
现在假设有4个对象:object1-object4,将四个对象hash后映射到环形空间中:
首先通过hash函数计算出这四个对象的hash值key,这些对象的hash值肯定是会落在上述中的环形hash空间范围上的,对象的hash对应到环形hash空间上的哪一个key值那么 该对象就映射到那个位置上,这样对象就映射到环形hash空间上了。
接下来把chche映射到hash空间(基本思想就是讲对象和cache都映射到同一hash数值空间中,并且使用相同的hash算法,可以使用cache的ip地址或者其他因子),假设现在有三个cache:
hash(cache A) = key A;
... ...
hash(cache C) = key C;
可以看到,Cache和Obejct都映射到这个环形hash空间中了,那么接下来要考虑的就是如何将object映射到cache中。其实在这个环形hash空间进行一个顺时针的计算即可, 例如key1顺时针遇到的第一个cache是cacheA,所以就将key1映射到cacheA中,key2顺时针遇到的第一个cache是cacheC,那么就将key2映射到cacheC中,以此类推。如下图:
现在移除一个cacheB节点、这时候key4将找不到cache,key4继续使用一致性hash算法运算后算出最新的cacheC,以后存储与读取都将在cacheC上:
移除节点后的影响范围在该节点逆时针计算到遇到的第一个cache节点之间的数据节点。这个范围是比较小的。
现在看一下增加一个节点:
如上图所示,在cacheB和cacheC之间增加了cacheD节点,那么object2在顺时针遇到的第一个cache是cacheD,此时就会将object2映射到cacheD中,增加cache节点所影响 的范围也就是cacheD和cacheB之间的那一段,范围也比较小。
上述情况仅适用于服务节点在哈希环上分布均匀的情况,如果哈希环上服务器节点的 分布位置不均匀,则会导致某个区间内的数据项的大量数据存放在一个服务器节点中。如下图,A 缓存服务器就会接收大量请求,当该服务器崩溃掉之后,B 服务器,C 服务器会依次崩溃,这样就会造成 服务器雪崩效应,整个缓存服务器集群都会瘫痪。
这种时候就需要引入虚拟节点来解决问题了。
一致性hash 算法 一定程度上解决了node宕机后的大部分数据失效问题,但是也会导致node 的热点问题,降低性能,这个又该怎么解决呢?可以通过增加虚拟节点的方式 让 hash 点散落更均匀 ,不光能解决热点问题,还可以达到自动的负载均衡效果。
例如我们拥有 A、B、C 三台服务器,我们在哈希环上创建哈希服务器的时候,可以为其创建 N 个虚拟节点,这些虚拟节点都是指向真实服务器的 IP,这样我们在哈希环上的服务器节点分布就会很均匀。
有了虚拟节点,就可以尽可能让更多的Node有机会被请求,从而分担热点压力,达到负载均衡的效果。这时环形hash空间上分布就越来越均匀,移除或增加cache时所受到的影响就会越小。
一致性命中率计算公式:
(1 - n / (n + m)) * 100%
n = 现有的节点数量
m = 新增的节点数量
Redis 集群没有使用一致性hash, 而是引入了 哈希槽的概念.
Redis 集群有16384个哈希槽,每个key通过CRC16校验后对16384取模来决定放置哪个槽.集群的每个节点负责一部分hash槽,举个例子,比如当前集群有3个节点,那么:
这种结构很容易添加或者删除节点. 比如如果我想新添加个节点D, 我需要从节点 A, B, C中的部分槽到D上. 如果我想移除节点A,需要将A中的槽移到B和C节点上,然后将没有任何槽的A节点从集群中移除即可. 由于从一个节点将哈希槽移动到另一个节点并不会停止服务,所以无论添加删除或者改变某个节点的哈希槽的数量都不会造成集群不可用的状态.
redis cluster拥有固定的16384个slot(槽) 这个槽是虚拟的,并不是真正存在。slot被分布到各个master中,当某个key映射到某个master负责的槽时,就由 对应的master为key提供服务。在redis cluster中只有master才拥有对slot的所有权,slave只负责使用slot,并没有所有权。
那么 redis Cluster 又是如何知道哪些槽是由哪些节点负责的呢?Master 又是如何知道哪个槽是自己的呢?
每个Master节点都维护着一个位序列,为16384 / 8 字节;Master 节点 通过 bit 来标识哪些槽自己是否拥有。比如对于编号为1的槽,Master只要判断序列的第二位(索引从0开始)是不是为1即可。
集群同时维护着槽与集群节点的映射关系,由16384个长度的数组记录,槽编号为数组的下标,数组内容为集群节点,这样就可以很快地通过槽编号找到负责这个槽的节点。
下面看下redis cluster是通过什么样的方式进行分片存储的
key 与 slot 的映射算法公式如下:
HASH_SLOT=CRC16(key) mod 16384
//少量优化性能
public ThreadLocal<MessageDigest> md5Holder = new ThreadLocal<MessageDigest>();
public static final Hashing MD5 = new Hashing() {
public long hash(String key) {
return hash(SafeEncoder.encode(key));
}
public long hash(byte[] key) {
try {
if (md5Holder.get() == null) {
md5Holder.set(MessageDigest.getInstance("MD5"));
}
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException("++++ no md5 algorythm found");
}
MessageDigest md5 = md5Holder.get();
md5.reset();
md5.update(key);
byte[] bKey = md5.digest();//获得MD5字节序列
//前四个字节作为计算参数,最终获得一个32位int值.
//此种计算方式,能够确保key的hash值更加“随即”/“离散”
//如果hash值过于密集,不利于一致性hash的实现(特别是有“虚拟节点”设计时)
long res = ((long) (bKey[3] & 0xFF) << 24)
| ((long) (bKey[2] & 0xFF) << 16)
| ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF);
return res;
}
};
//shards列表为客户端提供了所有redis-server配置信息,包括:ip,port,weight,name
//其中weight为权重,将直接决定“虚拟节点”的“比例”(密度),权重越高,在存储是被hash命中的概率越高
//--其上存储的数据越多。
//其中name为“节点名称”,jedis使用name作为“节点hash值”的一个计算参数。
//---
//一致性hash算法,要求每个“虚拟节点”必须具备“hash值”,每个实际的server可以有多个“虚拟节点”(API级别)
//其中虚拟节点的个数= “逻辑区间长度” * weight,每个server的“虚拟节点”将会以“hash”的方式分布在全局区域中
//全局区域总长为2^32.每个“虚拟节点”以hash值的方式映射在全局区域中。
// 环形:0-->vnode1(:1230)-->vnode2(:2800)-->vnode3(400000)---2^32-->0
//所有的“虚拟节点”将按照其”节点hash“顺序排列(正序/反序均可),因此相邻两个“虚拟节点”之间必有hash值差,
//那么此差值,即为前一个(或者后一个,根据实现而定)“虚拟节点”所负载的数据hash值区间。
//比如hash值为“2000”的数据将会被vnode1所接受。
//---
private void initialize(List<S> shards) {
nodes = new TreeMap<Long, S>();//虚拟节点,采取TreeMap存储:排序,二叉树
for (int i = 0; i != shards.size(); ++i) {
final S shardInfo = shards.get(i);
if (shardInfo.getName() == null)
//当没有设置“name”是,将“SHARD-NODE”作为“虚拟节点”hash值计算的参数
//"逻辑区间步长"为160,为什么呢??
//最终多个server的“虚拟节点”将会交错布局,不一定非常均匀。
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());
}
}
public R getShard(String key) {
return resources.get(getShardInfo(key));
}
//here:
public S getShardInfo(byte[] key) {
//获取>=key的“虚拟节点”的列表
SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
//如果不存在“虚拟节点”,则将返回首节点。
if (tail.size() == 0) {
return nodes.get(nodes.firstKey());
}
//如果存在,则返回符合(>=key)条件的“虚拟节点”的第一个节点
return tail.get(tail.firstKey());
}
主要使用了TreeMap,细节见:https://www.iteye.com/blog/shift-alt-ctrl-1885959