分布式选举\共识算法之Bully、Raft与Paxos

注：本文章作为基础入门理解

Bully Algorithm（选举算法）  

简述：

Bully算法是一种协调者（主节点）竞选算法，主要思想是集群的每个成员都可以声明它是主节点并通知其他节点。别的节点可以选择接受这个声称或是拒绝并进入主节点竞争。被其他所有节点接受的节点才能成为主节点。节点按照一些属性来判断谁应该胜出。这个属性可以是一个静态ID，也可以是更新的度量像最近一次事务ID（最新的节点会胜出）

三种消息类型：

 Election消息：表示发起一次选举

 Answer（Alive）消息：对发起选举消息的应答

 Coordinator（Victory）消息：选举胜利者向参与者发送选举成功消息

选举流程：

-如果P是最大的ID，直接向所有人发送Victory消息，成为新的Leader；否则向所有比它大的ID的进程发送Election消息

-如果P在发送Election消息后没有收到Alive消息，则P向所有人发送Victory消息，成为新的Leader

-如果P收到了从比自己ID还要大的进程发来的Alive消息，P停止发送任何消息，等待Victory消息（如果过了一段时间没有等到Victory消息，重新开始选举流程）

-如果P收到了比自己ID小的进程发来的Election消息，回复一个Alive消息，然后重新开始选举流程

-如果P收到Victory消息，把发送者当做Leader

应用场景举例：

mongodb，elasticsearch（类Bully）

那mongodb是怎进行选举的呢？官方这么描述:

We use a consensus protocol to pick a primary. Exact details will be spared here but that basic process is:

1. get maxLocalOpOrdinal from each server.
2. if a majority of servers are not up (from this server’s POV), remain in Secondary mode and stop.
3. if the last op time seems very old, stop and await human intervention.
4. else, using a consensus protocol, pick the server with the highest maxLocalOpOrdinal as the Primary.

大致翻译过来为使用一致协议选择主节点。基本步骤为：

1. 得到每个服务器节点的最后操作时间戳。每个mongodb都有oplog机制会记录本机的操作，方便和主服务器进行对比数据是否同步还可以用于错误恢复。
2. 如果集群中大部分服务器down机了，保留活着的节点都为 secondary状态并停止，不选举了。
3. 如果集群中选举出来的主节点或者所有从节点最后一次同步时间看起来很旧了，停止选举等待人来操作。
4. 如果上面都没有问题就选择最后操作时间戳最新（保证数据是最新的）的服务器节点作为主节点。

触发条件：

1. 初始化一个副本集时。
2. 副本集和主节点断开连接，可能是网络问题。
3. 主节点宕掉。

Raft 共识算法

 简述：

与Paxos不同Raft强调的是易懂（Understandability），Raft和Paxos一样只要保证n/2+1节点正常就能够提供服务；众所周知但问题较为复杂时可以把问题分解为几个小问题来处理，Raft也使用了分而治之的思想把算法流程分为三个子问题：选举（Leader election）、日志复制（Log replication）、安全性（Safety）三个子问题。

角色类型：

在Raft算法中节点存在Follower、Candidate、Leader三种状态。

选举流程：

 Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。每一个follower都有一个时钟，是一个随机的值，表示的是follower等待成为leader的时间，谁的时钟先跑完，则发起leader选举。

  Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC。结果有以下三种情况：

• 赢得了多数的选票，成功选举为Leader；
• 收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；
• 没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

动图过程展示：http://thesecretlivesofdata.com/raft/

日志复制（数据共识\保证数据一致性）

1、日志复制的过程

  Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

• 客户端的每一个请求都包含被复制状态机执行的指令。
• leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让他们复制这条信息。
• 假如这条日志被安全的复制，领导人就应用这条日志到自己的状态机中，并返回给客户端。
• 如果 follower 宕机或者运行缓慢或者丢包，leader会不断的重试，直到所有的 follower 最终都复制了所有的日志条目。

  简而言之，leader选举的过程是：1、增加term号；2、给自己投票；3、重置选举超时计时器；4、发送请求投票的RPC给其它节点。

应用场景举例：

Etcd、Consul

Consul中的Raft

只有以server模式运行的Consul节点，才会被认为是Raft节点集的一部分。所有的client节点会把收到的请求转发到server节点中。这么设计的原因主要是出于性能方面的考虑：节点集中的个数越多，那么法定个数的值也就越大，这会导致leader节点可能需要等待数百个follower节点对一条log entry的agree信息。

在开始的时候，单个Consul server进入到bootstrap模式，这种模式允许它把自己选举为leader。当leader被选举出来之后，别的server就可以被加入到节点集中，从而保障了一致性和安全性。最终，当最初的几台server被加进来后，bootstrap模式可以被关闭。

consul server加入节点集之后，他们会知道哪台机器是当前的leader。当一个RPC请求到达一台非leader server上时，这个请求会被转发到leader上。如果这个请求是一个查询类型（只读），leader会基于现在的状态机生成结果。如果这个请求是一个事物类型的请求（会修改状态），leader会生成一个新的log entry，并用Raft的方法去处理它。当这个log entry被提交并且被应用到状态机上时，这个事物就算完成了。

Raft会把log entry复制到多台机器上，因此网络延迟对于性能的影响很大。因为这个原因，每个数据中心选出一个独立的leader并且维护一份不相交的节点集。数据通过数据中心的方式做分割，因此每个leader只对自己这个数据中心内的数据负责。当一个请求到达一个数据中心，这个请求会被转发到正确的leader那里。这种设计下，我们可以做到低延迟事物以及高可用，而不用牺牲一致性。

补充：

蚂蚁金服开源SOFAJRaft，生产级Java Raft算法库，基于 Raft 一致性算法的生产级高性能 Java 实现，支持 MULTI-RAFT-GROUP，适用于高负载低延迟的场景。

Paxos算法

Paxos不太容易理解，这里只是简单叙述，后续会详解。

简述：

Paxos是能够基于一大堆完全不可靠的网络条件下却能可靠确定地实现共识一致性的算法。也就是说：它允许一组不一定可靠的处理器（服务器）在某些条件得到满足情况下就能达成确定的安全的共识，如果条件不能满足也确保这组处理器（服务器）保持一致。

在Paxos算法中，有三种角色：

• Proposer
• Acceptor
• Learners

Paxos算法的过程（算法描述）

Paxos算法类似于两阶段提提交，其算法执行过程分为两个阶段。具体如下：

阶段一（prepare阶段）：

(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。Pareper（N）

(b) 如果一个Acceptor收到一个编号为N的Prepare请求，如果小于它已经响应过的请求，则拒绝，不回应或回复error。若N大于该Acceptor已经响应过的所有Prepare请求的编号（maxN），那么它就会将它已经接受过（已经经过第二阶段accept的提案）的编号最大的提案（如果有的话，如果还没有的accept提案的话返回{pok，null，null}）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

阶段二（accept阶段）：

(a) 如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value（某个acceptor响应的它已经通过的{acceptN，acceptV}），如果响应中不包含任何提案，那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。如果N小于Acceptor以及响应的prepare请求，则拒绝，不回应或回复error（当proposer没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出prepare请求）。

应用场景举例：

Zookeeper