raft leader选举

Last updated on 8 months ago

​

raft介绍

是一种强一致性、去中心化、高可用的分布式协议，是一种leader-based的共识算法；由于 一致性算法中最为出名 Paxos比较难理解，于是有两位学者研究出了raft算法，号称是最容易理解的共识算法（读了论文，确实比较容易理解）

这篇文章主要对 结合raft论文和网上的文章做一个输出，从三个部分介绍 raft

  • raft 协议能做什么
  • raft 中的 leader 选举
  • raft 中的 日志同步和安全性（待更新，会在另外一篇文章）

谈到分布式就离不开一致性的问题，这里的一致性就是 CAP理论的Consistnecy ，在raft中 强一致性的，什么是强一致性呢？假如有三台服务器A，B，C，A收客户端发来的数据后，将数据拷贝到B，C作为副本保存，只有拷贝数据全部完成了，A才可以告知客户端接收数据成功，这是为了确保每个时刻外部从服务器读数据都是一致的；而Raft 使用了一种共识算法来实现前面所说的强一致性。

先说几个概念：

Raft中的角色： 在 Raft 系统中的有三种角色： 领导者（Leader）、跟从者（Follower）和候选人（Candidate）

  • leader： leader 责任去管理副本日志
  • follower： 负责投票，只回复leader和candidate请求
  • candidate： follower 转换成leader的中间转态

Term： 在Raft中的时间会别划分为一个一个Term，而Term就是一个leader的在任的时间（可以理解为leader 当了多久），这个Term时间包含了 leader选举的时间和 leader “在职”的时间，没一个Term都编号，这里可以理解为是第几届的任期

Raft中的通信方式：在Raft服务器之间 使用RPC通信方式 ，其中只有类型的RPC：

  • RequestVote RPCs： 请求投票RPC
  • AppendEntries RPCs： 添加日志RPC

为什么要选举：集群中一般有三台及以上的服务器，而且为奇数，一般那有一个主节点实现了协同和管理，如果主节点宕机了，其他服务器来顶替，而选哪个服务器呢？在raft中使用了 日常生活中的民主投票机制类似，核心思想是“少数服从多数”，从而推选出新的 leader。

Leader选举

​ 当服务器开始启动时候，一开始的状态为follower；这里有一个机制是 如果有leader 存在，会定期发送给心跳包给 全部follower（可以理解为给员工发工资），用来确保 leader的地位（让员工干活有激情），但是如果一个 follower没有接收到心跳包，他就准备造反了（自己想当老板），在没有收到心跳包后的超时时间内自己发起一场选举，此时follower状态转换为candidate，并发送一个 RequestVote 类型 RPCs给全部follower，让他们来投票（他自己也可以投票，投给自己，以先到先得的基础上，最多投票给一个候选人），如果票数超过一半，candidate会成为新的leader。注意每一个term中只会产生一个 leader！

此时candidate面临三种情况：

  1. 我赢了，成为 leader

  2. 刚好 其他follower也发起了选举，另一个服务器赢了

  3. 平局，这个任期谁也没赢

第一种情况，candidate获得了 一半以上的投票，成为了leader。它向其他服务器发送心跳消息，相当于说告诉其他成员你们有leader了，以建立其权威，并防止新的选举。

第二种情况是，此时这个Term里面不止有一个 candidate, 可能另外一个candidate比较快发起投票，先到先得。

第三种情况，没有产生leader，原因可能是 有很多 follower都同时成为了candidate（都想造反），导致没有一个candidate过得过半的票数，此时再来一次，新建一个Term；但问题是，重来一次还是有可能发生的！这里引用了一个随机选举超时的机制，即在成为candidate 前都需要等待一段随机时间，加入 A 等待100ms，B 等150ms，C等200ms，A肯定是最小转变candidate的，此时只有一个candidate，其他都为 follower，这样可以尽可能的避免 投票分裂的情况。

当 candidate在等待 投票结果时，收到了 ”前 leader “ AppendEntries RPC，此时怎么办呢？ 此时 candidate 会比较谁的 Term比较早，比如说 leader 是 13届的任期，而candidate是14届了，那说明已经不是同个时代的事直接忽略；而如果说 leader 是14届或者说更大，则说明candidate已经落伍了，是 “旧时代的 余党” ,而且此时有leader 了，没必要继续下去，此时 candidate 会转换成 follower。

这里建议看下动画加深理解 http://thesecretlivesofdata.com/raft/