凤凰架构——分布式共识算法

2023-10-18 10:59

本文主要是介绍凤凰架构——分布式共识算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

分布式共识算法

随时可变的数据,保证在分布式环境下的可靠性?
状态转移——以同步为代表的数据复制方法(牺牲可用性)


保证数据在分布式环境下的可用性?
操作转移——通过确定的操作产生确定的结果(状态机)
只要初始状态一致,操作一致,允许期间状态存在不一样,但是执行完毕的结果是一致的(状态机复制)


Quorum 机制——超过一般机器的节点完成状态转换,容忍少数机器失联(增加可用性)


共识(Consensus)与一致性(Consistency)的区别:一致性是指数据不同副本之间的差异,而共识是指达成一致性的方法与过程。

Paxos

算法流程

Paxos 算法将分布式系统中的节点分为三类:

  • 提案节点: 称为 Proposer,提出对某个值进行设置操作的节点,设置值这个行为就被称之为提案(Proposal),值一旦设置成功,就是不会丢失也不可变的。 (基于操作转移类似于记录日志)
  • 决策节点: 称为 Acceptor,是应答提案的节点,决定该提案是否可被投票、是否可被接受。提案一旦得到过半数决策节点的接受,即称该提案被批准(Accept),提案被批准即意味着该值不能再被更改,也不会丢失,且最终所有节点都会接受该它。(决策节点的个数应该为奇数)
  • 记录节点: 被称为 Learner,不参与提案,也不参与决策,只是单纯地从提案、决策节点中学习已经达成共识的提案,譬如少数派节点从网络分区中恢复时,将会进入这种状态。

第一阶段“准备”(Prepare)
如果某个提案节点准备发起提案,必须先向所有的决策节点广播一个许可申请(称为 Prepare 请求)。提案节点的 Prepare 请求中会附带一个全局唯一的数字 n 作为提案 ID(可使用时间戳加Server ID),决策节点收到后,将会给予提案节点两个承诺(Promise)与一个应答。
两个承诺是指:

  • 承诺不会再接受提案 ID 小于或等于 n 的 Prepare 请求。
  • 承诺不会再接受提案 ID 小于 n 的 Accept 请求。

一个应答是指:

  • 不违背以前作出的承诺的前提下,回复已经批准过的提案中 ID 最大的那个提案所设定的值和提案 ID,如果该值从来没有被任何提案设定过,则返回空值。如果违反此前做出的承诺,即收到的提案 ID 并不是决策节点收到过的最大的,那允许直接对此 Prepare 请求不予理会。

第二阶段“批准”(Accept)过程
这时有如下两种可能的结果:

  • 如果提案节点发现所有响应的决策节点此前都没有批准过该值(即为空),那说明它是第一个设置值的节点,可以随意地决定要设定的值,将自己选定的值与提案 ID,构成一个二元组“(id, value)”,再次广播给全部的决策节点(称为 Accept 请求)。
  • 如果提案节点发现响应的决策节点中,已经有至少一个节点的应答中包含有值了,那它就不能够随意取值了,必须无条件地从应答中找出提案 ID 最大的那个值并接受,构成一个二元组“(id, maxAcceptValue)”,再次广播给全部的决策节点(称为 Accept 请求)。

当每一个决策节点收到 Accept 请求时,都会在不违背以前作出的承诺的前提下,接收并持久化对当前提案 ID 和提案附带的值。如果违反此前做出的承诺,即收到的提案 ID 并不是决策节点收到过的最大的,那允许直接对此 Accept 请求不予理会。


当提案节点收到了多数派决策节点的应答(称为 Accepted 应答)后,协商结束,共识决议形成,将形成的决议发送给所有记录节点进行学习。

在这里插入图片描述

工作实例

有两个并发的请求分别希望将同一个值分别设定为 X(由 S1作为提案节点提出)和 Y(由 S5作为提案节点提出),以 P 代表准备阶段,以 A 代表批准阶段,这时候可能发生以下情况:

  • 情况一:譬如,S1选定的提案 ID 是 3.1(全局唯一 ID 加上节点编号),先取得了多数派决策节点的 Promise 和 Accepted 应答,此时 S5选定提案 ID 是 4.5,发起 Prepare 请求,收到的多数派应答中至少会包含 1 个此前应答过 S1的决策节点,假设是 S3,那么 S3提供的 Promise 中必将包含 S1已设定好的值 X,S5就必须无条件地用 X 代替 Y 作为自己提案的值,由此整个系统对“取值为 X”这个事实达成一致,如图 6-2 所示。
    在这里插入图片描述

  • 情况二:事实上,对于情况一,X 被选定为最终值是必然结果,但从图 6-2 中可以看出,X 被选定为最终值并不是必定需要多数派的共同批准,只取决于 S5提案时 Promise 应答中是否已包含了批准过 X 的决策节点,譬如图 6-3 所示,S5发起提案的 Prepare 请求时,X 并未获得多数派批准,但由于 S3已经批准的关系,最终共识的结果仍然是 X。
    在这里插入图片描述

  • 情况三:当然,另外一种可能的结果是 S5提案时 Promise 应答中并未包含批准过 X 的决策节点,譬如应答 S5提案时,节点 S1已经批准了 X,节点 S2、S3未批准但返回了 Promise 应答,此时 S5以更大的提案 ID 获得了 S3、S4、S5的 Promise,这三个节点均未批准过任何值,那么 S3将不会再接收来自 S1的 Accept 请求,因为它的提案 ID 已经不是最大的了,这三个节点将批准 Y 的取值,整个系统最终会对“取值为 Y”达成一致,如图 6-4 所示。
    在这里插入图片描述

  • 情况四:从情况三可以推导出另一种极端的情况,如果两个提案节点交替使用更大的提案 ID 使得准备阶段成功,但是批准阶段失败的话,这个过程理论上可以无限持续下去,形成活锁(Live Lock),如图 6-5 所示。在算法实现中会引入随机超时时间来避免活锁的产生。
    在这里插入图片描述

Multi Paxos

这篇关于凤凰架构——分布式共识算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/232112

相关文章

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java异常架构Exception(异常)详解

《Java异常架构Exception(异常)详解》:本文主要介绍Java异常架构Exception(异常),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. Exception 类的概述Exception的分类2. 受检异常(Checked Exception)

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存(InnoDBBufferPool)和二级缓存(QueryCache),文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查