Paxos算法是Leslie Lamport在1990年提出的，是一种基于消息传递具有高度容错的
共识算法。为了方便描述，便于理解，Lamport创造出了一个虚拟希腊城邦，命名为Paxos，这个民主的城邦日常会有很多的决议提出，为了让大家高效的达成一致，Lamport制定的决议条文，就是该算法本尊了。
来自网络
为什么要强调共识(consensus)，因为Paxos常被误认为是一致性(consistency)算法，两者是不一样的。中文里会说“达成共识”和“达成一致”，感觉一样样的。但从英文上看，就是两个词，那如何帮助理解呢？举个例子：
“我们中午去吃啥？”
“米饭”
“好”
这时候大家对中午吃什么达成了共识 - “米饭”。最后小伙伴们都很开心的去吃饭了，可能你去了这家餐馆，她去了另一家饭店，大家都遵守承诺，中午吃了米饭，这个最终的结果是一致的。
把上面这个例子转换成计算机领域的实际用例有：分布式日志系统。分布式日志系统要求所有的备份都是一致的，并且日志是有序的。这时不同的备份机收到不同的日志写请求，他们分别都对第三条日志该写什么，提出自己的写请求，假设是logA, logB。最后备份机们商量后，决定大家都在自己的第三条日志处写上logB。那么这里的共识就是“第三条写logB”，但怎么写，何时写，就不在Paxos算法的范畴里了，而是一致性的范畴了。
Paxos
将上面的例子用Paxos来表示，如下图所示：
在Paxos城邦里，存在二种角色：
- 议员，就像咱们的人大代表：
- 提议者(Proposer)：提出意见的议员，比如：我有一个大胆的想法
- 接收者(Acceptor)：收到这个提议的议员
- 学习者(Learner)，就像咱们普通大众，经过议员们讨论，是时候涨肉价了，普通大众表示情绪稳定，知道了就行
结合上面流程，来解释一下Paxos算法：
- 做为提议者，我有一个想法，我想提议大家中午吃米饭
- 我正式发出提议 - PREPARE(ID:1)，这个id是递增，并全局唯一的，从这个时候开始了Paxos的一个回合。ID可能实现的机制有：nanosecond-level timestamp
- 提议发出后，做为接收者，我不仅需要响应说我接收到了，还需要保证我不会接受其它PREPARE ID低于1的提议 - PROMISE(ID:1) ，也就是说大于1的我是会接受的，秉着契约精神，一旦PROMISE，是不能反悔的。
- 作为提议者，当接收到超过一半的PROMISE后，意味着共识已经达成。如何定义“超过一半”，通常的算法是：majority(m = h + 1, all = 2h +1)。这时提议者将发出请求，共识已经达成，这轮共识的结果是吃米饭：PROPOSE(ID:1, Value:Rice)。
- 作为接收者，收到PROPOSE后，会根据自己的PROMISE进行接收，基于之前没有接收过别的PROPOSE - ACCEPTED(ID:1, Value: Rice)，因为一旦PROMISE是不能反悔的。同时，也会告知所有的学习者LEARNER。
以上是只有一个提议者的情况，并且所有接收者之前都没有接收过其它的提议。那么接下来我们看看，如果有多个提议者时，也就是发生竞争时，会发生什么：
- 假设在提议Rice这前，就已经有另一个提议者提议吃Noodle了，不过因为网络原因，接受者们普遍先接收到提议Rice，这时当已经收到PREPARE(ID:1)的接收者，已经承诺不会再接收小于ID:1的PREPARE请求，那么(6)PREPARE(ID:0)抵达时，会被忽略掉(7)。
- 当提议者的提议超时时，提议者会自动按照递增的规则生成新的提议，如(8)PREPARE(ID:2)
- 当发出新的提议抵达接收者时，根据约定，这次的ID:2大于之前承诺过的ID，那么这一次将会接受该PREPARE，会给出自己的PROMISE，不过这一次会和之前的不同，会带上已经接收过的提议信息：(9)PROMISE(ID:2, accepted-id:1, value:Rice)。告新的诉提议者，这一轮我已经接受了其它人的提议。需要多个Paxos回合，达到一轮共识。
- 当提议者接收到带有值的PROMISE后，会意识到，共识已经达成，因为只有超过半数，才会发生这种情况。接收者会放弃自己原先的提议，广播这个共识(10)PROPOSE(ID:2, Value:Rice)。
从以上例子中可以看出，Paxos共识算法的关键点有：
- 提议的ID是唯一，并递增的：大家都只响应最新的提议，也就是大于自己PROMISE过的值
- 绝大多数同意，就表明协议已经达成
- 一旦PROMISE过，就不能反悔了，得有契约精神
也因为以上规则，会出现如下冲突的情况：
也就是当提议者都在提议，并且条件差不多时，比如，都在同一机房。当提议者发出提议后，接收者也都PROMISE了，当还在等待绝大多数PROMISE的过程中，另一位提议者又发出了自己的请求，这时接收者因为也还没等来接收的值，就会返回PROMISE并且没有接收值。这时，如果先前的接收者收到了足够多的PROMISE后，发出的PROPOSE也会被接收者拒绝或者忽略掉，因为有保证过只处理较新的ID，这时就会导致提议者发出更新的请求，出现竞争。通常的做法是给到提议者，一定的时间(BACKOFF)去接收足够的PROMISE。
Paxos共识算法确实就这么简单，在后续的系列文章中，我们可以看看，以Paxos算法为基础，进化来的其它算法，以及各自的适用场景。
全文完
