理解Paxos-分布式系统一致性算法 (一)

简介

Paxos是一个分布式系统一致性算法,用于在分布式系统中的多个节点之间,就某个值达成一致。为便于理解Paxos,本文首先会解释一些背景概念,以及一些上下文关系。然后给出正确性推导的简单介绍,以及最终的两阶段协议。最后会给出一些重要补充,关于演进和具体实现(状态机)。后续如果有机会,会补充一些Paxos实践相关的内容。

本文主要的参考是:

有兴趣的话可以阅读原文。

理解概念

首先需要理解的是一致性问题。在一个分布式系统里,多个进程之间需要就某个值(value)达成一致,那么有人要提出(propose)提议(proposal),有人要接受(accept),最后大家要了解(learn)这个值。这里分别对应的是三种角色:

  • proposer
  • acceptor
  • learner

而进程可能是这三种角色中的任意一个或多个,但这里我们不关心这种对应关系。

我开始阅读原文的时候,遇到的一个比较大的障碍是,不理解这里的value的概念及后面的两阶段在整体上下文里的关系。然后看到一些正确性推导的时候就更不知道在说什么了。这里首先明确一下,value是在分布式系统里,多个进程之间,需要达成一致的值;可能是就是一个值,也可能是一条日志,或者多条日志(比如数据库事务日志),或者是其他需要同步的值。而Paxos两阶段的目标就是在这些进程之间达成一致,可能是正常情况下客户端提交的请求,要从接受请求的server同步到其他server;也可能是在异常情况下,恢复已经达成一致的值,以达到最终一致。这些概念后面会有详细介绍。

需要注意的是,现在讲到的都是一轮Paxos的执行,也就是一个Paxos Instance,涉及到的是一个value。后面会讲到多个Paxos Instance同时执行的情况。

另外,在Paxos里假设的通讯模型是非拜占庭模型(non-Byzantine),简单点说就是:

  • 上述角色可以以任意的速度通讯,可能停止,可能重启
  • 传送的消息可能需要任意长的时间才能送达,可能延迟,可能重复,可能丢失,但是他们不会损坏(no lie)

拜占庭模型详细信息可以参考维基百科,Byzantine_fault_tolerance

正确性推导

选择一个值最简单的方法是,只使用一个acceptor,它会接受第一个接收到value。如下图所示:

Single Acceptor

但是acceptor挂掉的话,整个过程将无法继续,所以需要有多个acceptor。这里采用的方法是,在大多数acceptor接受的情况下(即多数派,majority),一个value被选择出来。

在初始状态,如果有且仅有一个value被提出,这时候要达成一致的话,需要满足如下需求:

P1. An acceptor must accept the first proposal that it receives.  

需要注意的是,这里的proposal是第一个被提出的,之前没有其他的proposal提出。

接受第一个proposal是初始状态下必需的,但是这会导致投票分裂的问题。即不同acceptor接受了来自不同proposer的proposal,导致没有多数派形成决议。如下图所示,S1和S2接受了red,S3和S4接受了blue,S5接受了green,没有多数派形成。

Split Votes

为解决这个问题,需要acceptor能够接受多个proposal。为了区分这些proposal,我们还要生成不同的proposal id,那现在proposal就有了id和value两部分。

在能够接受多个proposal的情况下,还要保证一点:已经被choose的值不会变,即新的proposal包括的仍然是已经choose的值。需要再强调的是,这里仍然是在一个Paxos Instance,即一次Paxos算法的执行,仍然在对一个值进行表决。为了确保已经被choose的值不会变,可以通过如下条件保证:

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.  

由于proposal id是唯一且有序的,那么可以保证只有一个值被选择。proposal是由acceptor接受的,那么可以通过acceptor做出限制,P2可以通过P2a保证:

P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.  

有一种异常情况,P1和P2a是冲突的:假设一个proposer使用一个更大的id,并没有使用已经达成决议的值,任意提出了proposal;这时一个一直没有收到过任何proposal的acceptor,恢复过来,接收到了第一个proposal,;按照P1,它应该接受这个proposal;但是按照P2a,它不应该接受这个proposal;这就有了冲突。

为了解决这个问题,可以通过限制proposer做出限制,把P2a加强成P2b:

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.  

任何新的proposal必须都由proposer提出,那么可以由proposer保证新的proposal都包含已经达成决议的值,这个可以通过递推进行证明,比较简单,这里不再详述。

任何达成决议的值,都必须由多数派接受。那么我们可以通过如下P2c来保证P2b的成立:

P2c. For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.  

也就是说,要提出一个proposal(n, v),那么要满足两个条件,A或者B:

A. 多数派S里,没有acceptor接受过任何小于n的proposal
B. 多数派S里,v是acceptor接受过的最大proposal的值

为了满足这两个条件,一个proposer提出proposal的时候,首先要获得已经被接受或者将要被接受的最大proposal的值;也就是说,在这时候,可能有别的proposer也要提出proposal。已经被accept过的proposal可以获得,但是还没有accept的proposal(可能将要被accept)肯定是不可能获得的。这时候可以通过proposer来进行限制,要求acceptor不再接受小于n的proposal(类似一个barrier)。这就引出了提出proposal的算法:

  1. Prepare Request
    proposer选择一个新的proposal number n,并且发送给acceptor,要求acceptor做出回应:

    A. 不再accept比n小的proposal
    B. 返回小于n的最大的proposal

  2. Accept Request
    如果proposer收到了来自多数派的回应,那么它就可以用n和收到的acceptor返回的最大的proposal包括的值v,进行提议:proposal(n, v);如果响应没有包含proposal,那么它可以选择任何值。它向acceptor发送proposal的请求,叫做Accept Request。

上述是proposer的算法,而对于acceptor来说,按照上述Prepare Request的要求,它需要遵守自己的承诺:如果已经相应过一个proposal id = n,那么它不能再accept小于n的值。

P1a . An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.  

这里需要注意的是P1a是包含P1的。

此外,如果acceptor已经响应过一个大于proposal(n),那么就没必要再回应id为n的proposal,因为它肯定不会再accept id为n的proposal了(这是它的承诺)。还有,如果acceptor已经接受过proposal(n)了,那么也不用再回应id为n的proposal(非正常情况)。

flacro

Read more posts by this author.