[译文] Redis 中的哈希槽与一致哈希

关于Redis集群中的哈希槽

Redis 中的哈希槽是在6 多年前Redis Cluster 3.0 版本发布时引入的。事实上，Redis 集群花费了太多时间来开发，你可能会在这个截屏视频当时不稳定的版本）中注意到———Salvatore Sanflippo在它发布前两年就代表了这个特性。

哈希槽表示 Redis 集群背后用于管理密钥的算法。后者代表了传统的异步主从设置在Redis通用单主设置中不具备的分片方案或分布式数据库。

关于Redis集群的一点

Redis 集群，如果将其与非分布式数据库设置的独立 Redis 进行比较，则是一种不同的解决方案，它适用于数据分区或分片。这里的分片意味着数据在多个 Redis 实例之间共享。

如前所述，Redis Cluster 是在 Redis 3.0 版本中添加的，它提供了执行数据同步、复制和管理节点访问持久性（如果某些会宕机）的能力。这意味着 Redis Cluster 为在节点出现故障或通信问题的情况下继续操作提供一定程度的可用性。此外，它只是代表了用于分段、复制和节点管理的完整集群解决方案。

Redis 集群中的节点使用 Redis 集群协议与 Redis 集群中的每个其他节点连接，以获得网状网络拓扑。节点使用 TCP 八卦协议和配置更新机制进行通信，以减少节点之间交换的消息数量。

尽管 Redis Cluster 是 Redis 中的一个强大功能，但就独立 Redis 而言，它有其局限性，例如，如果您使用带有副本的主节点。例如，在独立的 Redis 中，如果您有一个主从复制，则可以使用 0 - 15 个数据库（默认情况下），您可以通过配置进行调整。但是，在一个Redis Cluster中，只能在数据库0中操作，即只有一个数据库，并且不允许使用SELECT命令。另一方面，并​​非所有命令都可以像所说的那样工作，例如MSET和MGET不能工作，因为它们必须驻留在一个插槽中。

例如：

192.168.40.190:6001> keys *<font></font>
1) "mykey{node2}"<font></font>
2) "kiddo:3"<font></font>
3) "mykey2{node2}"<font></font>
4) "book:2"

虽然这行不通：

192.168.40.190:6001> mget mykey{node2} mykey2{node2} book:2<font></font>
(error) CROSSSLOT Keys in request don't hash to the same slot

或者

192.168.40.190:6001> mget mykey{node2} mykey2{node2} kiddo:3<font></font>
(error) CROSSSLOT Keys in request don't hash to the same slot

然而：

192.168.40.190:6001> mget mykey{node2} mykey2{node2}<font></font>
1) "a,b,c"<font></font>
2) "a,b,c"

由于它们使用Hash Tags位于同一个插槽上。它是一个 Redis 集群概念，可用于强制某些键存储在同一个哈希槽中。检查其钥匙槽时，将显示以下信息：

192.168.40.190:6001> CLUSTER KEYSLOT mykey{node2}<font></font>
(integer) 15917<font></font>
192.168.40.190:6001> CLUSTER KEYSLOT mykey2{node2}<font></font>
(integer) 15917

而其他键在同一个节点上但在不同的插槽上：

192.168.40.190:6001> CLUSTER KEYSLOT kiddo:3<font></font>
(integer) 14082<font></font>
192.168.40.190:6001> CLUSTER KEYSLOT book:2<font></font>
(integer) 12948

什么是Redis中的哈希槽？

Redis 集群使用一种称为一致性散列的复合分区形式，它计算特定键应分配给哪个 Redis 实例。这个概念在 Redis 集群中被称为哈希槽。密钥空间在集群中的不同主节点之间进行分区。它分为 16384 个槽，有效地设置了 16384 个主节点的集群大小上限（但是，建议的最大节点大小约为 1000 个节点）。

哈希槽是将CRC-16哈希算法应用于键，然后使用 16384 计算模数。 Redis 集群用于计算键的哈希槽的具体哈希算法是：

HASH_SLOT = CRC16(key) mod 16384

尽管 CRC-16 有其他类型，但 Redis 有以下使用该算法的细节：

• 名称：XMODEM（也称为ZMODEM或CRC-16/ACORN或CRC-CCITT）
• 宽度：16位
• 多边形：1021（实际上是 x 16 + x12 + x5 + 1）
• 初始化：0000
• 反映输入字节：假
• 反射输出 CRC：假
• 输出 CRC 的异或常数：0000
• “123456789”的输出：31C3

每个主节点都分配有一个子范围的哈希槽，并且键和值将驻留在该 Redis 实例上。基本上，每个键都被散列成一个介于 0 和 16383 之间的数字。这 16k 个散列槽被分配给不同的主节点。

如果您想知道为什么是 16384（或 0 - 16383），Salvatore 对此有很好的解释。基本上，Redis 选择 16384 个槽是因为 16384 条消息只占用 2k，而 65535 则需要 8k。出于集群规模设计考虑，集群最多支持 1000 个分片。16384是一个比较好的选择。需要保证在最大的集群规模和均匀分布的槽位下，每个分片的平均槽数不是太大而是太小。

一致性哈希与哈希槽
在 Redis 3.0 之前，当 Redis Cluster 还不可用时，在多个 master 之间分配 key 以观察负载管理以实现分片或数据分区时一直是一个挑战。对于Redis 3.0及以下版本，Redis-server没有分片功能，只有主从模式。就用于缓存到 Redis 的密钥的充分分配而言，一致散列和散列槽是足够的算法。还有其他方法可以实现这样的逻辑拆分或散列算法 - 虽然其他算法有效，但与一致性散列和 Redis 主从模式中常用的散列槽相比，它的性能不如或性能低得多或 Redis 集群。但是在这篇博客中，我们将重点介绍两种算法模式，Consistent Hashing 和 Hash Slot。

顾名思义，这两种算法都使用哈希函数，因此使用哈希表。考虑一个您不断填充或检索存储桶对象的存储桶。Consistent Hashing 和 Hash Slots 的操作类似于存储桶。假设我们有一个大小为 N 的数组，每个条目都指向一个对象桶。添加一个新对象需要我们做 ah(k) % N 即 hash(key) modulo N。然后检查结果索引处的桶。如果对象尚不存在，则添加该对象。要搜索一个对象，我们也这样做，只是查看存储桶以检查该对象是否在那里。尽管哈希表（或此类比中的桶）中的搜索是线性的，但适当大小的哈希表每个桶应具有相当少的对象数量，从而导致几乎恒定的时间访问平均时间复杂度为 O(N/k) ,

一致性哈希

Redis 中的多个客户端都支持一致性哈希。Twemproxy支持多种散列模式，包括一致性散列和分发。Jedis、Ketama等其他客户也在使用这种方法。

Consistent Hashing 是一种不直接依赖于服务器数量的分配方案，因此在添加或删除服务器时，需要重新定位的密钥数量被最小化。一致性哈希是一个简单但聪明的概念。Karger 等人首先描述了它。1997 年在麻省理工学院的一篇学术论文中。它通过在抽象圆或哈希环上为它们分配一个位置而独立于分布式哈希表中的服务器或对象的数量。这允许服务器和对象在不影响整个系统的情况下扩展。是一个0 - 2 ^ 32 - 1次方的圆，主要操作步骤如下：

• 哈希一个节点，通常使用其节点的IP或带有唯一标签的数据进行哈希（IP），并将其值分配在这个封闭的圆圈上。
• Hash（key）存储的key，然后在这个封闭的圆上分配它的值。
• 从 hash(key) 映射到圆圈的位置顺时针找到的节点是存储密钥的节点。如果圆上0处没有找到节点，则0后顺时针方向的第一个节点为key存储节点。

基本上，顺时针方向要么是逆时针，要么是逆时针方向，只要它围绕应根据圆圈中节点的分布存储哈希（密钥）的检查。例如，请考虑我的以下示例：

以下哈希是我使用 CRC-32 作为节点名称的地方，结果如下：

考虑插入我心爱的宠物的名字，我最终得到以下结果，

在我们的图中，它根据顺时针模式检查哪个散列应该属于。然而，这些值根据其在圆圈中的 2 ^ 32 - 1 个哈希值内的范围进行检查和放置。这些值被分配为存储，它是按顺时针模式放置后的最近邻居。在这方面，请考虑 nodeA 崩溃或遇到网络分区。显然，我们在图中的平衡程度将被拆除，因为顺时针模式中的下一个邻居将是应存储密钥的目的地的目标。在那种情况下，这就是拓扑发生变化时的处理方式，

在这种状态下，它会导致数据倾斜，导致密钥分布不平衡，而节点 B 与节点 C 相比，可以留下较少的密钥。现在，这会影响缓存的性能状态，因为这意味着必须将密钥移动到另一个节点。需要注意的是，在Redis Cluster之前，该算法不是由Redis服务器本身或Redis数据库识别，而是由TwemProxy、Jedis等客户端识别为示例之一。在这种情况下，确定其所属的键可能会影响与 Redis 连接以检查是否存在缓存的应用程序的性能。否则，它将添加或存储新密钥（假设是来自当前正在经历网络分区的节点的现有密钥）。当然，

在你的Redis主从模式集群一直出现网络分区的现象中，时刻保持高可用非常重要。这意味着可以配置和设置从属服务器和 Redis Sentinel 以进行故障转移，并在分片集群中扮演发生故障的主服务器的角色。但是，这在 Redis 集群中是不同的情况。

Redis 集群中的哈希槽

由于我们之前已经讨论过 Redis 集群中的哈希槽，因此哈希槽仍然共享使用哈希或复合分区的概念，但不依赖于一致性哈希所基于的基于圆的算法。哈希槽负责处理分片环境中主从模型所没有的重要性，例如添加和删除节点。在这种情况下，水平向上或向下扩展可以很顺利，或者至少对 Redis 集群的性能影响较小。考虑下图：

从图像中深入了解Redis的聚类

哈希槽是预先计算好的，它完全由 Redis 集群的管理员决定。例如，这是在创建集群时预先确定的：

root@pupnode18:~# redis-cli --cluster create 192.168.40.170:6001 192.168.40.180:6001 192.168.40.190:6001 192.168.40.210:6001 192.168.40.221:6001 192.168.40.222:6001 --cluster-replicas 1<font></font>
<font></font>
>>> Performing hash slots allocation on 6 nodes...<font></font>
<font></font>
Master[0] -> Slots 0 - 5460<font></font>
<font></font>
Master[1] -> Slots 5461 - 10922<font></font>
<font></font>
Master[2] -> Slots 10923 - 16383<font></font>
<font></font>
Adding replica 192.168.40.221:6001 to 192.168.40.170:6001<font></font>
<font></font>
Adding replica 192.168.40.222:6001 to 192.168.40.180:6001<font></font>
<font></font>
Adding replica 192.168.40.210:6001 to 192.168.40.190:6001<font></font>
<font></font>
M: f1502d9387e91c1e36cb0c309a5d57ac55bd74bb 192.168.40.170:6001<font></font>
<font></font>
  slots:[0-5460] (5461 slots) master<font></font>
<font></font>
M: 361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6 192.168.40.180:6001<font></font>
<font></font>
  slots:[5461-10922] (5462 slots) master<font></font>
<font></font>
M: 2f35603cb4b0fc89241af0c0fc44b36181f9c298 192.168.40.190:6001<font></font>
<font></font>
  slots:[10923-16383] (5461 slots) master<font></font>
<font></font>
S: 2bedffc625d87413758125d695ee53f69b14cc5f 192.168.40.210:6001<font></font>
<font></font>
  replicates 2f35603cb4b0fc89241af0c0fc44b36181f9c298<font></font>
<font></font>
S: ea3f9475069cc8a93a26af8d649136ae1617f07c 192.168.40.221:6001<font></font>
<font></font>
  replicates f1502d9387e91c1e36cb0c309a5d57ac55bd74bb<font></font>
<font></font>
S: 5fadaa2a1b3a06b0fcf88e29e754ed053dce8e9a 192.168.40.222:6001<font></font>
<font></font>
  replicates 361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6<font></font>
<font></font>
Can I set the above configuration? (type 'yes' to accept): yes<font></font>
<font></font>

在上面的命令中，我指示使用具有 3 个主节点和 3 个副本的redis-cli命令启动我的 Redis 集群。除此之外，值得一提的是哈希槽的自动分配，即

Master[0] -> Slots 0 - 5460<font></font>
Master[1] -> Slots 5461 - 10922<font></font>
Master[2] -> Slots 10923 - 16383

使用 yes 接受后，Redis 将自动计算所有这些插槽分配以及主副本的设置：

>>> Nodes configuration updated<font></font>
<font></font>
>>> Assign a different config epoch to each node<font></font>
<font></font>
>>> Sending CLUSTER MEET messages to join the cluster<font></font>
<font></font>
Waiting for the cluster to join<font></font>
<font></font>
<font></font>
<font></font>
>>> Performing Cluster Check (using node 192.168.40.170:6001)<font></font>
<font></font>
M: f1502d9387e91c1e36cb0c309a5d57ac55bd74bb 192.168.40.170:6001<font></font>
<font></font>
  slots:[0-5460] (5461 slots) master<font></font>
<font></font>
  1 additional replica(s)<font></font>
<font></font>
M: 2f35603cb4b0fc89241af0c0fc44b36181f9c298 192.168.40.190:6001<font></font>
<font></font>
  slots:[10923-16383] (5461 slots) master<font></font>
<font></font>
  1 additional replica(s)<font></font>
<font></font>
S: 2bedffc625d87413758125d695ee53f69b14cc5f 192.168.40.210:6001<font></font>
<font></font>
  slots: (0 slots) slave<font></font>
<font></font>
  replicates 2f35603cb4b0fc89241af0c0fc44b36181f9c298<font></font>
<font></font>
M: 361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6 192.168.40.180:6001<font></font>
<font></font>
  slots:[5461-10922] (5462 slots) master<font></font>
<font></font>
  1 additional replica(s)<font></font>
<font></font>
S: ea3f9475069cc8a93a26af8d649136ae1617f07c 192.168.40.221:6001<font></font>
<font></font>
  slots: (0 slots) slave<font></font>
<font></font>
  replicates f1502d9387e91c1e36cb0c309a5d57ac55bd74bb<font></font>
<font></font>
S: 5fadaa2a1b3a06b0fcf88e29e754ed053dce8e9a 192.168.40.222:6001<font></font>
<font></font>
  slots: (0 slots) slave<font></font>
<font></font>
  replicates 361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6<font></font>
<font></font>
[OK] All nodes agree about slots configuration.<font></font>
<font></font>
>>> Check for open slots...<font></font>
<font></font>
>>> Check slots coverage...<font></font>
<font></font>
[OK] All 16384 slots covered

现在，回到上面显示的带有 Hash Slots 的图像，您可以看到 Redis Cluster 的强大功能以及完整的高可用性和冗余设置。请注意，您可以检索或查询以从从站获取密钥，但当然，在副本/从站中未启用写入。Redis Sentinel 设置在这里没有意义，因为 Redis Cluster Bus 和 gossip 协议处理这种持续监控，以确定集群节点是否健康或需要自动故障转移以防无法访问或停止与其余节点通信集群中的节点。

让我们在 Redis 集群中玩转哈希槽。首先，让我们看看节点列表及其分配的相关插槽：

192.168.40.170:6001> CLUSTER SLOTS<font></font>
<font></font>
1) 1) (integer) 0<font></font>
<font></font>
   2) (integer) 5460<font></font>
<font></font>
   3) 1) "192.168.40.170"<font></font>
<font></font>
      2) (integer) 6001<font></font>
<font></font>
      3) "f1502d9387e91c1e36cb0c309a5d57ac55bd74bb"<font></font>
<font></font>
   4) 1) "192.168.40.221"<font></font>
<font></font>
      2) (integer) 6001<font></font>
<font></font>
      3) "ea3f9475069cc8a93a26af8d649136ae1617f07c"<font></font>
<font></font>
2) 1) (integer) 5461<font></font>
<font></font>
   2) (integer) 10922<font></font>
<font></font>
   3) 1) "192.168.40.180"<font></font>
<font></font>
      2) (integer) 6001<font></font>
<font></font>
      3) "361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6"<font></font>
<font></font>
   4) 1) "192.168.40.222"<font></font>
<font></font>
      2) (integer) 6001<font></font>
<font></font>
      3) "5fadaa2a1b3a06b0fcf88e29e754ed053dce8e9a"<font></font>
<font></font>
3) 1) (integer) 10923<font></font>
<font></font>
   2) (integer) 16383<font></font>
<font></font>
   3) 1) "192.168.40.190"<font></font>
<font></font>
      2) (integer) 6001<font></font>
<font></font>
      3) "2f35603cb4b0fc89241af0c0fc44b36181f9c298"<font></font>
<font></font>
   4) 1) "192.168.40.210"<font></font>
<font></font>
      2) (integer) 6001<font></font>
<font></font>
      3) "2bedffc625d87413758125d695ee53f69b14cc5f"<font></font>
<font></font>
Now let's clear the keys for all master nodes then add the keys:<font></font>
<font></font>
192.168.40.170:6001> flushall async<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.170:6001> set waffles "white pet and chubby"<font></font>
<font></font>
-> Redirected to slot [14766] located at 192.168.40.190:6001<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.190:6001> set aysin "grayed hair and loves to lick"<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.190:6001> set happie "white and loves to lay eggs"<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.190:6001> set dindin "white and smallest yet cute tailed puff"<font></font>
<font></font>
-> Redirected to slot [10464] located at 192.168.40.180:6001<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.180:6001> set timmie "killer eyes when has done something bad"<font></font>
<font></font>
-> Redirected to slot [1602] located at 192.168.40.170:6001<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.170:6001> set cookies "max favorite playmate"<font></font>
<font></font>
-> Redirected to slot [13754] located at 192.168.40.190:6001<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.190:6001> keys *<font></font>
<font></font>
1) "happie"<font></font>
<font></font>
2) "aysin"<font></font>
<font></font>
3) "cookies"<font></font>
<font></font>
4) "waffles"<font></font>
<font></font>
192.168.40.190:6001> set pepper "tummy touches the ground"<font></font>
<font></font>
-> Redirected to slot [3936] located at 192.168.40.170:6001<font></font>
<font></font>
OK<font></font>
<font></font>
192.168.40.170:6001> set buchappie  "always barks"<font></font>
<font></font>
-> Redirected to slot [7027] located at 192.168.40.180:6001<font></font>
<font></font>
OK

这就是 Redis 集群中哈希槽的情况：

显然，对于这个非常小的数据，我要说的是不平衡的。但是，对于要管理的大型和大数据，这是非常有效的分布。如前所述，通过添加使用Hash Tags，您可以做更多的事情来管理要保留的节点（或技术上的插槽）。例如：

192.168.40.170:6001> keys *<font></font>
<font></font>
1) "pepper"<font></font>
<font></font>
2) "timmie"<font></font>
<font></font>
192.168.40.170:6001> CLUSTER KEYSLOT "pogiey{pet:cat}"<font></font>
<font></font>
(integer) 3209<font></font>
<font></font>
192.168.40.170:6001> CLUSTER KEYSLOT "pogiey"<font></font>
<font></font>
(integer) 12253

密钥显示在此节点上分配了“pepper”和“timmie”。然而，如果我添加“pogiey”，它将被分配给哈希槽 12253，它属于分配给节点 192.168.40.190 的 10923 - 16383 范围。为了使其与您想要的节点保持一致或保持一致，使用哈希标签解决了这个问题，因为它强制键留在那个节点中，其中 { 和 } 大括号内的字符串是为哈希槽计算的字符串。

考虑到节点 192.168.40.190 宕机，在我的当前示例中存储了最多的密钥。显然，它不会影响性能，因为 Redis 集群有自己的高可用性功能来执行故障转移并让副本接管故障的主服务器。例如，我停止或杀死了节点 192.168.40.190 中的 Redis 服务器，我最终以 192.168.40.210 接管作为主节点，因为它是 192.168.40.190（以前的和失败的主节点）的副本。见下文，

192.168.40.170:6001> cluster nodes<font></font>
<font></font>
361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6 192.168.40.180:6001@16001 master - 0 1625005786259 2 connected 5461-10922<font></font>
<font></font>
2bedffc625d87413758125d695ee53f69b14cc5f 192.168.40.210:6001@16001 master - 0 1625005786761 7 connected 10923-16383<font></font>
<font></font>
2f35603cb4b0fc89241af0c0fc44b36181f9c298 192.168.40.190:6001@16001 master,fail - 0 1625005785657 3 connected<font></font>
<font></font>
ea3f9475069cc8a93a26af8d649136ae1617f07c 192.168.40.221:6001@16001 slave f1502d9387e91c1e36cb0c309a5d57ac55bd74bb 0 1625005785254 1 connected<font></font>
<font></font>
f1502d9387e91c1e36cb0c309a5d57ac55bd74bb 192.168.40.170:6001@16001 myself,master - 0 1625005785000 1 connected 0-5460<font></font>
<font></font>
5fadaa2a1b3a06b0fcf88e29e754ed053dce8e9a 192.168.40.222:6001@16001 slave 361e4fdd5a8f9e0eb0c594cc1ef797a07441c0f6 0 1625005785254 2 connected

以粗体突出显示，它表明它仍然可以继续持有并向请求的客户端提供密钥（范围为 10923 - 16383 个哈希槽），从而保持集群的高性能状态。如果节点持有密钥 10923 - 16383（其 IP 以 190 和 221 结尾），则集群无法再工作。见下文：

192.168.40.180:6001> set petnew "something here"<font></font>
<font></font>
(error) CLUSTERDOWN The cluster is down

Redis 日志应显示它无法进行法定人数：

6669:M 29 Jun 2021 22:41:36.273 * Marking node 2f35603cb4b0fc89241af0c0fc44b36181f9c298 as failing (quorum reached).<font></font>
<font></font>
6669:M 29 Jun 2021 22:41:36.273 # Cluster state changed: fail<font></font>
<font></font>
6669:M 29 Jun 2021 22:41:43.318 * Marking node 2bedffc625d87413758125d695ee53f69b14cc5f as failing (quorum reached).<font></font>

由于管理 10923-16383 哈希槽的 master-replica 不再可用，Redis Cluster 共识需要法定人数才能正常和健康地运行——它必须达到至少 3 个主节点运行，并且副本在至少有一个可用于进行故障转移。

现在，如果您考虑扩展或假设替换当前集群中的节点，则可以使用SETSLOT、ADDSLOTS等命令和redis-cli等工具来帮助您。Redis Cluster 在水平扩展和缩减集群时非常高效，甚至在垂直扩展时进行维护。

结论

散列槽与一致散列显示在不同级别上运行以提供数据分发的密钥，尤其是在分布式计算环境中。在这种情况下，分片或数据分区环境是两种算法都适用的地方，以提供最有效的数据管理方式。但是，Hash Slots 是一种新方法，但该算法仅适用于运行 Redis Cluster 时。另一方面，如果使用主副本（或从）模式，则依赖于客户端（例如 Twemproxy 或 Jedis）将依赖于一致的哈希算法。显然，散列槽的行为有所不同，因为它为可以检索密钥的位置强制执行散列的一致性，并且不需要运行其他额外服务（例如 Redis Sentinel）来提供故障转移以实现高可用性。这是由 Redis 集群管理的。尽管 Redis 集群中可能不存在这些特性有利有弊，但在使用 Redis 集群时，向上和向下扩展使其更容易并确保性能和稳定性。因此，散列槽以这种方式更有效。