[Paxos] Paxos Made Simple 读后感

Paxos 由著名图灵奖获得者Leslie Lamport提出,该算法是分布式一致性算法中的奠基之作,今天初读此文仅将相关学习心得予以记录。

1.Paxos 是什么?主要用来解决什么问题?

Paxos是一个用于实现可容错的分布式系统的算法,主要用于保证分布式集群中多备份系统之间的操作和数据的一致性。这样集群中的每台机器对外相当于完全一致,从而其互相之间可以互为备份,从而使得系统能够容忍一定数量的机器出问题(宕机、断网、硬盘损坏等等)。

2.Paxos的基本原理是什么?

介绍paxos的算法之前,首先介绍一个paxos算法中涉及到的几个角色:

  • proposer 提出提案者,在实际应用中可以理解为request的接受者,该角色接收到用户请求,并向集群提出提案要求执行该request。
  • acceptor 接收者,接收者接收到来自其他的proposer的提案,并按照一定的逻辑决定是否接收当前的提案,也就是是否接收request并准备执行request的角色。
  • learner 学习者,能够从其他节点获取某个被共识之后的提案。

2.1 paxos解决的问题

假设有n个独立的进程分别能够提出一个值,那么pasos算法用于保证这些进程提出的值的其中之一能够被正确处理。

paxos算法的安全性前提条件为:

  1. 只有被提议的值才有可能被选中,也就是说不可能有凭空出现的值出现;
  2. 一次只有一个值会被选中;
  3. 进程不会learn到一个没有被选中的值;

ps:这里的选中是翻译论文中的propose,其实我感觉这里的propose value可以理解为对某个请求的共识,也就是当进程接收到客户的请求时需要paxos算法保证每次各个进程所处理的请求一致。

pasox算法的关键也就是对这种

2.2 paxos算法的论述以及推论

2.2.1 如何选择一个提案?

对于单个服务器而言,可以按照先到先服务的顺序去选择提案,但是对于多个进程怎么保证提案选择?提案可以由任何一个proposer发出,每个acceptor收到提案的顺序会有所不同,如何保证各个acceptor按同样的顺序接收提案是paxos算法的核心。

为了保证其一直性,paxos给出一系列的接收提案的规定及其推论:

P1: An acceptor must accept the firtst proposal that it receives.(任何接收者都按照先来先服务的原则接收提案。)

P1这个会引起另外一个问题:也就是每个进程接收到的提案顺序不一样,这会造成整个系统的不一致

为了解决这个问题,paxos为每个拟接收的提案(后文直接用Request替代好了)分配一个序号,每个acceptor可以同时接收多个Request,但是一个时间只有一个Request会得到一个序号,序号是递增的。每个Request分配需要必须要集群中大多数节点同意,这里的大多数由系统的Intersection Quorum决定,本场景中的quorum数最少系统节点数目的一半加1。

P2: If a proposal with value v is choosen, then every higger-numbered proposal that is choosen has value v.(如果某个值v在num k的时候被选中,num 大于k的Proposal中能够看到之前选中的v的值)

由P1和P2可以得出一个提案提交的算法:

  1. 某个节点上的Proposer提出一个新的proposal num k,并发送到其他一定数量的acceptor,让其保证一下两点:(这被称为PrepareRequest(n) n是request的序号)
  • 不在接收proposal num < k的提案;
  • proposal num 小于k的所有提案已经被accept了;
  1. 如果该Proposer接收到来自大多数的节点对1中的PrepareRequest的回应,那么Proposer会选择Responses中的最大的proposal提案序号,如果responders没有改提案号,Proposer就会自己随机选择一个并和之前的k一起发送AcceptRequest(n, v)到acceptors;

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

2.2.2 Proposal 与Acceptor之间的交互流程

  • 阶段一:

    Proposer节点接收到客户端请求,向集群中其他Acceptor节点发送该请求提案,并赋给该提案一个最新的序列号,即发送Prepare消息。
sequenceDiagram
Proposer ->> Acceptors: Prepare(n)
  • 阶段二:

    Acceptor节点接收到Prepare消息之后需要进行检查,如果n的值大于当前该节点之前Prepare的最大的序列号则接受该消息,并在接下来的处理过程中不再接收序列号小于n的其他Prepare消息。
sequenceDiagram
Acceptors ->> Proposer: OK, not accept Prepare.num < n and highest-numbered proposal it has accepted(if any)
  • 阶段三:

    Proposer节点在阶段一之后等待Acceptor节点的返回,当接收到大于Quorum数量的相应之后,向Acceptor节点发送Accept(n,v)消息。n即Prepare中的序列号,v = (Acceptor返回的其最大的accepted 的序列号)|| (Acceptor没返回的情况下,Proposer节点任意指定)
sequenceDiagram
Proposer ->> Acceptors: Accept(n, v)
  • 阶段四:

    Acceptors收到Accept之后进行请求的具体执行

3.Paxos有哪些适用领域以及其有哪些限制?

Paxos解决的问题:

  • 异步网络环境中,多进程之间操作的一致性

Paxos的前置条件有:

  • 该算法只能够适用于系统中不包含拜占庭节点的情况;
  • 该算法的正确性前提是系统中不能超过一半的机器出现问题;

4.Paxos的成熟应用以及发展现状?

Paxos目前广泛运用在目前的分布式系统,典型的分布式协调服务有开源的Zookeeper系统以及Google的Chubby,国内的阿里的OceanBase等等。

5.分布式一致性还有哪些算法可以用?分别有哪些有缺点?

比较著名的还有VR,Raft

以及能够容忍拜占庭节点的PBFT等

上一篇:Paxos算法 Paxos Made Simple


下一篇:C# 线程更新UI