共识算法

共识算法是一种用于分布式系统中的算法，其目的是让不同的节点在没有中心化控制的情况下，达成一致的决策。这个决策可以是任何事情。

在一个分布式系统中，每个节点都有自己的数据和状态，这些节点需要相互通信以达成共识。共识算法的作用就是让这些节点在达成共识时，保持一致性和正确性。

这对于构建高可用性、高性能、可拓展性的分布式系统至关重要。

适用于实际系统的共识算法通常具有以下特性：

• 安全。确保在非拜占庭条件下的安全性，包括网络延迟、分区、包丢失、复制和重新排序
• 高可用。只要大多数服务器是可操作的，并可以相互通信，那么这些服务器就可以看做完全功能可用。
• 一致性不依赖时序。错误的时钟和极端的消息延迟，在最坏的情况下也只造成可用性问题，而不会产生一致性问题。
• 在集群中大多数服务器响应，命令就可以完成，不会被少数运行缓慢的服务器来影响整体性能

Paxos算法

Paxos是第一个被证明完备的共识算法（前提是不存在拜占庭将军问题，即没有恶意节点）

pax算法主要包含

• Basic Paxos算法：描述的是多节点之间如何就某个值（提案）达成共识
• Multi-Paxos思想：描述的是执行多个Basic Paxos示例，就一系列值达成共识。

Basic Paxos算法的3个重要角色

• 提议者（Proposer）:也称协调者（coordinator），提议者负责接收客户端的请求并发起提案。提案信息包括编号（Proposal ID）和提议的值（Value）
• 接受者（Acceptor）:也可以叫做投票员（voter）,负责对提议者的提案进行投票，同时需要记住自己的投票历史；
• 学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

Raft算法

由于Paxos算法在国际上被公认难以理解和实现，不断有人简化，诞生了比Paxos算法更易理解的和实现的共识算法Raft算法。

Raft节点类型

一个Raft集群包括若干服务器，以典型的5服务器集群举例。在任意的时间，每个服务器一定会处于以下三个状态中的一个：

• Leader：负责发起心跳，响应客户端，创建日志，同步日志。
• Candidate: Leader选举过程中的临时角色，由Follower转化而来，发起投票参与竞选。
• Follower: 接受Leader的心跳和日志同步数据，投票给Candidate。

正常的情况下，只有一个服务器是Leader，剩下的服务器是Follower。Follower是被动的，他们不会发送任何请求，只是响应来自Leader和Candidate的请求

Raft 任期

Raft把时间切割为任意长度的任期（Term），每个Term都是一个连续递增的编号，采用连续的整数来表示。每个任期都由一次选举开始，每一轮选举都是一个Term任期，若选举失败则这个任期内没有Leader。如果选举出了Leader则这个任期内由Leader负责集群状态管理，在一个Term中只能产生一个Leader。

Term的变化流程：Raft开始时所有的Follower的Term为1，其中一个Follower的超时时间到期后转换为Candidate，Term加1（这时为2），然后开始选举，这时候有几种情况会使Term发生改变：

• 如果当前Term为2的任期内没有选举出Leader或出现异常，则Term递增，开始新一任期选择。 （平票或出问题了）
• 当这轮Term为2的周期选举出Leader后，过一段时间Leader挂掉了，Follower转为Candidate，Term递增（新Leader挂掉，新的任期开始）
• 当Leader或Candidate发现自己的Term比别的Follower小，Leader或Candidate将转为Follower,Term递增（之前挂掉Leader重新连上了）
• 当Follower的Term比别的Term小，follower也将更新Term保持与其他Follower一致（之前挂掉的Follower重新连上了，且有新的Leader出现）

每次Term的递增豆浆发生新一轮选举，Raft保证一个Term任期内只有一个Leader，在Raft正常运转中所有的节点的Term都是一致的，如果节点不发生故障一个Term会一直保持下去，当节点收到的请求中Term比当前Term小时则拒绝该请求。

日志

• entry: 每一个时间称为entry,只有Leader可以创建entry。entry的内容<term,index,cmd>其中cmd是可以应用到状态机的操作。
• log: 由entry构成的数据组，每一个entry都有一个表明自己在log中的index。只有Leader才可以改变其他节点的log。entry总是先被Leader添加到自己的log数组中，然后再发起共识请求，获得同意后才会被Leader提交给状态机。Follower只能从Leader获取新日志和当前的commitIndex，然后把对应的entry应用到自己的状态机中。

领导人选举

Raft使用心跳机制来触发Leader选举。

Leader会向所有的Follower周期性发送心跳保证自己的Leader地位。如果Follower一个周期内没收到心跳，则选举超时，开始进行选举新的Leader。Follower会自增自己的term号并且转换为Candidate，然后会向所有节点发起请求，Candidate的状态会持续直到：

• 自己赢得选举
• 其他节点赢得选举
• 无节点赢得选举

赢的条件为： 一个Candidate在一个任期内收到了来自集群内 的多数选票（N/2+1）。

当Candidate选举的时候，可能会收到来自Leader的心跳，此时分两种情况：

• 该Leader的term号大于等于自己的term号。对方已成为Leader，自己退回Follower
• 该Leader的term号小于自己的term号。那么拒绝请求并让该节点更新term。

由于可能存在多位Candidate的情况，如果仅依靠投票，可能会出现无限重复的情况。

Raft使用了随机的选举超时时间来避免。每个Candidate在发起选举后，都会随机化一个新的选举超时时间，这种机制使得各个服务器能够分散开，在大多数情况下只有一个服务器会率先超时，他会在其他服务器超时之前赢得选举。

Raft日志复制

一旦选出了Leader，它就开始接受客户端请求。每一个客户端的请求都包含一条需要被复制状态机的命令

Leader收到客户端请求后，会先生成一个entry。包含<index,term,cmd>，再将这个entry添加到自己的日志末尾后，向所有的节点广播该entry，要求其他服务器复制这条entry。

如果Follower接受该entry，则entry添加到自己的日志后面，同时返回给Leader同意。

如果Leader收到了多数的成功响应，Leader会将这个entry应用到自己的状态机中，之后可以称这个entry是committed的，并且向客户端返回执行结果。

raft保证以下两个性质：

• 在两个日志里，有两个entry拥有相同的index和term,那么他们一定有相同的cmd
• 在两个日志里，有两个entry拥有相同的index和term,那么他们前面的entry也一定相同。

第一条通过仅有一个Leader保证，第二个需要一致性检查来保证。

一般情况，Leader和Follower的日志是一致的，但由于Leader崩溃，导致了日志不一样，Leader会强制Follower复制自己的日志。Leader会进行比对，找到日志一致的地方，然后删除Follower之后的日志，把之后的日志发给Follower。

• 具体实现步骤为。Leader给每一个Follower维护了一个nextINdex。它表示将要发送给Follower的下一条日志条目的索引。当一个Leader选举成功时，它会将nextIndex初始化为它最新的日志条目索引数+1。如果一个Follower的日志和Leader不一致，则AppendEntries一致性检查会在下一次AppendEntries RPC时返回失败。失败之后，Leader会将nextIndex递减然后重试AppendEntries RPC。最终一致。这时Follower会移除掉冲突日志，并且添加Leader的日志条目，这样就保证了Leader和Follower的日志一致性，这样会持续到当前任期结束。

安全性

选举限制

Leader需要保证自己存储全部已经提交给日志条目，这样才可以使日志条目只有一个流向。Leader到Follower.

每个Candidate发送RequestVoteRPC时，都会带上最后一个entry的信息，所有节点收到投票时，会对该entry进行比较，如果发现自己的更新，则拒绝投票给该Candidate。

判断日志新旧的方式：如果两个日志的term不同，term大的更新；如果term相同，更长的index更新。

节点崩溃

如果Leader崩溃，集群中的节点在electTimeout时间内没有收到Leader的心跳信息就会触发新一轮的选举，在选举期间整个集群对外是不可用的。

如果Follower和Candidate崩溃，处理方式会简单很多。之后发送给它的RquestVoteRPC和AppendEntriesRPC会失败。由于raft的所有请求都是幂等的，所以失败的话会无限重试。如果崩溃回复后，就可以收到新的请求，然后选择追加或者拒绝entry。

时间与可用性

raft的要求之一就是安全性不依赖于时间：系统不能仅因为一些事件发生的比预想快或者慢一些就产生错误。为了保证上诉要求，最好能满足以下的时间允许：

broadcastTime << electionTimeout << MTBF

• broadcastTime:向其他节点并发发送消息的平均响应时间；
• electionTimeout：选举超时时间；
• MTBF（mean time between failures）:单台机器的平均健康时间；