分布式一致性算法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

提议

1
2
3
4
5
6
class Propose {
// 提议的编号
rnd: number;
// 提议的内容
value: Object;
}

Proposer

提议的发起者

1
2
3
class Proposer {
propose: Propose;
}

只携带一个propose.

Phase1ReqData

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

1
2
3
4
class Phase1ReqData{
// 提案的rnd
rnd: number;
}

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

Acceptor

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

Phase1ResData

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

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

Phase2ReqData

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

1
2
3
4
5
6
class Phase2ReqData {
// 提案的rnd
rnd: number;
// 提案的value
value: Object;
}

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

Phase2ResData

Phase2中, Acceptor向Proposer返回的数据

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

Basic Paxos的过程

开始前的状态

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
proposer = {
propose: {
rnd: 1,
value: "SomeValue"
}
}

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

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

Phase-1 proposer请求的阶段

```{rnd: 1}```, 将其发送给三个```acceptor```.
1
2
3
4
5
6
7
8
9
10
11

#### 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设为phase1ReqDatarnd, 然后将生成的生成一个phase1ResData返回. 即, 返回的phase1ResData中携带的lastRndacceptor先前的lastRnd, 然后acceptorlastRnd设为收到的phase1ReqDatarnd.

Phase-1 proposer

两个问题

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