跳过正文

Raft Cluster Support For Non-Voting Memebers

作者
杨全烨
系统软件:操作系统、网络与分布式系统。
目录

也是Raft中一个很有意思的话题,我们来实现一个新的角色:Learner. 那这个实现的排期还挺紧迫的,这个毫无疑问也是比预选举协议更具有挑战性。

原issue

关于Raft的架构可以在Raft Cluster Pre-Vote Protocol中复习,这是我们做的第一个Raft相关的PR.

刚好同时了解集群的原理:特性:Redis Cluster 集群

需求是这么写的:

Implement support for “Learner” or “Observer” non-voting roles in the Raft consensus group. 实现learner 或者 observer.(实际上就是learner).

Non-voting nodes should still replicate the Raft log to receive topology updates so they can serve client requests like CLUSTER SLOTS accurately. learner应该复制日志状态机,同时接受拓扑更新,这样就能精确serve来自client的请求。(读处理,写转发)

They should not participate in write quorums or elections, preventing performance overhead and scale limitations on the voting core. In a cluster with hundreds of nodes, it’s beneficial if only ~5 nodes are voting members, to minimize the risk of many nodes simultaneously requesting votes for themselves in a leader election, resulting in high risk of split vote. 不参与选举和日志写入的多数派的确认,防止选举的性能变差。 为什么不参与确认? 因为同步这段时间内,新加入节点的log都很少,根本无法参与确认,如果一下加进来太多,会导致很长时间新的日志无法提交。 数百个nodes组成的集群,最多只要有5个nodes来真的做选举就好,减少许多节点同时发起选举导致的脑裂问题(虽然随机选举超时时间已经很大程度上解决了这个问题

Support potential chaining-style replication of the Raft log where learners pull from other nodes rather than all overloading the leader. (This point seems like a separate feature, but we should think about the future possibility.) 就是如果说一个voting节点需要被上百个learner同时, 网络IO会成为瓶颈,是否使用链式复制(常见的设计思想,见Google File System中的Dataflow,就是链式的流水线传输。)

之后reviewer和我们align了一下:

I think we should add all nodes as learners by default. When a node has caught up with the raft log, it can be promoted to a follower. I believe this is some recommendation some paper. Btw, does any of you know which paper describes Raft learners? 这里的看法是,当一个节点被加入集群的时候,首先应当作为learner,之后完全同步上日志进度了之后(这里的考究就是,到底是必须一模一样还是说不一定完全一样),才能作为follower. 实际上这里的细节还需要考究,需要研究一下论文原文和etcd的源码看看。

To @nemtsv’s questions:

1. Yes, a learner can be primary and replica. 在主从复制的特性中,learner可以作为主节点(own a slot),也可以作为从节点。 选举的时候不是主节点来做会存在问题么?

2. I think it’s good to distinguish an entry that affects quorum from an entry that doesn’t, especially if we want to implement config-on-append later (Raft Cluster: Config-on-append for membership changes #3926). If we want to add all new nodes as learners first, then maybe NODE_JOIN should make the new node a learner. Or we add a flag to NODE_JOIN to say whether it’s a voter or not. Regardless, we’ll need to be able to promote learners to followers and demote followers to learners, so we’ll need new entry types for that. When a node is removed, NODE_FORGET would apply to learners and voters or should we split that one as well, i.e. demote to follower before we append NODE_FORGET? 我认为区分“影响法定人数(quorum)的日志条目”“不影响法定人数的日志条目”是件好事,特别是考虑到如果我们以后想实现 config-on-append(追加时即生效配置). 如果首先作为learner 添加,那么也许 NODE_JOIN 就应该默认使新节点成为 learner。 或者我们在 NODE_JOIN 中添加一个标志,来指定它是 voter 还是 learner。 无论如何,我们都需要具备将 learner 提升为 follower,以及将 follower 降级为 learner 的能力,因此我们需要为此引入新的日志条目类型。 当移除一个节点时,NODE_FORGET 应该同时适用于 learner 和 voter 呢, 还是我们也应该把它拆分开,比如在追加 NODE_FORGET 之前,先将其降级为 learner.

这个地方还没对齐,还需要在调研一下。 -> 这里就应该直接移除这个节点,基于我们已经实现了预选举机制。

3. Yeah, I think server.cluster->size should represent the voters only. In gossip cluster, the cluster size is only the primaries with slots, i.e. the voters, so we can keep the same convention in raft cluster. 就是cluster大小仅代表voter的数量。但是这里矛盾的点不是learner也能作为主节点持有slot么? 这个也好像不矛盾,主从和控制平面完全是两码事。

4. Yeah PROMOTE <id> and something similar for DEMOTE <id> – one node at a time to match the current config-on-apply logic for quorum updates. But these words can also mean promote to leader, candidate, so maybe ADD_VOTER <id> and DEL_VOTER <id> is clearer? 修改一下语义?

5. I don’t think this problem applies to this issue. A singleton leader becomes a joiner (just waiting to be added to a cluster) and then reverts to singleton leader again after a timeout. There’s no learner role involved here. Maybe it’s a scenario that only affects Raft Cluster: Merging non-singleton clusters #3868? We can discuss it on that issue. 这个是集群合并中需要考察的问题,就是leader的退化问题。

Then, we’ll also need a flag in nodes.conf to say if a node is a voter or not. We could use one of these: 在集群配置中加一个标志,用于表明一个节点是否是voter。

- node flags 就使用前两个吧 - aux fields - one of the unused columns ping-sent, pong-received

Just a though: (If we ever want to do joint consensus, we could list all the voters on every quorum change, e.g. an entry like CONFIG_VOTERS id1 id2 id3 .... Did we already say we don’t need joint consensus? If we just keep a list of uncommitted voters or something, maybe it’s not really that difficult? 🤔 We can change this later if we want to implement joint consensus though. If we do it, we can just use this entry type every time we add or remove voters. There shouldn’t be more than 5 or 7 voters in a cluster, normally.)

实际上主要就是搞清楚这几点
#

还有一点就是我们本次的变更都做的是单个集群成员的变更

共识角色和数据解耦
#

这是整个系统设计中最容易混淆的部分:

  • 数据层面(Valkey/Redis 语义): 节点分为 Primary(持有 Slot 负责读写)和 Replica(负责数据同步)。

  • 共识层面(Raft 语义): 节点分为 Voter(参与 Leader 选举和日志提交的 Majority 计算)和 Learner(只接收日志,不计入计算)。

@zuiderkwast 明确了一点:这两种维度是正交的。 一个 Learner 节点完全可以在 Valkey 层面上是一个 Primary(负责特定 Slot 的数据)。

这在“集群合并(Cluster Merging)”场景下极为重要,因为合并过来的节点必须能持有它原来的数据(Primary),但在它的 Raft 日志跟上大部队之前,不能赋予它投票权(Learner)。

指令怎么设计?
#

为了安全地改变集群拓扑,你们决定采用单节点成员变更(Single-server configuration change),抛弃容易引发混淆的 PROMOTE/DEMOTE,转而设计明确的 Raft 控制命令:

  • NODE_JOIN 接下来你需要修改这部分逻辑,让新节点接入时默认以 Learner 身份运作,而不是立刻成为 Voter

  • ADD_VOTER <id>DEL_VOTER <id> 这将是你需要新增的核心集群内部通信/Raft 状态机日志(State Machine Log)。 这两个状态机日志的目的就是为了进行learner和follower之间转换的操作。

    • ADD_VOTER 用于当 Leader 观测到 Learner 的 nextIndex 已经追赶上来后,发出一条配置变更日志。 就是你跟上我的log了,我才允许你上升成为follower。(这里的细节就是到底跟到了什么水平才会允许成为follower,见论文内部的细节)
    • 当这条日志被多数派提交后,目标 Learner 正式成为 Voter,server.cluster->size 才会立刻增加。
  • 关于 NODE_FORGET 的小纠结: 维护者提出了一个很好的边界问题:如果要踢掉一个 Voter,是直接用 NODE_FORGET 把它踢走,还是强制要求先下发 DEL_VOTER 把它降级为 Learner,然后再下发 NODE_FORGET

  • etcd的实现内部,是直接剔除这个节点,如果是voter,重算quorum,如果是learner,就更加可以直接删除

  • 因为我们已经实现了预投票Raft Cluster Pre-Vote Protocol机制,所以被删除的节点不会扰乱集群。

所以我们这里就直接删除即可,不需要进行两段式的下降,注意这里还需要立刻触发Quorum的重新计算。

Quorum计算重构
#

加入的节点中需要过滤掉learner才行,这个比较明确。

持久化
#

node.conf, 标志位,知道对方是voter还是learner.

在稍微看下论文和etcd的代码实现,调研一下我们就开始具体的实现操作。 事实上我们这个需要实现的就是单个集群成员变更。

单节点集群成员变更的原理
#

Joint Consensus已经在Raft-Extended Version 6-7 详解中进行了详细的陈述。 我们想在这里讲解一下单节点集群成员变更.

有两个RPC:

AddServer:向集群中增加一个server. leader侧实现: 1.检查是否还是leader 2.固定轮数内应该赶上leader,或者最后一轮超时,都添加失败 3.等待上一个config commited 4.添加新的config log

RemoveServer: 从集群中移除一个server. 自己看图片吧。

Safety
#

抽屉原理
#

直接转换可能会导致split brain的出现。 比如:

在这种情况下,如果直接转换,可能就会导致两个leader被选出来。

Most membership change algorithms introduce additional mechanism to deal with such problems. This is what we did for Raft initially, but we later discovered a simpler approach, which is to disallow membership changes that could result in disjoint majorities. 大多数成员变更都会引入新的机制来处理。 开始Raft也是这么做的。 之后我们发现了更简单的方法,那就是禁止会导致出现不相交的多数派的成员变更? 上面这个例子,就是新旧的集群中没有出现交集

only one server can be added or removed from the cluster at a time. 这就是单节点集群成员变更,每次只允许添加或者删除一个节点。

依旧Understandability.

单点操作的情景就是这样的:

很简单,比如(a)中向一个4个节点的cluster中加入一个node,那么原来四个的majority是3,现在5个的majority也是3,这33必有交集,那么一定不会出现脑裂,可以直接切换。

依旧抽屉原理

配置为日志
#

集群配置被作为特殊的条目存储在复制日志(replicated log)中并进行通信。 这利用了 Raft 中已有的机制来复制和持久化配置信息。 这也允许集群在配置变更进行期间,继续为客户端提供服务, 做法是在配置变更和客户端请求之间强制建立顺序(同时允许两者在流水线和/或批处理机制中并发复制)。

Append即生效
#

当 Leader 收到从当前配置(Cold)中添加或移除服务器的请求时, 它将新配置(Cnew)作为一条日志条目追加到自己的日志中, 并使用常规的 Raft 机制复制该条目新配置一旦被添加到某台服务器的日志中,就会立即在该服务器上生效: Cnew 条目被复制给 Cnew 里的服务器, 并且 Leader 使用 Cnew 的多数派来决定 Cnew 条目是否已被提交。 这意味着服务器不会等待配置条目被提交才去使用它,每台服务器总是使用它在日志中找到的最新配置。

一旦config entry 被复制,就需要即刻生效,这和数据的日志是有区别的。

一旦 Cnew 条目被提交,配置变更就完成了。 此时,Leader 知道 Cnew 服务器中的多数派已经采用了 Cnew。 它也知道,任何还没有切换到 Cnew 的服务器都不可能再形成集群的多数派, 且没有 Cnew 的服务器也不可能被选为 Leader。Cnew 的提交允许继续执行以下三件事:

  1. Leader 可以向客户端确认配置变更已成功完成

  2. 如果配置变更移除了某个服务器,该服务器现在可以被关闭(shut down)。

  3. 可以开始下一次的配置变更。在此之前,重叠的配置变更可能会退化为图 4.2 所示的不安全情况

所以配置变更请求应当具有幂等性,也就是真的一次只能加一个server,要不然就没有意义了。 上一次完成之前,下一次绝不能开始。

为什么append即生效?
#

如上所述,服务器总是使用日志中最新的配置,无论该配置条目是否已提交。 这允许 Leader 轻松避免配置变更的重叠,只需在上一次变更的条目提交之前不开始新的变更即可。 如果服务器只有在得知 Cnew 被提交后才采用 Cnew,Raft 的 Leader 将很难知道旧集群的多数派何时采用了它。 Leader 将需要追踪哪些服务器知道了该条目被提交,而且服务器还需要将它们的 commit index 持久化到磁盘上; Raft 根本不需要这两种机制。 相反,每台服务器只要日志里有 Cnew 就会立刻采用它。

不幸的是,这个决定确实意味着,由于 Leader 的更换,一条关于配置变更的日志条目有可能会被覆盖/移除(removed); 在这种情况下,服务器必须做好准备,回退(fall back)到它日志中的上一个配置

RPC和config是独立的
#

在 Raft 中,达成共识(不论是投票还是日志复制)使用的是调用方(caller)的配置:

  • 服务器会接受来自它最新配置中并不存在的 Leader 的 AppendEntries 请求。否则,一个新服务器将永远无法被加入到集群中(它会拒绝接受所有在“添加该服务器的配置条目”之前的日志)。

  • 服务器也会把票投给它最新配置中并不存在的 Candidate(前提是该候选人拥有足够新的日志和当前任期)。有时为了保持集群的可用性,这张选票是必不可少的。例如,考虑向一个 3 节点集群中添加第 4 个节点。如果其中一个节点宕机,就需要这台新节点的选票才能形成多数派并选出 Leader。 因此,服务器在处理传入的 RPC 请求时,不会去查阅/参考它们当前的配置

这个issue描述的就是这样的问题,那这个处理就应该暂时不需要放在我们这里了,了解一下即可。

Availability
#

这里才是我们要讨论的重点,可用性。 也就是learner需要满足什么?

直接加一个空log的server可能会造成风险:

(a)描述了什么? 就是在空的S4被加入之后,S3瞬间fail,4节点的majority是3,但是此时对于之后的日志,暂时无法提交(当S4没有赶上最新的log的时候),此时你可以认为系统暂时失去了可用性。

这里就是产生了木桶短板效应,之后的日志的提交都要等到这个S4结束才可以。

(b)道理是类似的,就是你迅速成功的连续加入了3个server,但是此时之后要commit的时候,就一定需要456中的一个来commit,同样失去了可用性。

4.2.1 Catching up new servers (learners)
#

这才真的到我们关心的阶段,就是新加入的server先作为learner,等学习的差不多了,才升级成follower.

暂时作为一个non-voting member加入。

所以怎么追,一直追下去不是,这样就变成了著名的芝诺悖论, 阿喀琉斯能追上乌龟,但是learner却没办法追上server成为follower,我们肯定不可以进行无限的同步

我们有一套自己的机制:

设想这样一种情景,new server加入了我们的集群。然后leader和这个new server开始进行同步的操作。 开始的时候new server的日志为空,需要复制的时间可能会长一点,这是round1,这期间,leader又拿到了黄色的日志,这是round2. 可以预想的是,之后的增量的日志会越来越少,因为之后需要同步的日志会越来越少,但是不会完全相同,除非client停止发送请求。

The leader needs to determine when a new server is sufficiently caught up to continue with the configuration change.

那么leader就需要决定什么时候一个new server才是真的足够可以成为一个follower.

事实上,Raft是,我们可以容忍的不可用性在一个选举超时时间之内。

如果new server不可用,或者太慢,leader应该及时回滚这次集群变更操作。

我们就采用这样的算法: 1.日志复制分成多轮,每轮都要全部复制round开始时收到的全部log. 2.等待固定的轮数(比如10轮),如果在最后一轮的时间小于了一个超时选举时间(这很合理),那么就可以晋升,这意味着目前的可用性是我们可以接受的。要不然就直接回滚了,意思就是我们接受不了这个时间。

要时间短就需要实现日志的快速回退,这是我们之前实现过的,没有什么难度,不用我们来处理。

我们主要修改什么?
#

每次改完之后,你可以直接进行三个测试:

~/Project/valkey feat/raft-learners-3866* 11s ❯ ./runtest --single unit/cluster/cluster-raft-meet \
          --single unit/cluster/cluster-raft-proto \
          --single unit/cluster/cluster-raft

1.md文件设计,learner承担了什么角色。 2.增加配置文件中一个learner的角色

一个值得商榷的地方是cacth-up-server在算法中的具体实现
#

Raft论文中给出的手法是固定等待10轮,然后最后一轮看是否在选举超时时间之内。 这个目前还是没有定下来。 直接看match占比多少也是可行的。