分布式基础概念 - 选举算法

选举算法 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 的心跳，则主动触发选举

选举过程：

发出选举的节点角度

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

2. 投自己一票

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

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

5. 等待回复

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

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

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

日志序列同步：

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

1. 客户端发送命令给 Leader。

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

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

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

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

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

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

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

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

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

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

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

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

安全原则：

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

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

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

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

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

如有问题，欢迎加微信交流：w714771310，备注- 技术交流  。或关注微信公众号【码上遇见你】。