分布式系统开发的Raft共识算法

除了提高整个系统的性能之外，分布式系统的一个重要特性就是提高系统的可靠性。提供可靠性可以理解为系统中一台或多台机器的故障不会导致系统不可用或导致数据丢失。保证系统可靠性的关键是多实例。一旦存在多个副本，就面临多个副本之间的一致性问题

一致性算法用于解决分布式环境中多个副本之间的数据一致性问题。经过。业界最著名的共识算法就是大名鼎鼎的Paxos，但Paxos是出了名的难以理解，而Raft的诞生就是为了探索一种更容易理解的共识算法，它将一致性分解为领导者选举。 、日志复制和安全性是三个重要要素。

1。 Leader选举

Raft算法将时间按照任意长度进行划分。这些术语由连续的数字表示。每个任期的开始都是一次选举。如果候选人赢得选举，他将成为剩余任期的领导人。如果没有选出领导人，新的任期开始，下一次选举立即开始

那么选举什么时候开始呢？事实上，领导者会定期向所有追随者发送心跳，以确保其领导者地位。如果一个follower在一个周期内没有收到心跳信息，则认为没有可用的leader，并改变自己的状态成为候选者。并开始选举选出新的leader

raft选举过程有3个规则

（1）规则：如果请求投票的服务器任期比自己的任期长，则为服务器投票

(2)、规则：在一个任期内，一台服务器最多只能投票给一名候选人，先到先得

(3)、规则：随机选举超时

避免投票，因为分布均匀，没有服务器。为了成为Leader，每个服务器都是在固定范围内随机选择的，因此每个服务器的选举超时时间是不同的。这种机制保证了大多数情况下只有一台服务器会先超时，当其他服务器超时时才超时。先前赢得选举并向其他服务器发送心跳信息

当候选人收到大多数节点的选票时，它会切换到领导者。如果找到领导者或收到更高任期的请求，它将切换到追随者。角色变更时完成选举。安全原则：每届最多选举一名领导人

2。期刊复制

要了解期刊复制，首先要了解期刊匹配原则和期刊提交原则这两个概念
期刊匹配原则描述的是，如果不同期刊中的两个条目具有相同的索引和术语号，他们保存的作业是相同的。如果不同日志中的两个条目具有相同的索引和术语编号，则它们之间的所有条目都是相同的
可提交日志描述了领导者在复制后创建的条目。这篇日记在大多数服务器上都可以通过。Leader的日志中可以记录以前的条目，包括前一个Leader所做的条目

在日志复制过程中，Leader必须找到follower与他的日志一致的位置，然后删除该位置条目之后的follower ，然后将其该位置之后的条目发送给follower

完整的过程是，客户端向leader发送请求，leader将日志条目添加到其日志中，并向follower服务器发起日志复制请求并行，领导确认了日记。一旦条目被安全复制，该条目就会被应用到状态机，并将结果返回给客户端，从而向跟踪器发出提交日志条目的请求。一旦一台服务器应用了为其在状态机中提供索引位置的日志条目，所有其他服务器将不会将另一个条目应用于该索引位置

日志复制可能会出现一些异常

(1) ，例外：数据正在发送给leader，但没有复制到follower

leader异常，client无法收到确认。重新选举后，客户端可以重新向leader发送请求
（2），异常：数据到达leader节点，并成功复制到所有follower节点，但没有收到leader的响应

重新选举后-election -election ，虽然数据在跟踪节点上处于未提交状态，但仍然保持一致。重新选举leader后即可完成数据提交。由于原来的leader异常，client无法收到确认，会重新向leader发送请求。 Raft要求RPC是幂等的，所以服务端必须实现去重机制
(3)。例外：数据到达领导节点并成功复制到所有或大多数跟随者。节点，数据在leader中处于已提交状态，但在follower中处于未提交状态

此阶段，leader挂掉，重新选举出新的leader

（4），例外：有由于网络分区出现重复领导者
以 5 个服务器节点为例。正常情况下，节点A作为Leader，接收客户端请求，并与四个Follower节点B、C、D、E同步日志。由于网络原因，节点A、B无法与C、D、E通信。 C 、D和E重新选举并选出领导者。假设节点 E 获胜，此时会出现重复的领导者。然后网络恢复，A和B将充当E

3的追随者。安全
Raft 通过比较日志中最后一个条目的索引和术语编号来确定更新两个日志中的哪一个。如果两个期刊不同，则更新较大的分期号。如果任期编号相同，则更新较长的议程。
为了确保安全，Raft 同意了一些选举限制。 RequestVote RPC 包含候选人的议程信息。如果服务器自己的日记比候选人新，那么对候选人的投票将被拒绝

这种行为的背后隐藏着整个领导者原则。如果日记条目是在特定期间提交的，那么该条目肯定会出现在所有术语更新中。伟大领袖之中。所有日志数据仅从Leader节点写入Follower节点，Leader节点上的日志仅被追加，不会被删除或覆盖。

作者简介：京东高级工程师-梁松华