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

但无论何种错误必须保证paxos算法的正确性，这就需要proposer、aceptor、learn都做能持久存储，以做到server”醒来“后仍能正确参与paxos处理。

propose该存储已提交的最大proposal编号、决议编号（instance id）

acceptor储已promise的最大编号；已accept的最大编号和value、决议编号

learn存储已学习过的决议和编号

以上就是paxos算法的大概介绍，目的是对paxos算法有粗略了解，知道算法解决什么问题、算法的角色及怎么产生的，还有就是算法执行的过程、核心所在及对容错处理的要求。

但仅根据上面的描述还很难翻译成一个可执行的算法程序，因为还有无限多的问题需要解决：

Leader选举算法

Leader宕机，但新的Leader还未选出，对系统会有什么影响

更多交叉在一起的错误发生，还能否保证算法的正确性

learn到达该怎么学习决议

instance no、proposal no是该维护在哪里？

性能

众多问题如雪片般飞来，待这些都逐一解决后才能讨论实现的问题。当然还有一个最重要的问题，paxos算法被证明是正确的，但程序如何能被证明是正确的？

前两篇Paxos算法的讨论，让我们对paxos算法的理论形成过程有了大概的了解，但距离其成为一个可执行的算法程序还有很长的路要走，原因是很 多的细节和错误未被考虑。Google Chubby的作者说，paxos算法实现起来远没有看起来简单，原因是paxos的容错仅限于server crash这一种情况，但在实际工程实现时要考虑磁盘损坏、文件损坏、Leader身份丢失等诸多的错误。

1. Paxos各角色的职能

在paxos算法中存在Client、Proposer、Proposer Leaer、Acceptor、Learn五种角色，可精简为三种主要角色：proposer、acceptor、learn。角色只是逻辑上存在的，在实际实现中，节点可以身。

在我们的讨论中，我们先假定没有Proposer Leader这一角色，在不考虑活锁的情况下，如果算法过程正确，那有Leader角色的算法过程肯定也正确。

除了五种角色，还有三个重要的概念：instance、proposal、value，分别代表：每次paxos选举过程、提案、提案的value

当然，还有4个关键过程：

(Phase1)：prepare

(Phase1)：prepare ack

(Phase2)：accept

(Phase2)：accept ack

对acceptor来说，还蕴含是着promise、accept、reject三个动作。

先上一幅图，更直观地对几种角色的职能加以了解（各角色的具体职能参考Lamport的论文就足够了）：

上图不是非常严格，仅为表现各角色之间的关系。

2. Proposer

在Proposer、Acceptor、Learn中均涉及到proposal的编号，该编号应该有proposer作出改变，对其他的角色是只读 的，这就保证了只有一个数据源。当多个proposer同时提交proposal时，必须保证各proposer的编号唯一、且可比较，具体做法之前已经 提到。这里还要强调一点的是，仅每个proposer按自己的规则提高编号是不够的，还必须了解“外面”的最大编号是多少，例如，P1、P2、P3（请参 考：Paxos算法2#再论编号问题：编号唯一性）

P3的当前编号为初始编号2

当P3提交proposal时发现已经有更大的编号16（16是P2提出的，按规则：5*3+1）

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