本篇为资料整理
4.3 Paxos协议
Paxos用于达成共识性问题，即对多个节点产生的值，该算法能保证只选出唯一一个值。
主要有三类节点：
- 提议者（Proposer）：提议一个值；
- 接受者（Acceptor）：对每个提议进行投票；
- 告知者（Learner）：被告知投票的结果，不参与投票过程。
规定一个提议包含两个字段：[n, v]，其中 n 为序号（具有唯一性），v 为提议值。
4.3.1 Prepare 阶段
下图演示了两个 Proposer 和三个 Acceptor 的系统中运行该算法的初始过程，每个 Proposer 都会向所有 Acceptor 发送 Prepare 请求。
当 Acceptor 接收到一个 Prepare 请求，包含的提议为 [n1, v1]，并且之前还未接收过 Prepare 请求，那么发送一个 Prepare 响应，设置当前接收到的提议为 [n1, v1]，并且保证以后不会再接受序号小于 n1 的提议。
如下图，Acceptor X 在收到 [n=2, v=8] 的 Prepare 请求时，由于之前没有接收过提议，因此就发送一个 [no previous] 的 Prepare 响应，设置当前接收到的提议为 [n=2, v=8]，并且保证以后不会再接受序号小于 2 的提议。其它的 Acceptor 类似。
如果 Acceptor 接收到一个 Prepare 请求，包含的提议为 [n2, v2]，并且之前已经接收过提议 [n1, v1]。如果 n1 > n2，那么就丢弃该提议请求；否则，发送 Prepare 响应，该 Prepare 响应包含之前已经接收过的提议 [n1, v1]，设置当前接收到的提议为 [n2, v2]，并且保证以后不会再接受序号小于 n2 的提议。
如下图，Acceptor Z 收到 Proposer A 发来的 [n=2, v=8] 的 Prepare 请求，由于之前已经接收过 [n=4, v=5] 的提议，并且 n > 2，因此就抛弃该提议请求；Acceptor X 收到 Proposer B 发来的 [n=4, v=5] 的 Prepare 请求，因为之前接收到的提议为 [n=2, v=8]，并且 2 <= 4，因此就发送 [n=2, v=8] 的 Prepare 响应，设置当前接收到的提议为 [n=4, v=5]，并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。
4.3.2 Accept 阶段
当一个 Proposer 接收到超过一半 Acceptor 的 Prepare 响应时，就可以发送 Accept 请求。
Proposer A 接收到两个 Prepare 响应之后，就发送 [n=2, v=8] Accept 请求。该 Accept 请求会被所有 Acceptor 丢弃，因为此时所有 Acceptor 都保证不接受序号小于 4 的提议。
Proposer B 过后也收到了两个 Prepare 响应，因此也开始发送 Accept 请求。需要注意的是，Accept 请求的 v 需要取它收到的最大提议编号对应的 v 值，也就是 8。因此它发送 [n=4, v=8] 的 Accept 请求。
4.3.3 Learn 阶段
Acceptor 接收到 Accept 请求时，如果序号大于等于该 Acceptor 承诺的最小序号，那么就发送 Learn 提议给所有的 Learner。当 Learner 发现有大多数的 Acceptor 接收了某个提议，那么该提议的提议值就被 Paxos 选择出来。
具体参考：
微信 PaxosStore：深入浅出 Paxos 算法协议
介绍的比较全面中国人最容易懂的paxos
4.4 Raft
Raft是一个用于日志复制，同步的一致性算法，是Paxos的简易版本。每个结点分为leader，follower和candidate三种状态。
当集群中有leader时，后续操作类似于二阶段、三阶段提交。其他结点是follower，follower会通过心跳与leader保持联系。
4.4.1 Leader Election
如果leader挂了，那么raft就起作用了，用来选取下一个leader，具体过程如下：
- 剩余的follower会通过心跳发现leader挂了，但是谁先发现leader挂了，谁就先成为candidate。（这一等待过程称为election timeout，时间随机为150ms到300ms。率先成为candidate的结点会进入下一轮term投票，
term表示leader的任期）
- candidate会先投自己一票，
并把自己的term+1，然后给其他结点发送vote request，带有自己更新后的term，此时cadidate也会重置election timeout（其他节点如果是follwer状态，且request的term大于自己的term，才会返回赞成票，同时将自己的term+1，并重置election timeout）
- 如果cadidate在timeout之前收到的投票数超过一半时，该candidate就自动成为leader，成为leader后会给其他结点以心跳形式发送带有附加信息的消息，其他结点收到心跳后就知道新的leader产生了，自己都变成follower。follwer每次收到心跳都会重置heartbeat timeout，并回复心跳消息
- 如果leader挂了，那么就会重复1的过程。
- 如果两个follower同时发现leader挂了，都成了candidate，并发送各自的vote request，由于各节点收发速率不同，那么可能出现两个candidate同票，之后大家随机休息一阵，进行下一轮选举。谁先从休息中恢复就可以先发起投票，然后进而回到第一步开始，成为leader。
4.4.2 Log Replication
leader收到客户端请求时，会添加到自己的log中，并向其他follower发送append entries，follower接收后判断是否满足条件，满足条件就将其添加到本地log中，并回复leader成功response。leader在收到大多数成功的response后就把log提交，表示请求被raft系统接受。
具体参考：
网友评论