# Paxos算法
解决分布式场景下的"一致性问题"的算法
# Basic Paxos
# 角色介绍
- Client：系统的外部角色，请求的发起人。像民众。
- Propser：接受Client的请求，向集群提出提议（propose），并在冲突发生时，起到冲突调节的作用。像议员，替民众提出议案。
- Acceptor（Voter）：提议投票和接收者，只有在形成法定人数(quorum)时，提议才会最终被接受。像国会。
- Learner：提议接受者，backup，备份，对集群一致性没什么影响。像记录员。
# 步骤
# 1a：Prepare
proposer提出一个提案，编号为N，N大于proposer之前提出的案件编号，请求acceptor的quorum接受
# 1b：Promise
如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝
# 2a：Accept
如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N和内容
# 2b：Accepted
如果此acceptor再次期间没有收到任何编号大于N的提案，则接受此案件的内容，否则忽略
# 看图说明
# 正常情况
# 部分节点失败，但是达到大多数
# Proposer失败
# 一个常见的问题——活锁
有时候出现这种情况：1号提案发出，acctepor通过1号提案，这时2号提案发出（一号提案内容还没到达），acctepor通过2号提案，这时1号提案内容到达，因此抛弃1号提案内容（1号提案发现发现自己被抛弃了，于是提3号提案过去），3号提案发出，acctepor通过3号提案，2号提案内容到达（发现自己被抛弃了，于是提4号提案过去），不断往复，于是无法真正接受某个提案的内容，只是在不断变换讨论哪个提案。
解决方案：就是给一个随机的时间，被占了后先等一等，不立即发送，然后在随机等一等。
其他问题：
- 难实现，角色太多了
- 2轮RPC，第一轮确定讨论几号提案，第二轮确定内容接不接受，效率低
- 活锁
# Multi Paxos
新概念，Leader：唯一的propser，所有的请求都经过此Leader
因此不会有人跟Leader去抢提交提案
这种方法需要首先竞选Leader，竞选后直接提交案件和内容，就不需要先问讨论几号提案了，如果Leader挂了就重新竞选Leader。
这种方法进一步减少了角色，进一步简化
例如上图中，3个Server，其中一个Leader，2个Slave