# 算法 A Basic Paxos Algorithm Demo Using Erlang

yfractal · 2019年08月05日 · 1918 次阅读

## 算法描述

### Phase 2

#### Phase 2a: Accept

If a Proposer receives enough Promises from a Quorum of Acceptors, it needs to set a valuealo v to its proposal. If any Acceptors had previously accepted any proposal, then they'll have sent their values to the Proposer, who now must set the value of its proposal, v, to the value associated with the highest proposal number reported by the Acceptors, let's call it z. If none of the Acceptors had accepted a proposal up to this point, then the Proposer may choose the value it originally wanted to propose, say x[17].

The Proposer sends an Accept message, (n, v), to a Quorum of Acceptors with the chosen value for its proposal, v, and the proposal number n (which is the same as the number contained in the Prepare message previously sent to the Acceptors). So, the Accept message is either (n, v=z) or, in case none of the Acceptors previously accepted a value, (n, v=x).

#### Phase 2b: Accepted

If an Acceptor receives an Accept message, (n, v), from a Proposer, it must accept it if and only if it has not already promised (in Phase 1b of the Paxos protocol) to only consider proposals having an identifier greater than n.

If the Acceptor has not already promised (in Phase 1b) to only consider proposals having an identifier greater than n, it should register the value v (of the just received Accept message) as the accepted value (of the Protocol), and send an Accepted message to the Proposer and every Learner (which can typically be the Proposers themselves). Else, it can ignore the Accept message or request.

## Erlang 实现

paxos 中，在 proposal 给 acceptor 发消息的时候，都会发一个 n，这个可以近似认为是 transaction id。在下面我们叫它 sequence number。

### Acceptor

Acceptor 的职责主要有，接收 Proposer 的提议，和把自己接受的提议告诉 Proposer。

Acceptor 职责有两个，一个是接收准备阶段的消息，一个是接收提议，代码如下。

``````-module(paxos_acceptor).

%% 声明使用 gen_server 这个 behaviour。
-behaviour(gen_server).

%% 创建 paxos_acceptor process

prepare(Pid, From, SeqNum) ->
%% acceptor 接收消息，异步返回，所以使用 gen_server:cast
gen_server:cast(Pid, {prepare, From, SeqNum}).

accept(Pid, From, {SeqNum, NewProposal}) ->
gen_server:cast(Pid, {accept, From, {SeqNum, NewProposal}}).
``````

``````handle_cast({prepare, From, SeqNum}, State) ->
State2 = do_prepare(From, SeqNum, State),
``````

`do_prepare` 的实现：

acceptor 需要接收 proposer 发来的 sequence number（wikipedia 里的的 n），

``````do_prepare(From, SeqNum,
#state{highest_seq_num=HighestSeqNum, accepted_proposal=Proposal, id=Id} = State)
when SeqNum > HighestSeqNum ->
paxos_proposer:prepare(From, {SeqNum, Proposal, Id}),
State#state{highest_seq_num=SeqNum};

do_prepare(_, SeqNum, State) ->
State.
``````

accept 所做的事情也是类似的。如果收到 sequence number 比之前的大，则接收对应的 proposal，代码如下：

``````do_accept(From, {SeqNum, NewProposal},
#state{id=Id, highest_seq_num=HighestSeqNum} = State)
when SeqNum >= HighestSeqNum ->
paxos_proposer:proposal_accepted(From, {SeqNum, NewProposal}),

State#state{highest_seq_num=SeqNum, accepted_proposal=NewProposal};
do_accept(_, {SeqNum, NewProposal},
#state{id=Id, highest_seq_num=HighestSeqNum} = State) ->
State.
``````

### Proposer

proposer 和 acceptor 一样做两件事。

callback 我用 `state_functions``state_enter`。简单来说，就是用不同的方法表示所处的状态。每个状态，都会有 `enter` 方法。

``````prepare(enter, _Msg, Data) ->
timer:sleep(rand:uniform(5)),
Data2 = send_prepare_to_all_acceptors(Data),
{keep_state, Data2, [{state_timeout, 20, timeout}]};
prepare(cast, {prepare, SeqNum, Proposal, _AcceptorId},

MajorityCount = majority_count(Data),
if ReceivedMessagCount + 1 >= MajorityCount ->
{next_state, proposal, Data3};
true ->
{keep_state, Data3, [{state_timeout, 20, timeout}]}
end;
prepare(state_timeout, timeout, Data) ->
Data2 = send_prepare_to_all_acceptors(Data),
{keep_state, Data2, [{state_timeout, 20, timeout}]};

prepare(_, _, Data) ->
{keep_state, Data}.
``````

``````prepare(_, _, Data) ->
{keep_state, Data}.
``````

``````proposal(enter, _Msg, Data) ->
Data2 = send_proposal_to_all_acceptors(Data),
{keep_state, Data2, [{state_timeout, 15, timeout}]};
proposal(cast, {proposal_accepted, SeqNum, Proposal},
current_seq_number=SeqNum,
current_proposal=Proposal} = Data) ->
MajorityCount = majority_count(Data),
if ReceivedMessagCount + 1 >= MajorityCount ->
Data3 = Data#data{current_proposal=Proposal},
{next_state, consensus, Data3};
true ->
{keep_state, Data2, [{state_timeout, 20, timeout}]}
end;
proposal(state_timeout, timeout, Data) ->
{next_state, prepare, Data};
proposal(_, _, Data) ->
{keep_state, Data}.
``````

### 参考

yfractal 中提及了此贴 08月05日 22:51
yfractal 中提及了此贴 08月09日 02:22