b2b网站建设费用/长春网站优化团队
提到分布式算法,就不得不提 Paxos 算法,在过去几十年里,它基本上是分布式共识的代名词,因为当前一批常用的共识算法都是基于它改进的。比如,Fast Paxos 算法、Cheap Paxos、Raft 算法等。
由莱斯利·兰伯特(Leslie Lamport)于1990年首次提出,并在后续文章中进一步阐述。Paxos 算法旨在解决在一个可能发生网络分区、节点失效或其他异常情况的分布式环境中,如何让所有参与决策的节点对某个值达成一致同意的问题。
兰伯特提出的Paxos总共包含两部分:
- 一个是 Basic Paxos 算法,描述的是多节点之间如何就某个值(提案Value)达成共识
- 另一个是 Multi-Paxos 思想,描述的是执行多个 Basic Paxos 实例,就一系列值达成共识
Basic Paxos
先来看一个例子
假设有一个分布式集群,由三个节点 A、B、C 组成,提供只读 KV 存储服务,创建只读变量的时候,必须要先写入数据,而且这个数据后续不能被修改。因此一个节点写入只读变量后就不能再修改了,所以所有节点必须要先对只读变量达成共识,然后所有节点在一次创建这个只读变量。
当有多个客户端(如客户端1、2)访问这个系统试图创建同一个只读变量(如X),客户端1试图创建值为3的X,客户端2试图创建值为7的X,这样要如何达成共识,实现各节点上X值一直呢?
为了帮助人们更好的理解 Basic Paxos 算法,兰伯特在讲解时,也使用了一些独有而且比较重要的概念,提案、准备(Prepare)请求、接受(Accept)请求、角色等等,其中最重要的就是角色。因为角色是对 Basic Paxos 中最核心的三个功能的抽象,比如,由接受者(Acceptor)对提议者的值进行投票,并存储接受的值。
角色划分
在 Basic Paxos 中,由提议者(Proposer)、接受者(Acceotor)、学习者(Learner)三种角色,如图:
- 提议者(Proposer):提议一个值,用于投票表决。为了方便演示,可以把客户端1和2看做是提议者。但在绝大多数场景中,集群中收到客户端请求的节点,才是提议者。这样做的好处是,对业务代码没有侵入性,也就是说,我们不需要在代码中实现算法逻辑,就可以像使用数据库一样访问后端数据。
- 接受者(Acceptor):对每个提议的值进行投票,并存储接受的值,比如 A、B、C 三个节点。一般来说,集群中的所有节点都在扮演接受者的角色,参与共识协商,并接受和存储数据。
这里需要强调一下:前面不是说接收客户端请求的节点是提议者吗?这里怎么又是接受者呢?这是因为一个节点(或进程)可以身兼多个角色。想象一下,一个 3 节点的集群,1 个节点收到了请求,那么该节点将作为提议者发起二阶段提交,然后这个节点和另外 2 个节点一起作为接受者进行共识协商,就像下图的样子:
- 学习者(Leaner):被告知投票的结果,接受达成的共识值,存储保存,不参与投票的过程。一般来说,学习者是备份节点,比如“Master-Slave”模型中的Slave,被动的接受数据,容灾备份。
达成共识过程
有这样一个场景,假如你所在的公司有一个新项目需要开发,业务比较复杂,你的领导给组内每个成员下发了任务,要求每人写一个项目方案,最终开会讨论采用哪套方案,为了区分每套方案,每个方案都有一个标识,称为提案编号,来唯一标识。
与你的做法类似,在 Basic Paxos 中,兰伯特也使用提案代表一个提议。不过在提案中,除了提案编号,还包含了提议值。使用 [n, v] 表示一个提案,n 为提案编号,v 为提议值。
整个共识协商是分两个阶段进行的。假设客户端 1 的提案编号为 1,客户端 2 的提案编号为5,并假设节点 A、B 先收到来自客户端1的准备请求,节点 C 先收到来自客户端 2 的准备请求。
准备(Prepare)阶段
先来看第一阶段,首先客户端 1、2 作为提议者,分别向所有接受者发送包含提案编号的准备请求:
在准备请求时不需要准备提议的值的,只需要携带提案编号就可以了,这是容易误解的地方。接着,当A、B收到提案编号为 1 的准备请求,节点 C 收到提案编号为 2 的准备请求后,将进行这样的处理:
- 由于之前没有通过任何提案,所以节点 A、B 将返回一个"尚无提案"的响应。也就说节点 A和 B 在告诉提议者,我之前没有通过任何提案,并承诺以后不在响应提案编号小于等于 1 的准备请求,不会通过编号小于1的提案。
- 节点 C 也是如此,它将返回一个“尚无提案”的响应,并承诺以后不在响应提案编号小于 5 的提案,不会通过提案编号小于5的提案。
另外,当节点 A、B 收到提案编号为 5 的准备请求,和节点 C 收到提案编号为 1 的准备请求的时候,将进行这样的处理:
- 当节点 A、B 收到提案编号为 5 的准备请求时,因为提案编号 5 大于他们之前响应的准备请求的提案编号 1,而且两个节点都没有通过任何提案,所以它将返回一个“尚无提案”的响应,并承诺以后不在响应提案编号小于 5 的准备请求,不会通过提案小于 5 的提案。
- 当节点 C 收到提案编号为 1 的准备请求时,由于天编号 1 小于之前响应的准备请求的提案编号 5,所以丢弃该准备请求,不做响应。
接受(Acceptor)阶段
第二个阶段也就是接受阶段,首先客户端 1、2 在收到大多数节点的准备响应之后,会分别发送接受请求:
- 当客户端 1 收到大多数的接受者(节点A、B)的准备响应之后根据响应中提案编号最大的提案值,设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空,所以就把自己的提议值 3 作为提案的值,发送接受请求 [1, 3]。
- 当客户端2收到大多数的接受者的准备响应后(节点A、B、C),根据响应中提案编号最大的提案值,来设置接受请求中的值。因为该值来自节点 A、B、C 准备响应都为空,所以就把自己的提议值7作为提案的值,发送接受请求 [5, 7]。
当三个节点接受到两个客户端的接受请求时,会进行这样的处理:
- 当节点 A、B、C 接受到请求 [1, 3] 的时候,由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5,所以提案 [1, 3] 将被拒绝。
- 当节点 A、B、C 接受到请求 [5, 7] 的时候,由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5,所以就通过提案 [5, 7],也就是接受了值 7,三个节点就 X 值为 7 达成共识。
如果集群中有学习者,当接受者通过了一个提案时,就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案,那么它也通过该提案,接受该提案的值。
Multi-Paxos算法
Basic Paxos 只能就单个值(Value)达成共识,一旦遇到为一系列的值实现共识的时候,它就不管用了。虽然兰伯特提到可以通过多次执行 Basic Paxos 实例(比如每接收到一个值时,就执行一次 Basic Paxos 算法)实现一系列值的共识。但是,读完论文后,虽然每个英文单词都能读懂,但还是不理解兰伯特提到的 Multi-Paxos,为什么 Multi-Paxos 这么难理解呢?
兰伯特并没有把 Multi-Paxos 讲清楚,只是介绍了大概的思想,缺少算法过程的细节和编程所必须的细节。这就导致了每个人实现的 Multi-Paxos 都不一样。不过从本质上看,大家都是在兰伯特提到的 Multi-Paxos 思想上补充细节,设计自己的 Multi-Paxos 算法,然后实现它(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)。
所以这里补充一下,兰伯特提出的 Multi-Paxos 是一种思想,不是算法。而 Multi-Paxos 是一种统称,它是指基于 Multi-Paxos 思想,通过多个 basic-Paxos 实现一系列值的共识算法。这一点尤为重要。
到这里 Paxos 共识算法就介绍完了。
相关文章:

探索分布式强一致性奥秘:Paxos共识算法的精妙之旅
提到分布式算法,就不得不提 Paxos 算法,在过去几十年里,它基本上是分布式共识的代名词,因为当前一批常用的共识算法都是基于它改进的。比如,Fast Paxos 算法、Cheap Paxos、Raft 算法等。 由莱斯利兰伯特(L…...

使用 ES|QL 优化可观察性:简化 Kubernetes 和 OTel 的 SRE 操作和问题解决
作者:Bahubali Shetti 作为一名运营工程师(SRE、IT 运营、DevOps),管理技术和数据蔓延是一项持续的挑战。 简单地管理大量高维和高基数数据是令人难以承受的。 作为单一平台,Elastic 帮助 SRE 将无限的遥测数据&#…...

Docker 第十九章 : 阿里云个人镜像仓使用
Docker 第十九章 : 阿里云个人镜像仓使用 本章知识点: 如何创建镜像库,如何设置密码,如何登录与退出个人镜像仓,如何本地打镜像,如何将本地镜像推送到个人镜像库。 背景 在项目YapiDocker部署中,因读取mongo:latest 版本不一致,导致后续执行步骤的异常。遇到此场景…...

二、系统知识笔记-系统架构概述
一、系统架构定义 系统架构是指对一个系统的整体结构和组成部分进行描述和规划的过程。系统架构定义决定了系统的设计、开发和实施过程中的关键方向和决策。是系统的骨架和根基,支撑和链接各个部分,包括组件、连接件、约束规范以及指导这些内容设计与演…...

【高德地图】Android高德地图绘制标记点Marker
📖第4章 Android高德地图绘制标记点Marker ✅绘制默认 Marker✅绘制多个Marker✅绘制自定义 Marker✅Marker点击事件✅Marker动画效果✅Marker拖拽事件✅绘制默认 Infowindow🚩隐藏InfoWindow 弹框 ✅绘制自定义 InfoWindow🚩实现 InfoWindow…...

每天一个知识点 - 如何快速熟悉后端项目
入职一家新公司的时候,不可避免的就是接触到新公司的项目,有些项目一启动就是好几年,业务功能极其复杂,下面我总结几个方法让大家快速熟悉后端项目(图文结合) 用例图简析 用例是系统中的一个功能单元&…...

如何将cocos2d-x js打包部署到ios上 Mac M1系统
项目环境 cocos2d-x 3.13 xcode 12 mac m1 big sur 先找到你的项目 使用xcode软件打开上面这个文件 打开后应该是这个样子 执行编译运行就好了 可能会碰到的错误 在xcode11版本以上都会有这个错误,这是因为iOS11废弃了system。 将上面代码修改为 #if (CC_TARGE…...

pdffactory pro 8中文破解版
详细介绍 PdfFactory,PDF文档虚拟打印机,无须Acrobat即可创建Adobe PDF文件,创建PDF文件的方法比其他方法更方便和高效。支持将多个文档整合到一个PDF文件、增加字体和便签、PDF加密、去水印、压缩优化。 FinePrint,Windows虚拟…...

常用ADB命令整理已经ADB键盘输入
我们在测试Android app过程中 需要经常更换安装包的操作 熟练使用ADB命令可以提升测试效率 * 查看设备 adb devices ps这个命令是查看当前连接的设备, 连接到计算机的android设备或者模拟器将会列出显示 若有多台安卓设备,可以通过在adb后面加上 -s <设备id>…...

buuctf_N1BOOK_粗心的小李
题目: 看完题目,git下载文件?然后将.git文件传到线上环境?(which 会造成git泄露的安全威胁)<这个背景抱歉我不太了解哈,可能后续有补充> 这里主要记录做法过程: 工具…...

爬取链家二手房房价数据存入mongodb并进行分析
实验目的 1.使用python将爬虫数据存入mongodb; 2.使用python读取mongodb数据并进行可视化分析。 实验原理 MongoDB是文档数据库,采用BSON的结构来存储数据。在文档中可嵌套其他文档类型,使得MongoDB具有很强的数据描述能力。本节案例使用的…...

论文阅读:Ground-Fusion: A Low-cost Ground SLAM System Robust to Corner Cases
前言 最近看到一篇ICRA2024上的新文章,是关于多传感器融合SLAM的,好像使用了最近几年文章中较火的轮式里程计。感觉这篇文章成果不错,代码和数据集都是开源的,今天仔细读并且翻译一下,理解创新点、感悟研究方向、指导…...

一键获取电商平台商品信息,快速提高电商业务效率
阿里巴巴店铺所有商品API接口技术全解析 一、引言 在阿里巴巴这个全球领先的电商平台上,店铺所有商品API接口(item_search_shop)为开发者提供了一个便捷的途径,能够获取店铺的所有商品信息。通过这一接口,无论是数据…...

vue 中实现音视频播放进度条(满足常见开发需求)
由于开发需要,作者封装了一个音视频播放进度条的插件,支持 vue2 及 vue3 ,有需要的朋友可联系作者,下面是对该款插件的介绍。 插件默认样式👇(插件提供了多个配置选项,可根据自身需求进行个性化…...

【广度优先搜索】【网格】【割点】1263. 推箱子
作者推荐 视频算法专题 涉及知识点 广度优先搜索 网格 割点 并集查找 LeetCode:1263. 推箱子 「推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。 游戏地图用大小为 m x n 的网格 grid 表示,其中每个元素可以是墙、地板或…...

论文精读--GPT1
把transformer的解码器拿出来,在没有标号的大量文本数据上训练一个语言模型,来获得预训练模型,然后到子任务上微调,得到每个任务所需的分类器 Abstract Natural language understanding comprises a wide range of diverse tasks…...

C/C++的内存管理(1)
内存管理 C与C的内存分布C语言中动态内存管理方式回顾C内存管理的方式 C与C的内存分布 我们学习C语言时就知道,储存不同的变量计算机会相应分配不同区块的内存。那为什么要把内存化为不同的区域呢?实质上是为了方便管理 下面我们来看看下面一道例题&…...

C 标准库 - <stdlib.h>
简介 <stdlib.h> 头文件定义了四个变量类型、一些宏和各种通用工具函数。 库变量 下面是头文件 stdlib.h 中定义的变量类型: 序号变量 & 描述1size_t2wchar_t3div_t4ldiv_t 库宏 下面是头文件 stdlib.h 中定义的宏: 序号宏 & 描述1…...

Python中回调函数的理解与应用
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站零基础入门的AI学习网站~。 目录 前言 回调函数的概念 回调函数的基本用法 回调函数的实现方式 1 使用函数 2 使用类方法 3 使用类实…...

抖音数据挖掘软件|视频内容提取
针对用户获取抖音视频的需求,我们开发了一款功能强大的工具,旨在解决用户在获取抖音视频时需要逐个复制链接、下载的繁琐问题。我们希望用户能够通过简单的关键词搜索,实现自动批量抓取视频,并根据需要进行选择性批量下载。因此&a…...

PostgreSQL如何使用UUID
离线安装时,一般有四个包,都安装的话,只需要开启uuid的使用即可,如果工具包(即 postgresql11-contrib)没有安装的话,需要单独安装一次,再进行开启。 开启UUID方法 下面介绍一下如何开启&#…...

网络原理 - HTTP/HTTPS(4)
HTTP响应详解 认识"状态码"(status code) 状态码表示访问一个页面的结果.(是访问成功,还是失败,还是其它的一些情况...).(响应结果如何) 学习状态码 -> 为了调试问题. 写服务器时,按照状态码的含义正确使用. 200 OK 这是最常见的状态码,表示访问成功. 抓包抓…...

Vue+SpringBoot打造在线课程教学系统
目录 一、摘要1.1 系统介绍1.2 项目录屏 二、研究内容2.1 课程类型管理模块2.2 课程管理模块2.3 课时管理模块2.4 课程交互模块2.5 系统基础模块 三、系统设计3.1 用例设计3.2 数据库设计 四、系统展示4.1 管理后台4.2 用户网页 五、样例代码5.1 新增课程类型5.2 网站登录5.3 课…...

数据存储-文件存储
一、CSV文件存储 csv是python的标准库 列表数据写入csv文件 import csvheader [班级, 姓名, 性别, 手机号, QQ] # 二维数组 rows [[学习一班, 大娃, 男, a130111111122, 987456123],[学习二班, 二娃, 女, a130111111123, 987456155],[学习三班, 三娃, 男, a130111111124, …...

【Activiti7】全新Activiti7工作流讲解
一、Activiti7概述 官网地址:https://www.activiti.org/ Activiti由Alfresco软件开发,目前最高版本Activiti 7。是BPMN的一个基于java的软件实现,不过 Activiti 不仅仅包括BPMN,还有DMN决策表和CMMN Case管理引擎,并且有自己的用户管理、微 服务API 等一系列功能,是一…...

C++ 学习(1)---- 左值 右值和右值引用
这里写目录标题 左值右值左值引用和右值引用右值引用和移动构造函数std::move 移动语义返回值优化移动操作要保证安全 万能引用std::forward 完美转发传入左值传入右值 左值 左值是指可以使用 & 符号获取到内存地址的表达式,一般出现在赋值语句的左边ÿ…...

Redis能保证数据不丢失吗?
引言 大家即使没用过Redis,也应该都听说过Redis的威名。 Redis是一种Nosql类型的数据存储,全称Remote Dictionary Server,也就是远程字典服务器,用过Dictionary的应该都知道它是一种键值对(Key-Value)的数…...

C++基础知识(六:继承)
首先我们应该知道C的三大特性就是封装、继承和多态。 此篇文章将详细的讲解继承的作用和使用方法。 继承 一个类,继承另一个已有的类,创建的过程 父类(基类)派生出子类(派生类)的过程 继承提高了代码的复用性 【1】继承的格式 class 类名:父类名 {}; 【…...

RM电控讲义【HAL库篇】(二)
8080并口模式是一种常见的计算机接口模式,主要用于LCD(液晶显示屏)模块。 在8080并口模式中,通信端口包括多种信号线,用于实现数据的读写和控制功能。主要的信号线包括: CS(片选信号ÿ…...

Mac安装Appium
一、环境依赖 一、JDK环境二、Android-SDK环境(android自动化)三、Homebrew环境四、Nodejs 安装cnpm 五、安装appium六、安装appium-doctor来确认安装环境是否完成七、安装相关依赖 二、重头大戏, 配置wda(WebDriverAgent&#x…...