Redis入门：数据分片算法

Redis入门：数据分片算法

1 Hash取余

hash取余对数据key-value的key值做hash取余计算，得到结果只要key值不变(字符串相等)取余结果在[0,1,2,3,…,n-1]，n=分片个数(节点个数)。 计算公式如下：

(key.hashCode()&Integer.MAX_VALUE)%N
# 其中N为分片(节点)个数

• key.hashCode()：对key做hash散列计算，只要key值不变，得到一个不变可正可负的整数。只要散列计算，能够做到key不变，整数结果不变，不一定非得使用hashCode最终任意一个key值都会对应[-21亿,21亿]区间的一个整数。
• key.hashCode()&Integer.MAX_VALUE：31位二进制保真运算，目的是将前面的整数保真后31位二进制，保证他是一个正整数。&位的与运算。目的是取得一个正整数。

结论1：当key值不变时，可以得到一个不变的正整数。

(key.hashCode()&Integer.MAX_VALUE)%N
N=5,取余结果 [0,1,2,3,4]
N=4,取余结果 [0,1,2,3]
N=3,取余结果 [0,1,2]
对N取余 结果[0,1,2,3,4,5…,N-1]

结论2：当key值不变时，可以通过hash取余得到[0,1,2,…,N-1]一个不变的取余结果。

hash取余就可以应用在redis分布式数据分片计算逻辑中。

当有key-value出现时，先对key做hash取余n是节点个数(现在是3)；所有节点jedis排序(list) 0 1 2 … n-1 使用到取余结果对应到一个固定的jedis对象，最终连接固定的redis节点。

在一个频繁发生扩容缩容的分布式结构中，hash取余不适用，但是N不发生变化的结构中总是使用hash取余。

1.1 缺点

作为散列算法，考虑分布式缓存中的数据分片过程的哈希取余的缺点。

1.1.1 散列算法都会出现数据倾斜

数据倾斜：

例如：3个redis节点，在散列计算后的存储数据有可能是以下情况：

• Node1：4000条数据。
• Node2：3000条数据。
• Node3：1500条数据。

此情况已经产生了2500条数据的最大偏移，按此比例计算，当数据存储量上亿条时，这种数据倾斜会造成集群中节点间巨大的负载差距。

解决数据倾斜的方法：

• 可以在key值上做文章。因为key值是自定义的，所以可以使用uuid或者md5加密，来保证key的散列平均分布。在key取值的时候就进行散列分布。

1.1.2 大量数据迁移

哈希取余的散列计算，在增加或者减少节点的时候，会导致数据迁移量过大。

2 Hash一致性

由上述原因，jedis的数据分片没有使用hash取余计算而是引入的hash一致性。

1997年麻省理工学院的学生开发了哈希一致性的计算方法。引入了一个0-43亿的整数哈希环(0-2^32)，把节点的ip和端口和其他信息作为字符串的对象进行散列计算。

例如："192.168.40.120:6379^

jedis对将要存储的key做同样的散列计算。

例如："ITEM_CAT_0"--散列计算--[0-2^32]的整数。

利用这个hash环上的对应内容的散列结果，对key做顺时针寻找最近节点映射整数的判断，以这样一种计算，将所有的key值进行数据分片的计算。

如下图所示：

• key1顺时针最近节点——node1
• key2，key3顺时针最近节点——node3
• key4顺时针最近节点——node2

2.1特点

2.1.1减少增删节点的数据迁移量

当增加节点node4时，如下图：

对于当前存在的数据，只需要根据顺时针最近节点的计算原理，迁移key4，其他的key都不用动。按此来说，只要迁移绿色线条上的数据即可。

当节点删除时(node3)，如下图：

对于当前存在的数据，只需要迁移key2和key3到node2即可。如果数据较多，只需迁移node3的数据到node2即可，也就是蓝色线条上的所有数据。

2.1.2解决数据平衡的问题

单独的使用节点ip+端口+其他信息的散列映射，有可能导致数据的倾斜量过大。为了解决数据平衡的问题，hash一致性引入虚拟节点的概念。

针对虚拟节点的官方说明，每个物理节点默认会产生1000个虚拟节点，散列分布在hash环上，就相当于每个物理节点分割成了1001个节点，这样多节点的散列分布就能保证数据的平衡存储。如下图：

在没有虚拟节点的情况下，node2需要存储key2、key3、key4、key5，node1存储key1，数据就产生了较大的倾斜。

当引入了虚拟节点的映射(ip+端口+#1)，虚拟节点大致算法如下：

• node1-node1-01:"192.168.40.139:6379#01"
• node1-node1-02:"192.168.40.139:6379#02"

此时key值存放结果变成node1存储key1、key2、key4，node2存储key3、key5。数据存储就相对平均了。