Paxos算法分析

Paxos 算法要解决的问题是在一个分布式系统中如何就某个值（提案）达成一致。是一个非常基础而且经典的算法，也是目前最有效的一个算法。【来自Schooner中国团队，转载请申明】

算法理论描述：

提案的提出与通过

通过一个提案分为两个阶段：

1. prepare 阶段：
   1. proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派；
   2. acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor 将自己上次的批准回复给 proposer，并承诺不再批准小于 n 的提案；
2. 批准阶段：
   1. 当一个 proposor 收到了多数 acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 acceptors 发送 accept 请求，包括编号 n 和根据 P2c 决定的 value（如果根据 P2c 没有决定 value，那么它可以自由决定 value）。
   2. 在不违背自己向其他 proposer 的承诺的前提下，acceptor 收到 accept 请求后即批准这个请求。

这个过程在任何时候中断都可以保证正确性。例如如果一个 proposer 发现已经有其他 proposers 提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述 prepare 过程中，如果一个 acceptor 发现存在一个更高编号的”草案”，则需要通知 proposer，提醒其中断这次提案。

详细的解释，见http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95，已经说的很清楚了，不过理论性比较强，这里，就我个人的理解，做一个比较通俗的分析，希望可以帮助大家理解

假设条件：

1. 不存在拜占庭失效，即所有的消息可以丢失，可以乱序，但是不可能出现错误。
2. 所有的提案之间都存在偏序关系，这里我们可以简单的假设，所有的提案编号都是唯一且单调递增的。

核心概念：

1. 提案只有在提出之后才能批准
2. 批准分为两个阶段，批准提案和批准该提案的值
3. 值的形成不是简单的由提案提出，需要由批准提案的返回值决定
4. 每次算法执行过程中，只能批准一个值
5. 每次批准需要大于半数的人同意

算法描述：

我们通过一个分布式的Key-Value store系统来描述这个算法。假设系统中有5个节点（A,B,C,D,E），共同维护一个分布式的Key-Value store。那么我们可以通过工程实际对应上述抽象概念，每一个写请求对应一个提案（Paxos针对的应该是对于同一个值的写请求，即我们常说的写冲突），每一个写请求都应该是一个事务，所以应该有一个trx-id, 对应我们的提案编号。我们通过一个写冲突来描述算法过程。

1. A节点接受一个写请求（set abc=0,trx-id=0），同时D节点接受一个写请求(set abc=1, trx-id=1)
2. A的写请求提交多数派，A,B,C审议，D的写请求提交多数派C,D,E审议
3. A，B同意A，D，E同意D，关键点在C
4. 如果C先收到A的请求，那么C先同意A，不回复任何值，但记下A的值(set abc=0), 之后C收到D的请求，发现D的trx-id大于A的，那么C回复同意D，但是同时回复值需要是0（因为C已经记下A的值为0）
   1. A收到回复，发现没有任何值，于是设其写请求的值是0提出值批准请求给A,B,C。D收到回复，发现值是0，设其写请求的值是0提出值批准请求给C,D,E
   2. A,B批准A的值批准请求，D,E批准D的值批准请求，C由于已经批准了trx-id=1的请求，所以驳回了A trx-id=0的值批准请求,  之后C批准D的值批准请求
   3. 最终D的提案获得通过，但是值是0
   4. 将通过的提案广播出去，所有节点set abc=0
5. 如果C先收到D的请求，那么C先同意D，不回复任何值，但记下D的值(set abc=1), 之后C收到A的请求，发现A的trx-id小于D的，那么不回复A，
   1. A只收到A,B的回复，提案失败，D收到C,D,E的回复，提案成功
   2. D收到回复，发现没有任何值，设其写请求的值是1提出值批准请求给C,D,E.
   3. C,D,E批准D的值批准请求
   4. 最终D的提案获得通过，其值是1.
   5. 将通过的提案广播出去，所有节点set abc=1

那么通过上述的描述，我们就可以看到，一个写冲突就可以解决了，无论最终结果是值为1还是值为0，系统不会出现数据不一致问题，即Paxos算法可以很严格的保证数据的一致性。但是，具体算法的时间复杂度还是比较高的，在工程实践中，需要考虑采用其变种，降低一部分的一致性要求或降低系统的并发度，来提高该算法的实用性，将在后续文章中讨论。