小工具知识网

当前位置: 首页 > 行业知识 > JAVA面试题分享五百六十五:为啥Redis用哈希槽,不用一致性哈希?

行业知识

JAVA面试题分享五百六十五:为啥Redis用哈希槽,不用一致性哈希?

2026-11-20 16:49:52 来源:互联网转载

首先,从使用hash取模数据分片开始说起

���论是哈希槽,还是一致性hash,都属于hash取模数据分片。

先从经典的hash取模数据分片说起

假如 Redis集群的节点数为3个,使用经典的hash取模算法进行数据分片,实际上就是一个节点一个数据分片,分为3片而已。

每次请求使用 hash(key) % 3 的方式计算对应的节点,或者进行 分片的路由。

经典哈希取模分片的问题和对策:

哈希取模分片有一个核心问题:对扩容不友好,扩容的时候数据迁移规模太大。

比如,把节点从3个扩展到4个, 具体如下:

原来的分片路由算法是:hash(key) % 3

现在的分片路由算法是:hash(key) % 4

分片路由算法调整之后,那么,大量的key需要进行节点的迁移。

换句话,即当增加或减少节点时,原来节点中的80%以上的数据,可能会进行迁移操作,对所有数据重新进行分布。

如何应对呢?

规避的措施之一:如果一定要采用哈希取模分片,建议使用多倍扩容的方式,这样只需要适移50%的数据。例如以前用3个节点保存数据,扩容为比以前多一倍的节点即6个节点来保存数据,这样移动50%的数据即可。

规避的措施之一:采用一致性hash分片方法。

哈希取模分片优点:

  • 配置简单:对数据进行哈希,然后取余

    哈希取模分片缺点:

    • 数据节点伸缩时,导致大量数据迁移

    • 迁移数量和添加节点数据有关,建议翻倍扩容

      一致性hash算法

      如果redis使用一致性hash算法进行数据分片,那么核心会涉及到的两个阶段:

      • 第一阶段,需要完成key到slot槽位之间的映射。

      • 第二阶段,需要完成slot槽位到 redis node节点之间的映射。

        首先看第一阶段。

        第一阶段,需要完成key到slot槽位之间的映射

        第一阶段,使用了哈希取模的方式,不同的是:  对 2^32 这个固定的值进行取模运算。

        注意,这里的取模的除数,是 2^32 , 相当于  2^32个槽位, 英文是 slot 。

        通过这个槽位的计算,可以确定 key => slot 之间的映射关系。

        第二阶段,需要完成slot槽位到 redis node节点之间的映射。

        第二阶段,需要完成slot槽位到 redis node节点之间的映射。

        如何完成 slot  槽位到node 节点之间的映射呢?

        这里,需要 采用一种特殊的结构:Hash槽位环。

        Hash槽位环

        把一致哈希算法是对 2^32  slot 槽位虚拟成一个圆环,环上的对应 0~2^32 刻度,

        如何完成 slot  槽位到node 节点之间的映射呢?

        假设有4个redis 节点, 可以把 2^32  slot 槽位环分成4段, 每一个redis 节点负责存储一个slot分段

        如何对每一个key进行node 路由呢?

        第一步 进行slot槽位计算:每一个key进行hash运算,被哈希后的结果 2^32  取模,获得slot 槽位、

        第二步 在hash槽位环上,按顺时针去找最近的redis节点,这个key将会被保存在这个节点上。

        一致性哈希原理:

        将所有的数据用hash取模, 映射到 2^32个槽位。

        把2^32个槽位 当做一个环,把N个redis 节点瞬时间放置在槽位环上,从而把槽位环分成N段,每redis 节点负责一个分段。

        当key在槽位环上路由的时候,按顺时针去找最近的redis节点,这个key将会被保存在这个节点上。

        来看一致性哈希 三个经典场景:

        经典场景1:Key入环

        下图我们四个key(Key1/Key2/Key3)经过哈希计算,放入下面环中,第一步是进行hash计算,取模后得到slot槽位。

        找到了slot槽位,相当于已经成功映射到哈希环上,

        然后将槽位按顺时针方向,找到离自己最近的redis节点上,将value存储到那个节点上。

        经典场景2:新增redis节点

        现在,需要对redis 节点进行扩容, 在redis1 和 redis2之间,新增加点redis 5。

        具体的操作是:在hash槽位环上,把redis 5节点放置进去

        添加了新节点之后,对所有的redis 2上的数据,进行重新的检查。

        如果redis 2上的数据,顺时针方式最近的新节点不是redis 2而是 redis 5的话,需要进行迁移,迁移到redis 5。

        比如,上图的key2,需要从redis 2迁移 redis 5。

        而其他节点上的数据,不受影响。比如redis1、redis3、redis4上的数据不受影响。上图中,key1和key3不受影响

        经典场景3:删除redis节点

        假设,删除hash环上的节点redis 2

        那么存储在redis 2节点上的key2,将会重新映射找到离它最近的节点redis3,如下图

        另外,key1、key3不受影响。

        经典哈希取模与一致性hash的对比:

        前面讲到,假设Redis 集群使用经典哈希取模分片, 缺点是在数据节点伸缩时,导致大量数据迁移:

        • 最少50%的数据要迁移,这个是在翻倍扩容场景

        • 一般有80%以上的数据要迁移。

          假设Redis 集群使用一致性哈希取模分片, 通过上面的一致性哈希取模新增节点、一致性哈希取模删除节点的分析之后, 可以得到:

          • 一致性hash在伸缩的时候, 需要迁移的数据不到25%(假设4个节点)。

          • 和普通hash取模分片相比, 一致性哈希取模分片需要 迁移的数据规模缩小2倍以上。

            一致性hash的数据不平衡(数据倾斜)问题

            标准的一致性hash,存在一个大的问题:数据不平衡(数据倾斜)问题。

            回顾一下,一致性hash算法的两个阶段:

            • 第一阶段,需要完成key到slot槽位之间的映射。

            • 第二阶段,需要完成slot槽位到 redis node节点之间的映射。

              在这个两阶段中,数据不平衡(数据倾斜)问题的来源在第二阶段:

              • 第一个阶段,hash算法是均匀的。

              • 第二个阶段,如果某个节点宕机,那么就会出现节点的不平衡。

                迁移之后,发生了 严重的数据倾斜,或者不平衡。Redis 3上4个key,而redis 1、redis 4上只有1个key。

                这样,redis2 上的数量很多,此时会导致节点压力陡增。

                旱涝不均。

                那如何解决这个旱涝不均问题呢?答案是通过 虚拟节点。

                什么是 虚拟节点?

                虚拟节点 可以理解为逻辑节点,不是物理节点。 假设在hash环上,引入 32 个虚拟 reids节点。

                如何找到物理节点呢? 办法是增加一次映射:虚拟节点到物理节点的映射。

                假设加上一层  32 个虚拟 redis节点到 4个  redis 物理节点映射。一种非常简单的map参考映射方案

                假设物理节点 redis 3被移除,那么,把redis 3负责的逻辑节点,二次分配到其他三个物理节点就行了

                无论如何,通过虚拟节点,就会大大减少了 一致性hash 算法的数据倾斜/数据不平衡。

                一致性hash的简易实现

                可以使用TreeMap 来实现一致性hash,原因有二:

                • TreeMap的key是有序,

                • 使用TreeMap的ceilingEntry(K k) 方法,可以返回大于或等于给定参数K的键, 这就是映射到的节点。

                  TreeMap是一个小顶堆,默认是根据key的自然排序来组织(比如integer的大小,String的字典排序)。底层是根据红黑树的数据结构构建的。

                  这里使用TreeMap的ceilingEntry(K key) 方法,该方法用来返回与该键至少大于或等于给定键,如果不存在这样的键的键 - 值映射,则返回null相关联。

                  一致性hash的简易实现,参考代码如下:

                  package com.th.treemap;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.TreeMap;public class ConsistentHash {    /**     * 假设我们一共初始化有8个节点(可以是ip, 就理解为ip吧);     * 把 1024个虚拟节点跟 8个资源节点相对应     */    public static Map nodeMap = new HashMap();    public static int V_redisS = 1024; // 假设我们的环上有1024个虚拟节点    static TreeMap virtualHashRingMap = new TreeMap();    private static final Integer REAL_redis_COUNT = 8;    static {        nodeMap.put(0, "redis_0");        nodeMap.put(1, "redis_1");        nodeMap.put(2, "redis_2");        nodeMap.put(3, "redis_3");        nodeMap.put(4, "redis_4");        nodeMap.put(5, "redis_5");        nodeMap.put(6, "redis_6");        nodeMap.put(7, "redis_7");          for (Integer i = 0; i  ASK 重定向目标节点」这一流程。 

                  问题3:为什么Redis Cluster哈希槽数量是16384 (16K)?

                  前面讲到 redis 哈希与一致性hash所不同的是:

                  • 第一:槽位规模不同。

                    redis 集群将数据划分为 16384 个槽位(哈希槽),一致性hash有  2^32 个槽位。

                  • 第二:hash slot和node 节点的映射关系不同。

                    一致性hash是哈希环顺时针映射, redis 哈希槽是静态映射。

                    问题是:一致性哈希算法是对2的32次方取模,而哈希槽是对2的14次方取模。为啥Redis 不设置 2的32次方 个槽位呢?

                    为啥 16384 (16K) 个槽位, redis 给出的主要原因是:

                    • 1:网络带宽的因素:

                      Redis节点间通信时,心跳包会携带节点的所有槽信息,通过这些槽位元数据来更新配置。

                      所以,槽位数量不能太多,如果太多,那么通讯的报文就太大了。reids 采用 16384 个插槽,一个槽位占用一个二进制为,16384  (16384/8=2048)占通讯报文空间 2KB;  反过来,如果采用 65536 个插槽,占空间 8KB (65536/8)。

                    • 2:当集群扩展到1000个节点时,也能确保每个master节点有足够的插槽,每个节点16384 /1024=16个槽位,也足够了

                    • 3:Redis Cluster 不太可能扩展到超过 1000 个主节点,太多可能导致网络拥堵。

                      在实际应用中,一个redis cluster集群不超过200个节点,超过200个节点就会有大量的gossip 协议的报文, 很容易出现网络拥塞。

                      关于这个问题,Redis作者的回答在这里:why redis-cluster use 16384 slots? · Issue #2576 · redis/redis

                      为什么Redis是使用哈希槽而不是一致性哈希呢?

                      接下来,我们再总结一下,为什么Redis是使用哈希槽而不是一致性哈希呢?

                      首先, Redis哈希槽和一致性哈希,总体的流程都是差不多的,都是两个阶段:

                      • 第一阶段是:hash 取模

                      • 第二阶段是:node 映射

                        第一阶段都是 hash 之后取模分片。分为两步:

                        • 第一步:hash。hash算法的功效,核心就是保证数据不倾斜,或者说保证分布均匀。redis cluster 的hash算法,采用的是 crc16 哈希算法。

                        • 第二步:取模。就是槽位的数量, redis 集群的把数据分为16484 (16K)个slot槽位。一致性哈希是 2的32次方个槽位。

                          为啥redis cluster 不设置 2的32次方个槽位呢?主要是考虑节点数在1000的规模一下,而是使用gossip 去中心一致性协议,数据包不能太大,16K 个二进制位 2K字节已经很大了。

                          第二阶段是:node 映射。

                          • 一致性hash是哈希环顺时针映射,

                          • redis 哈希槽是静态映射。

                            通过前面的对比,得到一个结论:

                            • 一致性hash 哈希环顺时针映射 优先考虑的是:如何实现 最少的节点数据发生数据迁移。

                              一致性hash 哈希环上面,只有被干掉的节点顺时针方向最近的那一个节点涉及到数据迁移;其他间隔较远的节点,不涉及到数据迁移。

                            • redis cluster  哈希槽静态映射 优先考虑的是: 如何 实现数据的均匀。

                              redis cluster 各个节点都会参与数据迁移,优先保证各个redis节点承担同样的访问压力。

                            • 同时,redis cluster  哈希槽静态映射还有一个优点,手动迁移。

                              redis cluster  可以自动分配,也可以根据节点的性能(比如Memory大小) 手动的调整slot的分配。

                              附录1:Raft 协议

                              Raft协议对标Paxos,容错性和性能都是一致的,但是Raft比Paxos更易理解和实施。系统分为几种角色:Leader(发出提案)、Follower(参与决策)、Candidate(Leader选举中的临时角色)。

                              刚开始所有节点都是Follower状态,然后进行Leader选举。成功后Leader接受所有客户端的请求,然后把日志entry发送给所有Follower,当收到过半的节点的回复(而不是全部节点)时就给客户端返回成功并把commitIndex设置为该entry的index,所以是满足最终一致性的。

                              Leader同时还会周期性地发送心跳给所有的Follower(会通过心跳同步提交的序号commitIndex),Follower收到后就保持Follower状态(并应用commitIndex及其之前对应的日志entry),如果Follower等待心跳超时了,则开始新的Leader选举:首先把当前term计数加1,自己成为Candidate,然后给自己投票并向其它结点发投票请求。直到以下三种情况:

                              • 它赢得选举;

                              • 另一个节点成为Leader;

                              • 一段时间没有节点成为Leader。

                                在选举期间,Candidate可能收到来自其它自称为Leader的写请求,如果该Leader的term不小于Candidate的当前term,那么Candidate承认它是一个合法的Leader并回到Follower状态,否则拒绝请求。

                                如果出现两个Candidate得票一样多,则它们都无法获取超过半数投票,这种情况会持续到超时,然后进行新一轮的选举,这时同时的概率就很低了,那么首先发出投票请求的的Candidate就会得到大多数同意,成为Leader。

                                在Raft协议出来之前,Paxos是分布式领域的事实标准,但是Raft的出现打破了这一个现状(raft作者也是这么想的,请看论文),Raft协议把Leader选举、日志复制、安全性等功能分离并模块化,使其更易理解和工程实现,将来发展怎样我们拭目以待(挺看好)。

                                Raft协议目前被用于 cockrouchDB,TiKV等项目中,据我听的一些报告来看,一些大厂自己造的分布式数据库也在使用Raft协议。

                                附录2:Gossip 协议

                                Gossip协议与raft协议最大的区别就是它是彻底的去中心化的,

                                Gossip 协议也叫 Epidemic Protocol(流行病协议),主要用于消息传播,是一种一致性算法。

                                协议也非常好理解,正如协议的名称,如流行病一样靠“感染”节点进行持续传播。

                                使用 Gossip 协议的有:Redis Cluster、Consul、Apache Cassandra等。

                                Gossip协议基本思想就是:一个节点想要分享一些信息给网络中的其他的节点,于是随机选择一些节点进行信息传递。这些收到信息的节点接下来把这些信息传递给其他一些随机选择的节点。

                                Gossip 整体过程描述如下。

                                1. Gossip 是周期性的散播消息

                                2. 被感染节点随机选择 k 个邻接节点(fan-out)散播消息,假设把 fan-out 设置为2,每次最多往2个节点散播

                                3. 每次散播消息都选择尚未发送过的节点进行散播

                                4. 收到消息的节点不再往发送节点散播,比如 A -> B,那么 B 进行散播的时候,不再发给 A

                                前面的raft协议虽然去中心化,但是还是要选出一个类似于Leader的角色来统筹安排事务的响应、提交与中断,

                                但是Gossip协议中就没有Leader,也不选举leader每个节点都是平等的。

                                 

                                Gossip 协议 每个节点存放了一个key,value,version构成的列表,每隔一定的时间,节点都会主动挑选一个在线节点进行上图的过程(不在线的也会挑一个尝试),两个节点各自修改自己较为落后的数据,最终数据达成一致并且都较新。节点加入或退出都很容易。

                                Gossip 协议优点

                                • 扩展性

                                  Gossip 协议的可扩展性极好,一般只需要 O(LogN) 轮就可以将信息传播到所有的节点,其中 N 代表节点的个数。即使集群节点的数量增加,每个节点的负载也不会增加很多,几乎是恒定的。这就允许集群管理的节点规模能横向扩展到几千几万个,集群内的消息通信成本却不会增加很多。

                                  • 容错

                                    网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播,Gossip 协议具有天然的分布式系统容错特性。

                                    • 健壮性

                                      Gossip 协议是去中心化的协议,所以集群中的所有节点都是对等的,任何节点出现问题都不会阻止其他节点继续发送消息。任何节点都可以随时加入或离开,而不会影响系统的整体服务质量。

                                      • 最终一致性

                                        消息传播是指数级的快速传播,因此当有新信息传播时,消息可以快速地发送到全局节点。

                                        系统状态的不一致可以在很快的时间内收敛到一致。

                                        Gossip 协议缺点

                                        • 消息延迟

                                          节点随机向少数几个节点发送消息,消息最终是通过多个轮次的传播而到达全网,不可避免的造成消息延迟。不适合于对实时性要求较高的场景。

                                          • 消息冗余

                                            节点会定期随机选择周围节点发送消息,而收到消息的节点也会重复该步骤,因此就不可避免的存在消息重复发送给同一节点的情况,造成了消息的冗余,同时也增加了收到消息的节点的处理压力。

上一篇:怎么看服务器是ssd硬盘?

下一篇:请问怎么看主机型号啊