分布式-PAXOS算法

PAXOS算法

数据同步方法

• 状态转移。

将主节点数据同步到从节点。

• 操作转移

存储主节点执行过的命令，即“操作日志”。通过重新执行命令，来进行数据同步。

多节点环境下，操作转移的方式，对于数据的一致性，需要一种共识算法。

Paxos算法

简介

Paxos 不直接应用于工业界，但它的变体算法， Multi Paxos、Raft 算法，以及 ZAB 等算法，都是分布式领域中的基石。

组成

Paxos 算法将分布式系统中的节点分为提案节点、决策节点和记录节点三类。

提案节点：称为 Proposer，提出对某个值进行设置操作的节点，设置值这个行为就是提案（Proposal）。值一旦设置成功，就是不会丢失也不可变的。

决策节点：称为 Acceptor，是应答提案的节点，决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受，就意味着这个提案被批准（Accept）。提案被批准，就意味着该值不能再被更改，也不会丢失，且最终所有节点都会接受它。

记录节点：被称为 Learner，不参与提案，也不参与决策，只是单纯地从提案、决策节点中学习已经达成共识的提案。比如，少数派节点从网络分区中恢复时，将会进入这种状态。

在使用 Paxos 算法的分布式系统里，所有的节点都是平等的，它们都可以承担以上某一种或者多种角色。

工作流程

Paxos 算法是怎么解决并发操作带来的竞争的？

Paxos 算法包括“准备（Prepare）”和“批准（Accept）”两个阶段。

第一阶段“准备”（Prepare）就相当于抢占锁的过程。

如果某个提案节点准备发起提案，必须先向所有的决策节点广播一个许可申请（称为 Prepare 请求）。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID，决策节点收到后，会给提案节点两个承诺和一个应答。

其中，两个承诺是指：承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求；承诺不会再接受提案 ID 小于 n 的 Accept 请求。

一个应答是指：在不违背以前作出的承诺的前提下，回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID，如果该值从来没有被任何提案设定过，则返回空值。如果收到的提案 ID 并不是决策节点收到过的最大的，那就可以直接不理会这个 Prepare 请求。

当提案节点收到了多数派决策节点的应答（称为 Promise 应答）后，可以开始第二阶段“批准”（Accept）过程。这时有两种可能的结果：

• 如果提案节点发现所有响应的决策节点此前都没有批准过这个值（即为空），就说明它是第一个设置值的节点，可以随意地决定要设定的值；并将自己选定的值与提案 ID，构成一个二元组 (id, value)，再次广播给全部的决策节点（称为 Accept 请求）。

• 如果提案节点发现响应的决策节点中，已经有至少一个节点的应答中包含有值了，那它就不能够随意取值了，必须无条件地从应答中找出提案 ID 最大的那个值并接受，构成一个二元组 (id, maxAcceptValue)，然后再次广播给全部的决策节点（称为 Accept 请求）。

当每一个决策节点收到 Accept 请求时，都会在不违背以前作出的承诺的前提下，接收并持久化当前提案 ID 和提案附带的值。如果违反此前做出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的，那允许直接对此 Accept 请求不予理会。

当提案节点收到了多数派决策节点的应答（称为 Accepted 应答）后，协商结束，共识决议形成，将形成的决议发送给所有记录节点进行学习

活锁问题

如果两个提案节点交替使用更大的提案 ID 使得准备阶段成功，但是批准阶段失败的话，这个过程理论上可以无限持续下去，形成活锁（Live Lock）。