‍‍‍‍

基本算法(basic paxos)

‍‍‍算法(决议的提出与批准)主要分为两个阶段:

1. prepare阶段： 

(1). 当Proposer希望提出方案V1，首先发出prepare请求至大多数Acceptor。Prepare请求内容为序列号<SN1>;

(2). 当Acceptor接收到prepare请求<SN1>时，检查自身上次回复过的prepare请求<SN2>

    a). 如果SN2>SN1，则忽略此请求，直接结束本次批准过程;

    b). 否则检查上次批准的accept请求<SNx，Vx>，并且回复<SNx，Vx>；如果之前没有进行过批准，则简单回复<OK>;

 

2. accept批准阶段： 

(2a). 经过一段时间，收到一些Acceptor回复，回复可分为以下几种:

        a). 回复数量满足多数派，并且所有的回复都是<OK>，则Proposer发出accept请求，请求内容为议案<SN1，V1>;

        b). 回复数量满足多数派，但有的回复为：<SN2，V2>，<SN3，V3>...,，则Porposer找到所有回复中序列号最大的（SNx）值（Vx），假设为  <SNx，Vx>，则发出accept请求，请求内容为议案<SN1，Vx>;

        c). 回复数量不满足多数派，Proposer尝试增加序列号为SN1+，转1继续执行;

 

  (2b). 经过一段时间，Proposer收到一些Acceptor回复，回复可分为以下几种:

        a). 回复数量满足多数派，则确认V1被接受;

        b). 回复数量不满足多数派，V1未被接受，Proposer增加序列号为SN1+，转1继续执行;

(3). 在不违背自己向其他Proposer的承诺的前提下，Acceptor收到accept 请求后即接受并回复这个请求。

 

Paxos算法的用处

      1.领导选举，当主节点宕机，从节点服务器群组发起领导选举

     2.多节点数据日志同步，数据副本一致性（multi-paxos）。

          多个Proposer（Client）发起数据请求，把所有请求交由Proposer Leader来向Acceptor集群发送日志同步请求。log-replication

       详情: ,(基于multi-paxos的复制协议)

    3.paxos用来在多个process之间对同一个值达成一致

 

‍‍‍‍

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

 

分布式系统Paxos算法

 

libpaxos 库

(微信)

 

微信PaxosStore：深入浅出Paxos算法协议