# loop_in_codes

## 图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议，它有多重要呢？

## 算法内容

Phase 1

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.

Phase 2

(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

## 实例及详解

Paxos中有三类角色`Proposer``Acceptor``Learner`，主要交互过程在`Proposer``Acceptor`之间。

`Proposer``Acceptor`之间的交互主要有4类消息通信，如下图：

• phase 1
• a) proposer向网络内超过半数的acceptor发送prepare消息
• b) acceptor正常情况下回复promise消息
• phase 2
• a) 在有足够多acceptor回复promise消息时，proposer发送accept消息
• b) 正常情况下acceptor回复accepted消息

paxos中文wiki上的例子为例。简单来说该例子以若干个议员提议税收，确定最终通过的法案税收比例。

A3在T1发出accepted给A1，然后在T2收到A5的prepare，在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况：

• A5发来的N5小于A1发出去的N1，那么A3直接拒绝(reject)A5
• A5发来的N5大于A1发出去的N1，那么A3回复promise，但带上A1的(N1, 10%)

A5在收到promise后，后续的流程可以顺利进行。但是发出accept时，因为收到了(AcceptN, AcceptV)，所以会取最大的AcceptN对应的AcceptV，例子中也就是A1的10%作为AcceptV。如果在收到promise时没有发现有其他已记录的AcceptV，则其值可以由自己决定。

it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

## 总结

Leslie Lamport没有用数学描述Paxos，但是他用英文阐述得很清晰。将Paxos的两个Phase的内容理解清楚，整个算法过程还是不复杂的。

## 参考文档

posted on 2014-10-15 22:45 Kevin Lynx 阅读(10126) 评论(6)  编辑 收藏 引用 所属分类: network

### 评论

#### #re: 图解分布式一致性协议Paxos[未登录] 2014-10-17 22:33 杨粼波

@zuhd 看下ZooKeeper就明白了，ZooKeeper是Paxos算法的实现。  回复  更多评论

#### #re: 图解分布式一致性协议Paxos 2016-02-22 12:11 tievoli

very nice...  回复  更多评论

#### #re: 图解分布式一致性协议Paxos 2016-06-20 12:04 MaxLiu

acceptor 阶段2 if(K > MaxN) 的约束少了个, 除了令 AcceptN = K, AcceptV = V 外, 还要令 MaxN = K.  回复  更多评论