Paxos学习笔记

在理解Paxos的时候,一开始觉得很莫名其妙,看了挺多的资料的,但是一直没有理解到,最后还是回归到论文上,看了Leslie Lamport的论文:Paxos Made Simple之后,才恍然大悟

这篇文章主要记录的就是这个学习,思考的过程,根据论文,加上自己的理解总结而成

Paxos学习笔记

一致性

所谓的一致性,通俗地理解,就是数据的状态一直处理正常状态

而分布式一致性,自然就是在分布式环境下使得数据保持一致性了

一致性有不同的模型

  • 强一致性
    • Paxos
    • Raft
    • ZAB
  • 弱一致性
  • 最终一致性(本身属于弱一致性,不过比较突出,所以单独拎出来)
    • DNS

容错性

容错性,可以通俗地理解为,当系统某个或者某几个部件出现故障的时候,系统依旧能保持正常地运行

后面的推导过程可以看到为啥子Paxos是具有高容错性的算法

Paxos

在理解Paxos的时候,一开始觉得很莫名其妙,看了挺多的资料的,但是一直没有理解到,最后还是回归到论文上,看了Leslie Lamport的论文:Paxos Made Simple之后,才恍然大悟

下面详细介绍Paxos的推导过程,基本上是参考论文的思路来的,不过补充多一些这个过程的思考

Paxos是什么

Paxos是由Leslie Lamport提出的一个分布式一致性算法(Consensus Algorithm)

特点:强一致性、容错性

为什么需要Paxos

这里的标题可能不太合适,准确地来说,是为什么会出现不一致的情况,而Paxos刚刚好能解决这个问题,所以这里就以为什么需要Paxos作为小标题

一致性问题这个在单机环境下,可以通过事务等来控制,但是在分布式环境下,问题就很复杂了

通常情况下,分布式系统上的同一功能的节点会有多个,原因在于,单个节点如果挂了,那整个系统就将处于不可用状态了

引入多节点,保证了可用性,但是会出现不一致的情况,比如,某一个客户端修改某个节点,A,上存储的数据,之后A在同步给其他节点的时候,部分节点还没有同步到,A就挂了,那么此时就出现不一致了,此时该以谁为准呢

Paxos的出现,不是为了预防这种情况的发生,而是在出现这种情况的时候,系统如何快速地恢复到一致的情况,即使得不一致的数据快速地一致起来,让系统尽快地可用

基础信息

网络不可靠:网络本身是不可靠的,这一点基本可以达成共识,网络存在延迟、乱序的情况,当然,也存在数据被干扰而损坏的情况,但在Paxos中,假定数据不会被篡改,即不存在拜占庭将军问题

var:这里为了简化问题,我们以一个变量var作为讨论的对象,出现的不一致即var出现了多个不同的值

安全性问题:所谓的安全性问题,就是保证不该出现的情况一定不会出现,有几个比较重要的情况

  • var的某个值只有在被提出来决策的时候,才有可能被选定,没有出现过的值不应该被选定
  • var的多个值中只有一个被选定
  • 如果一个值被选定了,那就是真的被选定的

活性问题:与安全性相对,活性保证的是该出现的一定会出现,同样有几个重要的情况

  • 所有提出来的var的值,最终一定有一个被选定
  • 如果被选定了,其他人一定能够获取到该值

Paxos中的三大角色(Agent)

  • Proposers,提出var值的人,也即需要确定var值的人
  • Acceptors,决策var值的人,也即确定var最终值的人
  • Learners,学习决策出来的var值的人,这篇文章应该只会出现这一次,囧….

为什么需要这么多角色?

  • 首先,Proposer是必须的,就是因为Proposer数据出现不一致了,才会需要讨论的
  • 其次,Acceptors是必须的(Acceptor同时可以是Proposer),既然出现不一致,那总是需要有人来决定到底以谁为准
  • 最后,Learners,这个确实是可有可无的

虽然Paxos中有三个角色,但是觉得跟实现的映射关系是比较随意的,如一个进程可以同时身兼多个角色

在Paxos中,由于Aagent需要记住自己已经选过的某个值,所以需要对该值进行持久化,防止重启/崩溃恢复之后丢失数据

提案:也可以称为提议,就是记录某一个变量的某一个值,由Proposer提出,交由Acceptor决策

大多数原则:也成为少数服从多数原则,在一个团体中,如果大部分的人都同意了,那么未同意的少部分人就只能放弃自己的想法,转成同意,最小的大部分是集体数量的一半+1

确定一个值

确定一个值,其实也就是某个提案在集群中达到一致,这里计提案为:<var, value>

方案一:单个Acceptor

有了上面的情况之后,接下来我们来讨论如何确定一个值,首先,最简单的方式就是,只通过一个Acceptor来决策,Acceptor只接受提交的第一个var值,之后的直接以第一个值为准即可,那就没啥好争的了,拼手速吧

这个方案是最简单的,但存在前面提到的单点问题,如果Acceptor挂了,那场面就很尴尬了

方案二:多个Acceptor

既然一个Acceptor有问题,那就多个咯

多个Acceptor解决了单点的问题,但引入了其他的复杂问题

首先,前面活性问题提到了,被提出来提案的一定要能够决策出唯一一个出来,但是,如果每个Acceptor都选择不接受,那么被提出来的所有值都无法决策,所以需要Acceptor做出如下保证

P1:每个Acceptor必须同意接收到的第一个提案

这样子,活性的问题解决了吗?并没有,因为出现下面的情况

1
2
3
4
5
6
7
8
9
10
11
# case 1
P1 ---> A1
P2 ---> A2
P3 ---> A3

# case 2
P1 ---> A1
---> A2
A3(x)
p2 ---> A4
---> A5

虽然每个Acceptor都同意了自己收到的第一个提案,然后拒绝/忽略后续的,从而导致了上面的尴尬场景出现了,此时,提案虽然被决策出来了,但是违背了安全性

这也意味着P1其实不够完善,只要求接收第一个提案是不够的,既然不够,那继续加强完善就可以了,如何完善呢?

为了保证一个提案被接受了,那就要求所有人都同意这个值的时候,才能同意这个提案,但是所有人太多了,Paxos中以大多数为准,也即一个提案,只有被大多数Acceptor接受了,这个提案才算被接受

上面的话,也即意味着一个Acceptor必须接受不止一个提案,如果只接受一个的话,大多数是很难达到的(上面的那两个例子),那么问题又来了,一个Acceptor接受多个提案,那要怎么区分这些提案呢?

简单,为每个提案分配一个ID就行了,这样子就能够区分开来了,此时,提案就变为:<var, value, ID>,ID只要全局单调递增即可

解决了提案无法区分的问题,那就意味着此时Acceptor能够区分开多个不同的提案了,那么原始问题解决了吗?

并没有,因为此时Acceptor可以不停地接受ID更大的提案,并且不停地覆盖掉对应的值,从而导致一个值即使被选定了,也可能被覆盖掉

1
2
3
4
5
6
7
8
P1 ---> A1 <var, v1, 1>
P1 ---> A2 <var, v1, 1>
P1 ---> A3 <var, v1, 1>
A4
A5
-----
此时var的值已经选定了(大多数原则),但是如果此时P2提了个新的提案<var, v2, 2>
那么会导致被选定出来的值又被覆盖了,从而违背了安全性中的一个值被选定必定是被选定出来的

这说明上述的还是不够完善,需要继续完备,问题出在于,被选定的值依旧被后面的提案覆盖了,所以只需要保证这个就可以了

P2:如果一个提案<var, v1, ID_1>被接受了,那么被选中的所有编号比其高的提案的值,也必须是v1

为了保证P2成立,可以通过要求Acceptor碰到编号比自己已经批准过的提案编号还高的提案时,不要审批,来实现

P2a:如果一个提案<var, v1, ID_1>被接受了,那么所有其批准的所有编号比v1高的提案,其值必须是v1

可是,事实上P2a还是有问题

1
2
3
4
5
P1 ---> A1 <var, v1, 1>
P1 ---> A2 <var, v1, 1>
P1 ---> A3 <var, v1, 1>
A4 <var, null, null>
A5 <var, null, null>

此时如果P2提出新的提案<var, v2, 2>,对于A4、A5而言,根据P1,是必须接受的,所以又出现了尴尬的场面,安全性又违背了

可是此时对于A4、A5来说,他们也是很无奈,根据约定,是必须要接受的,可是接受了,又说是错误的,从A4、A5的角度来说,已经无法处理这种情况了

解决问题的方式从来都不止一种,比如把提出问题的人解决了也是能够解决问题的,换句话说,既然对于Acceptor而言,已经无法应付这种情况了,那么只要提出问题的人不要乱提问题,那问题也是能得到解决的,也即

p2b:如果一个提案<var, v1, ID_1>已经被接受了,那么所有提出来的编号比其高的提案,其值必须是v1

那么问题又来了,对于P而言,如何知道当前提案是否已经被接受了呢?方法其实也是很简单,在提出提案之前,先问一下各位Acceptor,对于提案,是否已经接受过了,如果接受过了,请告诉我他的编号以及值是啥,然后,提案者再根据收集到的信息发起提案,那么万事就大吉了,当然,此时需要Acceptor做出承诺,不能再接受编号比我低的提案了

到了这里,Paxos算法也就推导出来了

Paxos算法

Paxos算法分为两个阶段

  • 第一阶段称为Prepare,目的是为了从Acceptor中获取当前提案的相关信息
  • 第二阶段称为Accept,目的是为了决策出提案的值

第一阶段

Proposer选择一个编号为ID_X的提案,向所有Acceptor发起Prepare请求

Acceptor可以做出如下反应

  • 忽视/丢弃这个请求
  • 将已经接受过的提案的编号以及其值返回给提案者(如果存在)

第二阶段

如果Proposer收到大多数Acceptor返回的响应,则可以继续执行第二阶段

  • 如果所有的响应的值都是null,则说明此时提案还没有被决策出来,那么自己可以选择一个值来发起Accept请求
  • 如果某个响应已经包含了值,那么从所有响应中,选择编号最大的值,作为提案的值,发起Accept请求

此时Acceptor根据接受到的Accept请求,做出如下反应

  • 如果accept请求的提案编号小于之前已经承诺过的编号,则返回错误或者忽略请求

  • 如果编号等于承诺过的编号,则将值更改为对应的值(此时的值要么是没有任何人提出的,要么是已经决策出来的,所以不违反安全性要求)

  • 由于Accept请求是在Prepare之后提出的,所以,不存在编号大于当前已经记录的最大编号这种情况

到这里,Paxos算法就推导完成了

关于Paxos的容错性,从这里可以看到,只要挂掉的Acceptor数量低于总体的一半,那么至少会有一个Acceptor记录了新的值,从而可以继续决策,并且维持这个值不变

活性问题

上述的Paxos中存在一个问题,称为活锁

前面提到了,Paxos第一阶段提出的Prepare请求,会使得Accept拒绝所有编号比其低的请求,所以会有下面的情况存在

  1. A1发起Prepare请求,编号为ID_1
  2. 发起Accept之前,A2发起了Prepare请求,编号为ID_2
  3. A1发起Accept请求,此时,由于编号已经低于记录的最大编号,那么就拒绝了
  4. A1重新发起Prepare请求,编号为ID_3
  5. A2发起Accept请求,此时,由于编号已经低于记录的最大编号,那么就拒绝了
  6. …..然后 ,就停不下来了

此时,陷入了死锁状态

在论文中,Leslie Lamport提出可以通过选举出一个主要的Proposal,所有的提案全部由Proposal提出即可

这里,由于能力有限,就没接着研究下去了….

希望后面有能力继续专研一下,顺便看下其实现代码…