集群规范

欢迎阅读 KeyDB 集群规范。在这里，您将找到有关 KeyDB 集群算法和设计原理的信息。本文档正在编写中，因为它将与 KeyDB 的实际实现持续同步。

设计的主要特性和原理#

KeyDB 集群目标#

KeyDB 集群是 KeyDB 的分布式实现，其目标按设计重要性顺序如下：

高性能和高达 1000 个节点的线性可伸缩性。没有代理，使用异步复制，并且不对值执行合并操作。
可接受的写入安全性：系统（尽力而为地）尝试保留来自连接到大多数主节点的客户端的所有写入。通常会有很小的窗口，确认的写入可能会丢失。当客户端位于少数分区时，丢失确认写入的窗口会更大。
可用性：KeyDB 集群能够承受大多数主节点可达的分区，并且对于每个不再可达的主节点，至少有一个可达的副本。此外，通过使用*副本迁移*，不再由任何副本复制的主节点将从由多个副本覆盖的主节点接收一个副本。

已实现子集#

KeyDB 集群实现了 KeyDB 非分布式版本中所有单键命令。只要键都属于同一个节点，执行复杂多键操作的命令，如 Set 类型联合或交集，也已实现。

KeyDB 集群实现了一个名为 哈希标签 的概念，可用于强制某些键存储在同一个节点中。但是，在手动重新分片期间，多键操作可能会在一段时间内不可用，而单键操作始终可用。

KeyDB 集群不支持像独立版本的 KeyDB 那样多的数据库。只有一个数据库 0，并且不允许使用 SELECT 命令。

KeyDB 集群协议中的客户端和服务器角色#

在 KeyDB 集群中，节点负责持有数据，并获取集群状态，包括将键映射到正确的节点。集群节点还能够自动发现其他节点，检测无法工作的节点，并在需要时将副本节点提升为主节点，以便在发生故障时继续运行。

为了执行其任务，所有集群节点都通过 TCP 总线和二进制协议连接，该协议称为 KeyDB 集群总线。集群中的每个节点都通过集群总线连接到所有其他节点。节点使用八卦协议传播有关集群的信息，以发现新节点，发送 ping 包以确保所有其他节点正常工作，并发送表示特定条件所需的集群消息。集群总线还用于在集群中传播 Pub/Sub 消息，并在用户请求时协调手动故障转移（手动故障转移不是由 KeyDB 集群故障检测器发起，而是由系统管理员直接发起）。

由于集群节点无法代理请求，客户端可能会使用重定向错误 -MOVED 和 -ASK 重定向到其他节点。理论上，客户端可以自由地向集群中的所有节点发送请求，如果需要则进行重定向，因此客户端不需要持有集群状态。但是，能够缓存键和节点之间映射的客户端可以显着提高性能。

写入安全性#

KeyDB 集群在节点之间使用异步复制，并采用 最后故障转移获胜 的隐式合并函数。这意味着最后选定的主数据集最终会替换所有其他副本。在分区期间，总会有一段时间可能会丢失写入。然而，对于连接到大多数主节点的客户端和连接到少数主节点的客户端来说，这些时间窗口是截然不同的。

KeyDB 集群更努力地保留由连接到大多数主节点的客户端执行的写入，而不是在少数端执行的写入。以下是在故障期间导致多数分区中丢失已确认写入的场景示例：

写入可能到达主节点，但主节点可能能够回复客户端，而写入可能不会通过主节点和副本节点之间使用的异步复制传播到副本。如果主节点在写入未到达副本的情况下死亡，则如果主节点在足够长的时间内无法访问，以致其某个副本被提升，则写入将永远丢失。在主节点完全突然失效的情况下，这通常很难观察到，因为主节点会尝试同时回复客户端（确认写入）和副本（传播写入）。然而，这是一种真实的故障模式。
另一种理论上可能导致写入丢失的故障模式如下：

主节点由于分区而无法访问。
它被其某个副本故障转移。
一段时间后，它可能再次可访问。
具有过时路由表的客户端可能会在旧主节点被集群转换为副本（新主节点的副本）之前写入旧主节点。

第二种故障模式不太可能发生，因为主节点无法与大多数其他主节点通信足够长的时间以进行故障转移，将不再接受写入，并且当分区修复后，写入仍然会在短时间内被拒绝，以允许其他节点通知配置更改。此故障模式还需要客户端的路由表尚未更新。

针对分区少数端的写入有更大的丢失窗口。例如，KeyDB 集群在具有少数主节点和至少一个或多个客户端的分区上会丢失大量写入，因为发送到主节点的所有写入都可能在主节点在多数端进行故障转移时丢失。

具体来说，主节点要被故障转移，它必须在至少 NODE_TIMEOUT 时间内无法被大多数主节点访问，因此如果在此时间之前修复分区，则不会丢失任何写入。当分区持续时间超过 NODE_TIMEOUT 时，在此之前在少数端执行的所有写入都可能丢失。但是，KeyDB 集群的少数端将在与多数端失去联系后立即开始拒绝写入，因此有一个最大窗口，在此之后少数端变得不再可用。因此，在此之后不会接受或丢失任何写入。

可用性#

KeyDB 集群在分区中的少数端不可用。在分区中的多数端，假设有至少多数主节点和每个无法访问的主节点的一个副本，集群将在 NODE_TIMEOUT 时间加上副本选举并故障转移其主节点所需的几秒钟（故障转移通常在 1 或 2 秒内执行）后再次可用。

这意味着 KeyDB 集群旨在在集群中少数节点发生故障时继续运行，但对于需要在大规模网络分裂事件中保持可用性的应用程序来说，它不是一个合适的解决方案。

在一个由 N 个主节点组成，每个节点都有一个副本的集群示例中，集群的多数端将保持可用，只要单个节点被分区，并且当两个节点被分区时，其可用性概率为 1-(1/(N*2-1))（第一个节点故障后，我们总共有 N*2-1 个节点，唯一没有副本的主节点故障的概率是 1/(N*2-1))）。

例如，在一个有 5 个节点且每个节点只有一个副本的集群中，当两个节点被分区离开多数时，集群不再可用的概率为 1/(5*2-1) = 11.11%。

由于 KeyDB 集群的一项名为 副本迁移 的功能，集群的可用性在许多实际场景中得到了改善，因为副本会迁移到孤立主节点（不再拥有副本的主节点）。因此，在每次成功的故障事件中，集群都可以重新配置副本布局，以便更好地抵御下一次故障。

性能#

在 KeyDB 集群中，节点不将命令代理到负责给定键的正确节点，而是将客户端重定向到服务键空间给定部分的正确节点。

最终，客户端会获得集群的最新表示以及哪个节点服务哪个键子集，因此在正常操作期间，客户端直接联系正确的节点以发送给定命令。

由于使用异步复制，节点不会等待其他节点确认写入（如果不是使用 WAIT 命令显式请求）。

此外，由于多键命令仅限于 *近* 键，因此数据除了在重新分片时，从不会在节点之间移动。

正常操作的处理方式与单个 KeyDB 实例的情况完全相同。这意味着在具有 N 个主节点的 KeyDB 集群中，您可以预期其性能与单个 KeyDB 实例乘以 N 相同，因为设计是线性扩展的。同时，查询通常在一次往返中完成，因为客户端通常与节点保持持久连接，因此延迟数据也与单个独立 KeyDB 节点的情况相同。

KeyDB 集群的主要目标是实现极高的性能和可伸缩性，同时保留弱但合理的安全性形式和可用性。

为什么要避免合并操作#

KeyDB 集群设计避免在多个节点中出现同一键值对的冲突版本，因为在 KeyDB 数据模型中，这并非总是可取的。KeyDB 中的值通常非常大；常见列表或有序集合包含数百万个元素。此外，数据类型在语义上也很复杂。传输和合并这些类型的值可能成为主要瓶颈和/或可能需要应用程序端逻辑的非平凡参与、额外的内存来存储元数据等等。

这里没有严格的技术限制。CRDT 或同步复制的状态机可以模拟类似于 KeyDB 的复杂数据类型。但是，此类系统的实际运行时行为将与 KeyDB 集群不同。KeyDB 集群旨在覆盖非集群 KeyDB 版本的确切用例。

KeyDB 集群主要组件概述#

键分布模型#

键空间被分割成 16384 个槽，有效地将集群大小上限设置为 16384 个主节点（然而，建议的最大节点数量约为 1000 个节点）。

集群中的每个主节点处理 16384 个哈希槽的一个子集。当没有正在进行的集群重新配置（即，哈希槽没有从一个节点移动到另一个节点）时，集群是**稳定的**。当集群稳定时，单个哈希槽将由单个节点提供服务（但是，服务节点可以有一个或多个副本，在网络分裂或故障的情况下，这些副本将替换它，并且可以用于在可接受陈旧数据读取的情况下扩展读操作）。

用于将键映射到哈希槽的基本算法如下（有关此规则的哈希标签例外，请阅读下一段）

HASH_SLOT = CRC16(key) mod 16384

CRC16的规定如下：

名称：XMODEM（也称为 ZMODEM 或 CRC-16/ACORN）
宽度：16 位
多项式：1021（实际为 x^16 + x^12 + x^5 + 1）
初始化：0000
反射输入字节：False
反射输出 CRC：False
与输出 CRC 异或常数：0000
"123456789" 的输出：31C3

CRC16 输出的 16 位中有 14 位被使用（这就是为什么上面公式中有模 16384 操作）。

在我们的测试中，CRC16 在将不同类型的键均匀分布到 16384 个槽中表现出色。

注意：本文档附录 A 中提供了 CRC16 算法的参考实现。

键哈希标签#

哈希槽的计算有一个例外，用于实现 哈希标签。哈希标签是一种确保多个键分配到相同哈希槽的方法。这用于在 KeyDB 集群中实现多键操作。

为了实现哈希标签，在某些条件下，键的哈希槽计算方式略有不同。如果键包含“{...}”模式，则仅对 { 和 } 之间的子字符串进行哈希以获取哈希槽。但是，由于可能存在多个 { 或 }，因此算法由以下规则明确规定：

如果键包含 { 字符。
并且如果 { 右侧有 } 字符
并且如果在第一次出现 { 和第一次出现 } 之间有一个或多个字符。

那么，与其哈希整个键，不如只哈希第一个 { 和其后的第一个 } 之间的内容。

示例：

键 {user1000}.following 和 {user1000}.followers 将哈希到相同的哈希槽，因为为了计算哈希槽，只会哈希子字符串 user1000。
对于键 foo{}{bar}，整个键将像往常一样被哈希，因为第一个 { 后面紧跟着 } 而中间没有字符。
对于键 foo{{bar}}zap，子字符串 {bar 将被哈希，因为它是第一个 { 和其右侧第一个 } 之间的子字符串。
对于键 foo{bar}{zap}，子字符串 bar 将被哈希，因为算法在找到第一个有效或无效（内部没有字节）的 { 和 } 匹配时停止。
从算法中可以得出，如果键以 {} 开头，则保证整个键被哈希。这在使用二进制数据作为键名时非常有用。

加上哈希标签例外，以下是 Ruby 和 C 语言中 HASH_SLOT 函数的实现。

Ruby 示例代码

def HASH_SLOT(key)
s = key.index "{"
if s
e = key.index "}",s+1
if e && e != s+1
key = key[s+1..e-1]
end
end
crc16(key) % 16384
end

C 示例代码

unsigned int HASH_SLOT(char *key, int keylen) {
int s, e; /* { 和 } 的起始-结束索引 */

/* 查找第一个 '{'。 */
for (s = 0; s < keylen; s++)
if (key[s] == '{') break;

/* 没有 '{'？哈希整个键。这是基本情况。 */
if (s == keylen) return crc16(key,keylen) & 16383;

/* 找到 '{'？检查是否有对应的 '}'。 */
for (e = s+1; e < keylen; e++)
if (key[e] == '}') break;

/* 没有 '}' 或 {} 之间没有内容？哈希整个键。 */
if (e == keylen || e == s+1) return crc16(key,keylen) & 16383;

/* 如果我们在这里，则 { 和其右侧的 } 都存在。哈希
* { 和 } 之间的数据。 */
return crc16(key+s+1,e-s-1) & 16383;
}

集群节点属性#

每个节点在集群中都有一个唯一的名称。节点名称是 160 位随机数的十六进制表示，该随机数在节点第一次启动时获得（通常使用 /dev/urandom）。节点将其 ID 保存在节点配置文件中，并将永久使用相同的 ID，或者至少在系统管理员不删除节点配置文件或通过 CLUSTER RESET 命令请求“硬重置”的情况下。

节点 ID 用于在整个集群中识别每个节点。给定节点可以更改其 IP 地址，而无需更改节点 ID。集群还能够检测 IP/端口的变化，并使用在集群总线上运行的八卦协议进行重新配置。

节点 ID 并不是与每个节点关联的唯一信息，但它是唯一始终全局一致的信息。每个节点还具有以下一组关联信息。有些信息是关于此特定节点的集群配置详细信息，并最终在整个集群中保持一致。而其他信息，例如上次 ping 节点的时间，则特定于每个节点。

每个节点都维护着它所知道的集群中其他节点的以下信息：节点 ID、节点的 IP 和端口、一组标志、如果节点被标记为 replica 则其主节点是谁、上次 ping 节点的时间和上次收到 pong 的时间、节点的当前*配置纪元*（在本规范后面详细解释）、链接状态以及最后是服务的哈希槽集。

CLUSTER NODES 文档中详细解释了所有节点字段。

CLUSTER NODES 命令可以发送到集群中的任何节点，并根据查询节点对集群的本地视图提供集群状态和每个节点的信息。

以下是向由三个节点组成的小集群中的主节点发送 CLUSTER NODES 命令的示例输出。

$ keydb-cli cluster nodes
d1861060fe6a534d42d8a19aeb36600e18785e04 127.0.0.1:6379 myself - 0 1318428930 1 connected 0-1364
3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 2 connected 1365-2729
d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 3 connected 2730-4095

在上面的列表中，不同的字段依次是：节点 ID、地址:端口、标志、上次发送 ping、上次收到 pong、配置纪元、链接状态、槽。关于上述字段的详细信息将在我们讨论 KeyDB 集群特定部分时介绍。

集群总线#

每个 KeyDB 集群节点都有一个额外的 TCP 端口，用于接收来自其他 KeyDB 集群节点的传入连接。此端口与用于接收来自客户端传入连接的正常 TCP 端口之间存在固定偏移量。要获取 KeyDB 集群端口，应在正常命令端口上加 10000。例如，如果 KeyDB 节点正在端口 6379 上侦听客户端连接，则集群总线端口 16379 也将打开。

节点间通信完全通过集群总线和集群总线协议进行：一个由不同类型和大小的帧组成的二进制协议。集群总线二进制协议未公开文档，因为它不适用于外部软件设备使用此协议与 KeyDB 集群节点通信。但是，您可以通过阅读 KeyDB 集群源代码中的 cluster.h 和 cluster.c 文件来获取有关集群总线协议的更多详细信息。

集群拓扑#

KeyDB 集群是一个全网格，其中每个节点都通过 TCP 连接与所有其他节点连接。

在 N 个节点的集群中，每个节点有 N-1 个出站 TCP 连接和 N-1 个入站连接。

这些 TCP 连接始终保持活动状态，并且不会按需创建。当节点在集群总线中期望 ping 响应的 pong 回复时，在等待足够长的时间将节点标记为不可达之前，它将尝试通过从头开始重新连接来刷新与节点的连接。

虽然 KeyDB 集群节点形成一个全网格，但**节点使用八卦协议和配置更新机制，以避免在正常情况下节点之间交换过多的消息**，因此交换的消息数量不是指数级的。

节点握手#

节点始终接受集群总线端口上的连接，即使接收到的 ping 节点不受信任，也会回复 ping。但是，如果发送节点不被视为集群的一部分，则接收节点将丢弃所有其他数据包。

节点只有通过两种方式才能将另一个节点视为集群的一部分：

如果一个节点通过 MEET 消息进行自我介绍。meet 消息与 PING 消息完全相同，但强制接收者接受该节点作为集群的一部分。节点**仅当**系统管理员通过以下命令请求时才向其他节点发送 MEET 消息：
CLUSTER MEET ip 端口
如果一个已经受信任的节点传播关于另一个节点的信息，该节点也会将另一个节点注册为集群的一部分。因此，如果 A 知道 B，并且 B 知道 C，最终 B 会将关于 C 的八卦消息发送给 A。当这种情况发生时，A 会将 C 注册为网络的一部分，并尝试连接 C。

这意味着，只要我们以任何连接图加入节点，它们最终都会自动形成一个完全连接的图。这意味着集群能够自动发现其他节点，但前提是存在由系统管理员强制建立的信任关系。

这种机制使集群更加健壮，但阻止了不同 KeyDB 集群在 IP 地址更改或其他网络相关事件后意外混淆。

重定向和重新分片#

MOVED 重定向#

KeyDB 客户端可以自由地向集群中的每个节点（包括副本节点）发送查询。节点将分析查询，如果查询可接受（即，查询中只提到一个键，或者提到的多个键都属于同一个哈希槽），它将查找哪个节点负责键或键所属的哈希槽。

如果该哈希槽由该节点提供服务，则查询将直接处理；否则，该节点将检查其内部哈希槽到节点映射，并向客户端回复一个 MOVED 错误，示例如下：

获取 x
-MOVED 3999 127.0.0.1:6381

错误包括键的哈希槽（3999）和可以服务查询的实例的 IP:端口。客户端需要将查询重新发送到指定的节点 IP 地址和端口。请注意，即使客户端等待很长时间才重新发送查询，在此期间集群配置发生更改，如果哈希槽 3999 现在由另一个节点提供服务，目标节点将再次回复 MOVED 错误。如果联系的节点没有更新的信息，也会发生同样的情况。

因此，从集群的角度来看，节点由 ID 标识，我们尝试通过仅仅暴露哈希槽与由 IP:port 对标识的 KeyDB 节点之间的映射来简化与客户端的接口。

客户端不需要，但应该尝试记住哈希槽 3999 由 127.0.0.1:6381 提供服务。这样，一旦需要发出新命令，它就可以计算目标键的哈希槽，并更有可能选择正确的节点。

另一种方法是，当收到 MOVED 重定向时，使用 CLUSTER NODES 或 CLUSTER SLOTS 命令刷新整个客户端集群布局。当遇到重定向时，很可能多个槽而不是仅仅一个槽被重新配置，因此尽快更新客户端配置通常是最佳策略。

请注意，当集群稳定（配置没有正在进行的更改）时，最终所有客户端都将获得哈希槽 -> 节点的映射，从而使集群高效，客户端直接访问正确的节点而无需重定向、代理或其他单点故障实体。

客户端**还必须能够处理本文档稍后描述的 -ASK 重定向**，否则它不是一个完整的 KeyDB 集群客户端。

集群实时重新配置#

KeyDB 集群支持在集群运行时添加和删除节点。添加或删除节点被抽象为相同的操作：将哈希槽从一个节点移动到另一个节点。这意味着可以使用相同的基本机制来重新平衡集群、添加或删除节点等。

要向集群添加新节点，需向集群添加一个空节点，并将一些哈希槽从现有节点移动到新节点。
要从集群中删除节点，分配给该节点的哈希槽将移动到其他现有节点。
为了重新平衡集群，给定的一组哈希槽在节点之间移动。

实现的核心是移动哈希槽的能力。从实际角度来看，哈希槽只是一组键，因此 KeyDB 集群在**重新分片**期间真正做的是将键从一个实例移动到另一个实例。移动哈希槽意味着移动所有恰好哈希到此哈希槽的键。

为了理解其工作原理，我们需要展示用于在 KeyDB 集群节点中操作槽转换表的 CLUSTER 子命令。

以下子命令可用（此处不相关的其他子命令除外）：

CLUSTER ADDSLOTS slot1 [slot2] ... [slotN]
CLUSTER DELSLOTS slot1 [slot2] ... [slotN]
CLUSTER SETSLOT slot NODE node
CLUSTER SETSLOT slot MIGRATING node
CLUSTER SETSLOT slot IMPORTING node

前两个命令，ADDSLOTS 和 DELSLOTS，仅用于将槽分配（或移除）到 KeyDB 节点。分配槽意味着告诉给定的主节点它将负责存储和提供指定哈希槽的内容。

哈希槽分配后，它们将通过八卦协议在集群中传播，如“配置传播”部分稍后所述。

ADDSLOTS 命令通常在从头创建新集群时使用，以将所有 16384 个可用哈希槽的子集分配给每个主节点。

DELSLOTS 主要用于手动修改集群配置或调试任务：实际上很少使用。

SETSLOT 子命令用于将槽分配给特定的节点 ID（如果使用 SETSLOT <slot> NODE 形式）。否则，槽可以设置为两种特殊状态：MIGRATING 和 IMPORTING。这两种特殊状态用于将哈希槽从一个节点迁移到另一个节点。

当一个槽被设置为 MIGRATING 时，该节点将接受所有关于该哈希槽的查询，但前提是该键存在，否则该查询将使用 -ASK 重定向转发到迁移的目标节点。
当槽被设置为 IMPORTING 时，节点将接受所有关于该哈希槽的查询，但前提是请求前有 ASKING 命令。如果客户端没有给出 ASKING 命令，查询将通过 -MOVED 重定向错误重定向到真正的哈希槽所有者，就像通常发生的那样。

让我们通过哈希槽迁移的示例来更清楚地说明这一点。假设我们有两个 KeyDB 主节点，分别称为 A 和 B。我们想将哈希槽 8 从 A 移动到 B，因此我们发出如下命令：

我们发送 B: CLUSTER SETSLOT 8 IMPORTING A
我们发送 A: CLUSTER SETSLOT 8 MIGRATING B

所有其他节点将继续将客户端指向节点“A”，每当它们使用属于哈希槽 8 的键进行查询时，因此发生的情况是：

所有关于现有键的查询都由“A”处理。
所有关于 A 中不存在键的查询都由“B”处理，因为“A”会将客户端重定向到“B”。

通过这种方式，我们不再在“A”中创建新键。同时，在重新分片和 KeyDB 集群配置期间使用的 keydb-cli 将把哈希槽 8 中存在的键从 A 迁移到 B。这通过以下命令执行：

CLUSTER GETKEYSINSLOT 槽计数

上述命令将返回指定哈希槽中的 count 个键。对于返回的键，keydb-cli 会向节点“A”发送 MIGRATE 命令，该命令将以原子方式将指定键从 A 迁移到 B（两个实例都会在迁移键所需的时间内锁定（通常非常短），因此没有竞争条件）。MIGRATE 的工作原理如下：

MIGRATE 目标_主机 目标_端口 "" 目标_数据库 id 超时 键 key1 key2 ...

MIGRATE 将连接到目标实例，发送键的序列化版本，一旦收到 OK 代码，将从其自身数据集中删除旧键。从外部客户端的角度来看，键在任何给定时间要么存在于 A 中，要么存在于 B 中。

在 KeyDB 集群中，除了数据库 0 之外，无需指定其他数据库，但 MIGRATE 是一个通用命令，可用于不涉及 KeyDB 集群的其他任务。MIGRATE 已优化，即使在移动长列表等复杂键时也能尽可能快，但在 KeyDB 集群中，如果在应用程序使用数据库时存在延迟限制，则重新配置存在大键的集群不被视为明智的做法。

当迁移过程最终完成时，SETSLOT <slot> NODE <node-id> 命令将发送到参与迁移的两个节点，以便将槽重新设置为正常状态。同样的命令通常会发送到所有其他节点，以避免等待新配置在集群中自然传播。

ASK 重定向#

在上一节中，我们简要谈到了 ASK 重定向。为什么我们不能简单地使用 MOVED 重定向？因为 MOVED 意味着我们认为哈希槽永久由不同的节点提供服务，并且下一个查询应该尝试针对指定的节点，而 ASK 意味着仅将下一个查询发送到指定的节点。

这是必要的，因为关于哈希槽 8 的下一个查询可能涉及仍然在 A 中的键，所以我们总是希望客户端先尝试 A，然后根据需要尝试 B。由于这仅发生在 16384 个可用哈希槽中的一个哈希槽上，因此对集群的性能影响是可以接受的。

我们需要强制这种客户端行为，因此为了确保客户端只在尝试 A 之后才尝试节点 B，节点 B 将只接受一个设置为 IMPORTING 的槽的查询，如果客户端在发送查询之前发送了 ASKING 命令。

基本上，ASKING 命令在客户端上设置了一个一次性标志，强制节点服务一个关于 IMPORTING 槽的查询。

从客户端角度看，ASK 重定向的完整语义如下：

如果收到 ASK 重定向，仅将重定向的查询发送到指定节点，但继续将后续查询发送到旧节点。
以 ASKING 命令开始重定向的查询。
暂不更新本地客户端表以将哈希槽 8 映射到 B。

一旦哈希槽 8 迁移完成，A 将发送 MOVED 消息，客户端可以永久将哈希槽 8 映射到新的 IP 和端口对。请注意，如果一个有缺陷的客户端过早执行映射，这不是问题，因为它在发出查询之前不会发送 ASKING 命令，因此 B 将使用 MOVED 重定向错误将客户端重定向到 A。

槽迁移以相似的术语但不同的措辞（为了文档冗余）在 CLUSTER SETSLOT 命令文档中进行了解释。

客户端首次连接和重定向处理#

虽然可以有一个不记住槽配置（槽号与提供服务的节点地址之间的映射）在内存中，并且只通过联系随机节点等待被重定向来工作的 KeyDB 集群客户端实现，但这样的客户端将非常低效。

KeyDB 集群客户端应该尝试足够智能，以记住槽配置。但是，此配置不**需要**保持最新。由于联系错误的节点只会导致重定向，因此应触发客户端视图的更新。

客户端通常需要在两种不同情况下获取槽的完整列表和映射的节点地址：

启动时，用于填充初始槽配置。
当收到 MOVED 重定向时。

请注意，客户端可以通过仅更新其表中的已移动槽来处理 MOVED 重定向，但是这通常效率不高，因为通常会一次性修改多个槽的配置（例如，如果一个副本被提升为主节点，则旧主节点服务的所有槽都将被重新映射）。更简单的做法是，在遇到 MOVED 重定向时，从头开始获取完整的槽到节点映射。

为了获取槽配置，KeyDB Cluster 提供了 CLUSTER NODES 命令的替代方案，它不需要解析，并且仅提供客户端严格所需的信息。

新命令名为 CLUSTER SLOTS，它提供一个槽范围数组，以及服务指定范围的关联主节点和副本节点。

以下是 CLUSTER SLOTS 的输出示例：

127.0.0.1:7000> cluster slots
1) 1) (整数) 5461
2) (整数) 10922
   3) 1) "127.0.0.1"
2) (整数) 7001
   4) 1) "127.0.0.1"
2) (整数) 7004
2) 1) (整数) 0
2) (整数) 5460
   3) 1) "127.0.0.1"
2) (整数) 7000
   4) 1) "127.0.0.1"
2) (整数) 7003
3) 1) (整数) 10923
2) (整数) 16383
   3) 1) "127.0.0.1"
2) (整数) 7002
   4) 1) "127.0.0.1"
2) (整数) 7005

返回数组中每个元素的前两个子元素是范围的起始和结束槽。附加元素表示地址-端口对。第一个地址-端口对是服务该槽的主节点，附加的地址-端口对是所有服务相同槽且未处于错误状态（即，FAIL 标志未设置）的副本。

例如，输出的第一个元素表示槽 5461 到 10922（包括起始和结束）由 127.0.0.1:7001 提供服务，并且可以通过联系 127.0.0.1:7004 处的副本扩展只读负载。

如果集群配置不当，CLUSTER SLOTS 不保证返回覆盖全部 16384 个槽的范围，因此客户端应通过使用 NULL 对象填充目标节点来初始化槽配置映射，并在用户尝试执行属于未分配槽的键命令时报告错误。

在发现槽未分配时向调用方返回错误之前，客户端应尝试再次获取槽配置，以检查集群现在是否已正确配置。

多键操作#

使用哈希标签，客户端可以自由使用多键操作。例如，以下操作是有效的：

MSET {user:1000}.name Angela {user:1000}.surname White

当键所属的哈希槽正在进行重新分片时，多键操作可能会变得不可用。

更具体地说，即使在重新分片期间，针对所有存在且仍在同一节点（无论是源节点还是目标节点）中的键的多键操作仍然可用。

对不存在的键或在重新分片期间在源节点和目标节点之间拆分的键的操作将生成 -TRYAGAIN 错误。客户端可以在一段时间后重试操作，或者报告错误。

一旦指定哈希槽的迁移完成，所有多键操作将再次对该哈希槽可用。

使用副本节点扩展读取#

通常，副本节点会将客户端重定向到给定命令涉及的哈希槽的权威主节点，但是客户端可以使用副本通过 READONLY 命令来扩展读取。

READONLY 告诉 KeyDB 集群副本节点，客户端可以读取可能过时的数据，并且不感兴趣运行写入查询。

当连接处于只读模式时，只有当操作涉及副本主节点不提供服务的键时，集群才会向客户端发送重定向。这可能发生的原因是：

客户端发送了关于此副本主节点从未提供服务的哈希槽的命令。
集群被重新配置（例如重新分片），副本不再能够为给定哈希槽提供命令。

发生这种情况时，客户端应按前几节所述更新其哈希槽映射。

连接的只读状态可以使用 READWRITE 命令清除。

容错#

心跳和八卦消息#

KeyDB 集群节点持续交换 ping 和 pong 包。这两种包具有相同的结构，并且都携带重要的配置信息。唯一的实际区别是消息类型字段。我们将 ping 和 pong 包的总和称为*心跳包*。

通常，节点会发送 ping 包，这将触发接收方回复 pong 包。然而，这并非必然如此。节点也可以仅发送 pong 包，以向其他节点发送有关其配置的信息，而无需触发回复。这对于尽快广播新配置非常有用，例如。

通常，节点每秒会 ping 几个随机节点，因此每个节点发送（和接收）的 ping 和 pong 包总数是一个常量，无论集群中的节点数量如何。

然而，每个节点都会确保 ping 每个超过 NODE_TIMEOUT 时间一半没有发送 ping 或收到 pong 的其他节点。在 NODE_TIMEOUT 到期之前，节点还会尝试重新连接与其他节点的 TCP 链接，以确保节点不会仅仅因为当前 TCP 连接存在问题而被认为是不可达的。

如果 NODE_TIMEOUT 设置为较小值且节点数量 (N) 非常大，则全局交换的消息数量可能很大，因为每个节点都会在 NODE_TIMEOUT 时间的一半内尝试 ping 每个没有新信息的其他节点。

例如，在一个 100 个节点的集群中，节点超时设置为 60 秒，每个节点每 30 秒将尝试发送 99 个 ping，总共每秒 3.3 个 ping。乘以 100 个节点，整个集群每秒有 330 个 ping。

有方法可以减少消息数量，但是目前没有关于 KeyDB 集群故障检测所使用的带宽问题的报告，因此目前使用明显且直接的设计。请注意，即使在上述示例中，每秒交换的 330 个数据包也均匀分配给 100 个不同的节点，因此每个节点接收到的流量是可接受的。

心跳包内容#

Ping 和 pong 包包含一个所有类型包通用的报头（例如，请求故障转移投票的包），以及一个 Ping 和 Pong 包特有的特殊八卦部分。

通用报头包含以下信息：

节点 ID，一个 160 位伪随机字符串，在首次创建节点时分配，并在 KeyDB 集群节点的整个生命周期中保持不变。
发送节点的 currentEpoch 和 configEpoch 字段，用于挂载 KeyDB 集群使用的分布式算法（这将在下一节中详细解释）。如果节点是副本，则 configEpoch 是其主节点的最后一个已知 configEpoch。
节点标志，指示节点是副本、主节点，以及其他单比特节点信息。
发送节点所服务的哈希槽的位图，如果节点是副本，则为其主节点所服务的槽的位图。
发送方 TCP 基本端口（即 KeyDB 用于接受客户端命令的端口；在此基础上加 10000 即可获得集群总线端口）。
从发送方角度看集群的状态（down 或 ok）。
发送节点的主节点 ID（如果它是副本）。

Ping 和 pong 包也包含八卦部分。此部分向接收方提供了发送节点对集群中其他节点的看法。八卦部分仅包含发送方已知节点集中几个随机节点的信息。八卦部分中提到的节点数量与集群大小成比例。

对于八卦部分中添加的每个节点，将报告以下字段：

节点ID。
节点的IP和端口。
节点标志。

八卦部分允许接收节点从发送方角度获取其他节点的状态信息。这对于故障检测和发现集群中的其他节点都很有用。

故障检测#

KeyDB 集群故障检测用于识别主节点或副本节点何时无法被大多数节点访问，然后通过将副本提升为主节点来响应。当无法进行副本提升时，集群将进入错误状态，以停止接收来自客户端的查询。

如前所述，每个节点都带有与其他已知节点相关联的标志列表。用于故障检测的两个标志称为 PFAIL 和 FAIL。PFAIL 表示*可能故障*，是一种未经确认的故障类型。FAIL 表示节点正在发生故障，并且此条件在固定时间内被大多数主节点确认。

PFAIL 标志

当节点超过 NODE_TIMEOUT 时间无法访问时，一个节点会用 PFAIL 标志标记另一个节点。主节点和副本节点都可以将另一个节点标记为 PFAIL，无论其类型如何。

KeyDB 集群节点不可达的概念是，我们有一个**活动的 ping**（我们发送的 ping，尚未收到回复）待处理时间超过 NODE_TIMEOUT。为了使此机制工作，NODE_TIMEOUT 必须相对于网络往返时间而言较大。为了在正常操作期间增加可靠性，节点将在未收到 ping 回复的情况下经过一半 NODE_TIMEOUT 时间后立即尝试与集群中的其他节点重新连接。此机制确保连接保持活动状态，因此断开的连接通常不会导致节点之间出现错误的故障报告。

FAIL 标志

单独的 PFAIL 标志只是每个节点关于其他节点的本地信息，不足以触发副本提升。要使节点被视为宕机，PFAIL 条件需要升级到 FAIL 条件。

如本文档的节点心跳部分所述，每个节点都会向所有其他节点发送八卦消息，其中包含一些随机已知节点的状态。每个节点最终都会收到每个其他节点的一组节点标志。通过这种方式，每个节点都有一种机制来向其他节点发出它们检测到的故障条件信号。

当满足以下条件时，PFAIL 条件升级为 FAIL 条件：

某个节点（我们称之为 A）将另一个节点 B 标记为 PFAIL。
节点 A 通过八卦部分收集了集群中大多数主节点对 B 状态的看法。
大多数主节点在 NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT 时间内发出 PFAIL 或 FAIL 条件信号。（在当前实现中，有效性因子设置为 2，因此这只是 NODE_TIMEOUT 时间的两倍。）

如果以上所有条件都为真，则节点 A 将：

将节点标记为 FAIL。
向所有可达节点发送 FAIL 消息（与心跳消息中的 FAIL 条件不同）。

FAIL 消息将强制每个接收节点将该节点标记为 FAIL 状态，无论它是否已将该节点标记为 PFAIL 状态。

请注意，*FAIL 标志主要是一次性的*。也就是说，节点可以从 PFAIL 变为 FAIL，但 FAIL 标志只能在以下情况下清除：

节点已可访问且是副本。在这种情况下，FAIL 标志可以清除，因为副本不会进行故障转移。
节点已可访问且是未服务任何槽的主节点。在这种情况下，FAIL 标志可以清除，因为没有槽的主节点实际上不参与集群，并且正在等待配置以加入集群。
节点已可访问且是主节点，但已过了很长时间（N 倍 NODE_TIMEOUT）仍未检测到任何副本提升。在这种情况下，最好让它重新加入集群并继续。

值得注意的是，虽然 PFAIL -> FAIL 的转换使用了一种形式的协议，但所使用的协议是弱的：

节点在一段时间内收集其他节点的视图，因此即使大多数主节点需要“同意”，实际上这只是我们从不同节点在不同时间收集的状态，我们不确定，也不要求，在给定时刻大多数主节点都同意。但是我们丢弃过时的故障报告，因此故障是在一段时间内由大多数主节点发出的信号。
虽然每个检测到 FAIL 状况的节点都会使用 FAIL 消息将该状况强制施加到集群中的其他节点，但无法确保消息会到达所有节点。例如，一个节点可能检测到 FAIL 状况，但由于分区而无法到达任何其他节点。

然而，KeyDB 集群故障检测具有活跃性要求：最终所有节点都应就给定节点的状态达成一致。存在两种可能源于脑裂条件的情况。要么少数节点认为节点处于 FAIL 状态，要么少数节点认为节点不处于 FAIL 状态。在这两种情况下，集群最终都会对给定节点的状态有统一的视图：

情况 1：如果大多数主节点已将一个节点标记为 FAIL，由于故障检测及其产生的“连锁效应”，每个其他节点最终都会将主节点标记为 FAIL，因为在指定的时间窗内将报告足够的故障。

情况 2：当只有少数主节点将节点标记为 FAIL 时，副本提升将不会发生（因为它使用更正式的算法，确保每个人最终都知道提升），并且每个节点将根据上述 FAIL 状态清除规则清除 FAIL 状态（即，在 N 倍 NODE_TIMEOUT 经过后没有提升）。

FAIL 标志仅用作触发算法安全部分的触发器，用于副本提升。理论上，副本可以独立行动，并在其主节点不可达时启动副本提升，并等待主节点拒绝提供确认，如果主节点实际上可被大多数节点访问。然而，PFAIL -> FAIL 状态的额外复杂性、弱协议以及 FAIL 消息强制在集群可达部分中以最短时间传播状态，都具有实际优势。由于这些机制，通常所有节点将在集群处于错误状态时同时停止接受写入。这是 KeyDB 集群应用程序所期望的功能。此外，避免了由于本地问题（主节点可被大多数其他主节点访问）导致副本无法到达其主节点而发起的错误选举尝试。

配置处理、传播和故障转移#

集群当前纪元#

KeyDB 集群使用类似于 Raft 算法“term”的概念。在 KeyDB 集群中，该术语称为纪元（epoch），用于为事件提供递增的版本控制。当多个节点提供冲突信息时，其他节点就可以理解哪个状态是最新的。

currentEpoch 是一个 64 位无符号数。

在节点创建时，每个 KeyDB 集群节点，无论是副本还是主节点，都将 currentEpoch 设置为 0。

每次从另一个节点收到数据包时，如果发送方的纪元（集群总线消息头的一部分）大于本地节点纪元，则 currentEpoch 将更新为发送方纪元。

由于这些语义，最终所有节点都将就集群中最大的 currentEpoch 达成一致。

当集群状态发生变化且节点寻求协议以执行某些操作时，此信息将发挥作用。

目前这只发生在副本提升期间，如下一节所述。基本上，纪元是集群的逻辑时钟，它规定给定信息优于纪元较小的信息。

配置纪元#

每个主节点总是在 ping 和 pong 包中通告其 configEpoch，以及一个通告其所服务的槽集的位图。

当创建新节点时，主节点中的 configEpoch 设置为零。

在副本选举期间会创建一个新的 configEpoch。尝试替换故障主节点的副本会增加其纪元，并尝试从大多数主节点获得授权。当副本获得授权后，将创建一个新的唯一 configEpoch，并且副本使用新的 configEpoch 转换为主节点。

如以下章节所述，configEpoch 有助于解决不同节点声称配置冲突时（由于网络分区和节点故障可能发生的情况）的冲突。

副本节点也在 ping 和 pong 数据包中通告 configEpoch 字段，但在副本情况下，该字段表示其主节点在上次交换数据包时的 configEpoch。这允许其他实例检测副本何时具有需要更新的旧配置（主节点不会向具有旧配置的副本授予投票权）。

每次已知节点的configEpoch发生变化时，所有接收到此信息的节点都会将其永久存储在nodes.conf文件中。currentEpoch值也发生同样的情况。在节点继续其操作之前，这两个变量在更新时都会被保存并fsync-ed到磁盘上。

在故障转移期间使用简单算法生成的configEpoch值保证是新的、增量的和唯一的。

副本选举与晋升#

副本选举与晋升由副本节点处理，主节点投票支持要晋升的副本。当主节点从其至少一个具有成为主节点先决条件的副本的角度看处于FAIL状态时，就会发生副本选举。

为了使副本晋升为master，它需要开始并赢得选举。对于给定的master，如果master处于FAIL状态，所有副本都可以开始选举，但只有一个副本会赢得选举并晋升为master。

满足以下条件时，副本开始选举：

副本的master处于FAIL状态。
master正在服务非零数量的槽位。
副本复制链接与master的断开时间不超过给定时间，以确保晋升的副本数据足够新鲜。此时间可由用户配置。

为了被选举，副本的第一步是增加其currentEpoch计数器，并请求master实例的投票。

副本通过向集群中的每个master节点广播FAILOVER_AUTH_REQUEST包来请求投票。然后它等待最长两倍的NODE_TIMEOUT时间以等待回复到达（但至少等待2秒）。

一旦master为给定副本投票，通过FAILOVER_AUTH_ACK积极回复，它在NODE_TIMEOUT * 2期间不能再为同一master的另一个副本投票。在此期间，它将无法回复同一master的其他授权请求。这对于保证安全性不是必需的，但对于防止多个副本在大致相同的时间被选举（即使使用不同的configEpoch）是有用的，这通常是不希望的。

副本会丢弃任何AUTH_ACK回复，如果其纪元小于发送投票请求时的currentEpoch。这确保它不会计算用于先前选举的投票。

一旦副本收到大多数master的ACK，它就赢得了选举。否则，如果在两倍的NODE_TIMEOUT期间（但始终至少2秒）内未达到多数，则选举中止，并在NODE_TIMEOUT * 4（并始终至少4秒）后再次尝试新的选举。

副本排名#

一旦master处于FAIL状态，副本会等待一小段时间，然后尝试被选举。延迟计算如下：

延迟 = 500毫秒 + 0到500毫秒之间的随机延迟 +
REPLICA_RANK * 1000毫秒。

固定延迟确保我们等待FAIL状态在集群中传播，否则副本可能会在master仍然不知道FAIL状态时尝试被选举，从而拒绝授予其投票。

随机延迟用于解除副本同步，使它们不太可能同时开始选举。

REPLICA_RANK是此副本相对于它从主节点处理的复制数据量的排名。当主节点发生故障时，副本会交换消息以建立（尽力而为的）排名：复制偏移量最新鲜的副本排名为0，其次是排名1，依此类推。这样，最新鲜的副本会先于其他副本尝试被选举。

排名顺序并非严格执行；如果排名较高的副本未能当选，其他副本很快就会尝试。

一旦副本赢得选举，它将获得一个新的唯一且递增的configEpoch，该纪元高于任何其他现有master的纪元。它开始在ping和pong包中将自己宣传为master，提供一套所服务的槽位，其configEpoch将胜过过去的纪元。

为了加快其他节点的重新配置，一个pong包被广播到集群的所有节点。目前无法访问的节点最终会在收到来自另一个节点的ping或pong包时重新配置，或者如果其通过心跳包发布的信息被检测为过期，则会收到来自另一个节点的UPDATE包。

其他节点将检测到有一个新的master正在服务与旧master相同的槽位，但具有更大的configEpoch，并将升级其配置。旧master的副本（或如果重新加入集群的故障转移master）将不仅升级配置，还将重新配置以从新master复制。节点如何重新加入集群的配置将在下一节中解释。

主节点回复副本投票请求#

在上一节中讨论了副本如何尝试被选举。本节解释了从被请求为给定副本投票的主节点的角度来看会发生什么。

主节点以FAILOVER_AUTH_REQUEST请求的形式接收来自副本的投票请求。

要获得投票，需要满足以下条件：

主节点只在给定的纪元投票一次，并拒绝为较旧的纪元投票：每个主节点都有一个lastVoteEpoch字段，只要授权请求包中的currentEpoch不大于lastVoteEpoch，它就会拒绝再次投票。当主节点对投票请求做出肯定回复时，lastVoteEpoch会相应更新，并安全地存储在磁盘上。
主节点仅在副本的master被标记为FAIL时才为副本投票。
currentEpoch小于master的currentEpoch的授权请求将被忽略。因此，master的回复将始终具有与授权请求相同的currentEpoch。如果同一副本再次请求投票，增加currentEpoch，则可以保证master的旧的延迟回复不能被接受用于新的投票。

不使用规则3导致的问题示例：

主节点的currentEpoch为5，lastVoteEpoch为1（这可能在几次失败的选举后发生）

副本的currentEpoch为3。
副本尝试以纪元4 (3+1) 当选，master回复OK，currentEpoch为5，但回复延迟了。
副本稍后会尝试再次以纪元5 (4+1) 当选，延迟的回复到达副本，currentEpoch为5，并被接受为有效。

如果该master的副本已经投票，则master在NODE_TIMEOUT * 2过去之前不会投票给同一master的另一个副本。这并不是严格要求的，因为不可能有两个副本在同一纪元赢得选举。但是，在实际操作中，它确保当一个副本被选举时，它有足够的时间通知其他副本，并避免另一个副本赢得新选举，从而执行不必要的第二次故障转移的可能性。
master不会以任何方式努力选择最佳副本。如果副本的master处于FAIL状态，并且master在当前任期没有投票，则会授予肯定投票。最佳副本最有可能在其他副本之前开始选举并获胜，因为它通常能够更早地开始投票过程，正如上一节所述，因为它具有更高的排名。
当master拒绝为给定副本投票时，没有负面回应，请求会被简单地忽略。
主节点不会为发送的configEpoch小于主节点表中副本声称的槽位的任何configEpoch的副本投票。请记住，副本发送其主节点的configEpoch以及其主节点所服务槽位的位图。这意味着请求投票的副本必须具有比授予投票的主节点更新或相等的故障转移槽位配置。

分区期间配置纪元实用性的实际示例#

本节说明了纪元概念如何用于使副本晋升过程对分区更具弹性。

主节点无限期地无法访问。主节点有三个副本A、B、C。
副本A赢得选举并晋升为master。
网络分区导致A对集群中的大多数节点不可用。
副本B赢得选举并晋升为master。
分区使B对集群中的大多数节点不可用。
以前的分区已修复，A再次可用。

此时B已关闭，A再次作为master可用（实际上，UPDATE消息会迅速重新配置它，但这里我们假设所有UPDATE消息都丢失了）。同时，副本C将尝试被选举以接管B。发生的情况如下：

C将尝试被选举并成功，因为对其大多数master来说，其master确实已宕机。它将获得一个新的增量configEpoch。
A将无法声明它拥有其哈希槽，因为其他节点已经将相同的哈希槽与更高的配置纪元（B的纪元）关联起来，而不是A发布的纪元。
因此，所有节点都将升级其表，将哈希槽分配给C，集群将继续其操作。

正如您将在下一节中看到的那样，重新加入集群的陈旧节点通常会尽快收到配置更改通知，因为它一ping通任何其他节点，接收方就会检测到它有陈旧信息，并发送一条UPDATE消息。

哈希槽配置传播#

KeyDB Cluster 的一个重要部分是用于传播关于哪个集群节点服务给定一组哈希槽的信息的机制。这对于新集群的启动以及副本晋升以服务其故障主节点的槽位后升级配置至关重要。

相同的机制允许被无限期分区隔离的节点以合理的方式重新加入集群。

哈希槽配置有两种传播方式：

心跳消息。ping或pong包的发送者总是添加关于它（或它的主节点，如果它是副本）所服务的哈希槽集的信息。
UPDATE消息。由于每个心跳包中都包含发送者的configEpoch和所服务的哈希槽集的信息，如果心跳包的接收者发现发送者信息已过时，它将发送一个带有新信息的包，强制过时节点更新其信息。

心跳或UPDATE消息的接收者使用某些简单的规则来更新其将哈希槽映射到节点的表。创建新的KeyDB Cluster节点时，其本地哈希槽表简单地初始化为NULL条目，以便每个哈希槽不绑定或链接到任何节点。这看起来类似于以下内容：

-> NULL
-> NULL
-> NULL
...
-> NULL

节点更新其哈希槽表时遵循的第一个规则如下：

规则1：如果哈希槽未分配（设置为NULL），并且已知节点声称拥有它，我将修改我的哈希槽表并将声称的哈希槽与它关联。

因此，如果收到节点A的心跳，声称服务哈希槽1和2，配置纪元值为3，则表将修改为：

-> NULL
-> A [3]
-> A [3]
...
-> NULL

创建新集群时，系统管理员需要手动将每个master节点服务的槽位分配给自己（使用CLUSTER ADDSLOTS命令，通过keydb-cli命令行工具，或通过任何其他方式），信息将迅速在整个集群中传播。

然而，这条规则还不够。我们知道哈希槽映射可能在两个事件中发生变化：

副本在故障转移期间替换其master。
槽位从一个节点重新分片到另一个节点。

目前，我们只关注故障转移。当副本对其master进行故障转移时，它会获得一个配置纪元，该纪元保证大于其master的纪元（更一般地说，大于之前生成的任何其他配置纪元）。例如，节点B（A的副本）可能会以配置纪元4对A进行故障转移。它将开始发送心跳包（第一次进行集群范围的广播），由于以下第二个规则，接收者将更新其哈希槽表：

规则2：如果哈希槽已分配，且已知节点使用大于当前与该槽关联的master的configEpoch的configEpoch进行宣传，我将重新绑定该哈希槽到新节点。

因此，在收到来自B的消息，声称服务哈希槽1和2，配置纪元为4后，接收方将按以下方式更新其表：

-> NULL
-> B [4]
-> B [4]
...
-> NULL

存活性：由于第二条规则，集群中的所有节点最终将同意槽的所有者是那些在宣传它的节点中具有最大configEpoch的节点。

KeyDB Cluster中的这种机制被称为**最后故障转移胜出**。

在重新分片期间也会发生同样的情况。当导入哈希槽的节点完成导入操作时，其配置纪元会递增，以确保更改会在整个集群中传播。

UPDATE 消息，深入了解#

考虑到上一节的内容，更容易理解更新消息的工作原理。节点A可能在一段时间后重新加入集群。它将发送心跳包，声称它服务哈希槽1和2，配置纪元为3。所有具有更新信息的接收者将发现相同的哈希槽与节点B相关联，并且具有更高的配置纪元。因此，它们将向A发送一条包含新槽配置的UPDATE消息。A将根据上面的**规则2**更新其配置。

节点如何重新加入集群#

当节点重新加入集群时，也使用相同的基本机制。以上述示例为例，节点A将收到通知，哈希槽1和2现在由B服务。假设这两个是A服务的唯一哈希槽，A服务的哈希槽数量将降至0！因此，A将**重新配置为新主节点的副本**。

实际遵循的规则比这更复杂一点。一般来说，A可能在很长一段时间后重新加入，在此期间，A最初服务的哈希槽可能由多个节点服务，例如哈希槽1可能由B服务，哈希槽2由C服务。

因此，实际的KeyDB Cluster节点角色切换规则是：**一个主节点将改变其配置以复制（成为其副本）窃取其最后一个哈希槽的节点。**

在重新配置期间，服务哈希槽的数量最终将降至零，并且节点将相应地重新配置。请注意，在基本情况下，这仅意味着旧主节点将成为故障转移后替换它的副本的副本。但是，在一般形式中，该规则涵盖了所有可能的情况。

副本也完全一样：它们重新配置以复制窃取其前一个主节点的最后一个哈希槽的节点。

副本迁移#

KeyDB Cluster 实现了名为“副本迁移”的概念，以提高系统的可用性。其思想是，在主从设置的集群中，如果副本和主节点之间的映射是固定的，那么如果发生多个独立的单节点故障，可用性会随着时间的推移而受到限制。

例如，在一个每个master只有一个副本的集群中，只要master或副本发生故障，集群就可以继续运行，但如果两者同时发生故障则不能。然而，有一类故障是由于硬件或软件问题导致的独立单节点故障，这些故障会随着时间的推移而累积。例如：

主节点A有一个副本A1。
主节点A发生故障。A1被提升为新主节点。
三小时后，A1独立发生故障（与A的故障无关）。由于节点A仍处于宕机状态，没有其他副本可供提升。集群无法继续正常运行。

如果主副本之间的映射是固定的，使集群更能抵抗上述情况的唯一方法是为每个主节点添加副本，但这代价高昂，因为它需要运行更多的 KeyDB 实例，消耗更多的内存等等。

另一种方法是在集群中创建不对称性，并让集群布局随时间自动更改。例如，集群可能有三个主节点A、B、C。A和B各有一个副本，A1和B1。但是主节点C不同，它有两个副本：C1和C2。

副本迁移是副本自动重新配置的过程，目的是**迁移**到一个不再有覆盖范围（没有正常工作的副本）的master。通过副本迁移，上述场景变为以下情况：

主节点A发生故障。A1被提升。
C2 作为 A1 的副本迁移，否则 A1 将没有副本支持。
三小时后，A1也发生故障。
C2被提升为新的master以取代A1。
集群可以继续操作。

副本迁移算法#

迁移算法不使用任何形式的协议，因为KeyDB Cluster中的副本布局不是集群配置的一部分，不需要与配置纪元保持一致和/或版本化。相反，它使用一种算法来避免当master没有支持时副本的大规模迁移。该算法保证最终（一旦集群配置稳定）每个master都将至少由一个副本支持。

该算法的工作原理如下。首先我们需要定义在这种情况下什么是“良好副本”：良好副本是指从给定节点角度看未处于FAIL状态的副本。

该算法的执行由每个检测到至少有一个主节点没有良好副本的副本触发。然而，在所有检测到此条件的副本中，只有一部分应该采取行动。这部分实际上通常只有一个副本，除非不同的副本在给定时刻对其他节点的故障状态有略微不同的视图。

“活动副本”是指在连接副本数量最多的主节点中，未处于FAIL状态且节点ID最小的副本。

因此，例如，如果有10个master，每个master有1个副本，以及2个master，每个master有5个副本，那么尝试迁移的副本将是——在拥有5个副本的2个master中——节点ID最低的那个。鉴于没有使用任何协议，当集群配置不稳定时，可能会出现竞争条件，即多个副本认为自己是非故障且节点ID较低的副本（这在实践中不太可能发生）。如果发生这种情况，结果是多个副本迁移到同一个master，这是无害的。如果竞争以一种导致让出的master没有副本的方式发生，一旦集群再次稳定，算法将再次执行，并将一个副本迁移回原始master。

最终，每个master都将至少有一个副本支持。然而，正常行为是单个副本从具有多个副本的master迁移到孤立的master。

该算法由用户可配置的参数cluster-migration-barrier控制：副本可以迁移之前，master必须保留的良好副本数量。例如，如果此参数设置为2，则副本只有在其master仍有两个正常工作的副本时才能尝试迁移。

configEpoch 冲突解决算法#

在故障转移期间通过副本晋升创建新的configEpoch值时，它们保证是唯一的。

然而，在两种不同的事件中，新的configEpoch值以不安全的方式创建，只是简单地增加本地节点的currentEpoch并希望同时没有冲突。这两个事件都由系统管理员触发：

带有TAKEOVER选项的CLUSTER FAILOVER命令能够在**没有大多数master可用**的情况下手动将副本节点提升为master。例如，这在多数据中心设置中很有用。
由于性能原因，集群重新平衡的槽位迁移也会在本地节点内生成新的配置纪元，无需协商。

具体而言，在手动重新分片期间，当一个哈希槽从节点A迁移到节点B时，重新分片程序将强制B将其配置升级到一个比集群中找到的任何其他配置纪元都大的纪元（除非该节点已经是配置纪元最大的节点），而无需其他节点的同意。通常，实际的重新分片涉及移动数百个哈希槽（尤其是在小型集群中）。在重新分片期间，为每个移动的哈希槽生成新的配置纪元需要协议，这是低效的。此外，每次都需要对每个集群节点进行fsync以存储新配置。然而，由于它的执行方式，我们只需要在移动第一个哈希槽时有一个新的配置纪元，这使其在生产环境中效率更高。

然而，由于上述两种情况，可能会（尽管不太可能）出现多个节点具有相同配置纪元的情况。如果传播速度不够快，系统管理员执行的重新分片操作和同时发生的故障转移（加上大量运气不佳）可能会导致currentEpoch冲突。

此外，软件bug和文件系统损坏也可能导致多个节点具有相同的配置纪元。

当服务不同哈希槽的master具有相同的configEpoch时，没有问题。更重要的是，故障转移master的副本具有唯一的配置纪元。

尽管如此，手动干预或重新分片可能会以不同方式更改集群配置。KeyDB Cluster的主要存活属性要求槽位配置始终收敛，因此在任何情况下，我们都希望所有主节点具有不同的configEpoch。

为了强制执行此操作，在两个节点最终具有相同的configEpoch时，将使用**冲突解决算法**。

如果主节点检测到另一个主节点正在使用相同的configEpoch进行宣传。
并且，如果该节点的节点ID在字典顺序上小于声称相同configEpoch的另一个节点。
那么，它将其currentEpoch增加1，并将其用作新的configEpoch。

如果存在具有相同configEpoch的节点集，则除了节点ID最大的节点之外，所有节点都将前进，保证最终每个节点都将选择一个唯一的configEpoch，无论发生了什么。

这种机制还保证了在创建新集群后，所有节点都以不同的configEpoch开始（即使这实际上并未被使用），因为keydb-cli在启动时确保使用CONFIG SET-CONFIG-EPOCH。但是，如果由于某种原因节点配置错误，它将自动将其配置更新到不同的配置纪元。

节点重置#

节点可以进行软件重置（无需重启），以便在不同的角色或不同的集群中重复使用。这在正常操作、测试和云环境中非常有用，在这些环境中，给定节点可以重新配置以加入不同的节点集以扩大或创建新集群。

在KeyDB Cluster中，节点使用CLUSTER RESET命令进行重置。该命令提供两种变体：

CLUSTER RESET SOFT
CLUSTER RESET HARD

命令必须直接发送到要重置的节点。如果未提供重置类型，则执行软重置。

以下是重置操作执行的列表：

软重置和硬重置：如果节点是副本，它将转换为master，并且其数据集将被丢弃。如果节点是master并且包含键，则重置操作中止。
软重置和硬重置：所有槽位都被释放，手动故障转移状态被重置。
软重置和硬重置：节点表中的所有其他节点都被删除，因此节点不再知道任何其他节点。
仅硬重置：currentEpoch、configEpoch和lastVoteEpoch设置为0。
仅硬重置：节点ID更改为新的随机ID。

非空数据集的master节点无法重置（因为通常您希望将数据重新分片到其他节点）。但是，在特殊情况下（例如，当集群完全被销毁，旨在创建新集群时），必须在进行重置之前执行FLUSHALL。

从集群中移除节点#

实际上可以通过将节点的所有数据重新分片到其他节点（如果它是主节点）并关闭它来从现有集群中移除节点。但是，其他节点仍将记住其节点ID和地址，并尝试与其连接。

因此，当一个节点被移除时，我们希望也从所有其他节点的表中移除它的条目。这通过使用CLUSTER FORGET 命令来实现。

该命令执行两件事：

它从节点表中删除具有指定节点ID的节点。
它设置了一个60秒的禁令，以防止具有相同节点ID的节点被重新添加。

第二项操作是必需的，因为KeyDB Cluster使用gossip来自动发现节点，因此从节点A中移除节点X，可能导致节点B再次向A传播有关节点X的信息。由于60秒的禁令，KeyDB Cluster管理工具有60秒的时间从所有节点中移除该节点，从而防止由于自动发现而重新添加该节点。

更多信息请查阅CLUSTER FORGET文档。

发布/订阅#

在KeyDB Cluster中，客户端可以订阅每个节点，也可以发布到每个其他节点。集群将确保发布的消息按需转发。

当前实现将简单地将每个已发布的消息广播到所有其他节点，但未来某个时候将通过布隆过滤器或其他算法进行优化。