Paxos 算法

Paxos 算法 简介

• Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有高
  容错性的一致性算法。Google Chubby 的作者 Mike Burrows 说过，世上只有一种一致性算法，那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一种公认的晦涩难懂的算法，并且工程实现上也具有很大难度。较有名的 Paxos 工程实现有 Google Chubby、ZAB、微信的 PhxPaxos 等。
• Paxos 算法是用于解决什么问题的呢？Paxos 算法要解决的问题是，在分布式系统中如何
  就某个决议达成一致。

Paxos 与拜占庭将军问题

• 拜占庭将军问题是由 Paxos 算法作者莱斯利·兰伯特提出的点对点通信中的基本问题。该
  问题要说明的含义是，在不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所
  以，Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传
  递的消息是不会被篡改的。
• 一般情况下，分布式系统中各个节点间采用两种通讯模型：共享内存（Shared Memory）、
  消息传递（Messages Passing）。而 Paxos 是基于消息传递通讯模型的。

算法描述 三种角色

在 Paxos 算法中有三种角色，分别具有三种不同的行为。但很多时候，一个进程可能同
时充当着多种角色。

• Proposer：提案者，提议者，proposal 的提议者
• Acceptor：表决者
• Learners：学习者

Paxos 算法的一致性

Paxos 算法的一致性主要体现在以下几点：

• 每个提议者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号 N，
  即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案。
• 每个表决者在 accept 某提案后，会将该提案的编号 N 记录在本地，这样每个表决者中
  保存的已经被 accept 的提案中会存在一个编号最大的提案，其编号假设为 maxN。每个
  表决者仅会 accept 编号大于自己本地 maxN 的提案。
• 在众多提案中最终只能有一个提案被选定。
• 一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。
• 没有提案被提出则不会有提案被选定

算法过程描述

Paxos 算法的执行过程划分为两个阶段：准备阶段 prepare 与接受阶段 accept

• prepare 阶段

1. 提议者(Proposer)准备提交一个编号为 N 的提议，于是其首先向所有表决者(Acceptor)发送 prepare(N)请求，用于试探集群是否支持该编号的提议。
2. 每个表决者(Acceptor)中都保存着自己曾经 accept 过的提议中的最大编号 maxN。当一个
   表决者接收到其它主机发送来的 prepare(N)请求时，其会比较 N 与 maxN 的值。有以下
   几种情况：
   1. 若 N 小于 maxN，则说明该提议已过时，当前表决者采取不回应或回应 Error 的方
      式来拒绝该 prepare 请求；
   2. 若 N 大于 maxN，则说明该提议是可以接受的，当前表决者会首先将该 N 记录下来，并将其曾经已经 accept 的编号最大的提案 Proposal(myid,maxN,value)反馈给提议者，以向提议者展示自己支持的提案意愿。其中第一个参数 myid 表示表决者 Acceptor的标识 id，第二个参数表示其曾接受的提案的最大编号 maxN，第三个参数表示该提案的真正内容 value。当然，若当前表决者还未曾 accept 过任何提议，则会将Proposal(myid,null,null)反馈给提议者。
   3. 在 prepare 阶段 N 不可能等于 maxN。这是由 N 的生成机制决定的。要获得 N 的值，
      其必定会在原来数值的基础上采用同步锁方式增一。

• accept 阶段

1. 当提议者(Proposer)发出 prepare(N)后，若收到了超过半数的表决者(Accepter)的反馈，
   那么该提议者就会将其真正的提案 Proposal(myid,N,value)发送给所有的表决者。
2. 当表决者(Acceptor)接收到提议者发送的 Proposal(myid,N,value)提案后，会再次拿出自己
   曾经 accept 过的提议中的最大编号 maxN，或曾经记录下的 prepare 的最大编号，让 N
   与它们进行比较，若 N 大于等于这两个编号，则当前表决者 accept 该提案，并反馈给
   提议者。若 N 小于这两个编号，则表决者采取不回应或回应 Error 的方式来拒绝该提议。
3. 若提议者没有接收到超过半数的表决者的 accept 反馈，则重新进入 prepare 阶段，递增
   提案号，重新提出 prepare 请求。若提议者接收到的反馈数量超过了半数，则其会向外
   广播两类信息：
   1.向曾 accept 其提案的表决者发送“可执行数据同步信号”，即让它们执行其曾接收
   到的提案；
   2.向未曾向其发送 accept 反馈的表决者发送“提案 + 可执行数据同步信号”，即让
   它们接受到该提案后马上执行。

扩展

Paxos 算法存在“活锁问题”，Fast Paxos 算法对 Paxos 算法进行了改进：其只允许一个进程处理写请求，解决了活锁问题。