Paxos算法

发表于 | 评论数： | 阅读次数：

前言

本文以维基百科的定义为基础，做了一些改动，增加了场景描述。

Paxos算法是莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的共识（consensus）算法。

扩展：注意共识算法和一致性算法是不同的，线性一致性(Linearizability)，或称原子一致性或严格一致性指的是程序在执行的历史中在存在可线性化点P的执行模型，
这意味着一个操作将在程序的调用和返回之间的某个点P起作用。这里“起作用”的意思是被系统中并发运行的所有其他线程所感知。

词典

参与角色

  1. 提议者（proposers）
  2. 接受者（acceptors）
  3. 学习者（learners，允许身兼数职）

动作

  1. 提案（proposal）:由一个提议者发起，包括提案编号和提案value
  2. 接受提案（accept）:接受者收到提案之后可以批准提案
  3. 批准（chosen）:多数派（majority）接受者**接受提案**（accept），则提案获得批准
  4. 决议（value）:被批准的提案value

正常流程

通过正常流程学习Paxos算法，首先提出基础算法，之后会提出潜在问题，进行进一步完善

基础协议

  1. 决议只有在被提议者提出后才能被批准（未经批准的决议称为’提案‘）；
  2. 在一次Paxos算法的执行实例中，只批准一个决议；
  3. 学习者只能获得被批准的决议。

完善协议

为了满足基础协议的目标2，只批准一个决议，增加约束P1:接受者必须对第一次收到的提案进行接受提案处理，
这个约束并不能使得目标2可以完成，因为存在一个场景，即有偶数个接受者，其中一半接受提案A，另一边接受提案B。

仔细阅读目标2，只要提案value是相同的，就可以批准。为了避免无法区分两个提案value相同的提案，
在同一次Paxos算法的执行实例中通过了两者，增加约束P2:一旦一个具有value v的提案被批准，那么之后批准的提案必须具有value v。
发生场景是，提议A和提议B的提案value都是v，同一个接受者如果接受了提案A，也就可以接受提案B,因为他们的提案value相同，
此时需要提案携带顺序关系，比如分配协议编号，根据编号大小确定提议顺序，区分两次提案。

通过P1和P2约束，我们完成了对目标2的保证。

P2约束是保证两个提案会被分配到两次批准过程中，我们可以对P2约束再进行一次增强，在接受提案方面进行控制。
因为如果第一个提案被批准，则多数派（majority）接受者已经接受了决议，
增加约束P2a:一旦一个具有value v的提案被批准，那么之后任何接受者再次接受提案必须具有value v。

如果一个提议者和接受者在休眠过程中，系统执行了一次或多次批准，当他们被唤醒之后，参与到新一轮的Paxos算法的执行实例中，
此时提议者无法按照束P2a要求，携带上次的决议，而接受者在新一轮的Paxos算法的执行实例里，按照约束P1需要接收第一个提案，
按照照束P2a需要拒绝无法携带上次决议内容的提案，此时产生矛盾，针对P2a进行增强，
增加约束P2b:一旦一个具有value v 的提案被批准，那么以后任何提议者提出的提案必须具有value v。
P2b是对P2a更强的约束，在提出提案阶段就需要携带value v了。

那么如何让一个经历过休眠的提议者能够携带value v呢，
增加约束P2c:如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有接受提案编号小于n
的任何提案，要么他们已经接受提案的所有编号小于n的提案中编号最大的那个提案具有value v。
这里需要理解的是，一个提案被批准，是通过一个多数派来接受提案从而完成的，这里记录为编号n对应多数派c，
接收的是value v，而任意两个多数派之间必定会有至少一个公共成员，因为两个多数派都超过了半数嘛，在这个约束下，
只要提议者和一个多数派进行沟通获取上一次批准的提案，就可以找到P2b约束中要求的value v。

如果一个接受者没有进行过任何批准，提议者发起编号为n的提案，但是在投票之前又接收了（n-1）编号的提案，
如果（n-1）编号和n编号的提案value不同，则违反了约束P2c。
增加约束P1a:当且仅当接受者没有回应过编号大于n的提案时，可以接受提案编号为n的提案。
这样在并发情况下接受提案的时候，可以保证没有回应过编号大于当前编号的提案。

约束总结

最后完整记录下约束，来检查一下自己是否理解了约束目的吧：

1
2
3
4
5
6
P1：一个 acceptor 必须接受（accept）第一次收到的提案。
P2：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v。
P2a：一旦一个具有 value v 的提案被批准（chosen），那么之后任何 acceptor 再次接受（accept）的提案必须具有 value v。
P2b：一旦一个具有 value v 的提案被批准（chosen），那么以后任何 proposer 提出的提案必须具有 value v。
P2c：如果一个编号为 n 的提案具有 value v，那么存在一个多数派，要么他们中所有人都没有接受（accept）编号小于 n 
的任何提案，要么他们已经接受（accept）的所有编号小于 n 的提案中编号最大的那个提案具有 value v。

正常流程总结

  1. 提案
    1. 提议者指定提案编号n和提案value，发送给一个接受者多数派
    2. 接受者收到提案后，如果编号n大于所有已经回复的提案编号（代表已经接受提案），将上次接受的提案内容回复给提议者，并承诺不再接受编号n以下的提案
  2. 批准
    1. 当一个提议者接收到多数接受者接受提案的响应时，进入批准阶段，提议者向接受提案的接受者发送请求，根据编号n和P2c约束的value v，如果没有接受的value则可以自定义
    2. 如果接受者不违反对其他提议者的承诺，则接受提议