【redis】一致性hash算法和hash槽
普通hash取模
直接hash(key)%N , N为机器的数量,但不利于集器扩容或者缩容
一致性hash算法和hash槽
一致性hash算法是在redis 分片中使用,hash槽在redis cluster(集群)中使用
Redis一致性hash:Redis一致性hash是为了解决分布式环境下,数据分片的问题。在Redis集群中,数据是分布在不同的节点上的,这个过程就是数据分片。
Hash槽:在Redis中,数据是以hash槽的形式存储在不同的节点上的。Redis会根据key和节点的数量进行hash运算,然后将得到的结果对节点数量进行取模运算,最终得到的结果就是该key应该存储的hash槽。
一致性hash算法
应用场景:分布式缓存系统
Redis一致性hash是为了解决分布式环境下,数据分片的问题。在Redis集群中,数据是分布在不同的节点上的,这个过程就是数据分片
hash环
一致性hash是指将 “存储节点” 和 “数据” 都映射到一个首尾相连的hash环上。如果增删节点,仅影响该节点在hash环上顺时针相邻的后继节点,其他数据不会受到影响。
第一步:对存储节点进行哈希计算,也就是对存储节点做哈希映射,比如根据节点的 IP 地址进行哈希
假设有四个节点 Node A、B、C、D,经过 ip 地址的哈希计算,它们的位置如下:
第二步:当对数据进行存储或访问时,对数据进行哈希映射;
有4个存储对象 Object A、B、C、D,经过对 Key 的哈希计算后,它们的位置如下:
如何确定数据位于hash环上的位置?
对于各个 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 进行存储。
同理,假设现在数据量大了,需要增加一台节点 Node X。Node X 的位置在 Node B 到 Node C 直接,那么受到影响的仅仅是 Node B 到 Node X 间的数据,它们要重新落到 Node X 上。
一致性Hash算法使用 “取模法”,且是对 2^ 32次方取模,其可表示的范围为:0 ~ 2^32-1
与普通的hash算法有何不同?
普通的hash算法是对节点数进行hash,而一致性hash是对固定值 2^32 进行取模
易产生问题:数据倾斜
但是一致性哈希算法不能够均匀的分布节点,会出现大量请求都集中在一个节点的情况,在这种情况下进行容灾与扩容时,容易出现雪崩的连锁反应。
当在服务器节点数量太少的时候,容易出现分布不均而导致数据倾斜。
数据倾斜解决方法:虚拟节点映射
为了解决一致性哈希算法不能够均匀的分布节点的问题,就需要引入虚拟节点,对一个真实节点做多个副本。不再将真实节点映射到哈希环上,而是将虚拟节点映射到哈希环上,并将虚拟节点映射到实际节点,所以这里有「两层」映射关系。
映射关系:缓存数据 ➜ 虚拟节点 ➜ 真实节点
虚拟节点映射物理节点,redis哈希槽的数量是16384个,redis cluster采用的是 CRC16(key) % 16384 算法
个人理解:其实也就是通过构造大量的虚拟节点映射,使得当向redis集群中存储k-v时,hash取模的值可以更大,这样对数据取模后的结果也就更加分散(所有数据穿插分散在不同真实节点上)!
在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。
具体做法:可以在服务器IP或主机名的后面增加编号来实现,例如上面的情况,可以为每个服务节点增加三个虚拟节点,于是可以分为:RedisService1#1、 RedisService1#2、 RedisService1#3、 RedisService2#1、 RedisService2#2、 RedisService2#3
对于hash环来说,节点越多,数据分布越平稳。所以采用虚拟节点的方式,将一个节点虚拟成多个节点,保证环上有1000~2000个节点最佳。
一般10个Redis服务器的集群,每个节点可以虚拟100-200个节点,保证环上有1000-2000个节点
一般5个Redis集群,则每个节点虚拟200-400个节点,保证节点数是1000-2000之间,这样才能保证数据分布均衡
引入虚拟节点后,会提高节点的均衡度,还会提高系统的稳定性。
优点
一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。
新增服务器节点/删除服务器节点: 在hash环中新增服务器,也是通过hash算法确认分布,只需要移动一小部分数据即可;移除也是同理
应用
在redis集群(主从、哨兵)、缓存中间件memcached中都有使用到它
hash槽
基本概念:槽可以理解为分区,数据都是存放在分区中的,然后分区与机器进行动态绑定。
redis-cluster把所有的“物理节点”映射到 [0-16383] 槽上(不一定是平均分配),cluster 负责维护node ⇌ slot ⇌ value。
redis集群(cluster)并没有选用上面一致性哈希,而是采用了哈希槽(slot)的这种概念。主要的原因就是上面所说的,一致性哈希算法对于数据分布、节点位置的控制并不是很友好。
产生原因
如果Redis只用复制功能做主从,那么当数据量巨大的情况下,单机情况下可能已经承受不下一份数据,更不用说是主从都要各自保存一份完整数据。在这种情况下,数据分片是一个非常好的解决办法。因此可以借助hash槽自动对数据分片,并落到各个节点上分散存储。通过为每个节点指派不同数量的槽,可以控制不同节点负责的数据量和请求数。
hash方式:一个redis集群包含 16384 个哈希槽,数据库中的每个数据都属于这16384个哈希槽中的一个。集群使用公式 CRC16(key) % 16384 来计算键 key 属于哪个槽。一个redis节点包含N个槽,数据通过hash算法哈希到固定的槽里,所以槽只是决定了数据的存放位置,当多个数据hash出来的结果相同时,他们就被分配到相同的槽里,即也会映射到相同的服务节点上。
一致性hash算法和hash槽的本质区别
其实哈希槽的本质和一致性哈希算法非常相似,不同点就是对于哈希空间的定义。一致性哈希的空间是一个圆环,节点分布是基于圆环的,无法很好的控制数据分布。而 redis cluster 的槽位空间是自定义分配的,类似于 windows 盘分区的概念。这种分区是可以自定义大小,自定义位置的。
为什么redis集群不采用一致性哈希算法?
一致性哈希的节点分布基于圆环,无法很好的手动控制数据分布,比如有些节点的硬件差,希望少存一点数据,这种很难操作(还得通过虚拟节点映射,总之较繁琐)。
而redis集群的槽位空间是可以用户手动自定义分配的,类似于 windows 盘分区的概念,可以手动控制大小。例如机器硬盘小的,可以分配少一点槽位,硬盘大的可以分配多一点。
其实,无论是一致性哈希还是哈希槽的方式,在增减节点的时候,都会对一部分数据产生影响,都需要我们迁移数据,当然,redis集群也提供了相关手动迁移槽数据的命令。
原文地址:https://blog.csdn.net/xiazi0721/article/details/140700825
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!