Redis 数据分布介绍

一数据分布理论

一数据分布理论

分布式数据库首先要解决整个数据集按照分区规则映射到多个节点的问题，也就是需要把数据集划分到多个节点上，每个节点负责整个数据的一个子集。如图所示：

常见的分区规则有哈希分区和顺序分区两种：

哈希分区

离散度好，数据分布业务无关，无法顺序访问，如 Redis Cluster 、Dynamo

顺序分区

离散度易倾斜，数据分布业务相关，可顺序访问，如 Bigtable、Hbase

Redis Cluster采用哈希分区规则，我们重点分析哈希分区，下面我们来分析常见的几种哈希分区规则：

1.1 节点取余分区

使用特定的数据，如 Redis 的键或用户的 ID，再根据公式：hash(key)%N，计算出 hash 值，用来决定数据落到那个节点。

优点

这种方式的突出特点是简单性，常用于数据库的分库分表。

缺点

当节点数量变化时，如扩容或者收缩节点，数据节点映射关系需要重新计算，会导致数据的重新迁移。所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端数据库请求数据，产生缓存雪崩现象。

扩容时通常采用翻倍扩容，避免数据映射全部被打乱导致全量迁移的情况，如图所示。所以，我们应该想办法不让这种情况发生，但是由于上述 Hash 算法本身的缘故，使用取模法进行缓存时，这种情况是无法避免的，为了解决这些问题，Hash一致性算法（一致性Hash算法）诞生了。

1.2 一致性 Hash 分区

一致性 Hash 算法也是使用取模的方法，节点取余分区是对服务器的数量进行取模，而一致性Hash 算法是对 2^32 取模，什么意思呢？

简单来说，一致性 Hash 算法将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数 H 的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希环如下：整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1，也就是说0点左侧的第一个点代表2^32-1， 0和2^32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将四台服务器使用IP地址哈希后在环空间的位置如下：

数据读写执行节点查找操作时，先根据 key 计算hash值，然后顺时针找到第一个大于等于该哈希值的第一个服务器节点。例如我们有 Object A、Object B、Object C、Object D 四个数据对象，经过哈希计算后，在环空间上的位置如下：

根据一致性 Hash 算法，数据 A 会被定为到 Node A 上，B 被定为到 Node B 上，C 被定为到Node C上，D 被定为到Node D上。

这种方式相比节点取余最大的好处在于加入和删除节点只影响哈希环中相邻的节点，对其他节点无影响。但一致性hash存在以下几个问题：

加减节点会造成哈希环中部分数据无法命中，需要手动处理或者忽略这部分数据，因此一致性哈希常用于缓存场景。
当使用少量节点时，节点变化将大范围影响哈希环中数据映射，因此这种方式不适合少量数据节点的分布式方案。
普通的一致性哈希分区在增减节点时需要增加一倍或减少一半节点才能保证数据和负载均衡。

正因为一致性哈希分区的这些缺点，一些分布式系统采用虚拟槽对一致性哈希进行了改进，如Dynamo系统。

1.3 虚拟槽分区

虚拟槽分区巧妙地使用了哈希空间，使用分散度良好的哈希函数把所有数据映射到一个固定范围的整数集合中，整数定义为槽（slot）。这个范围一般远远大于节点数，Redis Cluster 槽范围是0-16383。槽是集群内数据管理和迁移的基本单位。采用大范围槽的主要目的是为了方便数据拆分和集群扩展。每个节点负责一定数据量的槽。