redis：数据分区的三种方法

Dear 丶 2022-09-15 06:01 230阅读 0赞

# 数据分区 #

## 什么是数据分区 ##

*  分布式数据库首先要解决把整个数据集按照分区规则映射到多个节点的问题，即把数据集划分到多个节点上，每个节点负责整体数据的一个子集。如下图：  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_17_color_FFFFFF_t_70_g_se_x_16]
 *  换句话说，redis分区就是将数据分布到不同的redis实例中，因此**对于每个redis实例所存储的内容仅仅是所有内容的一个子集**。
 *  这里重点需要关注的是**数据分区规则**。常见的分区规则有hash分区和顺序分区两种。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]

## 哈希分区 ##

由于redis cluster采用哈希分区规则，这里我们重点讨论哈希分区最几种常见的

### 节点取余分区 ###

> 规则

使用特地的数据，如redis的键或者用户ID，再根据节点数量N使用公式：hash(key)%N计算出哈希值，用来决定数据映射到哪一个节点上。

> 例子

假设有三台机器，数据落在哪台机器的算法为

c = Hash(key) % 3

例如key A的hash值为4，4%3=1，则落在第二台机器上。Key ABC哈希值为11，11%3=2，则落在第三台机上。

> 缺陷

利用这种算法，假设现在数据量太大了，需要增加一台机器。A原本落在第二台机器上，现在根据算法4%4 = 0，落在第一台机器上了，但是第一台机器上根本就没有A的值。**这样的算法会导致增加机器或者减少机器的时候，引起大量的缓存穿透，造成雪崩**

也就是说：当节点数量变化时，比如扩容或者收缩节点，数据节点映射关系需要重新计算，会导致数据的重新迁移

> 优点

这种方案的突出优点是简单性，常用于数据库的分库分表规则，一般采用预分区的方式，提前根据数据量划分好分区数，比如划分512或者1024张表，保证可支撑未来一段时间的数据量，在根据负载情况将表迁移到其他数据库中。扩容时通常采用翻倍扩容，避免数据映射全部被打乱导致全量迁移的情况。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_18_color_FFFFFF_t_70_g_se_x_16]

### 一致性哈希分区 ###

在1997年，麻省理工学院的Karger等人提出了一致性哈希算法，为的就是解决分布式缓存的问题。

> 思路

一致性哈希分区实现思路是为系统中每个节点分配一个token，范围一般在 0 2 32 0~2^\{32\} 0232，这些token过程一个hash环。数据读写执行节点查找操作时，先根据key计算hash值，然后顺时针找到第一个大于等于该哈希值的token节点

> 实现过程

在一致性hash算法中，整个hash空间是一个**虚拟圆环**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_12_color_FFFFFF_t_70_g_se_x_16]

假设有四个节点Node A、B、C、D，经过ip地址的哈希计算，它们的位置如下  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
有4个存储对象Object A、B、C、D，经过对Key的哈希计算后，它们的位置如下

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
对于各个Object，它所真正的存储位置是按顺时针找到的第一个存储节点。例如Object A顺时针找到的第一个节点是Node A，所以Node A负责存储Object A，Object B存储在Node B。

一致性哈希算法大概如此，那么它的容错性和扩展性如何呢？

假设Node C节点挂掉了，Object C的存储丢失，那么它顺时针找到的最新节点是Node D。也就是说Node C挂掉了，受影响仅仅包括Node B到Node C区间的数据，并且这些数据会转移到Node D进行存储。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16 3]

同理，假设现在数据量大了，需要增加一台节点Node X。Node X的位置在Node B到Node C直接，那么受到影响的仅仅是Node B到Node X间的数据，它们要重新落到Node X上。

> 优点

这种方式相比节点取余最大的好处至于**加入和删除节点值影响hash环中相邻的节点，对其他节点无影响**。

> 缺点

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

因为**一致性hash算法对数据分布、节点控制不是很友好**，所以redis集群(cluster)对一致性hash进行改进

### 虚拟槽分区 ###

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

如下图，当前节点平均大约负责3276个槽。由于采用高质量的hash算法，每个槽所映射的数据通常比较均匀，将数据平均划分为5个节点进行数据分区。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_13_color_FFFFFF_t_70_g_se_x_16]  
哈希槽其实是两个概念

*  第一个是哈希算法。redis cluster 的 hash 算法不是简单的 hash()，而是 crc16 算法，一种校验算法。
 *  另外一个就是槽位的概念，空间分配的规则。

其实哈希槽的本质和一致性哈希算法十分相似，不同的就是对于哈希空间的定义。一致性哈希的空间是一个圆环，节点分布是基于圆环的，无法很好的控制数据分布。而redis cluster的槽位空间是自定义分配的，类似于windows盘分区的概念。这种分区是可以自定义大小，自定位位置的。

redis cluster包含了16384个哈希槽，每个key通过计算后都会落在具体一个槽位上，而这个槽位是属于哪个存储节点的，则有用户自己定义分配。比如机器硬盘小的，可以分配少一点槽位，硬盘大的可以分配多一点。比如节点硬盘差不多则可以平均分配。所以哈希槽这种概念很好的解决了一致性哈希的弊端

另外在容错性和扩展性上，表象和一致性哈希一样，都是对受影响的数据进行迁移。而哈希槽本质上是对槽位的转移，把故障节点负责的槽位转移到其他正常的节点上。扩展节点也是一样的，把其他节点上的槽位转移到新的节点上。

但一定要注意的是，对于槽位的转移和分派，redis集群是不会自动进行的，而是需要人工培植的。所以redis集群的高可用是依赖于节点的主从复制和主从间的自动故障转移

![在这里插入图片描述][83a85842f3874b3ca51898f7dbba95bc.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c07b3fd316b34da5aa3db2f493b9062e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/513c08dab2234493b3a17ec9072c63e5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d1eb1de37dd44455ac1b9a6d78c04980.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/466bfc5f684f4585a900bf9dd507dcbc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f671cab646334c01bd75ffc61f65a19d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/49db7b78b9e5404599265c82122c9f71.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/f4d769fa40e64ca1b4522228963f1be6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fc949e19233143e9acb81d4341f4895a.png
[83a85842f3874b3ca51898f7dbba95bc.png]: /images/20220828/6519c9a7c2834279ad10067a2271a1a6.png