分布式一致性协议介绍（Paxos、Raft）

桃扇骨 2023-01-22 02:58 45阅读 0赞

** 两阶段提交**

Two-phase Commit（2PC）：保证一个事务跨越多个节点时保持 ACID 特性；

两类节点：协调者（Coordinator）和参与者（Participants），协调者只有一个，参与者可以有多个。

过程：

1.  准备阶段：协调者询问参与者事务是否执行成功；
2.  提交阶段：如果事务在每个参与者上都执行成功，协调者发送通知让参与者提交事务；否则，协调者发送通知让参与者回滚事务。

![221c990aeab8b02d66041b0777520cde.png][]

需要注意的是，在准备阶段，参与者执行了事务，但是还未提交。只有在提交阶段接收到协调者发来的通知后，才进行提交或者回滚。

存在的问题

*  参与者发生故障。解决方案：可以给事务设置一个超时时间，如果某个参与者一直不响应，那么认为事务执行失败。
 *  协调者发生故障。解决方案：将操作日志同步到备用协调者，让备用协调者接替后续工作。

**Paxos（Lamport）：**

分布式系统中的节点通信存在两种模型：**[共享内存][Link 1]**（Shared memory）和**[消息传递][Link 2]**（Messages passing）。

基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改即[拜占庭错误][Link 3]的情况。

Paxos算法解决的问题是在一个可能发生上述异常的[分布式系统][Link 4]中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

主要有三类节点：

1.  提议者（Proposer）：提议一个值；
2.  接受者（Acceptor）：对每个提议进行投票；
3.  告知者（Learner）：被告知投票的结果，不参与投票过程。

![06ce8e64441053b8fb57b72cc6b0a6f6.png][]

过程：

规定一个提议包含两个字段：\[n, v\]，其中 n 为序号（具有唯一性），v 为提议值。

下图演示了两个 Proposer 和三个 Acceptor 的系统中运行该算法的初始过程，每个 Proposer 都会向所有 Acceptor 发送提议请求。

![710089e336ff805bacd116afa7536869.png][]

当 Acceptor 接收到一个提议请求，包含的提议为 \[n1, v1\]，并且之前还未接收过提议请求，那么发送一个提议响应，设置当前接收到的提议为 \[n1, v1\]，并且保证以后不会再接受序号小于 n1 的提议。

如下图，Acceptor X 在收到 \[n=2, v=8\] 的提议请求时，由于之前没有接收过提议，因此就发送一个 \[no previous\] 的提议响应，并且设置当前接收到的提议为 \[n=2, v=8\]，并且保证以后不会再接受序号小于 2 的提议。其它的 Acceptor 类似。

![7d56098a50fd8ff5d628a44ca63db8ed.png][]

如果 Acceptor 接受到一个提议请求，包含的提议为 \[n2, v2\]，并且之前已经接收过提议 \[n1, v1\]。如果 n1 > n2，那么就丢弃该提议请求；否则，发送提议响应，该提议响应包含之前已经接收过的提议 \[n1, v1\]，设置当前接收到的提议为 \[n2, v2\]，并且保证以后不会再接受序号小于 n2 的提议。

如下图，Acceptor Z 收到 Proposer A 发来的 \[n=2, v=8\] 的提议请求，由于之前已经接收过 \[n=4, v=5\] 的提议，并且 n > 2，因此就抛弃该提议请求；Acceptor X 收到 Proposer B 发来的 \[n=4, v=5\] 的提议请求，因为之前接收到的提议为 \[n=2, v=8\]，并且 2 <= 4，因此就发送 \[n=2, v=8\] 的提议响应，设置当前接收到的提议为 \[n=4, v=5\]，并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。

![2498dedfe3f1931eedfb95e61e0b4351.png][]

当一个 Proposer 接收到超过一半 Acceptor 的提议响应时，就可以发送接受请求。

Proposer A 接受到两个提议响应之后，就发送 \[n=2, v=8\] 接受请求。该接受请求会被所有 Acceptor 丢弃，因为此时所有 Acceptor 都保证不接受序号小于 4 的提议。

Proposer B 过后也收到了两个提议响应，因此也开始发送接受请求。需要注意的是，接受请求的 v 需要取它收到的最大 v 值，也就是 8。因此它发送 \[n=4, v=8\] 的接受请求。

![d8d7de2c01503034f7cb86818e987c7e.png][]

Acceptor 接收到接受请求时，如果序号大于等于该 Acceptor 承诺的最小序号，那么就发送通知给所有的 Learner。当 Learner 发现有大多数的 Acceptor 接收了某个提议，那么该提议的提议值就被 Paxos 选择出来。

![6e3909786e7b45c59755cf4f28e4e020.png][]

---------------------------------------------------------------------------------------------------

**Raft（14年）：**简化，更容易理解，也更容易实现。

引入主节点，通过竞选。

节点类型：Follower、Candidate 和 Leader

Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选阶段。

流程：  
① 下图表示一个分布式系统的最初阶段，此时只有 Follower，没有 Leader。Follower A 等待一个随机的竞选超时时间之后，没收到 Leader 发来的心跳包，因此进入竞选阶段。

![51dfe797ed97b02df0b45ae4574442c3.gif][]

② 此时 A 发送投票请求给其它所有节点。

![39f836eaae3053a10e33b6318e7601a1.gif][]

③ 其它节点会对请求进行回复，如果超过一半的节点回复了，那么该 Candidate 就会变成 Leader。

![11d7b292d322fd22b0039ab84555bb04.gif][]

④ 之后 Leader 会周期性地发送心跳包给 Follower，Follower 接收到心跳包，会重新开始计时。

![5c348a2f86a977a65d00d33e286c8e86.gif][]

## 多个 Candidate 竞选 ##

① 如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票，例如下图中 Candidate B 和 Candidate D 都获得两票，因此需要重新开始投票。

![7b517bf9dae6b4f26c0c6c81b32d7765.gif][]

② 当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低。

![13a7c7be403a2233a15ead60b962c683.gif][]

## 日志复制 ##

① 来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。

![4115254183388d1788ccaec9b121daee.gif][]

② Leader 会把修改复制到所有 Follower。

![4ebca612c299a0784a90280e33c6007a.gif][]

③ Leader 会等待大多数的 Follower 也进行了修改，然后才将修改提交。

![71f495ad4142397e9cee303aa65f45a8.gif][]

④ 此时 Leader 会通知的所有 Follower 让它们也提交修改，此时所有节点的值达成一致。

![59d700204aec82ff51845fa6256087e5.gif][]

[221c990aeab8b02d66041b0777520cde.png]: /images/20221020/70de7fb6f88f4deb920f8543ca52a3ec.png
[Link 1]: https://zh.wikipedia.org/wiki/%E5%85%B1%E4%BA%AB%E5%86%85%E5%AD%98
[Link 2]: https://zh.wikipedia.org/w/index.php?title=%E6%B6%88%E6%81%AF%E4%BC%A0%E9%80%92&action=edit&redlink=1
[Link 3]: https://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98
[Link 4]: https://zh.wikipedia.org/wiki/%E5%88%86%E5%B8%83%E5%BC%8F%E8%AE%A1%E7%AE%97
[06ce8e64441053b8fb57b72cc6b0a6f6.png]: /images/20221020/50ae9bf3a55d4509ad7427710e75680f.png
[710089e336ff805bacd116afa7536869.png]: /images/20221020/18b96d9d1a804f2d9ca5f4ee57e61964.png
[7d56098a50fd8ff5d628a44ca63db8ed.png]: /images/20221020/e5837aac60d44141844a7f8f1bfa1738.png
[2498dedfe3f1931eedfb95e61e0b4351.png]: /images/20221020/6d91d11968d34052b3d7b8a08e29ce4d.png
[d8d7de2c01503034f7cb86818e987c7e.png]: /images/20221020/5e1811e7ffd24d86b74b46701621fdd5.png
[6e3909786e7b45c59755cf4f28e4e020.png]: /images/20221020/5ab98fd18b8b48d0a75c9afe52c717a4.png
[51dfe797ed97b02df0b45ae4574442c3.gif]: /images/20221020/bfac707bcd0f418a875f9a60cc7fc43b.png
[39f836eaae3053a10e33b6318e7601a1.gif]: /images/20221020/8ba84fac96244540a4cc2746e5afa4d8.png
[11d7b292d322fd22b0039ab84555bb04.gif]: /images/20221020/d2318c73ffbf4198b678a1303c1505d7.png
[5c348a2f86a977a65d00d33e286c8e86.gif]: /images/20221020/b51a7dc0e3094801847c1284cd89a29c.png
[7b517bf9dae6b4f26c0c6c81b32d7765.gif]: /images/20221020/98bef60da8b14858a504289a8d596170.png
[13a7c7be403a2233a15ead60b962c683.gif]: /images/20221020/b593c40796cf4c4e94e3527482e8b29f.png
[4115254183388d1788ccaec9b121daee.gif]: /images/20221020/101eca8df6f14b7f84a7eea2141e1db8.png
[4ebca612c299a0784a90280e33c6007a.gif]: /images/20221020/b4f7c25d784f4982be05cad330f2b17d.png
[71f495ad4142397e9cee303aa65f45a8.gif]: /images/20221020/41cb955ed823480196d0e71eee51b5b5.png
[59d700204aec82ff51845fa6256087e5.gif]: /images/20221020/56cfc868098749e68b90b0540c522217.png