0%

redis哈希槽

Redis集群中内置了2^14 = 16384个哈希槽,当需要在Redis集群中放置一个 key-value时,Redis先对 key 使用crc16算法算出一个结果,然后把结果对16384取模,这样每个 key 都会对应一个编号在 0-16383 之间的哈希槽,Redis会根据节点数量大致均等的将哈希槽映射到不同的节点。

一、概念

  1. Redis集群中内置了2^14 = 16384个哈希槽,当需要在Redis集群中放置一个 key-value时,Redis先对 key 使用crc16算法算出一个结果,然后把结果对16384取模,这样每个 key 都会对应一个编号在 0-16383 之间的哈希槽,Redis会根据节点数量大致均等的将哈希槽映射到不同的节点。

  2. 基本思想:

    • 一共有16384个槽,每个节点分管其中的一部分
    • 插入一个数据的时候,先根据CRC16算法计算key对应的值,然后用该值对16384取余数(CRC16(key) mod 16384),确定将数据放到哪个槽里面
    • 在增加新节点的时候,其他节点各自分出一些槽给新节点,对应的数据也一起迁出
    • 在移除节点的时候,只需要把待移除节点上的槽挪到其他节点就行了
    • 客户端可以向任何一个Redis节点发送请求,然后由节点将请求重定向到正确的节点上

二、例子

假设现在有3个节点已经组成了集群,分别是:A, B, C(它们可以是一台机器上的三个端口,也可以是三台不同的服务器)。采用哈希槽(hash slot)的方式来分配16384个slot后,它们三个节点分别承担的slot区间是:

  • 节点A覆盖0-5460
  • 节点B覆盖5461-10922
  • 节点C覆盖10923-16383

如果将新节点D添加到集群中,则只需要将节点A、B、C中的某些槽移动到节点D就可以了。通常的做法是从各个节点的前面各拿取一部分slot到D上,最后大致就会变成这样:

  • 节点A覆盖1365-5460
  • 节点B覆盖6827-10922
  • 节点C覆盖12288-16383
  • 节点D覆盖0-1364,5461-6826,10923-12287

如果用户要从集群中移除节点A,那么集群只需要将节点A中的所有哈希槽移动到节点B和C,然后再移除空白(不包含任何哈希槽)的节点A就可以了,最后大概就会变成这样:

  • 节点B覆盖0 - 2820,5461-10922
  • 节点C覆盖2821-5460,10923-16383

三、为什么要选择的槽是16384个呢?

  1. Redis的一个节点的心跳信息中需要携带该节点的所有配置信息,而16K大小的槽数量所需要耗费的内存为2K,但如果使用65K个槽,这部分空间将达到8K,心跳信息就会很庞大。
  2. Redis集群中主节点的数量基本不可能超过1000个。
  3. Redis主节点的配置信息中,它所负责的哈希槽是通过一张bitmap的形式来保存的,在传输过程中,会对bitmap进行压缩,但是如果bitmap的填充率slots / N很高的话
    ,bitmap的压缩率就很低,所以N表示节点数,如果节点数很少,而哈希槽数量很多的话,bitmap的压缩率就很低。而16K个槽当主节点为1000的时候,是刚好比较合理的,既保证了每个节点有足够的哈希槽,又可以很好的利用bitmap。
  4. 选取了16384是因为crc16会输出16bit的结果,可以看作是一个分布在0-2^16-1之间的数,redis的作者测试发现这个数对2^14求模的会将key在0-2^14-1之间分布得很均匀,因此选了这个值。

四、参考链接

  1. hash slot
  2. redis集群教程
  3. redis中文网