程序员经验分享-hwhale

Paxos算法

2023-05-16

Paxos算法

Paxos算法是一系列共识算法中的一个,其目的就是为了解决共识/一致性问题

这个Github连接中详细的列出了多种共识算法,还有一些工程实践的例子: 腾讯, Zookeeper(Handpoo下的一个分布式框架(Handoop是一个大数据分析和处理的软件平台,用Java写的,可以对大量计算机组成的集群进行海量数据的分布式计算))
算法
工程实践例子

本文主要介绍Paxos算法的背景和运用

三篇Paxos算法的文章: The Part-Time Parliament ,Paxos made simple,Fast Paxos

共识/一致性问题

假设有一组服务器保存了用户的余额，初始是100块，现在用户提交了两个订单，一个订单是消费10元，一个订单是充值50元。由于网络错误和延迟等原因，导致一部分服务器只收到了第一个订单（余额更新为90元），一部分服务器只收到了第二个订单（余额更新为150元），还有一部分服务器两个订单都接收到了（余额更新为140元），这三种保存用户余额的服务器无法就最终余额达成一致。

这就是一致性问题,即在多节点的网络中各节点就某一数据无法达成一致, 我们称解决共识问题的算法为共识算法

造成一致性问题的因素有很多:

  • 网络延迟
  • 不稳定的节点: 节点故障,断电,损坏等因素造成节点无法连入网络

总之一个分布式系统想要数据能够稳定可靠的在节点之间进行交流,就需要解决共识/一致性问题

FLP不可能定理

一般来说,一个问题都存在理论上的下限,例如对于囚徒困境问题,我们可以使用博弈论来进行分析,得出囚徒困境的最坏结果

对于一致性问题,我们也可以证明一致性问题的最差结果,即FLP定理. FLP定理由Fischer，Lynch和Patterson三人于1985年发表的论文中给出了证明,主要使用的是图论

FLP定理给出了异步分布式系统的共识问题的最差情况: 无解, 即在网络通信可靠的情况下,可扩展的异步分布式系统的共识问题是无解的, 因此不存在一个可以解决任意场景下的共识问题的算法

因此设计对任意场景下都适用的共识算法是徒劳的.但是我们可以开发针对某些特定场景下的共识算法,即在加强条件情况下的共识算法

Paxos算法

Paxos算法前提

明确一个算法的假设/前提/适用条件/使用场景才能知道该在什么情况下使用这个算法,所以先介绍Paxos算法的假设

通过前面的FLP定理可知,不存在通用的共识算法,因此==Paxos算法是针对非拜占庭场景下的共识算法==

拜占庭问题

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间,甚至还可以不传递消息。困扰这些将军的问题是，他们不确定通信兵中是否有叛徒，叛徒可能擅自变更自身传递的消息,即可以给其他军队带去恶意的消息。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢得战斗

简单的来说,拜占庭问题的核心是: 不可靠的通信

因此,Paxos算法的前提就是具备可靠的通信,节点间通信的可靠(消息能否送达), 和节点的安全性(节点不会被入侵而恶意攻击网络)就不是Paxos算法考虑的问题了.

Paxos算法的具体操作

Paxos算法的理论推导很麻烦, 特别绕, 但是有助于理解Paxos算法, 实际上Paxos算法的运用很简单

Paxos算法中的概念

Paxos算法是分轮次的,每一轮称为一个Paxos过程,每一轮都将会得到一个提案

Paxos算法中将网络中所有的节点分成了三种角色:

  • 提案者(Proposer)
    提案者负责提出提案,提案可以是任何需要达成共识/一致的内容, 比如一个日志,一个数据等等
    不同的提案者可以提出不同的甚至矛盾的内容,例如某个提案提议“将变量 X 设置为 1”, 另一个提案者提议“将变量 X 设置为 2”
    但对同一轮 Paxos 过程，最多只有一个提案的内容被批准
  • 接受者(Acceptor)
    接受者负责接收提案,并明确是接收还是拒绝
    只有被半数以上的接受者接收的提案才会被批准/通过
  • 学习者(Learner)
    学习者负责获取并同步最终通过/批准的提案,即明确最终的提案
    具体来说就是学习者通过读取各个提案者对这一轮各自提案的选择结果,如果某个提案被超过半数接受者通过,则学习者学习到了
    这个提案

此外对于提案还有分类:

  • 提案(Proposal) : 提案是一个由提案编号和提案值组成的键值对，即[proposalNo, proposalValue]([提案编号, 提案内容])
  • 共识(sensus) : 被半数以上的接受者接收的提案, 提案编号是最终能达成共识的关键

还有一些约束条件:

  • 提案的编号全局唯一且递增
  • 每个接受者都会记录已响应过的提案的最大编号，并且承诺不会接受比此提案号小的提案
  • 如果一个提案的v值(即提案的内容)被大多数接收者接收，那后续的所有被接受的提案中也必须包含先前被接受的提案的v值（提案由一个或多个v值和一个提案编号组成）
  • 提案者和接受者可以是同一个节点, 这有助于提案ID的增大

Paxos算法的流程

Paxos算法整体分为两步, 准备阶段(每个提案者提出自己的提案)和选举阶段(学习者确定最终的提案)

准备阶段

  1. 提案者生成全局唯一且递增的提案编号,ProposalID,并且向网路中的所有节点(接受者)发送Prepare请求
    Prepare请求不携带ProposalValue, 即不携带具体的提案内容,只有提案编号
  2. 接受者接收到提议者发来的Prepare请求后, 判断Prepare请求中的提案编号和之前已经响应的所有提案的编号大
    a. 如果大于先前所有的提案编号, 则
    a1. 在本地持久化该编号
    a2. 回复Prepare请求,并带上该接受者先前已经接受的提案中最大编号提案的提案编号和内容
    若此时还没有已Accept的提案，则返回的提案内容为空
    a3. 做出承诺: 不会接受任何小于当前更新后提案编号的提案
    b. 如果小于或等于先前所有的提案编号,则
    不回复Prepare请求或者回复Error

选举阶段

  1. 提案者发送Accept请求
    经过一段时间之后,提案者已经接收到一些接受者返回的请求,有以下三种情况:
    a. 回复数量 > 一半接受者数量, 且所有回复中的值为空, 则提案者向所有接受组合发出Accept请求,并带上自己的提案内容
    b. 回复数量 > 一半接受者数量, 且所有回复中的值不为空, 则提案者向所有接受组合发出Accept请求,并带上提议者接收到所
    有接受者的回复中最大的提案编号和对应的提案内容(把编号最大的提案的内容当做自己的提案内容)
    c. 回复数量 > 一半接受者数量, 且所有回复中的值不为空, 则尝试生成更大的ProposalID,然后结束此次提案,等待下一轮的准
    备阶段发出自己的提案
  2. 接受者应答提案者发来的Accept请求
    接受者收到Accept请求后,判断:
    a. 收到的提案编号 >= 先前最大的提案编号(一般情况下是等于)，则回复提交成功，并持久化新接收到的提案编号和提案内容
    b. 收到的提案编号 < 先前最大的提案编号, 则不回复或者回复提交失败
  3. 提案者统计接受者返回的应答
    经过一段时间后,提案者收集到一些接受者回复的信息,有几种情况:
    a. 回复数量 > 一半的接受者数量, 则表示提交value成功. 此时, 可以发一个广播给所有提案者和学习者,通知它们自己的提
    提案已经被通过,并带上自己的提案内容
    b. 回复数量 <= 一半的接受者数量，则尝试生成更大的 ProposalID, 然后结束此次提案,等待下一轮的准备阶段发出自己的提
    案
    c. 收到一条提交失败的回复, 则尝试生成更大的 ProposalID, 然后结束此次提案,等待下一轮的准备阶段发出自己的提案

Paxos算法时序图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4SMOBQDb-1608098281783)(图片/TB1lKX_gbGYBuNjy0FoXXciBFXa-932-698.png)]

Paxos算法的一些讨论

如何产生唯一的编号？

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

为什么在Paxos运行过程中，半数以内的接受者失效都能运行?

  1. 如果半数以内的接受者失效时还没确定最终的提案内容, 则此时, 所有的提议者实际上会发生竞争,最终会有一个提案会成功提交。再这之后,会有半过数的接受者以这个提案的内容提交成功。
  2. 如果半数以内的接受者失效时已确定最终的提案内容, 则此时, 所有提案者提交时必须以最终的提案的内容提交, 此值也可以被获取,并不再修改

如果过半数接受者失效,则最终能否产生一个提案?

不行,因为最终提案的产生要求具有半数以上的接受者同意

不过我自己的一个想法就是可以实行动态的半数接受者,即只要当前可用的接受者的半数即可(初步想法,没细想)

效时已确定最终的提案内容**, 则此时, 所有提案者提交时必须以最终的提案的内容提交, 此值也可以被获取,并不再修改

如果过半数接受者失效,则最终能否产生一个提案?

不行,因为最终提案的产生要求具有半数以上的接受者同意

不过我自己的一个想法就是可以实行动态的半数接受者,即只要当前可用的接受者的半数即可(初步想法,没细想)

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

paxos

Paxos算法 的相关文章

  • 如何在手机或平板上编写代码?

    下面给大家推荐一款免费的 在线协作式 基于浏览器的 IDE的在线编程网站 支持语言包括 Java C 43 43 C C JavaScript CSS PHP等50多种主流开发语言 地址 The collaborative browser

  • 羊了个羊, 低配版开源代码来啦~

    前几天朋友圈突然被一个小游戏 羊了个羊 刷屏了 xff0c 出于好奇我也打算小玩一把试试 xff0c 结果没想到上头了 游戏的玩法非常简单 xff0c 类似 消消乐 xff0c 从一堆方块中找到相同图案的 3 个方块并消除即可 但没想到 x

随机推荐

  • MySQL 使用索引和不使用索引的区别(附17W条数据SQL文件)

    MySQL 使用索引可以减少查询的时间 xff0c 而不使用索引的查询会更加耗时 xff0c 因为MySQL需要扫描整个表 此外 xff0c 使用索引可以提高查询的性能 xff0c 同时也可以提高查询的可读性和可维护性 换句话来说 使用索引

  • 如何使用AI来帮你写代码(Cursor使用教程)

    x1f4ac 产品介绍 cursor是一个新的Ide xff0c 它使用Ai来帮助您重构理解调试并使用Cursor编写代码我们的目标是使构建软件的过程更快 更愉快 我们从头开始构建了一个代码编辑器 xff0c 对我们的第一个功能进行了原型设

  • [Java多线程-基础] 如何定位线程中的死锁问题?

    x1f512 死锁代码 下面提供的代码演示了死锁的情况 程序创建了两个线程 xff0c 线程1和线程2 xff0c 它们都试图以不同的顺序获取两个不同的资源 xff0c resource1和resource2 线程1首先获取resource

  • [Java多线程-基础] 避免线程死锁问题(ReentrantLock的使用)

    ReentrantLock 的设计初衷是为了提供一种比 synchronized 更加灵活和可控的锁机制 与 synchronized 相比 xff0c ReentrantLock 提供了更多的功能 xff0c 如可重入性 公平锁和中断锁等

  • IDEA插件：智能代码生成器，附带注释和性能/安全检测功能

    x1f680 1 安装插件 在插件中搜索关键字 biot 点击安装 x1f680 2 代码生成 右侧的侧边栏点击biot后 在下方的输入框中输入你要问的内容 x1f680 3 biot AI 选中选区中的代码 点击鼠标右键让ai来帮你改代码

  • 安装Windows Server 2016 服务器 标准版

    注意事项 xff1a 安装带桌面版的 管理员密码设置 xff0c 要 注意大小写加数字 xff0c 不然会设置失败 安装文件下载 xff1a MSDN 我告诉你 PE U盘 微PE 服务器的驱动 xff0c 可以自己到对应服务器厂家的官网上

  • 第五节：基于Pytorch的相关可视化

    第五节 xff1a 基于Pytorch的相关可视化 在Pytorch发布后 xff0c 网络及训练过程的可视化工具也相应的被开发出来来帮助用户监督所建立的模型的结构和训练过程 本章将讲解HiddenLayer库 xff0c HiddenLa

  • 第六节：Pytorch实现全连接神经网络

    第六节 xff1a Pytorch实现全连接神经网络 前面的五节中 xff0c 我们讲解了使用PyTorch搭建一个神经网络中需要的需要各种技巧 xff0c 包括 xff1a 网络的搭建 选择不同的实践技巧 xff08 优化器选择 学习率下

  • 使用Visual Studio Code开发Arduino踩坑日记(持续更新)

    使用Visual Studio Code开发Arduino踩坑日记 持续更新 文章目录 使用Visual Studio Code开发Arduino踩坑日记 持续更新 1 在browse path中未找到包含文件问题描述问题分析解决思路解决过

  • 小白安装Ubuntu 18.04 LTS

    文章目录 小白安装Ubuntu 18 04 LTS作者 xff1a 王仕鸿日期 xff1a 2020 10 10 前言 xff08 可跳过 xff09 Ubuntu介绍操作系统介绍Ubuntu介绍 安装Ubuntu 18 04 LTS步骤一

  • 1_ROS基础

    ROS基础 本章讲解ROS中最基础的概念 不明白这些概念是没法学懂ROS的 学习了这些概念 后面我们将通过实操来在实践的过程中进一步体会 ROS是什么 ROS Robot Operating System 机器人操作系统 是一个提供一系列程

  • 2_ROS中的命令行工具

    ROS中的命令行工具 ROS中为我们提供了丰富的命令行工具 帮助我们进行代码的编写 调试 测试 框架的搭建 数据的显示等等 大图如下 所有的命令大致可以分为四类 分别是运行相关命令 编译相关命令 包制作管理相关命令 项目创建相关命令 下面进

  • 3_ROS创建工作空间和功能包

    3 ROS创建工作空间和功能包 前面我们讲解了ROS中的核心概念和使用ROS进行开发时候必须用到的命令行工具 下面我们就正式开始ROS中的开发 我们首先从创建工作空间和功能包开始 1 工作空间WorkSpace 工作空间是ROS中非常重要的

  • 4_Publieher的编程实现

    4 Publisher的编程实现 我们前面讲解了如何创建工作空间和功能包 但是我们都仅仅只创建了一个空的工作空间和功能包 什么都没有实现 我们想要进一步为功能包添加功能 就不可避免的需要添加Publisher和Subscriber 下面我们

  • 1.Latex介绍

    Latex介绍 本人鸿神 目前就读于XJTU 是一个即将开始科研的小白 既然做科研未来就无法避免发表论文 而发表论文就需要用到一系列的工具 Latex就是其中之一 谨以此文记录我的科研路 也希望Latex这一系列文章能够帮到各位 1 什么是

  • 2.Latex安装和TeXworks Editor基础

    二 Latex安装和TeXworks Editor使用教程 上一章我们讲解了什么是Latex和为什么我们要学习Latex 从这一章开始我们就要正式开始学习Latex 就像前面所讲的 Latex包含编译器和编辑器 我们需要在编辑器中编写夹杂代

  • 关于“ErrorFlash Download failed“Cortex-M3”的解决办法

    首先 xff0c 将仿真器连接电脑 xff0c 然后打开KEIL xff0c 点击FLash gt Erase xff0c 擦除Flash试一下 如果擦除不成功 xff0c 那么应该是的STM32的Flash被锁了 xff0c 要解锁一下

  • 3.Latex语法基础:命令与环境

    三 Latex语法基础 命令与环境 前面我们已经做好了开始编写Latex的一切准备工作 从这章开始 我们将开始讲解Latex语法 本章将讲解Latex语法的基础 命令与环境 1 命令与环境 命令 什么是命令 不同于其他编程语言 C C 43

  • Arduino多种传感器使用方法

    Arduino项目 智能窗户 前段时间参加了一个Arduino的比赛 具体内容就是用Arduino设计一个项目出来 我在的队伍的设计的项目就是智能窗户 智能窗户可以采集本地传感器采集到的环境参数 根据参数具有一套内部的逻辑判断 可以对温度

  • Paxos算法

    Paxos算法 Paxos算法是一系列共识算法中的一个 其目的就是为了解决共识 一致性问题 这个Github连接中详细的列出了多种共识算法 还有一些工程实践的例子 腾讯 Zookeeper Handpoo下的一个分布式框架 Handoop是

热门标签