分布式系统大纲指南之共识Consensus算法

上篇

　　前面章节我们讨论了如何秉承尽量回避共识一致性问题，但是现实中一些共识问题是回避不了的，比如实现串行化Serializability和线性化 linearizability就需要共识一致性, 为达成共识性，我们需要通过Paxos, ZAB, VR, 或Raft等算法获得，本篇介绍这几个算法，首先我们看一下共识的问题：

共识问题
- 三个处理服务器类型
  - 提议者: 提议一个值
  - 接受者: 选择一个值
  - 学习者: 读取被选中的值
- 接受者类别
  - 总共有N个接收者
  - F代表为允许失败的正常接收者
  - M代表为恶意的接收者
- 三条不变性定律:
  - 非琐碎: 只有被提议的值能被学习
  - 安全: 只有最多的值能被学习
  - 活跃度: 假设有一个提议者p, 一个学习者l, 和N-F种接受者集合，这些都是无故障的能彼此通讯，如果p提议了一个值，I最终会学习一个值。
下面几个系统整体等同于共识一致性问题
- 所以我们在这里的任何证明都适用于这些系统：
- 锁服务
- 有次序的日志
- 复制状态机
FLP理论告诉我们在异步网络中实现共识一致性是不可能的
- 在正确时间杀死一个处理服务器你能打断任何共识算法。
- 真实也许不是你想得那么坏
- 现实中，网络能达成共识的频度反而是经常且完全足够的。
- 更有甚者， FLP假设确定性处理服务器
  - 真实计算机都不是确定性的
  - Ben-Or 1983: "Another Advantage of free choice"
    - 这篇文章认为非确定性算法也能达成共识
Lamport 2002: tight bounds for asynchronous consensus(异步一致严格的界限)
- 至少需要两个提议者和一个恶意提议者, 那么 N > 2F + M
  - 也就是说"需要有大多数"，能够实现民主选举，正常数目多于不正常数目。
- 两个提议者和一个恶意提议者情况下, 至少有两个消息会延迟学习一个建议值
下面是务实的可实现的
- 在一个稳定集群中，你只能得到一个往返与大多数节点之间的来回路径距离。
- 更多在集群切换期间

Paxos

Paxos是共识算法的金字标准
- Lamport 1970 - The Part Time Parliament
  - 描述的是一个虚构的希腊民主
- Lamport 2001 - Paxos Made Simple
  - 为实现容错分布式系统的Paxos算法被认为是难以理解的，也许是因为最初的表现形式是希腊语，让许多读者感到陌生。事实上，它是最简单和最明显的分布式算法…最后一节完整的解释了Paxos算法，因为它可能是最经常被引用的关于分布式系统[理论文章的主题。”
- Google 2007 - Paxos Made Live
  - 来自于google锁服务产品的Chubby
- Van Renesse 2011 - Paxos Made Moderately Complex
在独立提议上提供共识
典型以大多数选举人数部署, 5 或 7 个节点
几种优化变种：
- Multi-Paxos
- Fast Paxos
- Generalized Paxos
- 每个变种有不同偏重风格可以结合使用
已经应用的产品系统
- Chubby
- Cassandra
- Riak
- FoundationDB
- WANdisco SVN servers

ZAB

ZAB是Zookeeper原子广播协议
Junqueira, Reed, 和 Serafini 2011 - Zab: High-performance broadcast for primary-backup systems
区别于Paxos
提供顺序一致性 (线性化写, 滞后的有序读)
- 能提供ZK客户端需要快速本地读
- 但是也有一个同步SYNC命令用来保持实时本地更新
- (SYNC + op) 也允许线性化读
遵循大多数选举人数, 5 或 7 个节点

Viewstamped复制

表现为复制协议，其实也是共识算法
事务处理加入一个视图改变算法
大多数节点知道的值能保证活到将来
好像没有产品
沿着Paxos发展, 有点受Raft影响

分布式系统大纲指南之共识Consensus算法

Paxos

ZAB

Viewstamped复制

Raft

分布式系统的共识(consensus)算法比较

分布式系统Paxos算法

分布式系统Raft算法