这里其实也暗喻了Conf Change中对Outgoing RPC的处理方法,即Leader不再向哪些不属于Cnew的机器发送心跳包和AppendEntries,这会导致这群机器TimeOut,然后触发选举机制扰乱整个集群;
注意上述这个情景不一定是坏的,反而在某些时刻是必要且合理的,例如Leader Step Down中所描述的第二个场景,我们更期望那个拥有Cnew的机器当选;
preVote可以很大程度上避免这种情景,但并不完全够用;preVote机制可以保证当Cnew成功备份到Majority时,那些不属于Cnew的机器无法通过preVote阶段,但在Cnew成功备份到Majority之前,preVote机制无法避免这次Distruption:
Raft的作者提供的建议是使用HeartBeat + RequestVote来最大程度的减小上述场景;在原算法中,任何Server只要发现拉票者的term至少比自己新,且拥有最新的日志,就会向它投票并考虑更新自己的term(如果term更高可能会直接或间接的罢黜Leader,即我们讨论的Distruptive);这里做出了一点限制:
在一个election timeout内如果收到了心跳包,则拒绝投票,拒绝重置定时器,或者会把这个请求延后;
理论上讲,如果election timeout内如果收到了心跳包,那么Leader大概率是存在的,因此问题不算很大;
这里与Leader Transfer的思想存在冲突,Leader Transfer是期望立刻触发选举的,因此对于那些Leader Transfer的请求还需要捎带一个flag,表示“我自己有disrupt the leader”的权力;
Conf Change 小结Cluster Member Change是一个必要且重要的操作,基本可以抽象为两类行为:添加新的机器,或者撤出某些机器;这里讨论了Cluster Member Change的三个问题:安全保证、可用性、具体实现;
首先是安全保证;Cluster Member Change唯一需要考虑的安全性问题是双主问题,即必须避免Cnew和Cold中的机器分别构成Qurom产生双主;最简单直接的方法就是一次仅增/删一台机器,这种情景下Cold和Cnew中的Qurom必定有交集,即最多只能形成一个Qurom,这样保证了安全性问题;
第二是可用性(Avalibility)问题;这主要体现在增加机器的场景下;新增的机器可能需要一段不短的时间来Catch Up,也可能新增的机器性能很差或环境很差;对于第一种情况,Raft算法设定了一种Learner角色,新加入的机器能够接收AppendEntries,但不被算入Qurom内,其投票请求也会被忽视,直到Leader认为它的确“赶上了”为止;对于第二种情况,作者提供了一种Catch Up算法,当新的Server无法赶上时,Leader会放弃这台机器并向管理员告知一个错误,期望将新的机器给撤出掉;注意到我们的Conf Change日志并不会到这台机器上,因此Conf Change只要在原来的集群上顺利提交,就可以将这个拖累的机器给撤出;
第三就是具体的实现细节了;对于Incomming RPC,必须全部接受并进行处理;对于Outgoing RPC,只需要发送给自己当前应用的配置下的Server就可以了;对于那些在新配置中被撤出的机器,要避免他们超时后拉票造成的Disruptive,这里使用了心跳机制 + RequestVote限制来拒绝拉票;
解耦TiKV里关于Raft基本移植了etcd中关于Raft的实现。一个很让我感到很惊奇的地方在它实现了Raft算法对存储、通信的解耦合。
当然也对使用提出了非常严格的限制。第一,由于内部逻辑中是没有时钟的,因此定时的逻辑必须由使用者来驱动(例如每100ms都要主动调用tick);第二,使用者必须保证正确处理全部的消息,例如说保证持久化、保证和其他peer之间的通信,如果处理出错甚至可能导致拜占庭错误。
选举由于Leader Transfer机制的引入和Conf Change的影响,选举规则还需要作出一些其他的调整;
首先讨论Conf Change。Conf Change中已经脱离了集群的机器由于无法收到AppendEntries,因此会成为Candidate并试图向其他Server拉票。由于Server必须处理一切的incomming RPC(不管这些RPC的源是否属于当前配置),因此集群可能被扰动。preVote机制是无法避免集群扰动的,因为已经脱离了当前config的Candidate仍然可能持有最新的日志并当选为Leader(这不可避免,因为Conf Change的实现也部分依赖于此,可以参考前文中关于Conf Change的讨论)。
Ongano的论文提出了一种方案:如果一台机器收到了拉票请求,即使对方的term比自己高,它也可以拒绝投票,如果:
它自己是Leader且最近check_qurom返回成功,或者
它自己是Follower且在election_timeout里收到了心跳;
满足1.2且请求消息并不是Leader Transfer请求;