分布式一致性算法:Raft学习

分布式一致性算法:Raft学习

1 什么是分布式系统?

分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。这些节点可能位于不同的物理位置,但它们协同工作以提供一个统一的计算平台或服务。分布式系统的出现是为了用廉价的、普通的机器完成单个计算机无法完成的计算、存储任务。其目的是利用更多的机器,处理更多的数据。例如,分布式计算系统、分布式存储系统(缓存、数据库、文件)等。

分布式和集群的区别

  • 分布式是指多个系统协同合作完成一个特定任务的系统。是不同的系统部署在不同的服务器上,服务器之间相互调用。主要工作是分解任务,把职能拆解,解决中心化管理。
  • 集群是指在几个服务器上部署相同的应用程序来分担客户端的请求。是同一个系统部署在不同的服务器上,比如一个登陆系统部署在不同的服务器上。使用场景是为了分担请求的压力。

在这里插入图片描述

分布式系统面临的挑战:

  • 网络延迟和分区

    节点间通过网络通信,而网络是不可靠的。可能的网络问题包括:网络分割、延时、丢包、乱序,网络的不可靠性和延迟可能导致节点之间的通信问题理。

  • 普遍的节点故障

    虽然单个节点的故障概率较低,但节点数目达到一定规模,出故障的概率就变高了。分布式系统需要保证故障发生的时候,系统仍然是可用的,这就需要监控节点的状态,在节点故障的情况下将该节点负责的计算、存储任务转移到其他节点。

  • 异构的机器与网络

    分布式系统中的机器,配置不一样,其上运行的服务也可能由不同的语言、架构实现,因此处理能力也不一样;节点间通过网络连接,而不同网络运营商提供的网络的带宽、延时、丢包率又不一样。怎么保证大家齐头并进,共同完成目标,这是个不小的挑战。

2 CAP理论

  • C consistency 一致性

  • 在分布式系统中有多个节点,整个系统对外提供的服务应该是一致的。即用户在不同的系统节点访问数据的时候应该是同样的结果,不能出现1号节点是结果1, 2号节点是结果2这种不一致的情况。

  • A availability 可用性

    分布式系统为用户提供服务,需要保证能够在一些节点异常的情况下仍然支持为用户提供服务

  • P partition tolerance 分区容错性(容灾)

  • 分布式系统的部署可能跨省,甚至跨国。不同省份或者国家之间的服务器节点是通过网络进行连接,此时如果两个地域之间的网络连接断开,整个分布式系统的体现就是分区容错性了。在这种系统出现网络分区的情况下系统的服务就需要在一致性 和 可用性之间进行取舍。要么保持一致性,返回错误。要么是保证可用性,使得两个地域之间的分布式系统不一致。

在这里插入图片描述

CAP理论一定是无法全部满足三者,只能满足其中的两者(CA、CP、AP)。

对于一个分布式系统而言,P是分布式的前提,必须保证,因为只要有网络交互就一定会有延迟和数据丢失,这种状况我们必须接受,必须保证系统不能挂掉。所以只剩下C、A可以选择。要么保证数据一致性(保证数据绝对正确),要么保证可用性(保证系统不出错)。

当选择了C(一致性)时,如果由于网络分区而无法保证特定信息是最新的,则系统将返回错误或超时

当选择了A(可用性)时,系统将始终处理客户端的查询并尝试返回最新的可用的信息版本,即使由于网络分区而无法保证其是最新的

3 分布一致性

在这里插入图片描述

分布式一致性是指在分布式环境中对某个副本数据进行更新操作时,必须确保其他副本也会更新,避免不同副本数据不一致。

总结来讲,分布式一致性就是为了解决以下两个问题:

  • 数据不能存在单个节点(主机)上,否则可能出现单点故障。
  • 多个节点(主机)需要保证具有相同的数据。

分布一致性可以分为弱一致性和强一致性:

  • **弱一致性 **(例如:DNS域名系统)

    弱一致性体现的是最终一致性,即如上CAP理论中 ,两个地域的请求分别通过两地的节点写入,可以不用立即进行同步,而是经过一段时间之后两地的用户数据变为一致。这种一致性成为弱一致性,即最终一致性。 也就是用户一地写入之后从另外一个节点读取,无法立即读到刚才写入的数据

  • **强一致性 **(又被称为共识,例如:银行系统)

    强一致性描述的是一个请求在一个节点写入之后在其他节点读取,则该数据的更新能够被立刻读到

4 强一致性(共识)算法

共识需要满足的性质:

  • 在非拜占庭条件下保证共识的一致性(C)。非拜占庭条件就是可信的网络条件,与你通信的节点的信息都是真实的,不存在欺骗。
  • 在多数节点存活时,保持可用性(A)。“多数”永远指的是配置文件中所有节点的多数,而不是存活节点的多数。多数等同于超过半数的节点,多数这个概念概念很重要,贯穿Raft算法的多个步骤。
  • 不依赖于绝对时间。理解这点要明白共识算法是要应对节点出现故障的情况,在这样的环境中网络报文也很可能会受到干扰从而延迟,如果完全依靠于绝对时间,会带来问题,Raft用自定的Term(任期)作为逻辑时钟来代替绝对时间。
  • 在多数节点一致后就返回结果,而不会受到个别慢节点的影响。这点与第二点联合理解,只要**“大多数节点同意该操作”就代表整个集群同意该操作**。对于raft来说,”操作“是储存到日志log中,一个操作就是log中的一个entry。

**常见的强一致性算法:**主从同步、多数派、Paxos、Raft、ZAB

5 Raft算法

5.1 概述

在这里插入图片描述

Raft算法又被称为基于日志复制的一致性算法,旨在解决分布式系统中多个节点之间的数据一致性问题。它通过选举一个**领导者(Leader)**,让领导者负责管理和协调日志复制,确保所有节点的数据一致。

  • 复制日志

    在分布式系统中,每个节点都维护着一份日志,记录系统操作的历史。为了保证数据一致性,这些日志需要在所有节点之间保持同步。 Raft通过领导者选举和日志复制机制,确保所有节点的日志最终是一致的。

  • 心跳机制与选举

    Raft使用心跳机制来触发选举。当系统启动时,每个节点(Server)的初始状态都是追随者(Follower)。每个Server都有一个定时器,超时时间为选举超时(Election Timeout),一般为150-300毫秒。如果一个Server在超时时间内没有收到来自领导者或候选者的任何消息,定时器会重启,并开始一次选举。

  • 选举过程(投票)

    当一个追随者节点发现自己超过选举超时没有收到领导者的消息,就会变为候选者(Candidate),并开始新一轮选举。候选者节点会增加自己的任期号,并向其他节点发送选票请求。每个节点只能在一个任期内投一票,并且通常会将票投给第一个请求投票的候选者。如果一个候选人在收到足够多的选票后,就成为新的领导者。

  • 多个候选者(选举失败—>重来)

    在选举过程中,可能会出现多个候选者同时竞争领导者的位置。这时,如果某个候选者无法在选举超时前获得大多数节点的支持,选举就会失败。失败后,所有候选者会重置自己的定时器,并在下一轮超时后再次发起选举,直到选出新的领导者为止。

5.2 工作模式:Leader-Follower 模式

  • Leader 一个集群只有一个leader,不断地向集群其它节点发号施令(心跳、日志同步),其它节点接到领导者日志请求后成为其追随者
  • Follower 一个服从leader决定的角色,追随领导者,接收领导者日志,并实时同步
  • Cadidate follower发现集群没有leader,会重新选举leader,参与选举的节点会变成candidate

5.3 重要概念

  • 状态机:raft的上层应用,例如k-v数据库
  • 日志log:raft保存的外部命令是以日志保存
  • term 任期:Term作为内部的逻辑时钟,使用Term的对比来比较日志、身份、心跳的新旧而不是用绝对时间
  • 提交日志 commit:raft保存日志后,经过复制同步,才能真正应用到上层状态机,这个“应用”的过程为提交
  • 节点身份 follower、Candidate、Leader :raft集群中不同节点的身份
  • 选举:follower变成leader需要选举
  • 心跳、日志同步:leader向follower发送心跳(AppendEntryRPC)用于告诉follower自己的存在以及通过心跳来携带日志以同步
  • 日志的term:在日志提交的时候,会记录这个日志在什么“时候”(哪一个term)记录的,用于后续日志的新旧比较
  • 日志条目 entry:日志条目是日志的基本单元。每个日志条目记录了一次状态变化或一个命令。日志条目包含了如下几个关键信息:
    • 索引(Index):该日志条目在日志中的位置。
    • 任期(Term):该日志条目被创建时的任期号。
    • 命令(Command):要应用于状态机的具体命令或操作。

5.4 日志 log

日志中保存客户端发送来的命令,上层的状态机根据日志执行命令,那么日志一致,自然上层的状态机就是一致的

核心思想:Raft算法可以让多个节点的上层状态机保持一致的关键是让==各个节点的日志保持一致==

5.5 任期 term

  • 每个节点都有自己的term,Term用连续的数字进行表示。Term会在follower发起选举(成为Candidate从而试图成为Leader )的时候加1,对于一次选举可能存在两种结果:

    • 胜利当选:超过半数的节点认为当前Candidate有资格成为Leader,即超过半数的节点给当前Candidate投了选票。
    • 失败:如果没有任何Candidate(一个Term的Leader只有一位,但是如果多个节点同时发起选举,那么某个Term的Candidate可能有多位)获得超半数的选票,那么选举超时之后又会开始另一个Term(Term递增)的选举
  • 对于节点,当发现自己的Term小于其他节点的Term时,这意味着“自己已经过期”,不同身份的节点的处理方式有所不同:

    • leader、Candidate:退回follower并更新term到较大的那个Term
    • follower:更新Term信息到较大的那个Term
  • 这里解释一下为什么 自己的Term小于其他节点的Term时leader、Candidate会退回follower 而不是延续身份,因为通过Term信息知道自己过期,意味着自己可能发生了网络隔离等故障,那么在此期间整个Raft集群可能已经有了新的leader、 提交了新的日志 ,此时自己的日志是有缺失的,如果不退回follower,那么可能会导致整个集群的日志缺失,不符合安全性。

  • 相反,如果发现自己的Term大于其他节点的Term,那么就会忽略这个消息中携带的其他信息(这个消息是过期的)。

5.6 工作机制

主要有以下四大模块,组成Raft算法:

  • 领导者选举
  • 日志同步、心跳
  • 持久化
  • 日志压缩,快照

5.7 领导者选举

节点需要通过集群元数据信息与其它节点进行沟通,而沟通的方式是**RPC请求**

5.8 日志同步、心跳

  • raft日志的两个特点
    • 两个节点的日志中,有两个 entry 拥有相同的 index 和 term,那么它们一定记录了相同的内容/操作,即两个日志匹配

    • 两个节点的日志中,有两个 entry 拥有相同的 index 和 term,那么它们前面的日志entry也相同

      如何保证这两点:

      保证第一点:仅有 leader 可以生成 entry

      保证第二点:leader 在通过 AppendEntriesRPC 和 follower 通讯时,除了带上自己的term等信息外,还会带上entry的index和对应的term等信息,follower在接收到后通过对比就可以知道自己与leader的日志是否匹配,不匹配则拒绝请求。leader发现follower拒绝后就知道entry不匹配,那么下一次就会尝试匹配前一个entry,直到遇到一个entry匹配,并将不匹配的entry给删除(覆盖)。

      注意:raft为了避免出现一致性问题,要求 leader 绝不会提交过去的 term 的 entry (即使该 entry 已经被复制到了多数节点上)。leader 永远只提交当前 term 的 entry, 过去的 entry 只会随着当前的 entry 被一并提交。

  • raft日志同步方式

    找到日志不匹配的那个点,然后只同步那个点之后的日志

    一个follower,如果leader认为其日志已经和自己匹配了,那么在AppendEntryRPC中不用携带日志(其他信息依然要携带),反之如果follower的日志只有部分匹配,那么就需要在AppendEntryRPC中携带对应的日志。心跳RPC可以看成是没有携带日志的特殊的日志同步RPC。

    日志同步(复制)的过程:

在这里插入图片描述

-------------------------------------------------------------------------------------------Raft算法的核心步骤👇------------------------------------------------------------------------------------------------

  1. 接收到客户端请求之后,领导者根据用户指令和自身任期以及日志索引等信息生成一条新的日志项,并附加到本地日志中。
  2. 领导者通过日志复制 RPC,将日志复制到其他跟随者节点。
  3. 跟随者将日志附加到本地日志成功之后,便返回 success,此时新的日志项还没有被跟随者提交。
  4. 当领导者接收到**大多数(超过集群数量的一半)**跟随者节点的 success 响应之后,便将此日志提交(commit)到它的状态机中。
  5. 领导者将执行的结果返回给客户端。
  6. 当跟随者收到下一次领导者的心跳请求或者新的日志复制请求之后,如果发现领导者已经应用了之前的日志,但是它自己还没有之后,那么它便会把这条日志项应用到本地状态机中。(类似于二阶段提交的方式)

-------------------------------------------------------------------------------------------Raft算法的核心步骤👆------------------------------------------------------------------------------------------------

5.9 持久化

Raft的一大优势就是Fault Tolerance(容灾),即能够在部分节点宕机、失联或者出现网络分区的情况下依旧让系统正常运行。为了保证这一点,除了领导选举与日志复制外,还需要定期将一些数据持久化到磁盘中,以实现在服务器重启时利用持久化存储的数据恢复节点上一个工作时刻的状态。持久化的内容仅仅是Raft层, 其应用层不做要求。

在这里插入图片描述

论文中提到需要持久化的数据包括:

  • voteFor

    voteFor记录了一个节点在某个term内的投票记录, 因此如果不将这个数据持久化, 可能会导致如下情况:

    • 在一个Term内某个节点向某个Candidate投票, 随后故障
    • 故障重启后, 又收到了另一个RequestVote RPC, 由于其没有将votedFor持久化, 因此其不知道自己已经投过票, 结果是再次投票, 这将导致同一个Term可能出现2个Leader
  • currentTerm:
    currentTerm的作用也是实现一个任期内最多只有一个Leader, 因为如果一个节点重启后不知道现在的Term时多少, 其无法再进行投票时将currentTerm递增到正确的值, 也可能导致有多个Leader在同一个Term中出现

  • Log:
    这个很好理解, 需要用Log恢复自身的状态

为什么只需要持久化votedFor, currentTerm, Log

其他的数据, 包括 commitIndexlastAppliednextIndexmatchIndex都可以通过心跳的发送和回复逐步被重建, Leader会根据回复信息判断出哪些Logcommit了。

什么时候持久化?

将任何数据持久化到硬盘上都是巨大的开销, 其开销远大于RPC, 因此需要仔细考虑什么时候将数据持久化。

如果每次修改三个需要持久化的数据: votedFor, currentTerm, Log时, 都进行持久化, 其持久化的开销将会很大, 很容易想到的解决方案是进行批量化操作, 例如只在回复一个RPC或者发送一个RPC时,才进行持久化操作

5.10 日志压缩、快照

参考文献

内容摘抄自一下文章,如有侵权,联系删除:

什么是分布式系统,这么讲不信你不会 - 知乎 (zhihu.com)

什么是分布式,分布式和集群的区别又是什么?这一篇让你彻底明白!_什么叫分布式-CSDN博客

终于有人把分布式系统架构讲明白了-CSDN博客

MIT6.824 Lab2 RAFT 介绍与实现 - pxlsdz - 博客园 (cnblogs.com)

MIT6.5840(6.824) Lec06笔记: raft论文解读2: 恢复、持久化和快照 (gfx9.github.io)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/372562.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Leetcode 295.数据流的中位数

295.数据流的中位数 问题描述 中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。 例如 arr [2,3,4] 的中位数是 3 。例如 arr [2,3] 的中位数是 (2 3) / 2 2.5 。 实现 MedianFinder 类: Media…

【笔记】太久不用redis忘记怎么后台登陆了

!首先启动虚拟机linux的centos7 2.启动finalshell 我的redis启动在根目录用 redis-server redis.conf --启动 systemctl status redis --查看redis状态 是否active redis-cli -h centos的ip地址 -p 你要用的redis端口号(默认为6379) -a 你…

UDP通讯实现

服务器端&#xff1a; 1.获取套接字 int fd;fdsocket(AF_INET,SOCK_DGRAM,0);if(fd<0){perror("socket");exit(0);} #include <sys/types.h> #include <sys/socket.h> int socket(int domain, int type, int protocol); -domain: 指定通信域&…

LInux安装

目录 1. LInux优点 1.1 安全性高 1.2 稳定性和可靠性高 1.3 开源和免费 1.4 资源利用效率 2. Linux虚拟机下载 2.1 VMware安装 2.2 虚拟机安装 2.3 Centos7下载 2.4 简单设置Centors-7 2.4.1 首次进入 2.4.2 联网设置 2.4.3 自动联网设置 2.4.4 自动锁屏设置 Li…

Hadoop-15-Hive 元数据管理与存储 Metadata 内嵌模式 本地模式 远程模式 集群规划配置 启动服务 3节点云服务器实测

章节内容 上一节我们完成了&#xff1a; Hive中数据导出&#xff1a;HDFSHQL操作上传内容至Hive、增删改查等操作 背景介绍 这里是三台公网云服务器&#xff0c;每台 2C4G&#xff0c;搭建一个Hadoop的学习环境&#xff0c;供我学习。 之前已经在 VM 虚拟机上搭建过一次&am…

C++初学者指南-5.标准库(第一部分)--顺序容器

C初学者指南-5.标准库(第一部分)–顺序容器 文章目录 C初学者指南-5.标准库(第一部分)--顺序容器标准顺序容器常见特点规律性&#xff1a;复制&#xff0c;分配&#xff0c;比较类型推导(C17)常用接口部分 array<T,size>vector\<T>C 的默认容器快速回顾迭代器范围插…

【粉丝福利 | 第8期】值得收藏!推荐10个好用的数据血缘工具

⛳️ 写在前面参与规则&#xff01;&#xff01;&#xff01; ✅参与方式&#xff1a;关注博主、点赞、收藏、评论&#xff0c;任意评论&#xff08;每人最多评论三次&#xff09; ⛳️本次送书1~4本【取决于阅读量&#xff0c;阅读量越多&#xff0c;送的越多】 目前市面上绝…

文档图像处理:大模型的突破与新探索

前言 随着数字化时代的到来&#xff0c;文档图像处理技术在各行各业扮演着越来越重要的角色。在2023第十二届中国智能产业高峰论坛&#xff08;CIIS 2023&#xff09;的专题论坛上&#xff0c;合合信息智能技术平台事业部副总经理、高级工程师丁凯博士分享了当前文档图像处理面…

如何学习和提升SQL

资料来源于腾讯技术直播&#xff0c;只作为学习记录&#xff0c;如有侵权&#xff0c;请联系作者进行删除

4.1 操作系统

大纲 进程管理重点&#xff0c;占本章历年考试一半分数&#xff0c; 前趋图、信号量和PV操作、死锁和银行家算法 出计算题 作业管理历年考试从来没有考过 操作系统概述 进程管理 进程的组成和状态 前趋图 进程资源图 真题 1

实验一 MATLAB \ Python数字图像处理初步

一、实验目的&#xff1a; 1&#xff0e;熟悉及掌握在MATLAB\Python中能够处理哪些格式图像。 2&#xff0e;熟练掌握在MATLAB\Python中如何读取图像。 3&#xff0e;掌握如何利用MATLAB\Python来获取图像的大小、颜色、高度、宽度等等相关信息。 4&#xff0e;掌握如何在M…

java花店管理系统eclipse开发mysql数据库

1 绪论 1.1 系统开发目的 随着人们物质生活水平和经济水平的不断提高&#xff0c;室内绿化布置、家庭园艺装饰、礼仪鲜花等日益受到重视和青睐&#xff0c;以及送鲜花给亲朋好友来表达自己的情谊。传统的花店对于信息的管理的主要方式是基于文本、表格等纸质手工处理&#xf…

SpringCloudAlibaba基础五 Nacos配置中心

一 Nacos配置中心介绍 官方文档&#xff1a;https://github.com/alibaba/spring-cloud-alibaba/wiki/Nacos-config Nacos 提供用于存储配置和其他元数据的 key/value 存储&#xff0c;为分布式系统中的外部化配置提供服务器端和客户端支持。使用 Spring Cloud Alibaba Nacos C…

剪辑抽帧技巧有哪些 剪辑抽帧怎么做视频 剪辑抽帧补帧怎么操作 剪辑抽帧有什么用 视频剪辑哪个软件好用在哪里学

打破视频节奏&#xff0c;让作品告别平庸。抽帧剪辑可以改变视频叙事节奏&#xff0c;人为制造冲突、转折、卡顿的效果。这种剪辑方式&#xff0c;不仅可以推进剧情发展&#xff0c;还能吸引观众的注意力&#xff0c;有效防止观影疲劳。有关剪辑抽帧技巧有哪些&#xff0c;剪辑…

mysql数据库中的视图view的概念和详细说明

目录 一、定义 二、视图view的分类 &#xff08;一&#xff09;按功能和特性分类 1、普通视图&#xff08;Regular View/Standard View&#xff09; 2、索引视图&#xff08;Indexed View&#xff09; 3、分割视图&#xff08;Partitioned View/Distributed Partitioned …

1.认识微服务

认识微服务 1.微服务2.微服务架构 1.微服务 微服务是一种经过良好架构设计的分布式架构设计&#xff0c;微服务架构特征&#xff1a; 单一指职责&#xff1a;微服务拆分粒度更小&#xff0c;每一个服务都对应唯一的业务能力&#xff0c;做到单一职责&#xff0c;避免重复业务…

Python提取视频文案

Python提取视频文案 1、背景描述2、视频转音频3、音频转文字 1、背景描述 在多媒体应用中&#xff0c;视频是一个信息量巨大的载体。然而&#xff0c;有时我们需要从视频中提取语音并转换为文本&#xff0c;以用于文本分析和机器学习训练 其中主要涉及到两个过程&#xff1a;视…

LVS+Nginx高可用集群---Nginx进阶与实战(二)

1.Nginx配置SSL证书提供https访问 大概步骤&#xff1a;云服务器-注册域名-配置SSL证书-下载证书&#xff0c;并且拷贝到nginx的conf目录下。 检查nginx是否含有ssl的模块-安装ssl模块-配置HTTPS模块-配置SSL-主域名可以通过HTTPS访问 配置模版&#xff1a; 添加上开启SSL的代…

python-课程满意度计算(赛氪OJ)

[题目描述] 某个班主任对学生们学习的的课程做了一个满意度调查&#xff0c;一共在班级内抽取了 N 个同学&#xff0c;对本学期的 M 种课程进行满意度调查。他想知道&#xff0c;有多少门课是被所有调查到的同学都喜欢的。输入格式&#xff1a; 第一行输入两个整数 N , M 。 接…

微服务-初级篇

微服务-初级篇 认识微服务1.1 单体架构1.2 分布式架构1.3 微服务 SpringCloud2.1 了解2.2 服务拆分原则2.3 服务拆分效果 Nacos注册中心3.1 认识和安装Nacos3.1.1 Nacos下载3.1.2 Nacos安装 3.2 服务注册到Nacos Feign远程调用4.1 Feign引入4.2 Feign配置 认识微服务 1.1 单体…