三,集群
广义上的集群,是指多个机器,构成的分布式系统,就可以称为一个集群,所以前面的主从复制和哨兵模式也可以看作是一个集群。
而侠义上的集群,是redis提供的集群模式。这个集群模式之下,主要是解决存储空间不足的问题。
在redis哨兵模式中,本质还是redis数据节点存储数据,其中就要求主节点/从节点来存储数据的全集。为了提高 数据存储的容量,这时就引入多台机器,每台机器只存储一部分数据。
假设有1TB的数据需要存储: 拿两台机器来存储 ,每台机器需要存储512GB。
拿三台机器来存储,每台机器需要存储300多GB。
拿四台机器来存储,每台机器需要存储 256GB......
但是还存在一个问题,如果使用三台机器来存储1TB的数据,如果某个机器挂了怎么办,所以我们还需要为每个机器 再分配几个从节点。
这三组机器的数据都是不同的,每个 slave都是mster的备份,当master挂了,slave就会晋升为master。
如上图所示,每个虚线框就可以看作是一个分片(Sharding)。
重点面试题:
三种主流的分片算法:哈希求余,一致性哈希算法,哈希槽分区算法。
1,哈希求余
借助hash函数,把一个key映射成为 一个数字,在对数组长度(这里就是分片的个数)进行求余,就可以得到这个key是在哪个分片中。
比如现在有3个分片,编号为0,1,2
此时就可以针对要查询的数据(或插入的数据)计算hash值(比如可以使用md5算法),再把这个值余上分片的个数,此时就会得到一个数字,这个数字就表示这个数据在哪个分片中。
但是当总体的数据增长时,就需要扩容,引入更多的分片,此时分片的个数就变了。
如果发现某个数据在扩容之后,不该待在当前的分片中,那么就需要重新分配数据(数据搬运)。这里涉及到的数据搬运不仅仅是主节点进行,从节点也需要进行。
这种方式开销极大,往往不能再生产环境上操作的,搬运成本比较大。
数据搬运成本大的原因:这种哈希求余的方式,导致数据是交替出现的,比如100出现在0号分片,101出现在1号分片,102出现在2号分片,103又是0号分片 。这就导致在扩容之后,分片个数增长,就会有 大量的数据需要进行搬运。
2,一致性哈希算法
这种方式可以降低上述的"搬运开销"。
key映射到分片序号的过程不再是简单的求余了,而是改成以下过程:
第一步:把0~2^32-1这个数据空间,映射到一个圆环上,按照顺时针方向增长。
第二步:假设分成3个分片,将分片放到对应的位置上
每个分片就会对应一个值,比如0号分片对应的值就是0
第三步:假定有一个key,计算得到的hash值为H,如何计算这个key是在哪个分区?此时H会在圆环上的某个位置,从这个位置开始,顺时针向下找,找到的第一个分片,就是这个key所属 的分片。
这就相当于,N个分片,把整个圆环分成N个区域,key的hash值落在哪个区域,它就属于哪个分片。
因此在 一致性哈希这样的设定下,把数据交替出现,改进成了连续出现。
在这种情况下,如何进行扩容,假设新增一个分片。
如下图所示,在圆环上找一个位置,设为3号分片的位置。该部分本来是0号分片上的,这样一来,只需将0号分片上的这段数据搬运到3号分片上即可,其他分片上的数据不需要搬运。
这种搬运的成本是有的,但是比之前哈希求余的方式低了不少。
这种方式,虽然搬运的成本降低了,但是也导致了各个分片上的数据量不均匀,称作数据倾斜。
3,哈希槽分区算法
这是Redis真正采用的分片算法。
哈希槽计算公式:hsah_slot=hash(key)%16384,一共有16384个槽。
假设现在有3个分片,一种分配方式如下:
0号分片:[0,5461],共5462个槽位。
1号分片:[5462,10923],共5462个槽位。
2号分片:[5463,16384],共5460个槽位。
这里只是分片的一种,分片可以很灵活。每个分片持有的槽位号:可以是连续的,也可以是不连续的。
此处 ,每个分片都会使用一个位图结构,来表示该分片有多少槽位号,16384个bit位,用每一位的0/1表示是否持有这个槽位。
现在假设要新增一个分片,那么此时可以从0号分片,1号分片,2号分片上分别截取一部分出来,放到新的分片上,这样就可以解决数据倾斜的问题。
4,故障处理
如果某个主节点挂了,此时就会把该主节点旗下的某一个从节点提拔为主节点,保证我们的redis能够正常工作。
故障判定
识别某个节点是否挂了。
节点A给节点B发送ping包,B就会给A返回一个pong包。ping和pong除了携带message type属性之外,其他部分都是一样的。还会包含集群的配置信息(该节点的id,该节点属于哪个分片,该节点是主节点还是从节点,从属于哪个主节点,持有哪些slot槽位)。
每个节点,每秒钟都会给一些 随机的节点发送ping包,而不是给所有节点都发送。这样设定设为了在节点很多的时候,心跳包也会非常多。
当节点A向节点B发送ping包后,B不能如期回应的时候,此时A就会尝试重置和B的TCP连接,看能否连接成功,如果连接失败,就会认为B节点下线了,A就会把B设为PFAIL状态(相当于主观下线)。
A判定B为PFAIL后,会通过redis内置的Gossip协议,和其他节点进行沟通,向其他节点确认B的状态。(每个 节点都会维护一个自己的下线列表,由于视角不同,每个节点的下线列表也就不同)。
此时A发现很多节点也认为B为PFAIL,并且数目超过集群节点个数的一半,那么A就会把B标记为PFAIL(相当于客观下线),并且把这个消息同步给其他节点(其他节点收到后,也会把B标记为PFAI)。
以下三种情况会出现集群宕机:
某个分片,所有的主节点和从节点都挂了。
某个分片,主节点挂了,没有从节点。
整个集群超过一半的主节点挂了。
故障迁移
还是上述的例子。
如果B是从节点挂了,那么就不需要进行故障迁移,毕竟从节点挂了,还可以通过访问同一个 分片内的主节点或者其他从节点来获取数据。
如果B是主节点,就会由B的从节点(比如C和D)发生故障迁移。重新挑选一个主节点,代替之前主节点的位置。
具体过程如下:
从节点需要判断自己是否具有参选资格,如果主节点和从节点太久没有进行通信(此时认为主节点和从节点的数据差异太大了),就失去竞选资格。
具有资格的节点,比如C和D,就会先休眠一段时间,休眠时间=500ms基础时间+【0,500ms】随机事件+排名*1000ms。offset值越大,排名就越靠前(越小)。offset表示主节点和从节点数据同步的进度。
比如C的休眠时间到了,C就会给集群中其他所有节点,进行拉票操作。但是只有主节点才有投票资格。
主节点就会把自己的票投给C节点(每个主节点只有一票),当C收到的票数超过主节点数目的一半,C就会晋升为主节点(C会自己执行slaveof no one,并且让D执行slaveof D)。
同时,C还会把自己称为主节点的消息,同步给集群中的其他节点,大家也都会更新自己保存的集群信息结构。
总之,哪个节点会成为主节点,就看哪个节点先被唤醒,哪个节点的休眠时间短,大概率就是新的主节点。
如果两个节点被唤醒的时间是差不多的,那么此时就各凭本事了,取决于网络延迟,线程调度等等因素。
上述选举的过程,称为Raft算法。