一、哈希分布
1、哈希取模
哈希分布就是将数据计算哈希值之后，按照哈希值分配到不同的节点上。例如有 N 个节点，数据的主键为 key，则将该数据分配的节点序号为：hash(key)%N
当增加或者减少node后，很难保证还能路由到原来的节点，因此所有的key都会受到影响
![]()
2、一致性哈希算法
1.将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0到Integer.MAX_VALUE-1（0~~2^32-1），整个哈希空间环就是下图中的黑色圆环
2.对每个服务器的唯一识别标志（IP或者主机名）求hash值，将得到的值放入第一步的圆环中对应的位置。如下图的node1 node2 node3 node4
-
3.对要保存的数据的key求hash值，将得到的值落入圆环中，就是下图的黄色圆圈，然后在圆环中顺时针找到最近的node（服务器的唯一识别标志（IP或者主机名）求hash值落在圆环中所在的点），该数据就存储在该node中
这时增加了一个节点node5,通过hash后落在了如图的位置，这时只需要修改n1到n5之间数据(原来是路由到n2 的)的路由即可，这样扩缩容受到影响的数据就很少
缺点：
1、一致性哈希解决了数据迁移量大的问题，但只是减轻了插入节点顺时针开始遇到的第一个机器负担，对于其他的节点并未起到减轻负载的作用。
2、服务节点太少时，数据分布不够均匀，容易因为节点分部不均匀而造成数据倾斜问题。
3、带虚拟节点的一致性哈希算法
这个主要是解决了一致性哈希的负载性差，数据分布不够均匀的问题，是一致性哈希的改进
假设我们部署了cache A 节点和 cache C节点 。现在我们将cache A 节点虚拟成如图的cache A1和cache A2，将cache C节点虚拟成如图的cache C1和cache C2，一共存在 4 个虚拟节点， hash(objec1)=key1->cache C2 ；hash(objec2)=key2->cache A1 ； hash(objec3)=key3->cache C1 ； hash(objec4)=key4->cache A2 ；因此对象 object4 和 object2 都被映射到了 cache A 上，而 object3 和 object1 映射到了 cache C 上。由于节点虚拟后节点相对分散，因此负载性和数据分布均匀性得到了提升
4、虚拟槽分区
虚拟槽分区是 redis cluster 中默认的数据分布技术，虚拟槽分区巧妙地使用了哈希空间，使用分散度良好的哈希函数把所有数据映射到一个固定范围的整数集合中，这个整数定义为槽(slot)，而且这个槽的个数一般远远的大于节点数。
在 redis cluster 中有16384(0~16383)个槽，会将这些槽平均分配到每个 master 上，在存储数据时利用 CRC16 算法，具体的计算公式为：slot=CRC16(key)/16384 来计算 key 属于哪个槽。在我们的集群环境中，一个 key 的存储或者查找过程如图：
分布式ID方案:
方案：
雪花算法：
1位，不用。二进制中最高位为1的都是负数，但是我们生成的id一般都使用整数，所以这个最高位固定是0
41位，用来记录时间戳（毫秒）41位可以表示2{41}-1个数字，也就是说41位可以表示2{41}-1个毫秒的值，转化成单位年则是(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69年
10位，用来记录工作机器id。可以部署在2^{10} = 1024个节点，一般是5+5代表，前5位服务器区号（例如上海一区）后五位代表服务器标识
12位，序列号，用来记录同毫秒内产生的不同id。表示可以每台服务器在这一毫秒内可以同时生成4096个不同的id。最大正整数是2^{12}-1 = 4095，即可以用0、1、2、3、....4094这4095个数字，来表示同一机器同一时间截（毫秒)内产生的4095个ID序号
由于在Java中64bit的整数是long类型，所以在Java中SnowFlake算法生成的id就是long来存储的。
- SnowFlake可以保证：
● 所有生成的id按时间趋势递增
● 整个分布式系统内不会产生重复id
