TDDMS揭秘（五）一致性协议Raft的工作原理及介绍--领导者选举及日志复制算法详解（中下）
友情链接：
- 星环分布式存储TDDMS大揭秘（一）分布式存储技术推出背景以及当前存在的挑战
- 星环分布式存储TDDMS大揭秘（二）TDDMS是什么
- TDDMS揭秘（三）分布式一致性技术是如何实现的（上）
- TDDMS揭秘（四）一致性协议Raft的工作原理及介绍--Raft协议背景及算法初剖析（中）
- TDDMS揭秘（六）一致性协议Raft的工作原理及介绍--安全属性及快照机制（下）
- TDDMS揭秘（七）Raft一致性协议在TDDMS中发挥了什么作用？承担了什么角色？
领导者的详细过程
1. 启动阶段
Raft采用心跳机制来触发leader选举。当服务器启动时，服务器首先作为follower。只要服务器从leader或者candidate接收到有效的RPC，他们就会保持其follower状态。
2. 状态转换，候选状态出现
为了维护集群Leader的权威，Leader节点会向其他Follower节点发送心跳来表达统治权。如果Follower节点在一段时间内（选举超时机制）没有收到任何通信，他就会过渡到候选状态并增加其当前任期，开始新的选举；
3. 请求投票
此时，超时节点将其状态更改为Candidate状态，它会为自己投票并向集群中的所有其他节点并行发送RequestVote RPC以建立多数并尝试成为Leader。其中，RequestVote RPC信息中包括候选人的任期、候选节点日志中最后的索引（lastLogIndex）以及任期（lastLogterm）。候选者继续保持这种状态，直到发生以下三种情况之一：（a）它赢得选举，（b）另一台服务器将自己确立为领导者，或（c）一段时间内没有获胜者。
3.1.1.投票流程
每台服务器都存储一个当前的任期号，该任期号随着时间的推移单调增加。 每当服务器通信时都会交换当前任期信息进行选举：
- 如果一台服务器的当前任期号小于另一台服务器的当前任期号，则它会将其当前的任期进行更新；
- 如果候选者或leader发现其任期号比其他服务器小，则会立即恢复为follower状态；
- Follower会评估候选者的日志确定其是否是最新的，如果不是则拒绝投票请求；如果是，则投票给候选者；
- 在任何时间点，任何其他服务器拥有更高的term number，它可以立即成为新任leader；
4.选举结果
情况1： 选举成功（Step: receives votes from majority of servers）
如果候选节点收到来自整个集群中同一任期的大多数服务器的选票（N/2+1），则该候选节点将赢得选举，此时，它会立刻将自己的状态更新为Leader，并向所有其他服务器发送心跳消息，以建立其权威并防止新的选举。每个节点针对每个term只能投出一张票，按照先到先得的原则确保了最多保只有一个 candidate 会成为 leader。
情况2：选举失败（Step: discovers current leader or new term）
在等待投票时，候选节点可能会从另一台声称是自己是leader的服务器收到AppendEntries RPC。如果这台服务器携带的任期（包含在其RPC中）跟候选节点自身当前的任期一样大或者比他大，那么候选节点则承认对方的leader身份并认为对方是生效的，然后将自身状态切换回follower状态。这说明其它节点已经成功赢得了选举，它只需立刻跟随即可。 如果RPC中的任期小于候选节点当前的任期，则候选节点拒绝此次请求并继续保持候选状态。
情况3：选举超时（Step: times out, new election）
最后一种情况是候选人既不会赢得选举，也不会输掉选举：如果许多follower同时成为候选人，选票可能会被分散，从而没有一个候选节点可以获得多数票的支持。当这种情况发生时，每个候选节点都将超时，此时它们需要通过增加自身的任期并发起新另一轮的RequestVote RPC来开始新一轮选举。但是需要注意的是，如果此时不采取额外措施，这种分散选票选不出leader的情况可能会无限期的重复发生。
为了解决上述风险，Raft采用了一个被称为随机选举超时的机制来减少后续出现分散投票的几率。简单来说就是为了预防多次出现平票的情况，每个节点的选举定时器时间都是不一样的，会从固定时间间隔（比如150-300毫秒）中随机选择。大多数情况下，只有一台服务器将超时，赢得选举，赢得选举后会在任何其他服务器超时之前发送心跳消息树立权威。相同的机制也应用于处理分裂投票。出现分裂投票的情况下，候选节点们在选举开始时重新启动该机制，降低新选举中再次出现分裂投票的可能性。
下图展现了出现分票的情况之一：
以上就是 Raft 的选主逻辑，但还有一些细节（譬如是否给该 candidate 投票还有一些其它条件）依赖算法的其它部分基础，具体将在后续的安全属性章节介绍。
一旦 leader 被票选出来，它就需要承担起相应的职责了，开始接收客户端的请求，并将日志条目复制到其他节点上确保数据一致性。
日志复制（Log replication）
正如前面的内容提到的状态复制机，只要保证节点log的一致性，就可以保证最终的一致性。Raft赋予了leader节点更强的领导力，所有的log都必须交给leader节点处理，并由leader节点复制给其它节点。这个过程，就叫做日志复制（Log replication）。
日志的结构通常如上图所示，每个日志条目都包含leader收到该条目时的任期和状态机的命令，任期号可以用于检测日志之间的不一致。每个日志条目还有一个唯一的整数索引值（log index），可以用于标识其在日志集合中的位置。此外，每条日志还会存储一个term number（日志条目方块最上方的数字，相同颜色任期号相同），该term表示leader收到这条指令时的当前任期，term相同的log是由同一个leader在其任期内发送的。
一旦Leader被选举出来，后续的接受客户端请求以及日志复制等操作主要由leader负责。客户端的每个请求都包含了需要由复制状态机执行的命令，leader会将命令作为新条目附加到其日志中，然后向其他服务器并行发出AppendEntries RPC以便它们复制该条目到相应的日志中。
a. 如果follower节点宕机或者运行缓慢，再或者网络数据包丢失，leader会不断地重试AppendEntries RPC，直到follower节点最后存储了所有的日志条目。
b. 一旦Leader收到超过一半follower的确认，则表明该条目已被成功复制（比如上图中的log index 7）。Leader将该条目应用（apply)到其本地状态机（被视为committed）并将执行结果返回给客户端。此事件还会提交leader日志中之前存在的条目，包括前任leader创建的条目。
Leader会持续发送心跳包给 followers，心跳包中会携带当前已经安全复制（我们称之为committed）的日志索引，以便其他服务器知晓。一旦follower得知日志条目已提交，它就会将该条目应用到其本地状态机（按日志顺序）。
Raft的日志机制（安全规则：日志匹配属性）确保了集群中所有服务器之间日志的高度一致性。日志匹配指的是说：
- 如果不同日志中的两个条目拥有相同的term和index，则它们存储着相同的命令。原因就是因为raft要求leader在一个term内针对同一个index只能创建一条日志，并且永远不会修改，保证“持久化”；
- 当发送AppendEntries RPC时，leader在其日志中会额外包含紧邻新条目之前的日志的index和term信息。如果followers在其日志中找不到具有相同索引和任期的日志条目，则它会拒绝新的日志条目。因此，如果不同日志中的两个条目如果拥有相同的index和term，则所有先前条目中的日志也都是相同的；
AppendEntries会执行一致性检查保留上述属性。
每当 AppendEntries 成功返回时，leader就可以知道follower的日志与自己的日志相同。正常运行时，leader和follower的日志保持一致，因此AppendEntries一致性检查不会失败，只会成功。
但是，在leader崩溃的情况下，日志可能会不一致，前任leader可能没有完全复制其日志中的所有条目。这些不一致可能会引起一系列问题引起失败，比如下图所示的内容，followers的条目与leader不完全一致，要么多了，要么缺少。
为了避免上述情况的发生，Leader通过强制follower复制自己的日志来处理不一致的问题：
- 既然要保证follower的日志与其自己的一致，leader需要将其日志与follower日志进行比较，找到它们之间最后一次达到一致的条目，就像前面提到的日志匹配属性，因此这个条目如果一致，之前的日志也一定都是一致的。然后接下来删除follower日志中此关键条目之后的所有条目，并向follower发送该点之后自己的所有条目进行同步；
- Leader会针对每个follower都维护一个nextindex，表示下一条需要发送给该follower的日志索引。在leader选举成功上任的时候，会将所有的nextIndex值初始化为其日志中最后一条日志的的日志索引+1；
- 如果follower和leader的日志不一致，则下次AppendEntries RPC中的AppendEntries一致性检查将失败，Leader将递减nextIndex并重试AppendEntries RPC，直到nextIndex达到Leader和follower日志匹配的点为止；
- 至此，AppendEntries成功，然后将删除follower日志中任何冲突的条目，并附加领导者日志中的条目（如果有）。
这样的话，leader以及follower的日志就会保持一致直到term任期结束都会保持这种状态。
图解：
注意：Leader永远不会覆盖或删除其日志中的条目，它只会追加新条目。
介绍完了领导职选举流程以及日志复制的工作原理，下一篇我们将来了解一下Raft协议如何确保每个状态机都可以以相同的顺序执行完全相同的命令，以及如何解决随着客户端请求增多日志变长带来的占用高额存储空间的问题。
下一篇：安全属性及快照机制
友情链接：
- 星环分布式存储TDDMS大揭秘（一）分布式存储技术推出背景以及当前存在的挑战
- 星环分布式存储TDDMS大揭秘（二）TDDMS是什么
- TDDMS揭秘（三）分布式一致性技术是如何实现的（上）
- TDDMS揭秘（四）一致性协议Raft的工作原理及介绍--Raft协议背景及算法初剖析（中）
- TDDMS揭秘（六）一致性协议Raft的工作原理及介绍--安全属性及快照机制（下）
- TDDMS揭秘（七）Raft一致性协议在TDDMS中发挥了什么作用？承担了什么角色？
领导者的详细过程
1. 启动阶段
Raft采用心跳机制来触发leader选举。当服务器启动时，服务器首先作为follower。只要服务器从leader或者candidate接收到有效的RPC，他们就会保持其follower状态。
2. 状态转换，候选状态出现
为了维护集群Leader的权威，Leader节点会向其他Follower节点发送心跳来表达统治权。如果Follower节点在一段时间内（选举超时机制）没有收到任何通信，他就会过渡到候选状态并增加其当前任期，开始新的选举；
3. 请求投票
此时，超时节点将其状态更改为Candidate状态，它会为自己投票并向集群中的所有其他节点并行发送RequestVote RPC以建立多数并尝试成为Leader。其中，RequestVote RPC信息中包括候选人的任期、候选节点日志中最后的索引（lastLogIndex）以及任期（lastLogterm）。候选者继续保持这种状态，直到发生以下三种情况之一：（a）它赢得选举，（b）另一台服务器将自己确立为领导者，或（c）一段时间内没有获胜者。
3.1.1.投票流程
每台服务器都存储一个当前的任期号，该任期号随着时间的推移单调增加。 每当服务器通信时都会交换当前任期信息进行选举：
- 如果一台服务器的当前任期号小于另一台服务器的当前任期号，则它会将其当前的任期进行更新；
- 如果候选者或leader发现其任期号比其他服务器小，则会立即恢复为follower状态；
- Follower会评估候选者的日志确定其是否是最新的，如果不是则拒绝投票请求；如果是，则投票给候选者；
- 在任何时间点，任何其他服务器拥有更高的term number，它可以立即成为新任leader；
4.选举结果
情况1： 选举成功（Step: receives votes from majority of servers）
如果候选节点收到来自整个集群中同一任期的大多数服务器的选票（N/2+1），则该候选节点将赢得选举，此时，它会立刻将自己的状态更新为Leader，并向所有其他服务器发送心跳消息，以建立其权威并防止新的选举。每个节点针对每个term只能投出一张票，按照先到先得的原则确保了最多保只有一个 candidate 会成为 leader。
情况2：选举失败（Step: discovers current leader or new term）
在等待投票时，候选节点可能会从另一台声称是自己是leader的服务器收到AppendEntries RPC。如果这台服务器携带的任期（包含在其RPC中）跟候选节点自身当前的任期一样大或者比他大，那么候选节点则承认对方的leader身份并认为对方是生效的，然后将自身状态切换回follower状态。这说明其它节点已经成功赢得了选举，它只需立刻跟随即可。 如果RPC中的任期小于候选节点当前的任期，则候选节点拒绝此次请求并继续保持候选状态。
情况3：选举超时（Step: times out, new election）
最后一种情况是候选人既不会赢得选举，也不会输掉选举：如果许多follower同时成为候选人，选票可能会被分散，从而没有一个候选节点可以获得多数票的支持。当这种情况发生时，每个候选节点都将超时，此时它们需要通过增加自身的任期并发起新另一轮的RequestVote RPC来开始新一轮选举。但是需要注意的是，如果此时不采取额外措施，这种分散选票选不出leader的情况可能会无限期的重复发生。
为了解决上述风险，Raft采用了一个被称为随机选举超时的机制来减少后续出现分散投票的几率。简单来说就是为了预防多次出现平票的情况，每个节点的选举定时器时间都是不一样的，会从固定时间间隔（比如150-300毫秒）中随机选择。大多数情况下，只有一台服务器将超时，赢得选举，赢得选举后会在任何其他服务器超时之前发送心跳消息树立权威。相同的机制也应用于处理分裂投票。出现分裂投票的情况下，候选节点们在选举开始时重新启动该机制，降低新选举中再次出现分裂投票的可能性。
下图展现了出现分票的情况之一：
以上就是 Raft 的选主逻辑，但还有一些细节（譬如是否给该 candidate 投票还有一些其它条件）依赖算法的其它部分基础，具体将在后续的安全属性章节介绍。
一旦 leader 被票选出来，它就需要承担起相应的职责了，开始接收客户端的请求，并将日志条目复制到其他节点上确保数据一致性。
日志复制（Log replication）
正如前面的内容提到的状态复制机，只要保证节点log的一致性，就可以保证最终的一致性。Raft赋予了leader节点更强的领导力，所有的log都必须交给leader节点处理，并由leader节点复制给其它节点。这个过程，就叫做日志复制（Log replication）。
日志的结构通常如上图所示，每个日志条目都包含leader收到该条目时的任期和状态机的命令，任期号可以用于检测日志之间的不一致。每个日志条目还有一个唯一的整数索引值（log index），可以用于标识其在日志集合中的位置。此外，每条日志还会存储一个term number（日志条目方块最上方的数字，相同颜色任期号相同），该term表示leader收到这条指令时的当前任期，term相同的log是由同一个leader在其任期内发送的。
一旦Leader被选举出来，后续的接受客户端请求以及日志复制等操作主要由leader负责。客户端的每个请求都包含了需要由复制状态机执行的命令，leader会将命令作为新条目附加到其日志中，然后向其他服务器并行发出AppendEntries RPC以便它们复制该条目到相应的日志中。
a. 如果follower节点宕机或者运行缓慢，再或者网络数据包丢失，leader会不断地重试AppendEntries RPC，直到follower节点最后存储了所有的日志条目。
b. 一旦Leader收到超过一半follower的确认，则表明该条目已被成功复制（比如上图中的log index 7）。Leader将该条目应用（apply)到其本地状态机（被视为committed）并将执行结果返回给客户端。此事件还会提交leader日志中之前存在的条目，包括前任leader创建的条目。
Leader会持续发送心跳包给 followers，心跳包中会携带当前已经安全复制（我们称之为committed）的日志索引，以便其他服务器知晓。一旦follower得知日志条目已提交，它就会将该条目应用到其本地状态机（按日志顺序）。
Raft的日志机制（安全规则：日志匹配属性）确保了集群中所有服务器之间日志的高度一致性。日志匹配指的是说：
- 如果不同日志中的两个条目拥有相同的term和index，则它们存储着相同的命令。原因就是因为raft要求leader在一个term内针对同一个index只能创建一条日志，并且永远不会修改，保证“持久化”；
- 当发送AppendEntries RPC时，leader在其日志中会额外包含紧邻新条目之前的日志的index和term信息。如果followers在其日志中找不到具有相同索引和任期的日志条目，则它会拒绝新的日志条目。因此，如果不同日志中的两个条目如果拥有相同的index和term，则所有先前条目中的日志也都是相同的；
AppendEntries会执行一致性检查保留上述属性。
每当 AppendEntries 成功返回时，leader就可以知道follower的日志与自己的日志相同。正常运行时，leader和follower的日志保持一致，因此AppendEntries一致性检查不会失败，只会成功。
但是，在leader崩溃的情况下，日志可能会不一致，前任leader可能没有完全复制其日志中的所有条目。这些不一致可能会引起一系列问题引起失败，比如下图所示的内容，followers的条目与leader不完全一致，要么多了，要么缺少。
为了避免上述情况的发生，Leader通过强制follower复制自己的日志来处理不一致的问题：
- 既然要保证follower的日志与其自己的一致，leader需要将其日志与follower日志进行比较，找到它们之间最后一次达到一致的条目，就像前面提到的日志匹配属性，因此这个条目如果一致，之前的日志也一定都是一致的。然后接下来删除follower日志中此关键条目之后的所有条目，并向follower发送该点之后自己的所有条目进行同步；
- Leader会针对每个follower都维护一个nextindex，表示下一条需要发送给该follower的日志索引。在leader选举成功上任的时候，会将所有的nextIndex值初始化为其日志中最后一条日志的的日志索引+1；
- 如果follower和leader的日志不一致，则下次AppendEntries RPC中的AppendEntries一致性检查将失败，Leader将递减nextIndex并重试AppendEntries RPC，直到nextIndex达到Leader和follower日志匹配的点为止；
- 至此，AppendEntries成功，然后将删除follower日志中任何冲突的条目，并附加领导者日志中的条目（如果有）。
这样的话，leader以及follower的日志就会保持一致直到term任期结束都会保持这种状态。
图解：
注意：Leader永远不会覆盖或删除其日志中的条目，它只会追加新条目。
介绍完了领导职选举流程以及日志复制的工作原理，下一篇我们将来了解一下Raft协议如何确保每个状态机都可以以相同的顺序执行完全相同的命令，以及如何解决随着客户端请求增多日志变长带来的占用高额存储空间的问题。
下一篇：安全属性及快照机制
登录后可评论
.jpg)
