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 算法来实现共识达成, 就不可避免会存在如下问题:

  1. 进程可能会慢, 被杀死或者重启
  2. 消息可能会丢失, 延迟或者重复

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