关键词：

文章目录

• Paxos
• • Paxos概念
  • Paxos角色
  • Paxos算法流程
  • • Paxos算法两个阶段
    • • 第一阶段：准备阶段
      • 第二阶段：批准阶段
      • 总结：
    • 图解算法流程
    • 举例说明算法流程
• 图解说明
• • 一个简单的提案
  • • 情况1：正常情况
  • 两个提案并发进行
  • • 情况2：S3先Accept S1的值，已返回Accept 的ack，再见到S5的提案
    • 情况3：S3先Accept S1的值，再见到S5的提案，再返回Accept的ack
    • 情况4：S3先见到S5的提案，再Accept S1的值
  • 操作的顺序问题
  • • 情况5：先加值操作再复制操作
    • 情况6：先复制操作再加值操作
• Paxos优缺点
• • • 情况6：Paxos会产生活锁问题

Paxos

Paxos概念

Paxos 是一种共识算法，目的是解决写多数派时的顺序性问题

多数派时的顺序性问题，简单理解：就是有一堆机器，每一台都可能会收到客户端的一条消息，那么这些及其到底使用哪条消息进行统一处理，这就需要将自己收到的消息，告诉其他的机器，让所有分布式系统中的机器，达到最终的一致，这就是达到共识。

Paxos采取了达成共识的方法是：少数服从多数。这也是我们在生活中常用的。

少数服从多数：只要有超过一半的机器认可某一个消息，那么最终就所有机器都接受这条消息并将它作为本次的结论。而竞选失败的少数派消息，就会被拒绝，并由第一个从客户端处接收到该消息的机器，向客户端发送失败结果，由客户端进行重试，去尝试在下一轮竞选中胜出。

少数服从多数，虽然说起来简单，但是在机器之间怎么传递提议，怎么表决，怎么统计多数，网络传输需要时间，在表决过程中，其他机器收到了新的消息怎么办，都需要一整套机制来解决，下面来一步步探究下：

Paxos角色

Paxos 角色划分：集群中的每个节点都可以充当任一角色

1. Proposer：负责生成提案：也就是在选举中提出提案的人，放到分布式系统里，就是接收到客户端写操作的人。一切行为都由Proposer提出提案开始，Paxos会将提案想要进行的操作，抽象为一个“value”，去在多台机器中传递，最后被所有机器接受。

注意：Paxos 算法允许有多个 Proposer 同时提案，但可能会引起活锁问题

2. Acceptor：负责批准提案：Acceptor 从含义上来说就是除了当前Proposer以外的其他机器，他们之间完全平等和独立，Proposer需要争取超过半数（N/2+1）的 Acceptor 批准后，其提案才能通过，它倡导的“value”操作才能被所有机器所接受

Acceptor 如果只有一个的话，存在单点问题，因此应当有多个

3. Learner：负责获取提案，Acceptor 批准提案后，会将提案发送给所有 Learner。即学习者这个角色，该角色是在达成决议时，对结论的学习者，也即是从其他节点“学习”最终提案内容。

这些角色只是在不同时间下，逻辑上的划分，实际上任何一台机器都可以充当这三个角色之一。

Paxos算法流程

Paxos算法两个阶段

第一阶段：准备阶段

proposer选择一个提案编号n并将prepare请求发送给acceptors中的一个多数派；

acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息(回复消息表示接受accept)，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案；

第二阶段：批准阶段

当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据P2c决定的value（如果根据P2c没有已经接受的value，那么它可以自由决定value）。

在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求。

这个过程在任何时候中断都可以保证正确性。例如如果一个proposer发现已经有其他proposers提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述prepare过程中，如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案。

总结：

执行一个修改操作，分成两个阶段：

1. 准备阶段：Proposer负责接收 client 请求并产生提案，必须由多数派 Acceptor 批准通过提案
2. 接受阶段：提案通过后，再将要执行的修改操作广播给 Acceptor，这次仍然多数派通过，此修改才能生效，可以返回响应给客户端

图解算法流程

如下图所示：

整个算法分成两个阶段：准备阶段，前两个箭头，批准（接受）阶段，后两个箭头。

准备阶段的目的是：第一拦截掉旧的提案，第二找到最新的 acceptValue

对于 Proposer 会处理一下信息：

• 预备阶段只发送提案号，接受阶段发送提案号+值
• 提案号 n 唯一且全局递增，大的提案号有更高优先级
• 如果见到最新已接受的值，就会替换掉 Proposer 自己的值，保证一致性

对于 Acceptor 会持久化以下信息：

• minN（最小提案号），会在预备阶段和接受阶段被更新为更大提案号，会用来决定 Proposer 是否能选中提案
• acceptN（已接受提案号）和 acceptValue（已接受值），会在接受阶段被更新，如果 minN > n 则不会更新

举例说明算法流程

还是拿机器举例

抽象和完善一下这个过程，就是：

1. Prepare准备阶段

   在该阶段，Proposer会尝试告诉所有的其他机器，我现在有一个提案（操作），请告诉我你们是否支持（是否能接受）。其他机器会看看自己是否已经支持其他提案了（是否接受过其他操作请求），并回复给Proposer（如果曾经接受过其他值，就告诉Proposer接受过什么值/操作）。

   1. Acceptor如果已经支持了编号N的提案，那么不会再支持编号小于N的提案，但可以支持编号更大的提案；
   2. Acceptor如果生效了编号为N的提案，那么不会再接受编号小于N的提案，且会在回复时告知当前已生效的提案编号与内容。

2. Accept提交阶段

   在该阶段，Proposer根据上一阶段接收到的回复，来决定行为：

   1. 如果上一阶段超过半数的机器回复说接受提案，那么Proposer就正式通知所有机器去生效这个操作；
   2. 如果上一阶段超过半数的机器回复说他们已经先接受了其他编号更大的提案，那么Proposer会更新一个更大的编号去重试（随机延时）；
   3. 如果上一阶段的机器回复说他们已经生效了其他编号的提案，那么Proposer就也只能接受这个其他人的提案，并告知所有机器直接接受这个新的提案；
   4. 如果上一阶段都没收到半数的机器回复，那么提案取消。
   5. PS：接受其他提案，以及提案取消的情况下，Proposer就要直接告诉客户端该次请求失败了，等待客户端重试即可。

这里可以看到，超过半数以上的机器是个很重要的决定结果走向的条件。

图解说明

一个简单的提案

情况1：正常情况

流程如下：

• Prooser 广播提案号 1
• 有 3 个 Acceptor 接到提案，此时满足 n > minN，那么将 minN 更新为 1
• 3个 Acceptor 成功返回，Prooser 收到的应答过半，但没有遇到更大的 acceptNo 和 acceptValue，因此使用自己的 value X
• Prooser 广播提案号和值 1:X
• 3 个 Acceptor 接到提案号和值，更新状态，返回 minN 值 1 给 P，也就是告诉Prooser 使用提案号1
• Prooser 收到过半应答，并检查发现没有出现 minN > 1，便选中提案值 X

两个提案并发进行

情况2：S3先Accept S1的值，已返回Accept 的ack，再见到S5的提案

• S1 广播提案号 1，想把值更新为 X
• S5 广播提案号 2，想把值更新为 Y
• S1、S2、S3 已经经历了 Accept 阶段并选中值 X
• 关键点，S3 也接到了 S5 的prepare 提案，这时是否会有不一致的情况呢？
• 此时 S3 状态已将 acceptN 和 acceptValue 分别更新为 1:X；再返回 S5 的 ack 时就会将 1:X 返回给 S5
• S5 用返回的 X 替换掉了自己原有的值 Y，并执行后续流程，后续都会同步为 X

情况3：S3先Accept S1的值，再见到S5的提案，再返回Accept的ack

• S1 广播提案号 1，想把值更新为 X
• S5 广播提案号 2，想把值更新为 Y
• S1、S2、S3 已经经历了 Accept 阶段，与例2 不同的是，值 X 还未选中
• 关键点，S3 也接到了 S5 的prepare 提案，这时是否会有不一致的情况呢？
• 此时 S3 状态已将 acceptN 和 acceptValue 分别更新为 1:X；再返回 S5 的 ack 时就会将 1:X 返回给 S5
• S5 用返回的 X 替换掉了自己原有的值 Y，并执行后续流程，后续都会同步为 X

情况4：S3先见到S5的提案，再Accept S1的值

• S1 广播提案号 1，想把值更新为 X
• S5 广播提案号 2，想把值更新为 Y
• 关键点，S3 还未经历 Accept 阶段时，就拿到了 S5 的 prepare 提案，这时是否会有不一致的情况呢？
• S3 在接到 S1 的 accept 请求时，n>=minN 条件不成立，因此没有更新 acceptN 和 acceptValue，并且返回的 minN 是 2
• 对 S1 来说，S3 返回的 minN 大于 n，选中失败；
• 想更新 X 需要发起新一轮提案，也就是后面的提案号3的过程
• 对 S5 来说，accept 阶段发送的是它自己的 2:Y，后续会把值同步为 Y

操作的顺序问题

情况5：先加值操作再复制操作

情况6：先复制操作再加值操作

Paxos优缺点

优点：paxos算法的优点很明显，按照此方法可以对多个数据值达到一致，收敛较好。

缺点：paxos算法的缺点是会出现活锁问题：考虑到一种极端的情况下，有两个proposer依次提出了一系列编号递增的议案，但是最终paxos无法形成最终的议案。

具体场景如下：

情况6：Paxos会产生活锁问题

活锁就是永远不会结束的锁

例如上面例子：

• Acceptor不再应答Proposal 提案号小于等于当前请求的Prepare请求。

• 意味着需要应答Proposal 提案号大于当前请求的Prepare请求。

• 两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）

• 两个值会一直持 失败的状态。

分布式共识算法——gossip协议（图解）

文章目录Gossip协议Gossip协议概念Gossip协议工作流程图解Gossip协议原理消息类型通信方式Gossip协议优点Gossip协议Gossip协议概念说到共识算法，大家首先想到的应该都是Raft、Paxos、Zab算法这类理解起来比较困难的强一致性算法。... 查看详情

分布式共识算法——gossip协议（图解）

文章目录Gossip协议Gossip协议概念Gossip协议工作流程图解Gossip协议原理消息类型通信方式Gossip协议优点Gossip协议Gossip协议概念说到共识算法，大家首先想到的应该都是Raft、Paxos、Zab算法这类理解起来比较困难的强一致性算法。... 查看详情

分布式共识算法——raft算法（图解）(代码片段)

...的完整性选民日志的一致性Raft算法Raft算法概念Raft是一种分布式一致性算法。Raft出现之前，Paxos一直是分布式一致性算法的标准。Paxos难以理解，更难以实现 查看详情

分布式共识算法——raft算法（图解）(代码片段)

...的完整性选民日志的一致性Raft算法Raft算法概念Raft是一种分布式一致性算法。Raft出现之前，Paxos一直是分布式一致性算法的标准。Paxos难以理解，更难以实现 查看详情

raft共识算法

raft共识算法分布式一致性问题如果说，服务器只有一个节点，那么，要保证一致性，没有任何问题，因为所有读写都在一个节点上发生。那如果server端有2个、3个甚至更多节点，要怎么达成一致性呢？下面就来介绍其中一种分布... 查看详情

paxos算法详细图解

1、Paxos算法的应用   Paxos算法及变种算法在分布式系统中应用广泛。   基于Paxos算法的变种有：ZAB、Raft   例如：   ?Zookeeper中的ZAB协议也是Paxos算法的变种。Zookeeper通过ZAB协议实现数据... 查看详情

分布式系统paxos算法(代码片段)

...服务器）保持一致。什么是共识？　　具体来说是这样：分布式系统中由于网络之间通讯可能会中断 查看详情

从分布式一致性到共识机制paxos算法

从分布式系统的CAP理论出发，关注分布式一致性，以及区块链的共识问题及解决。区块链首先是一个大规模分布式系统，共识问题本质就是分布式系统的一致性问题，但是又有很大的不同。工程开发中，认为系统中存在故障（fau... 查看详情

分布式入门：paxos算法

...一致性算法Paxos，具有高度容错特性，是目前公认的解决分布式一致性问题最有效的算法之一。前后写了三篇论文来解释该算法：Basic-PaxosMultiPaxosFastPaxos1一致性问题与共识问题提高分布式系统，就不得不提到分布式系统领域的核... 查看详情

图解分布式一致性协议paxos(代码片段)

Paxos协议/算法是分布式系统中比较重要的协议，它有多重要呢？<分布式系统的事务处理>：GoogleChubby的作者MikeBurrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。<大规模分布式存储系统>：... 查看详情

我啥时候使用像 Paxos 这样的共识算法而不是使用像 Vector Clock 这样的东西？

...2017-09-1903:10:44【问题描述】：我已经阅读了很多关于保证分布式系统中节点之间一 查看详情

详解分布式共识（一致性）算法raft

参考技术A所谓分布式共识（consensus），与CAP理论中的一致性（consistency）其实是异曲同工，就是在分布式系统中，所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法，它与一致性协议这个词也经常互... 查看详情

paxos算法理解

basicpaxosbasepaxos讲的是，分布式环境下，多个节点之间，如何就某个值达成共识，是一种共识算法。例如有一个三副本的kv存储系统，有三个节点，其中两个都接收到更新x的请求(如node1收到的是setx-2,node2收到的是setx=5)，basepaxos的... 查看详情

分布式共识历史简介

...时的PBFT（使用的拜占庭容错算法）算法。paxos是分布式共识算法的灵魂，以至于谷歌在08发表的大数据经典论文《T 查看详情

分布式共识算法随笔——从quorum到paxos(代码片段)

分布式共识算法随笔——从Quorum到Paxos概览:为什么需要共识算法？复制(Replication)是一种通过将同一份数据在复制在多个服务器上来提高系统可用性和扩展写吞吐的策略,。常见的复制策略有主从架构(Leader/Follower),多主架构(Multi-Lea... 查看详情

分布式系统共识机制：一致性算法设计思想

分布式系统共识机制：一致性算法设计思想Paxos算法节点角色算法流程Raft算法节点角色核心机制leader选举日志复制PBFTHotstuff门限签名核心机制二阶段提交协议三阶段提交协议这次以一个宏观的角度去总结自己学习过的一致性... 查看详情

raft算法论文(部分)

原文地址->Raft算法摘要Raft是用于管理被复制的日志的共识算法。它与multi-Paxos算法产生的效果相同，并且和Paxos算法一样高效。但是结构与Paxos不同。这使得Raft算法比Paxos算法更容易理解。也为构建实际系统提供了更好的基础... 查看详情

分布式系统共识机制：一致性算法设计思想

分布式系统共识机制：一致性算法设计思想Paxos算法节点角色算法流程Raft算法节点角色核心机制leader选举日志复制PBFTHotstuff门限签名核心机制二阶段提交协议三阶段提交协议这次以一个宏观的角度去总结自己学习过的一致性... 查看详情