Paxos

Paxos 共识算法

在 90 年代 Lamport 大师提出了一种基于消息传递且具有高度容错特性的共识(consensus)算法

注意这里的共识算法并不是一致性算法 (consistency algo), 二者的区别在于:

一致性算法: 主要关注数据的一致性, 确保所有节点(node/replica)在某个时间点看到相同的数据状态;
- 副本之间看到的值是否一样
- 如何解决多个副本间的写入冲突(如 last-write-wins, vector clocks)
共识算法: 多个节点就某个单一值(如某次写入, 谁是leader)达成一致的过程
- 分布式系统中的节点就"某个值"进行投票与确认
- 通常用于领导选举, 分布式日志, 状态同步
- 如 Paxos, Raft, PBFT(Practicle Byzantine Fault Tolerance Algo)
- 共识算法是实现强一致性的一种机制, 但不是一致性算法的全部
  - 强一致性: 无论何时, 所有用户读取某个数据项时, 都能看到最后一次成功写入的值

分布式系统中的节点通信存在两种模型: 共享内存(Shared memory)和消息传递(Messages passing)

如果基于 Messages Passing 算法来实现共识达成, 就不可避免会存在如下问题:

而 Paxos 算法的设计目标就是解决上述两个情况下的问题, 即不考虑拜占庭问题中的信息篡改的攻击情况

Lamport虚拟了一个叫做Paxos的希腊城邦, 这个岛按照议会民主制的政治模式制订法律, 但是没有人愿意将自己的全部时间和精力放在这种事情上, 所以无论是议员, 议长或者传递纸条的服务员都不能承诺别人需要时一定会出现, 也无法承诺批准决议或者传递消息的时间

对应于分布式系统, 议员对应于各个节点, 制定的法律过程对应于系统的状态;各个节点需要尽量保持一致的状态, 对应各议员推进法律决议推进;议员和服务员的不确定性对应于节点和消息传递通道的不可靠性

首先将议员的角色分为 proposers, acceptors, 和 learners(允许身兼数职)

Proposers: 提议者, 提出新的值
Acceptors: 接受者, 接受提议者的提议, 如果超过半数的接受者 (majority) 接受了提议者的提议, 则该提议被认为是被接受的 (chosen)
Learner: 学习者, 学习被接受的提议

在角色的定义下, 我们对新值的修改流程也可以有如下的定义和约束: