Paxos 算法，“when it is presented in plain English, it is very simple！”, 所以当以简单的中文呈现时，它也是非常地简单！
问题：当多个进程（proposer）同时想修改数据库（acceptor）中的一条记录时，同时通知那些需要了解更新的程序（learner），那么如何决定使用哪个进程的值进行更新呢？这时需要提出一个算法来解决这个问题，这个算法应当满足于下列条件：
1. 仅有一个被提议的值可以被选中。
2. 仅有一个值被选中
3. 一个进程不可能学习到一个被选中的值，除非这个值真的被选中。
Proposer、Acceptor和learner的具有以下性质：
1. 以任意的速度处理事务，可能失败并停止，也可能重启。以内所有的进程可能在一个值被选出后失败并重启，那么失败重启前已知的信息需要被保存，使得在重启之后仍保留之前已知的信息。
2. 消息传递的时间可能很长，消息可能被重复发送，但是消息的内容不会被篡改。
其实Paxos可以简单的分成两个阶段：
Phase 1：
(1）一个proposer选择一个编号n，并发送一个携带该编号的prepare request给大多数的acceptor；
(2) 当一个acceptor接收到一个prepare request，如果n大于之前已经恢复过的所有prepare
request中的编号，那么acceptor将回复这个prepare request（带上承诺：不再接受编号小于n的prepare
request，和，当前已经接受的编号最高的proposal的信息）给这个proposer（如果这个acceptor之前确实回复过这样的prepare
request，如果这个acceptor第一次被prepare request，那么其承诺：不再接受编号小于n的prepare
request，并回复一个空给proposer）。
Phase 2：
（1）如果一个proposer收到了来自大多数的acceptorprepare
request的回复，那么其将再次发送一个accept
request给这些acceptor（这儿又说回复相同的acceptor）带上编号n和value
v。这里的v时根据acceptor对prepare
request的回复消息来定的，如果回复消息中有前一个proposal已经提出的value，那么v就等于之前的value，否则这个proposer可以自己确定想要的value。
（2）如果一个acceptor收到了一个编号为n的accept request，除非在此之前其又接受了一个编号比n大的新的proposal，否则，这个acceptor将接受这个accept request。
一个proposer可以发出多个proposal，只要遵守上述的协议。一个proposer也可以在任何时候放弃自己的请求。从性能方面来考虑的话，如果一个acceptor接受了一个编号较高的新的proposal后，它应该通知之前回复过的proposer一遍这个proposer能够及时放弃后续操作而避免性能损失。这里仅仅是一个性能优化方面的考虑，不涉及到正确性问题。
2.3 学习一个被选中的value
一个learner如果想要
学习被选中的value的话，那么其就要去查询被大多数acceptor接受的proposal。最简单的做法就是，每当一个acceptor接受了一个新的proposal后就主动将该信息发送给所有的learner。这种方法能够保证所有的learner及时的更新被选中的value，但是会导致性能上的问题，因为这个方法在更新learner的知识时候需要的消息发送条数为：acceptor的个数
* learner的个数。
前面的非拜占庭消息发送模型保证了一个learner可以从其它的learner处学习某个被选中的value。那么一个acceptor在接受一个proposal后仅仅需要通知其中一个不同的learner就可以，其它的learner可以从这个learner处学习到。但是这优惠导致一个问题，如果这个learner在传播新学到的value之前挂掉的话，那么这个心value就无法被学习了。
同样，那就折中考虑吧，选择更新部分learner，这里就要在具体实现的时候综合考虑性能和一致性之间的平衡问题了。
两个重要的问题：
1. 为什么acceptor需要保证不接受编号较小的proposal？
为了保证编号能够一直增加，并且编号大的才能具有写入的权利，就像是排队买票一样。
2. proposer如何学习已经被accepted的proposal？
proposer在prepare request的回复消息中获取当前被接受的proposal的信息。
网友评论