分布式系统大纲指南之共识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影响

Raft

  • Ongaro & Ousterhout 2014 - In Search of an Understandable Consensus Algorithm
  • 维持一个复制的状态机切换事件日志
  • 能够实现任意顺序和线性化的状态机
    • RethinkDB
    • etcd
    • Consul

下篇

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

分布式系统Paxos算法

分布式系统Raft算法

 

 

猜你喜欢