paxos协议_从paxos到zookeeper_raft算法paxos算法(7)

如果仅有一个Master，宕机时选举的结果根本就无法被learn学习, 也就是说，Leader选举机制更多的是保证异常情况下算法的正确性，虚惊一场，paxos原来不是Master-Master。

在此，我们第一次提到了"learn"这个角色，在value被选择后，learn的工作就是去学习最终决议，学习也是算法的一部分，同样要在任何情况下保证正确性，后续的主要工作将围绕“learn”展开。

Paxos与二段提交

Google的人曾说，其他分布式算法都是paxos的简化形式。

假如leader只提交一个proposal给acceptor的简单情况：

发送prepared给多数派acceptor

接收多数派的响应

发送accept给多数派使其批准对应的value

其实就是一个二段提交问题，整个paxos算法可以看作是多个交叉执行而又相互影响的二段提交算法。

如何选出多个Value

Paxos算法描述的过程是发生在“一次选举”的过程中，这个在前面也提到过，实际Paxos算法执行是一轮接一轮，每轮还有个专有称呼：instance（翻译成中文有点怪），每instance都选出一个唯一的value。

在每instanc中，一个proposal可能会被提交多次才能获得acceptor的批准，一般做法是，如果acceptor没有接受，那 proposer就提高编号继续提交。如果acceptor还没有选择（多数派批准）一个value，proposer可以任意提交value，否则就必 须提交意见选择的，这个在P2c 中已经说明过。

Paxos中还有一个要提一下的问题是，在prepare阶段提交的是proposal的编号，之后再决定提交哪个value，就是value与编号是分开提交的，这与我们的思维有点不一样。

3. 学习决议

在决议被最终选出后，最重要的事情就是让learn学习决议，学习决议就是决定如何处理决议。

在学习的过程中，遇到的第一个问题就是learn如何知道决议已被选出，简单的做法就是每个批准proposal的acceptor都告诉每个需要 学习的learn，但这样的通信量非常大。简单的优化方式就是只告诉一个learn，让这个唯一learn通知其他learn，这样做的好是减少了通信 量，但坏处同样明显，会形成单点；当然折中方案是告诉一小部分learn，复杂性是learn之间又会有分布式的问题。

无论如何，有一点是肯定的，就是每个acceptor都要向learn发送批准的消息，如果不是这样的话，learn就无法知道这个value是否是最终决议，因此优化的问题缩减为一个还是多个learn的问题。

能否像proposer的Leader一样为learn也选个Leader？因为每个acceptor都有持久存储，这样做是可以的，但会把系统搞的越来越复杂，之后我们还会详细讨论这个问题。

Learn学习决议时，还有一个重要的问题就是要按顺序学习，之前的选举算法花费很多精力就是为了给所有的proposal全局编号，目的是能被按 顺序使用。但learn收到的决议的顺序可能不不一致，有可能先收到10号决议，但9号还未到，这时必须等9号到达，或主动向acceptor去请求9号 决议，之后才能学习9号、10号决议。

4. 异常情况、持久存储

在算法执行的过程中会产生很多的异常情况，比如proposer宕机、acceptor在接收proposal后宕机，proposer接收消息后宕机，acceptor在accept后宕机，learn宕机等，甚至还有存储失败等诸多错误。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29826-7.html