分布式系统设计之共识算法—2PC、3PC、 Paxos

简介: 分布式系统设计之共识算法—2PC、3PC、 Paxos

分布式共识协议有什么作用?

共识问题分布式计算中最基本的概念之一,是让分布式系统中的一组节点就某事达成一致的问题的一个价值、一个行动方案或一个决定。达成共识允许分布式系统充当单个实体,每个单独的节点都知道并同意整个网络的行为。

例如,共识的一些可能用途是:

  • 分布式事务处理
  • 分布式不同节点间同步时钟
  • 决定分布式算法的下一阶段(这是著名的复制状态机方法)
  • 选举一个领导节点来协调一些更高级别的协议

Google Chubby Service的发明者 Mike Burrows 说“只有一种共识协议,那就是 Paxos”

1 两阶段提交(2PC)协议

1.1 概念

两阶段提交又称 2PC,是一个非常经典的 强一致、中心化的原子提交协议。两阶段提交协议经常用来实现分布式事务,在两阶段协议中,系统一般包含两类节点:一类是 协调者,通常一个系统中只有一个;另一类是事务的 参与者,一般包含多个,在提交过程中任何节点都能当做协调者发起2PC,不必特别选举。

1.2 具体流程

2PC协议的两个步骤

  1. 请求(投票)阶段:联系每一位参与者,提出价值并收集他们的回应。
  2. 提交阶段:如果每个人都同意,请再次联系每个参与者,让他们知道。否则,请联系每个参与者以中止共识。
    网络异常,图片无法展示
    |

1.3 问题

  • 性能问题
    无论是在第一阶段的过程中,还是在第二阶段,所有的参与者资源和协调者资源都是被锁住的,只有当所有节点准备完毕,事务 协调者 才会通知进行全局提交,参与者 进行本地事务提交后才会释放资源。这样的过程会比较漫长,对性能影响比较大。
  • 单节点故障
    由于 协调者 的重要性,一旦 协调者 发生故障。参与者 会一直阻塞下去。尤其在第二阶段,协调者 发生故障,那么所有的 参与者 还都处于锁定事务资源的状态中,而无法继续完成事务操作。

2 三阶段提交(3PC)协议

2.1 概念

3PC是2PC的改进版本。3PC主要是为了解决两阶段提交协议的阻塞问题,2PC 存在的问题是当协作者崩溃时,参与者不能做出最后的选择。因此参与者可能在协作者恢复之前保持阻塞。改进措施:

(1) 引入超时机制,同时在 协调者 和 参与者中都引入超时机制。

(2) 在 2PC 的第二阶段中插入一个准备阶段,保证了在最后提交阶段之前各参与节点的状态是一致的。

也就是说,除了引入超时机制之外,3PC 把 2PC 的准备阶段再次一分为二,这样三阶段提交就有 CanCommit、PreCommit、DoCommit 三个阶段。

2.2 具体步骤

将 2PC 的第二阶段——“提交”——分成两个子阶段。第一个是“准备提交”阶段。当协调者在第一阶段收到一致的“是”票时,它会将此消息发送给所有副本。收到此消息后,副本进入一种能够提交事务的状态 - 通过获取必要的锁等 - 但至关重要的是,它们不会做任何他们以后无法撤消的工作。然后他们回复协调员,告诉它“准备提交”消息已收到。

网络异常,图片无法展示
|


2.3 问题

  • 依然没有完全解决数据不一致的问题

3 Paxos协议

Paxos 起来很像 2PC。提议者向接受者发送“准备”请求。当接受者表示同意接受提案时,提议者向接受者发送提交请求。最后,接受者回复提供者,表明提交请求成功或失败。一旦足够多的接受者提交了价值并通知了提议者,协议就会终止。

Paxos 为 2PC 添加了两个重要的机制。

  • 对请求进行排序,以便确定应该接受两个提案中的哪一个。
  • 当大多数接受者表示他们已经决定时,考虑接受一个提案。这与 2PC 不同,后者只有在每个接受者都同意的情况下才会接受提案。这导致了 2PC 的阻塞特性,其中单个故障节点可能导致协议永远不会终止,而提议者等待永远不会到来的回复。相反,在 Paxos 中,近一半的节点可能无法回复,协议仍将正确继续。

网络异常,图片无法展示
|


Paxos中两个重要的角色:

提议者:

  1. 向大多数接受者提交编号为n 的请求。等待大多数接受者回复。
  2. 如果多数人回复“同意”,他们还将发回他们已经接受的任何提案的价值。选择其中一个值,并发送带有提案编号和值的“提交”消息。如果尚未接受任何值,请使用您自己的值。相反,如果多数人回复“拒绝”,或未能回复,则放弃提案并重新开始。
  3. 如果大多数人使用“已接受”消息回复您的提交请求,则认为协议已终止。否则,放弃提案并重新开始。

接受者:

  1. 收到提案后,将其编号与您已经同意的编号最高的提案进行比较。如果新提案更高,请回复“同意”您已接受的任何提案的价值。如果它较低,则回复“拒绝”,以及最高提案的序列号。
  2. 当收到“提交”消息时,如果 a) 值与任何先前接受的提案相同并且 b) 它的序列号是您同意的最高提案号,则接受它。否则,拒绝它。

  3. 网络异常,图片无法展示
    |

参考文章:

www.the-paper-trail.org/post/2008-1…

www.the-paper-trail.org/post/2008-1…

www.the-paper-trail.org/post/2009-0…

blog.csdn.net/qq_38289815…


相关文章
|
9天前
|
消息中间件 算法 分布式数据库
Raft算法:分布式一致性领域的璀璨明珠
【4月更文挑战第21天】Raft算法是分布式一致性领域的明星,通过领导者选举、日志复制和安全性解决一致性问题。它将复杂问题简化,角色包括领导者、跟随者和候选者。领导者负责日志复制,确保多数节点同步。实现细节涉及超时机制、日志压缩和网络分区处理。广泛应用于分布式数据库、存储系统和消息队列,如Etcd、TiKV。其简洁高效的特点使其在分布式系统中备受青睐。
|
9天前
|
算法 分布式数据库
Paxos算法:分布式一致性的基石
【4月更文挑战第21天】Paxos算法是分布式一致性基础,由Leslie Lamport提出,包含准备和提交阶段,保证安全性和活性。通过提案编号、接受者和学习者实现,广泛应用于分布式数据库、锁和配置管理。其简单、高效、容错性强,影响了后续如Raft等算法,是理解分布式系统一致性关键。
|
8天前
|
算法 Go 分布式数据库
构建高可用的分布式数据库集群:使用Go语言与Raft共识算法
随着数据量的爆炸式增长,单一数据库服务器已难以满足高可用性和可扩展性的需求。在本文中,我们将探讨如何使用Go语言结合Raft共识算法来构建一个高可用的分布式数据库集群。我们不仅会介绍Raft算法的基本原理,还会详细阐述如何利用Go语言的并发特性和网络编程能力来实现这一目标。此外,我们还将分析构建过程中可能遇到的挑战和解决方案,为读者提供一个完整的实践指南。
|
9天前
|
算法
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
【免费】基于ADMM算法的多微网电能交互分布式运行策略(matlab代码)
|
9天前
|
算法 Serverless 调度
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
|
9天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
1天前
|
机器学习/深度学习 算法
基于BP神经网络的QPSK解调算法matlab性能仿真
该文介绍了使用MATLAB2022a实现的QPSK信号BP神经网络解调算法。QPSK调制信号在复杂信道环境下受到干扰,BP网络能适应性地补偿失真,降低误码率。核心程序涉及数据分割、网络训练及性能评估,最终通过星座图和误码率曲线展示结果。
|
2天前
|
机器学习/深度学习 算法 计算机视觉
基于yolov2深度学习网络模型的鱼眼镜头中人员检测算法matlab仿真
该内容是一个关于基于YOLOv2的鱼眼镜头人员检测算法的介绍。展示了算法运行的三张效果图,使用的是matlab2022a软件。YOLOv2模型结合鱼眼镜头畸变校正技术,对鱼眼图像中的人员进行准确检测。算法流程包括图像预处理、网络前向传播、边界框预测与分类及后处理。核心程序段加载预训练的YOLOv2检测器,遍历并处理图像,检测到的目标用矩形标注显示。
|
5天前
|
算法
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
MATLAB 2022a仿真实现了LDPC码的性能分析,展示了不同码长对纠错能力的影响。短码长LDPC码收敛快但纠错能力有限,长码长则提供更强纠错能力但易陷入局部最优。核心代码通过循环进行误码率仿真,根据EsN0计算误比特率,并保存不同码长(12-768)的结果数据。
26 9
m基于BP译码算法的LDPC编译码matlab误码率仿真,对比不同的码长
|
7天前
|
算法
MATLAB|【免费】融合正余弦和柯西变异的麻雀优化算法SCSSA-CNN-BiLSTM双向长短期记忆网络预测模型
这段内容介绍了一个使用改进的麻雀搜索算法优化CNN-BiLSTM模型进行多输入单输出预测的程序。程序通过融合正余弦和柯西变异提升算法性能,主要优化学习率、正则化参数及BiLSTM的隐层神经元数量。它利用一段简单的风速数据进行演示,对比了改进算法与粒子群、灰狼算法的优化效果。代码包括数据导入、预处理和模型构建部分,并展示了优化前后的效果。建议使用高版本MATLAB运行。