Quorum 机制

允许不追求系统内所有节点在任何情况下数据状态都一致，而是“少数服从多数”原则，系统中过半节点完成转换，就认为数据变化已经被正确地存储在系统当中。

Paxos

前提及目标

Paxos 算法的目标是让城邦能够在每一位居民都不承诺一定会及时参与的情况下，依然可以按照少数服从多数的原则，最终达成一致意见。
Paxos 不考虑 拜占庭将军 问题，即假设信息可能丢失或延迟，但不会被错误传递。

算法流程

节点分类

• 提案节点：Proposer，对某个值进行设置操作的节点，这个行为被称之为提案，一旦设置成功则不丢失不可变。Paxos 是典型的基于操作转移模型而非状态转移模型来设计的算法，因此这里设置值不是变量赋值，而是操作日志记录。
• 决策节点：Acceptor，应答提案的节点，决定该提案是否可被投票及批准。提案批准后意味着值不可修改不会丢失，且最终所有节点均会接受它。决策节点通常被设置为奇数个。
• 记录节点：Learner，不参与提案和决策，单纯学习已经达成共识的提案，如少数派节点从网络分区中恢复时，将会进入这种状态。

机制

• 分布式环境中的锁必须是可抢占的，以避免一个节点在取得锁之后，在释放锁之前发生崩溃失联，导致整个操作被无限期的等待所阻塞。
• 两个承诺：
  • 承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求。
  • 承诺不会再接受提案 ID 小于 n 的 Accept 请求。
• 一个应答：
  • 当每一个决策节点收到 Accept 请求时，都会在不违背以前作出的承诺的前提下，接收并持久化对当前提案 ID 和提案附带的值。如果违反此前做出的承诺，即收到的提案 ID 并不是决策节点收到过的最大的，那允许直接对此 Accept 请求不予理会。

Basic Paxos 缺陷

• 只能对单个值形成决议。
• 决议形成至少需要两次网络请求和应答（准备和批准阶段各一次）。
• 高并发情况下产生较大的网络开销。
• 两个提案节点交替使用更大的提案 ID 使准备阶段成功，批准阶段失败，可能形成活锁，需要引入随机超时时间。

Multi Paxos