图解分布式一致性协议Paxos

时间:2023-02-27 00:23:07

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢?

<分布式系统的事务处理>

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

<大规模分布式存储系统>

理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。

学习Paxos算法有两部分:a) 算法的原理/证明;b) 算法的理解/运作。

理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得多。

网上我觉得讲Paxos讲的好的属于这篇:paxos图解Paxos算法详解,我这里就结合wiki上的实例进一步阐述。一些paxos基础通过这里提到的两篇文章,以及wiki上的内容基本可以理解。

算法内容

Paxos在原作者的《Paxos Made Simple》中内容是比较精简的:

Phase 1

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.

Phase 2

(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

借用paxos图解文中的流程图可概括为:

图解分布式一致性协议Paxos

实例及详解

Paxos中有三类角色ProposerAcceptorLearner,主要交互过程在ProposerAcceptor之间。

ProposerAcceptor之间的交互主要有4类消息通信,如下图:

图解分布式一致性协议Paxos

这4类消息对应于paxos算法的两个阶段4个过程:

  • phase 1
    • a) proposer向网络内超过半数的acceptor发送prepare消息
    • b) acceptor正常情况下回复promise消息
  • phase 2
    • a) 在有足够多acceptor回复promise消息时,proposer发送accept消息
    • b) 正常情况下acceptor回复accepted消息

因为在整个过程中可能有其他proposer针对同一件事情发出以上请求,所以在每个过程中都会有些特殊情况处理,这也是为了达成一致性所做的事情。如果在整个过程中没有其他proposer来竞争,那么这个操作的结果就是确定无异议的。但是如果有其他proposer的话,情况就不一样了。

paxos中文wiki上的例子为例。简单来说该例子以若干个*提议税收,确定最终通过的法案税收比例。

以下图中基本只画出proposer与一个acceptor的交互。时间标志T2总是在T1后面。propose number简称N。

情况之一如下图:

图解分布式一致性协议Paxos

A3在T1发出accepted给A1,然后在T2收到A5的prepare,在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况:

  • A5发来的N5小于A1发出去的N1,那么A3直接拒绝(reject)A5
  • A5发来的N5大于A1发出去的N1,那么A3回复promise,但带上A1的(N1, 10%)

这里可以与paxos流程图对应起来,更好理解。acceptor会记录(MaxN, AcceptN, AcceptV)

A5在收到promise后,后续的流程可以顺利进行。但是发出accept时,因为收到了(AcceptN, AcceptV),所以会取最大的AcceptN对应的AcceptV,例子中也就是A1的10%作为AcceptV。如果在收到promise时没有发现有其他已记录的AcceptV,则其值可以由自己决定。

针对以上A1和A5冲突的情况,最终A1和A5都会广播接受的值为10%。

其实4个过程中对于acceptor而言,在回复promise和accepted时由于都可能因为其他proposer的介入而导致特殊处理。所以基本上看在这两个时间点收到其他proposer的请求时就可以了解整个算法了。例如在回复promise时则可能因为proposer发来的N不够大而reject:

图解分布式一致性协议Paxos

如果在发accepted消息时,对其他更大N的proposer发出过promise,那么也会reject该proposer发出的accept,如图:

图解分布式一致性协议Paxos

这个对应于Phase 2 b):

it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

总结

Leslie Lamport没有用数学描述Paxos,但是他用英文阐述得很清晰。将Paxos的两个Phase的内容理解清楚,整个算法过程还是不复杂的。

至于Paxos中一直提到的一个全局唯一且递增的proposer number,其如何实现,引用如下:

如何产生唯一的编号呢?在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择,例如系统有5个Proposer,则可为每一个Proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)

参考文档

图解分布式一致性协议Paxos的更多相关文章

  1. &lbrack;转帖&rsqb;图解分布式一致性协议Paxos

    图解分布式一致性协议Paxos https://www.cnblogs.com/hugb/p/8955505.html   Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分 ...

  2. &lbrack;转&rsqb;图解分布式一致性协议Paxos

    Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者MikeBurrows说过这个世界上只有一种一致性算法,那就是 ...

  3. 分布式一致性协议 --- Paxos

    问题 Paxos 到底解决什么样的问题,动机是什么 Paxos 流程是怎么样的? Paxos 算法的缺陷是什么 概述 Paxos 是分布式一致性算法,根据少数服从多数的原则多个节点确定某个数值.通过学 ...

  4. &lbrack;从Paxos到ZooKeeper&rsqb;&lbrack;分布式一致性原理与实践&rsqb;&lt&semi;二&gt&semi;一致性协议&lbrack;Paxos算法&rsqb;

    Overview 在<一>有介绍到,一个分布式系统的架构设计,往往会在系统的可用性和数据一致性之间进行反复的权衡,于是产生了一系列的一致性协议. 为解决分布式一致性问题,在长期的探索过程中 ...

  5. 搞懂分布式技术2:分布式一致性协议与Paxos,Raft算法

    搞懂分布式技术2:分布式一致性协议与Paxos,Raft算法 2PC 由于BASE理论需要在一致性和可用性方面做出权衡,因此涌现了很多关于一致性的算法和协议.其中比较著名的有二阶提交协议(2 Phas ...

  6. &lbrack;转帖&rsqb;分布式一致性协议介绍(Paxos、Raft)

    分布式一致性协议介绍(Paxos.Raft) https://www.cnblogs.com/hugb/p/8955505.html  两阶段提交 Two-phase Commit(2PC):保证一个 ...

  7. 使用GO实现Paxos分布式一致性协议

    什么是Paxos分布式一致性协议 最初的服务往往都是通过单体架构对外提供的,即单Server-单Database模式.随着业务的不断扩展,用户和请求数都在不断上升,如何应对大量的请求就成了每个服务都需 ...

  8. 分布式一致性协议Raft原理与实例

    分布式一致性协议Raft原理与实例 1.Raft协议 1.1 Raft简介 Raft是由Stanford提出的一种更易理解的一致性算法,意在取代目前广为使用的Paxos算法.目前,在各种主流语言中都有 ...

  9. Zookeeper——分布式一致性协议及Zookeeper Leader选举原理

    文章目录 一.引言 二.从ACID到CAP/BASE 三.分布式一致性协议 1. 2PC和3PC 2PC 发起事务请求 事务提交/回滚 3PC canCommit preCommit doCommit ...

随机推荐

  1. excel 作图中次横坐标及次纵坐标的调试,以及excel自定义轴标签的步骤方法

    在工作中除了要做一些常用的图表之外,不时还会有一切奇怪图表的制作需求. 今天的内容主要记录的是如何对excle图表的次横坐标及次纵坐标进行调试,以及如何自定义调整轴标签 首先看下如何做次纵坐标,工作中 ...

  2. java学习第10天 (增加关于eclipse添项目)

    自己遇到一个问题..觉得有必要说下,就是如何将别人发给你的文件也就是项目如何导入到你的eclipse中,不是直接add那么简单,首先右键找到import,找到general,展开找到existing ...

  3. 使用go的ssh包快速打造一个本地命令行ssh客户端

    热身运动

  4. JAVA对象是如何占用内存的

      本文使用的是32位的JVM ,jdk1.6.本文基本是翻译的,加上了一些自己的理解,原文见文章底下链接.     在本文中,我们讨论如何计算或者估计一个JAVA对象占多少内存空间.(注意,使用 C ...

  5. PHP signal 信号

    最早写php时,发现在终端执行一个php文件,会一直等待程序执行完成以后,终端才能继续下面的操作,若不小心按了下Ctrl+C会导致php程序退出,闭避免这种情况发生,将会使用php的系统编程,即sig ...

  6. python使用环境的设置

    virtualenv usage mkidr ~/pyenv cd ~/pyenv virtualenv pycaffe #it will setup a new python environtmen ...

  7. javascript语法之for-in语句

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  8. webpack4&period;0各个击破(9)—— karma篇

    webpack作为前端最火的构建工具,是前端自动化工具链最重要的部分,使用门槛较高.本系列是笔者自己的学习记录,比较基础,希望通过问题 + 解决方式的模式,以前端构建中遇到的具体需求为出发点,学习we ...

  9. page0902未完成

    /** * @author:(LiberHome) * @date:Created in 2019/3/1 23:14 * @description: * @version:$ */ import j ...

  10. 爬虫万金油,一鹅在手,抓遍全球:goose 简介!

    GOOSE 现已弃用 经过多年的服务,GOOSE接口和支持它的MySQL数据现已弃用 . 在我们进行替换的同时,我们建议寻找一般查询功能的用户在http://rdf.geneontology.org上 ...