paxos
声明：
- 本文思路完成模仿 朱一聪 老师的的 如何浅显易懂地解说 Paxos 而得，版权属于 朱一聪 老师 。只是为了自己理解更加透彻，又重新推导了一下而已。文章发出已经获得 朱一聪 老师的同意。
- 本文最后结论完全引用 Paxos Made Simple 中文翻译版
- 学习 paxos 请优先选择 Paxos Made Simple 和 Paxos lecture，不要选择本文。本文仅能起到引导思路的作用
- 文章肯定有不严谨，推导不严谨的地方，欢迎讨论。
背景：
在一个高可用分布式存储系统中，如果只使用一台机器，只要这台机器故障，系统就会崩溃。所以肯定需要多台机器，但是由于网络延迟，机器崩溃等原因，多台机器对于数据很难达成共识（Consensus not Consistency）。而 paxos 协议就是用来使各个机器达成共识的协议。
如何理解共识（Consensus）：
共识就是在一个或多个进程提议了一个值应当是什么后，使系统中所有进程对这个值达成一致意见。但是必须明确：在一个完全异步且可能出现任何故障的系统中，不存在一个算法可以确保达到共识（FLP Impossibility）。
前提:
需要保证安全性：
- 只有被提出的提案才能被选定
- 只能有一个值被选定
- 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个
可能出现的场景
- 进程之间的通信可能出现故障
- 每个进程都可能提出不同的值
- 每个进程也可能随时崩溃
- 进程之间传输的数据不会篡改
达成共识的条件
N 个进程中大多数（超过一半）进程都选定了同一个值
推导流程
假设存在三个进程 p1 p2 p3，共同决定 v 的值
1.1 每个进程只接受收到的第一个提案
场景 1.1.1
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 无
假设是 p1 的 proposal 优先到达 p3，p2 的 proposal 在到达 p3 时会被拒绝，系统就 v = a 达成了共识，反之如果 p2 的 proposal 优先到达，系统会就 v = b 达成共识。
场景 1.1.2
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: v = c
这样每个机器只能接受自己机器上的 proposal，对于 v 的值就永远不能达成共识了。
结论 1.1：
- 进程必须能够多次改写 v 的值，否则可能永远达不成共识
- 进程必须接受第一个 proposal，否则可能永远达不成共识（系统只有一个提案时）
1.2 每个进程只接受 proposal_id 大的提案
根据 1.1 的结论，进程必须接受第一个 proposal， 所以需要一种拒绝策略或者修正后到达的 proposal 的 value 我们需要额外的信息作为依据来完成。
- 我们得到哪些信息呢？
提出 proposal 进程的标识 process_id，当前进行到轮次 round_number（每个进程自增） - 这些信息有什么用？
这两个信息加在一起标识唯一的 proposal
暂定 proposal_id = round_number + process_id - 如何更新 proposal_id？
每个 process 的 proposal_id = max(proposal_id, a_proposal_id)
场景 1.2.1
假设 p1_proposal_id > p2_proposal_id
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 无
如果 p1 proposal 先到达 p3 ，p2 后到达，会形成
p1 proposal：v = a
p2 proposal: v = a
p3 proposal: v = a
系统就 v = a 达成共识。
场景 1.2.2
如果 p2 proposal 先到达 p3 , p1 后到达，p3 会先接受 p2 proposal，形成
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: v = b
系统就 v = b 达成共识，因为 p1 proposal 也已经发出，接着又会形成
p1 proposal：v = a
p2 proposal: v = a
p3 proposal: v = a
系统又就 v = a 达成了共识。
在这个策略中，有两个值先后达成共识，不满足安全性。
结论 1.2：
按照现有 1.2 策略存在proposal id 小 proposal 先到达，系统多次就不同的值达成共识的问题。从如下几个角度思考解决此问题
- p3 可以拒绝 p2 proposal(p2 proposal 先到达 p3，p2_proposal_id < p1_proposal_id )
- 限制 p1 提出的 proposal
1.3 p3 可以拒绝 p2 proposal 角度
- 发送带有 proposal_id PreProposal,
- 接收到 PreProposal 的进程，根据 proposal_id = max(proposal_id, accept_proposal_id) 进行更新
- 进程发送 proposal
- 每个进程只接受 proposal_id 大的 proposal
假设 p1_proposal_id > p2_proposal_id
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 无
场景 1.3.1
- p1_PreProposal 携带 p1_proposal_id 到达 p3
- P3 更新 p3_proposal_id 为 p1_proposal_id, P2 更新 p2_proposal_id 为 p1_proposal_id
- p2_PreProposal 携带 p2_proposal_id 到达，p2_proposal_id < p1_proposal_id，被拒绝。
- p1_proposal (v = a)到达 p2, p3
- 此时系统就 v = a 达成共识
- p1: v = a
- p2: v = a
- p3: v = a
场景 1.3.2
- p2_PreProposal 携带 p2_proposal_id 进行广播，到达 p3
- P3 更新 p3_proposal_id 为 p2_proposal_id
- p2_proposal (v = b)到达 p3，系统此时会就 v = b 达成共识
- p1: v = a
- p2: v = b
- p3: v = b
- p1_PreProposal 携带 p1_proposal_id 进行广播，到达 p2, p3, p2_proposal_id < p1_proposal_id，p2 p3 更新 proposal_id 为 p1_proposal_id
- p1_proposal (v = a)到达 p2, p3
- 此时系统就 v = a 达成共识
- p1: v = a
- p2: v = a
- p3: v = a
结论 1.3:
1.3 策略解决了一部分问题，但是还是依赖消息到达的先后顺序。在某些条件下还是不能保证安全性。
1.4 限制 p1 提出的 proposal
现在已知 process_id round_number，还能得到哪些信息？
按照 1.3 的策略，我们只是更新了接受 pre_proposal 的 accept_process 的 proposal_id 为较大的 proposal_id，并没有回复给发送 pre_propoal 的 send_process 任何消息。是不是可以把 accept_process 已经获得的提案的 proposal_id 和 proposal 这样是不是限制 send_process 接下来发送的 proposal ？现在模拟一下流程，看看能否解决 1.3 中存在的问题。
- 发送带有 proposal_id 的 PreProposal
- 接收到 PreProposal 的进程，根据 proposal_id = max(proposal_id, accept_proposal_id) 进行更新，并回复当前进程已经接收到的 proposal_id
- 进程发送 proposal
- 每个进程只接受 proposal_id 大的 proposal
假设 p1_proposal_id > p2_proposal_id
p1 proposal：v = a
p2 proposal: v = b
p3 proposal: 无
场景 1.4.1
- p2_PreProposal 携带 p2_proposal_id 进行广播，到达 p3
- P3 更新 p3_proposal_id 为 p2_proposal_id
- P3 给 P2回复 (p2_proposal_id, v=NULL)
- p2_proposal (v = b)到达 p3，系统此时会就 v = b 达成共识
- p1: v = a
- p2: v = b
- p3: v = b
- p1_PreProposal 携带 p1_proposal_id 进行广播，到达 p2, p3, p2_proposal_id < p1_proposal_id，p2 p3 更新 proposal_id 为 p1_proposal_id
- P3 回复 P1 (p2_proposal_id, v=b)
- P1 发现 P3 已经接受了 v = b，把自己的提案 v = a 修改成 v = b
- p1_proposal (v = b)到达 p2, p3
- 此时系统还是就 v = b 达成共识
- p1: v = b
- p2: v = b
- p3: v = b
问题得到了解决。
上文所有的推导，全部来源于三个进程，看似问题已经解决。但是这个流程能否一般化，应用于 N 个进程呢？提案数从 2 到 N 呢？
泛化推导，
场景 1.5 进程数从 3 到 N
Pi 进程集合：提出 PreProposal-i，Proposal-i(v = a)
Qi 进程集合：接受了 Proposal-i 的超半数进程
Pj 进程集合：提出 PreProposal-j，Proposal-j(v = b)
Qj 进程集合：接受了 Proposal-j 的超半数进程
Pk 进程集合：Qi 和 Qj 的进程集合交集
只要 Pk 能够拒绝 Proposal-i 和 Proposal-j 的一个就是安全的
每个 Proposal-j-id < Proposal-i-id
- Proposal-j 到达部分进程，此时系统未达成共识
- PreProposal-i 到达部分进程，此时系统未达成共识
- 所有接收到 PreProposal-i 的进程回复（Proposal-j-id， v = b）或者 （NULL， NULL） 给 Pi
- Pi 接受到（Proposal-j-id，v = b），将 Proposal-i 原先的 v = a 修改成 v = b，然后进行广播。
- 系统就 v = b 达成共识。
场景 1.6 不同的 proposal 由 2 到 N
假设 j - i = N，b - a = N
Pi Pi+1 ... Pi+N-1 Pj 每个进程组都会提出 Proposal(v = a, a+1, .. a+N-1, b) Proposal_id 大小顺序相反
Qi -> Qj 与 Pi 相对
Pk 是收到了很多不同提案的进程的集合，但是一直没有达成共识。
- Proposal-i+1 Proposal-i+2 到达 Pk，系统并没有达成共识。
- PreProposal-j 发出到达部分进程
- 接收到 PreProposal-j 的进程选择 [(Proposal-i+1-id, v = a + 1), (Proposal-i+2-id, v = a + 2)] 其中的一个或者两个一起回复给 Pj
- Pj 应该选择哪个 v 值修改自己的 proposal 呢
- 回顾前边的逻辑，每个进程会拒绝 Proposal-id 较小的提案，Proposal-i+1-id > Proposal-i+2-id
- Proposal-i+1-id 相比 Proposal-i+2-id 的提案肯定先到 Pk 的，系统还有一部分进程没有接收到 (Proposal-i+1-id, v = a + 1)，没有就 (Proposal-i+1-id, v = a + 1) 形成共识
- 假设 Pj 选择 proposal_id 较小的 proposal ，那么会选择 （Proposal-i+2-id, v = a + 2) ，在 Pj 发出 （Proposal-j, v = a + 2) 之前，没有收到 (Proposal-i+1-id, v = a + 1) 的进程可能恰好收到了，系统就 v = a + 1 达成了共识。此后（Proposal-j, v = a + 2) 达到了， 系统又 v = a + 2 达成的共识。系统两次达成共识，存在问题。
- 假设 Pj 选择 proposal_id 较大的 proposal，那么会选择 （Proposal-i+1-id, v = a + 1) ，在 Pj 发出 （Proposal-j, v = a + 1) 之前，没有收到 (Proposal-i+1-id, v = a + 1) 的进程可能恰好收到了，系统就 v = a + 1 达成了共识。此后（Proposal-j, v = a + 2) 达到了，还是 v = a + 1。不存在问题。
- 系统选择 proposal_id 较大的修改依据
- Pj 选择 proposal_id 较大的 proposal，修改 v = a + 1，并发出 （Proposal-j, v = a + 2）
- 系统就 v = a + 2 达成共识
不能覆盖的场景
如果每次 proposal 被接受之前，先接受了携带较大 proposal-id 的 PreProposal，这样每次都会拒绝即将成功的达成共识的 proposal 系统每次都不会达成共识。这个场景可以通过不断重试解决。
paxos
Proposer： 发起提案的进程
Acceptor： 接受题提案的进程
一个进程可能充当多个角色
Phase 1:
- Proposer 选择一个提案编号 n，然后向 Acceptors 的某个 majority 集合的成员发送编号为 n 的prepare请求。
- 如果一个Acceptor收到一个编号为 n 的prepare请求，且 n 大于它已经响应的所有prepare请求的编号，那么它就会保证不会再通过(accept)任何编号小于 n 的提案，同时将它已经通过的最大编号的提案(如果存在的话)作为响应。
Phase 2
- 如果 Proposer 收到来自半数以上的 Acceptor 对于它的 prepare 请求(编号为 n)的响应，那么它就会发送一个针对编号为 n ，value 值为 v 的提案的 accept 请求给 Acceptors，在这里 v 是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
- 如果 Acceptor 收到一个针对编号 n 的提案的accept请求，只要它还未对编号大于 n 的 prepare 请求作出响应，它就可以通过这个提案。
