分布式一致性算法-RAFT算法的理解和SOFA-RAFT的改进

简介 Raft是一种集群选举策略算法，用于保证集群的一致性。

Raft将单节点的状态变化转为日志，通过日志同步和日志回放保证一致性。当少数节点挂掉集群依然可以对外提供服务。

Raft是一个CP系统，牺牲了部分可用性（当leader切换时，服务短时间内不可用）。 节点启动 Raft集群中每个节点刚刚启动时候会通过本地的日志回放完成状态机的初始化，后与其他节点互联，加入集群，此时节点身份为跟随者。Leader会对刚加入集群的节点发起日志同步操作，将自己的日志同步到这个节点（leader日志一定最新）。 节点间互相保持心跳，心跳主要包含4个参数：当前任期-term、当前节点最大日志序号-maxIndex、当前节点已提交最大日志序号-maxCommitedIndex、当前领导者-leader。 节点身份状态 节点的身份分为三种，跟随者、候选人、领导者。 一个正常的系统应该有一个领导人，其余节点为跟随者。 当某节点触发了选举条件时，节点身份转化为候选人，候选人赢得选举成为领导者，否则退回跟随者。 当一个节点收到了一个比自己任期大的心跳时，无论当前处于任何状态，都应该立即采用对方任期，并且成为跟随者。 来自Leader的心跳会刷新节点内的一个用以触发选举的超时定时器（下文称为候选定时器）。 Leader选举的触发 节点进入集群时都是跟随者身份，由leader持续发送心跳刷新节点内的候选定时器，当节点一段时间没收到leader的心跳导致候选定时器超时，则节点身份转化为候选人。 定时器超时并非一个定值，raft采用了随机延时巧妙的解决了split vote问题（即多个候选人同时开始选举，导致选票被多人瓜分无法快速选出领导者）。 Leader选举过程 候选人将任期加一后投票给自己，而后向所有节点发送拉票信息请求选票，并开始选举计时，超时未完成则视为选举失败。 节点收到拉票信息后进行判断是否投票，若候选人任期不大于自己则拒绝投票（若和当前一样，则手上必然已经无票），若候选人日志序号比当前节点小则拒绝投票。否则投票给该节点，刷新候选定时器并更新任期。 候选人在候选期间可能收到三种信息： 跟随者的投票信息：代表该候选人票数加一，若此时票数大于集群节点数的一半，则选举成功，候选人成为领导者。

其他候选人的拉票信息：若对方任期小于自己则无视，若对方日志序号不大于自己则无视，否则该候选人退出选举，选举失败。

自称领导者的心跳：若对方任期小于自己则无视，否则该选举人退出选举，选举失败。（若领导者任期不小于自己，由于过半复制原则，已提交日志序号不可能小于自己，但是未提交日志序号可能小于自己，此处可能导致丢失未提交日志，需要补偿措施）。 日志同步过程 只有领导者可以写日志，并向其它节点发送新增的日志信息，Raft的日志同步遵循过半复制原则。 领导者将状态机更新，并写日志，向其余节点发送新增日志信息。 其余节点收到新增日志信息并应用到状态机后，向领导者响应（此处响应代表此条日志之前的日志也全部同步完毕，收到新增日志信息后依靠日志序号来判断是否连续，若不连续则从领导者同步之前的日志，最后再新增此条日志，保证有序） 领导者收到一半以上的节点的响应后，将此条日志设为已提交日志，即已提交日志序号加一，并向其它节点推送该信息。 其余节点收到最新的已提交序号后更新自己节点的已提交序号。 通过过半复制原则可以保证被领导者commit的日志必然会被下一个领导者继承，因为在选举人投票的时候，一半以上的节点已经拥有该日志，不会投票给无此日志的节点。 当新领导者当选时，若存在上一任遗留下来的未提交日志，无论是否有过半复制，一律认定为未提交日志，但不立即进行处理，而是当新的日志产生时，一起提交（序号X的日志被提交意味着序号小于X的日志已经全部提交）。 Raft存在的问题 未提交日志可能丢失，需要补偿机制 当一个跟随者因为自己的问题（网络延迟），发起选举，该节点会成功顶替现有领导者，即使现有领导者功能正常。 同一任期不会出现一个以上的领导者，但同一时间可能会出现两个领导者，Raft只能保证只有一个领导者可以提交日志（两个任期，新旧领导者，如网络故障导致集群分为两个分区，旧领导者在小分区，大分区有节点发起选举并成为新领导者） SOFAJRAFT的改进 新增了预投票机制，候选人需要先发起一次预投票，解决了2问题，流程如下： 节点候选计时器超时，节点成为候选人。 该候选人向所有节点发起一次预投票。 其他节点向当前领导者发起一次状态检测的请求，若当前领导者正常，则直接拒绝投票，否则按照原投票规则投票。 候选人预投票获取一半以上的票数后，发起正式的投票，在预投票超时后依然没有获得一半以上的票数则退回跟随者状态，刷新候选计时器重新计时。 领导者下台机制，当领导者在下台定时器超时前无法获得一半以上的节点的心跳响应时，领导者退位成为跟随者。 我的理解： 预投票机制保证了领导者无问题的时候阻止个别收不到领导者心跳的节点发起竞选，当其他节点收到预投票请求时候会检查当前领导者状态，此处若请求超时或者当前领导者状态异常，则进行投票。此机制结合领导者下台机制，我们会发现SOFAJRAFT用了一种很巧妙的方法解决了同一时间出现两个领导者的问题（问题3）：当候选人预选成功的时候，说明一半以上的节点请求当前领导者异常，请求超时的时间与领导者下台定时器的超时时间一致，当一半以上节点在预投票中投票给候选人时，意味着此时领导者已经触发下台机制，新领导者出现的时候旧领导者必然已经下台。