【86期】分布式基础概念-选举算法

选举算法Quorum机制、WARO

waro：一种简单的副本控制协议，写操作时、只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。优先保证读、任何节点读到的数据都是最新数据，牺牲了更新服务的可用性、只要有一个副本宕机了，写服务就不会成功。但只要有一个节点存活、仍能提供读服务

Quorum机制：10个副本，一次成功更新了三个，那么至少需要读取八个副本的数据，可以保证读到了最新的数据。无法保证强一致性，也就是无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。需要配合一个获取最新成功提交的版本号的metadata服务，这样可以确定最新已经成功提交的版本号，然后从已经读到的数据中就可以确认最新写入的数据

paxos算法

Paxos算法解决的是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各个节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能够得到一个一致的状态。为了保证每个节点执行相同的操作序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。在Paxos算法中，有三种角色：Proposer (提议者),Acceptor（接受者），Learners（记录员）

Proposer提议者：只要Proposer发的提案Propose被半数以上的Acceptor接受，Proposer就认为该提案例的value被选定了。

Acceptor接受者：只要Acceptor接受了某个提案，Acceptor就认为该提案例的value被选定了

Learner记录员：Acceptor告诉Learner哪个value被选定，Learner就认为哪个value被选定。

Paxos算法分为两个阶段，具体如下：

阶段一（preprae）：

(a) Proposer收到client请求或者发现本地有未提交的值，选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。

(b) Acceptor收到一个编号为N的Prepare请求，如果该轮paxos

本节点已经有已提交的value记录，对比记录的编号和N，大于N则拒绝回应，否则返回该记录value及编号

没有已提交记录，判断本地是否有编号N1，N1>N、则拒绝响应，否则将N1改为N（如果没有N1，则记录N），并响应prepare

阶段二（accept）：

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

(b)如果Acceptor收到一个针对编号为N的提案的Accept请求，Acceptor对比本地的记录编号，如果小于等于N，则接受该值，并提交记录value。否则拒绝请求

Proposer如果收到的大多数Acceptor响应，则选定该value值，并同步给leaner，使未响应的Acceptor达成一致

简单如图所示：

活锁：accept时被拒绝，加大N，重新accept，此时另外一个proposer也进行相同操作，导致accept一致失败，无法完成算法

multi-paxos：区别于paxos只是确定一个值，multi-paxos可以确定多个值，收到accept请求后，则一定时间内不再accept其他节点的请求，以此保证后续的编号不需要在经过preprae确认，直接进行accept操作。此时该节点成为了leader，直到accept被拒绝，重新发起prepare请求竞争leader资格。

raft算法

基本概念：

分布式一致性算法：raft会先选举出leader，leader完全负责replicated log的管理。leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。如果leader故障，followes会重新选举出新的leader

三种状态：一个节点任一时刻处于三者之一

leader：处理所有的客户端请求（如果客户端将请求发给了Follower，Follower将请求重定向给Leader）

follower：不会发送任何请求，只会简单地响应来自Leader或Candidate的请求

candidate：用于选举产生新的leader(候选人)

term：任期，leader产生到重新选举为一任期，每个节点都维持着当前的任期号

term是递增的，存储在log日志的entry中，代表当前entry是在哪一个term时期写入

每个任期只能有一个leader或者没有(选举失败)

每次rpc通信时传递该任期号，如果RPC收到任期号大于本地的、切换为follower，小于本地任期号则返回错误信息

两个RPC通信：

RequestVote RPC：负责选举，包含参数lastIndex，lastTerm

AppendEntries RPC：负责数据的交互。

日志序列：每一个节点上维持着一份持久化Log，通过一致性协议算法，保证每一个节点中的Log保持一致，并且顺序存放，这样客户端就可以在每一个节点中读取到相同的数据

状态机：日志序列同步到多数节点时，leader将该日志提交到状态机，并在下一次心跳通知所有节点提交状态机（携带最后提交的lastIndex）

何时触发选举：

集群初始化时，都是follower，随机超时，变成candidate，发起选举

如果follower在election timeout内没有收到来自leader的心跳，则主动触发选举

选举过程：

发出选举的节点角度

增加节点本地的term，切换到candidate状态

投自己一票

其他节点投票逻辑：每个节点同一任期最多只能投一票，候选人知道的信息不能比自己少（通过副本日志和安全机制保障），先来先得

并行给其他节点发送RequestVote RPCs(选举请求)、包含term参数

等待回复

收到majority(大多数)的投票，赢得选举，切换到leader状态，立刻给所有节点发心跳消息

被告知别人当选，切换到follower状态。（原来的leader对比term，比自己的大，转换到follower状态）

一段时间没收到majority和leader的心跳通知，则保持candidate、重新发出选举

日志序列同步：

日志需要存储在磁盘持久化，崩溃可以从日志恢复

客户端发送命令给Leader。

Leader把日志条目加到自己的日志序列里。

Leader发送AppendEntries RPC请求给所有的follower。携带了prevLogIndex，prevLogTermfollower收到后，进行日志序列匹配

匹配上则追加到自己的日志序列

匹配不上则拒绝请求，leader将日志index调小，重新同步直至匹配上，follower将leader的日志序列覆盖到本地

一旦新的日志序列条目变成majority的了，将日志序列应用到状态机中

Leader在状态机里提交自己日志序列条目，然后返回结果给客户端

Leader下次发送AppendEntries RPC时，告知follower已经提交的日志序列条目信息(lastIndex)

follower收到RPC后，提交到自己的状态机里

提交状态机时，如果term为上一任期，必须与当前任期数据一起提交，否则可能出现覆盖已提交状态机的日志

新选举出的leader一定拥有所有已提交状态机的日志条目

leader在当日志序列条目已经复制到大多数follower机器上时，才会提交日志条目。

而选出的leader的logIndex必须大于等于大多数节点，因此leader肯定有最新的日志

安全原则：

选举安全原则：对于一个给定的任期号，最多只会有一个领导人被选举出来

状态机安全原则：如果一个leader已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志

领导人完全原则：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中

领导人只附加原则：领导人绝对不会删除或者覆盖自己的日志，只会增加

日志匹配原则：如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同