Redis集群（cluster）

对于主从复制+哨兵的形式还是有所缺陷，于是产生了集群的这一种方式，其不同于复制+哨兵。

是什么？

由于数据量过大，单个Master复制集难以承受，因此需要对多个复制集进行集群，形成水平扩展，每个复制集只负责存储整个数据集的一部分，这就是Redis的集群。

有什么用？

提供在多个Redis节点间共享数据的程序集

Redis集群支持多个Master，每个Master又可以挂载多个Slave
- 读写分离
- 支持数据的高可用
- 支持海量数据的读写存储操作
由于Cluster自带Sentinel的故障转移机制，内置了高可用的支持，无需再去使用哨兵功能
客户端与Redis的节点连接，不再需要连接集群中所有的节点，只需要任意连接集群中的一个可用节点即可
槽位slot负责分配到各个物理服务节点，由对应的集群来负责维护节点、插槽和数据之间的关系

集群算法-分片-槽位slot

官网出处：

redis集群的槽位slot

Redis集群没有使用一致性hash，而是引入了哈希槽的概念

Redis集群由16384个哈希槽，每个key通过CRC15校验后对16384取模来决定放置哪个槽，集群的每个节点负责一部分哈希槽，例如：当前集群由3个节点，则

Redis集群的分片

分片是什么？

使用Redis集群时我们会将存储的数据分散到多台redis机器上，这称为分片，集群中的每个Redis实例都被认为是整个数据的一个分片

如何找到给定key的分片？

为了找到给定key的分片，我们对key进行CRC16(key)算法处理并通过对总分片数量取模，然后使用确定性哈希函数，意味着给定的key将多次始终映射到同一个分片，我们可以推断将来读取特定key的位置

槽位和分片的优势

最大优势：方便扩缩容和数据分派查找

这种结构很容易添加或删除节点，如果想添加一个新的节点，则需要从前面的节点中得到部分槽位给新的节点上，如果想移除某个节点则需要将该结点中的槽位移动到剩余节点的曹魏中，然后将没有任何槽位的节点移除即可，由于从一个节点将哈希槽移动到另一个节点并不会停止服务，所以无论添加删除或者改变某个节点的哈希槽的数量都不会造成集群不可用的状态

slot槽位映射的解决方案

哈希取余分区
- 两亿条记录就是两亿个k，v键值对，我们单机不行必须要分布式多机器，用户每次读写操作都是根据公式：hash(key) % N个机器数量，计算出哈希值，用来决定数据映射到哪一个节点上
- 优点：简单粗暴且直接有效，只需要预估好数据，规划好节点，就能保证一段时间的数据支撑，使用Hash算法让固定的一部分请求落到同一台服务器上，这样每台服务器固定处理一部分请求（并维护这些请求的信息），起到负载均衡分而治之的作用。
- 缺点：原来规划好的节点进行扩容或者缩容会比较麻烦，不管扩缩，每次数据变动导致节点有变动，映射关系需要重新进行计算，在服务器个数固定不变时没有问题，如果需要弹性扩容或故障停机的情况下，原来的取模公式就会发生变化：Hash(key) % 3会变成Hash(key) % ?，此时计算出的哈希地址经过取余运算的结果将发生很大变化，根据公式获取的服务器也会变得不可控。
一致性哈希算法分区
- 是什么？
  - 为了解决分布式缓存数据变动和映射问题。某个机器宕机了，分母数量发生改变，自然取余会导致问题的发生。
- 目的：当服务器数量发生变动时，尽量减少影响客户端到服务器的映射关系
- 三大步骤：
  1. 算法构建一致性哈希环（哈希环类似循环队列）
    - 一致性哈希环算法必然有个hash函数并按照算法产生hash值，这个算法的所有可能哈希值会构成一个集合，这个集合可以成为一个hash空间[0,2^32-1]，但这是一个线性空间（类似线性队列），于是我们通过对2^32取模，将其在逻辑上形成一个虚拟的环形空间，一致性Hash算法对2^32取模
      
      哈希环
  2. redis服务器IP节点映射
    - 将集群中的各个IP节点映射到环上的某一个位置
    - 将服务器使用Hash算法确定每台机器在哈希环上的位置
  3. key落到服务器的落键规则
    - 当我们需要存储一个kv键值对时，会按照和计算哈希环相同的函数去计算key的哈希值，然后再从计算出的位置沿着环的顺时针进行行走，遇到的第一台redis服务器就是该key应该定位到的服务器
    - 例如：现在有ObjectA、ObjectB、ObjectC、ObjectD四个数据对象，经过哈希函数算出位置如下图，这时候各自再沿着哈希环顺时针行走知道遇到的第一个服务器就是他们各自应该在的服务器即：ObjectA会被定位到NodeA上，ObjectB会被定位到NodeB上，ObjectC会被定位到NodeC上，ObjectD会被定位到NodeD上
- 优点：
  - 容错性：假设NodeC宕机，此时的A、B、D不会受到影响，一般的在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着哈希环逆时针行走遇到的第一台服务器）之间的数据，其他的不会收到影响，即C宕机了，受到影响的只是B、C之间的数据，且这些数据会转移到D进行存储
  - 扩展性：数据量增加，需要增加一台节点NodeX，X的位置在A和B之间，那受到影响的也就只是A到X之间的数据，重新把A到X的数据录入到X上即可，不会导致Hash取余全部数据重新计算
- 缺点：哈希环的数据倾斜问题。一致性Hash算法在服务节点太少时，容易因为节点分布不均匀而造成数据倾斜，即被缓存的对象大部分集中缓存在某一台服务器上
哈希槽分区
- 目的：为了解决一致性哈希算法的数据倾斜问题
- 实质：是一个数组[0,2^14-1]形成hash slot空间
- 能干什么？
  - 解决均匀分配的问题，在数据和节点之间又加入了一层，把这层称为哈希槽（hash slot），用于管理数据和节点之间的关系，现在就相当于节点上放的是槽，槽里放的是数据。
    
    槽解决的是粒度问题，相当于把粒度变大了，方便数据移动，哈希解决的是映射问题，使用key的哈希值来计算所在的槽，便于数据分配
- 多少个哈希槽？
  - 一个集群只能有16384个槽，编号0-16384（0~2^14-1）。这些槽会分配给集群中的所有主节点，分配策略没有要求
  - 集群会记录节点和槽的对应关系，解决了节点和槽的关系后，会需要对key求哈希值，然后对16384取模，余数是多少key就落入对应的槽里。HASH_SLOT = CRC16(key) mod 16384以槽为单位移动数据，因为槽的数目是固定的，处理起来比较容易，这样数据移动问题就得以解决
- 哈希槽计算
  - Redis集群中内置了16384个哈希槽，redis会根据节点数量大致均等的将哈希槽映射到不同的节点，当需要在Redis集群中放置一个key-value时，redis先对key使用CRC16算法算出一个值然后用该值对16384取余数，这样每个key都会对应一个编号在0-16383之间的哈希槽，映射到某个节点上，如下：
```
@Test
public void test3() {
    //import io.lettuce.core.cluster.SlotHash;
    System.out.println(SlotHash.getSlot("A"));		//6373
    System.out.println(SlotHash.getSlot("B"));		//10374
    System.out.println(SlotHash.getSlot("C"));		//14503
    System.out.println(SlotHash.getSlot("Hello"));	//866
}
```

为什么Redis集群的的最大槽数是16384个？

如果槽位为65536（2^16），发送心跳信息的消息头高达8k，发送的心跳包过于庞大
- 在消息头中最占空间的是myslot[CLUSTER_SLOT/8]
  - 当槽位为65536时，这块的大小是：65536÷8÷1024=8kb
  - 当槽位为16384时，这块的大小是：15384÷8÷1024=2kb
- 因为每秒钟redis节点需要发送一定数量的ping消息作为心跳包，如果槽位为65536，这个ping的消息头太大了，浪费带宽。
redis集群的主节点数量基本不可能超过1000个
- 集群节点越多，心跳包的消息体内携带的数据越多，如果节点过1000个，也会导致网络拥挤，因此redis作者不建议redis cluster节点数量超过1000个，那个对于节点数在1000个以内的redis集群，16384个槽位够用了，没有必要拓展到65536个
槽位越小，节点越少的情况下，压缩比高，容易传输
- Redis主节点的配置信息中它所负责的哈希槽是通过一张bitmap的形式来保存的，在传输过程中会对bitmap进行压缩，但是如果bitmap的填充率（slots / N）很高的话（N表示节点数），bitmap的压缩率就很低，如果节点数很少，而哈希槽数很多的话，bitmap的压缩率就很低