一、Raft概述Raft算法是分布式系统开发的首选共识算法。比如现在流行的Etcd和Consul。如果掌握了这个算法，就可以轻松应对大部分场景的容错和一致性需求。例如分布式配置系统、分布式NoSQL存储等，轻松突破系统的单机限制。Raft算法通过基于leader的所有方法实现一系列值的共识和各节点日志的一致性。2.Raft角色2.1Follower：普通人默默接收leader的消息。当leader的心跳消息超时时，他们会主动站出来推荐自己为候选人。Candidate：Candidate会向其他节点请求投票RPC消息，通知其他节点进行投票，如果获得多数投票，则晋升为Leader。领导：霸道总裁，一切靠我。处理写请求，管理日志复制，不断发送心跳消息通知其他节点“我是leader，我还活着，是不是”发起新的选举，还没有找到新的leader来代替我。如下图所示，用三个图分别代表followers、candidate、leader。作用三、单节点系统3.1数据库服务器现在假设有一个单节点系统，作为数据库服务器，存储一个值X。数据库服务器3.2客户端左边的绿色实心圆圈为客户端，而右边的蓝色实心圆圈就是节点a（Nodea）。Term代表任期，后面会提到。Client3.3客户端向服务器端发送数据。客户端向单节点服务器发送更新操作，将数据库中存储的值设置为8。在单机环境下（单服务器节点），客户端从服务器获取的值也是8。一致性为很容易确保。客户端向服务器发送数据。3.4多节点如何保证一致性？但是如果有多个服务器节点，如何保证一致性呢？例如，有三个节点：a、b、c。如下所示。这三个节点组成了一个数据库集群。客户端对这三个节点进行更新操作，如何保证三个节点存储的值是一致的呢？这就是分布式一致性的问题。Raft算法就是为了解决这个问题。当然还有其他协议也可以保证。本文只关注Raft算法。在多节点集群中，Raft算法如何保证在节点故障、分区错误等异常情况下集群中同时只有一个leader？下面开始讲解Raft算法选举leader的过程。4.Leader选举过程4.1初始状态在初始状态下，集群中的所有节点都是follower。如下图所示，共有三个节点（Node）a、b、c，任期（Term）为0。初始状态4.2成为候选者Raft算法实现了随机超时的特性，超时间隔为每个节点等待leader节点的心跳信息是随机的。例如，A节点等待超时的时间间隔为150ms，B节点为200ms，C节点为300ms。然后a先超时，因为没有等到leader的心跳信息，就发生了超时。如下图所示，三个节点的超时定时器开始运行。当节点A的超时时间到期时，节点A成为候选人并增加其任期数，Term值从0更新为1，并投票给自己。节点A：任期=1，投票计数=1。节点B：任期=0。节点C：任期=0。成为候选人4.3投票让我们看看候选人如何成为领导者。Leader选举Step1：节点A成为候选者后，向其他节点发送请求投票RPC信息，要求其他节点选举自己为Leader。步骤2：节点B和节点C收到节点A发送的投票信息请求后，将投票给节点A，并在编号为1的任期内增加自己的任期号。Step3：节点A获得3票，获得大多数节点的选票，从候选者中成为本任期的新leader。第四步：节点A作为leader，定时向节点B、C发送心跳消息，告诉节点B、C我是leader，并组织其他follower发起新的选举。第五步：节点B和节点C向节点A发送响应消息，告诉节点A我正常了。4.4Termofoffice英文为term，领导有任期。自动增加：Followers在等待leader的心跳信息超时后，将自己推荐为候选人，会增加任期数。如上图所示，节点A的term为0，在推荐自己作为候选时，term数会增加到1。更新为更大的值：当一个节点发现自己的任期数小于其他节点时，它会更新为更大的数值。例如，节点A的任期为1，请求投票。投票消息中包含节点A的任期编号，编号为1。节点B收到消息后，将自己的任期编号更新为1。恢复为follower：如果某个candidate或leader发现自己的任期数小于其他节点，则立即恢复为follower状态。在这种场景下，分区错误恢复后，任期号为3的leader收到任期号为4的心跳消息，则前者会立即回到follower状态。Rejectmessage：如果节点收到termnumber值较小的请求，则直接拒绝该请求。例如，任期号为6的节点A收到来自任期号为5的节点B的投票请求RPC消息，然后节点A将拒绝该消息。4.5选举规则在一个任期内，leader一直是leader，直到自身出现问题（如宕机）或网络问题（延迟），其他节点发起新一轮选举。在一次选举中，每个服务器节点最多为一个任期号投一票，投完就消失。4.6多数假设一个集群由N个节点组成，那么多数至少是N/2+1。例如：在一个3个节点的集群中，大部分是2个。4.7心跳超时为了防止多个节点同时投票，会为每个节点分配一个随机的选举超时时间。在此期间，该节点不能成为候选者，只能等到超时。比如上面的例子，节点A最先超时，最先成为候选者。通过这种巧妙的设计，在大多数情况下，只有一个服务器节点先发起选举，而不是同时发起选举，从而减少了因投票分裂而导致选举失败的情况。成为候选人5.领导者失败如果领导者节点失败，将触发新一轮选举。如下图所示，如果leader节点B出现故障，节点A和节点B会重新选举leader。Leader失效第1步：节点A失效，节点B和节点C没有收到来自Leader节点A的心跳信息，等待超时。步骤2：节点C先超时，节点C成为候选者。步骤3：节点C向节点A和节点B发起投票信息请求。步骤4：节点C响应投票并投票给C，但是节点A因为失败无法响应C的投票请求。第5步：节点C获得两票（多数票）并成为领导者。步骤6：节点C向节点A、B发送心跳信息，节点A响应心跳信息，节点B不响应心跳信息。总结Raft算法通过以下方式进行leader选举，保证一个任期只有一个leader，大大减少选举失败。任期Leader心跳信息随机选举超时时间超时时间先到先得投票原则大多数投票原则转载本文请联系悟空聊天架构公众号。
