分布式一致性算法paxos

资料: b站有人传的一个公开课
可靠分布式系统基础 Paxos 的直观解释PPT

Basic Paxos

相关概念

Proposer

提议的发起者

Acceptor

提议的审批者

Leaner

提议的学习者

Quorum

Acceptor的多数派

Phase

Basic Paxos分为两阶段, Phase-1和Phase-2

Round

选举的轮次

rnd

轮次编号, 在不同资料中也被叫做提议的编号

Value

提议的内容(值)

vRnd(value round number)

vRnd是Acceptor的属性, 是Acceptor上次接受的提议的rnd

数据/对象属性

Propose

提议

class Propose {
    // 提议的编号
    rnd: number;
    // 提议的内容
    value: Object;
}

Proposer

提议的发起者

class Proposer {
    propose: Propose;
}

只携带一个propose.

Phase1ReqData

Phase-1中, Proposer向Acceptor发送的数据:

class Phase1ReqData{
    // 提案的rnd
    rnd: number;
}

Phase-1中, Proposer仅向Acceptor提交提案rnd

Acceptor

class Acceptor {
    // 上次在Phase-1接受的提案的rnd
    lastRnd: number;
    // 上次在Phase-2接受的提案的rnd
    vRnd;
    // 接受的提案的value
    value: Object;
}

Phase1ResData

Phase-1中, Acceptor向Proposer返回的数据:

class Phase1ResData {
    // Acceptor上次在Phase-1接受的提案的rnd
    lastRnd: number;
    // Acceptor上次在Phase-2接受的提案的rnd
    vRnd;
    // Acceptor上次接受的天的value
    value;
}

Phase2ReqData

Phase-2中, Proposer向Acceptor发送的数据:

class Phase2ReqData {
    // 提案的rnd
    rnd: number;
    // 提案的value
    value: Object;
}

注意, 这里的value并不一定是先前Proposer携带的Propose的value, 有可能会在Phase-1接受到返回数据之后发生改变.

Phase2ResData

Phase2中, Acceptor向Proposer返回的数据

class Phase2ResData {
    // 是否已接受提案
    accepted: boolean;
}

Basic Paxos的过程

开始前的状态

初始数据用来模拟顺利提出, 接受一个Propose

proposer = {
    propose: {
        rnd: 1,
        value: "SomeValue"
    }
}

acceptor0 = {
    lastRnd: 0,
    vRnd: 0,
    value: null
}

// 初始化三个相同的acceptor
acceptor1 = {...acceptor0}
acceptor2 = {...acceptor0}

Phase-1 proposer请求的阶段

```{rnd: 1}```, 将其发送给三个```acceptor```.

#### Phase-1 acceptor对收到的请求进行处理的阶段
如果收到的```phase1ReqData```的```rnd```**大于**```acceptor```的```lastRnd```, 则通过该提案, 生成一个```phase1ResData```:  
```ts
phase1ResData = {
    lastRnd: acceptor.rnd
    // Acceptor上次在Phase-2接受的提案的rnd
    vRnd: acceptor.rnd;
    // Acceptor上次接受的天的value
    value: acceptor.value;
}

之后, 将acceptor自身的rnd设为phase1ReqData的rnd, 然后将生成的生成一个phase1ResData返回. 即, 返回的phase1ResData中携带的lastRnd是acceptor先前的lastRnd, 然后acceptor的lastRnd设为收到的phase1ReqData的rnd.

Phase-1 proposer

两个问题

• 这个蓝色圈内如果timeout了怎么处理我是知道的, 红色圈内如果timeout了怎么办?
  
• acceptor返回数据的时候, 如果有一个acceptor实际返回的是reject, 但是timeout了怎么办?如果其他acceptor结果都是accept是不是有点不对劲…本来有一个reject就该失败的