首页 > 编程语言 >分布式学习:Raft算法以及具体实现

分布式学习:Raft算法以及具体实现

时间:2024-09-15 10:46:04浏览次数:9  
标签:快照 log candidate 算法 follower Raft 日志 leader 分布式

Raft算法

一致性算法的要求:

  • 安全性,网络延迟、分区、丢包、重复和乱序等错误需要保证正确
  • 可用性:集群中只需要大多数机器即可运行
  • 不依赖时序保证一致性

三种状态:follower,candidate,leader

任期:逻辑时钟的作用,每一段任期从一次选举开始

  • 分票可能会导致一个任期没有leader

  • 用于检测一些过期的信息,比如说过期的leader(term小于candidate的term)

leader选举

什么时候选举:follower一段时间内没有收到任何消息(leader的追加日志,或candidate的投票请求),超过选举超时时间

什么情况投票:先来先服务 + candidate的日志必须和大多数服务节点的日志至少一样新

这是为了保证,成为leader的人必然拥有之前所有任期内已经被commit的日志,避免不同的状态机执行不同的指令序列

体现在代码上:使用log最后一个条目的term和idx来判断哪个是更新的日志

什么时候成为leader:获取大多数服务器节点针对同一任期号的选票

成为leader后做什么:立刻发送一轮心跳包维护自己权威,阻止发起新的选举

如果有旧leader从宕机恢复,并发送追加日志给candidate怎么办:比较两者的任期大小

如果产生分票,怎么避免:随机选举超时时间,把服务器的选举时间都分散开,对选举超时时间的基本要求为:大于 发送RPC一去一回的总时间, 小于 单个server平均故障间隔的时间

日志复制

什么时候追加日志给follower:

当leader接收到上层服务下发的命令后:将命令放到自己的log中,并行将应发送给各follower的日志条目发送给follower

体现在代码上:

在leader中维护了matchidx数组,记录每个follower现在更新到的日志下标;

nextidx数组,记录了要发送给每个follower的下个日志的下标;

prelogindex 和 prelogterm 指向 leader要发送日志的前一个日志,用以判断follower之前的日志是否与leader冲突,如果冲突则追加日志失败,follower返回Xterm,Xindex,Xlen

  • Xterm = -1, Xindex = -1, Xlen = follower全部日志长度:全部日志冲突
  • Xterm = 冲突log的term,Xindex = 冲突term内的第一条log的下标

帮助leader快速修改nextidx数组,定位到下一批应该追加给该follower的日志

什么时候返回结果:

当leader收到了大多数follow的追加成功回复后,leader会commit该日志,然后尝试apply该日志给上层存储服务,让上层执行并返回结果给客户端;

如果leader crash怎么办:follower太久没有收到heartbeat消息,触发选举超时,转变成candidate开始选举

如果follower crash怎么办:leader会无限重试发送追加日志给它们,直到它们重启

体现在代码上:

leader中有个专门的协程遍历matchindex数组,更新commitindex

并会在追加日志的时候附带发送commitindex,让follower更新该值;

leader和follower中都有个专门的协程,在commitindex更新时被唤醒,开始执行日志的apply

日志持久化

该部分较简单,只需在需要持久化的状态currentTerm,votedFor,log三者任一发生变化时,立刻调用persist()保存raftstate即可

其中currentTerm保存leader的当前任期值,votedFor保存follower的投票选择,log保存节点的日志,而诸如commitindex、lastapplied、nextindex[]、matchindex[]等状态,都可以通过保存的log,在Append Entries RPC的发送和返回中逐步调整恢复,故不需要保存

日志快照

  • 为了防止日志随着增长越来越大重放时间越来越长,所以使用snapshot,对一部分早期的日志进行快照

  • 快照内容除了包括应用数据信息,还包括了一些元数据信息:如快照中最后一个日志包含的term以及index

  • 一旦系统将快照持久化到了磁盘上,就可以删除快照最后一个日志之前的日志以及快照

  • 有时候,follower的进度太慢了,leader已经把应该发给它的日志给删除了,这个时候leader必须通过installsnapshot RPC给follower发送快照

    • 如果这个快照里包含了follower所没有的日志信息(也就是快照里的日志进度比follower所有的日志进度快),follower就会接收该快照,更新到自己的快照信息中

    在本处实现上,我选择follower在接收installsnapshot RPC时并不直接删除快照中所包含的日志,而是在上层应用调用CondInstallSnapshot判断成功应用快照后,才真正进行日志的裁剪

    因为在实现逻辑上,只有当上层应用调用CondInstallSnapshot判断可以安装快照之后,raft节点上快照所包含的日志信息才真正失效

该部分较为繁琐,涉及到很多关于日志的判断和操作,由于在该部分中日志的Index0也将发生变化,故也需要重构之前的日志追加功能,包括follower日志为空时的处理、包括leader日志为空时的处理等等

我选择在节点创造后的最开始时,在日志下标为0处保存一个空日志(方便还未接收上层应用的command时,可以顺利实现leader所发送的心跳包逻辑),而在日志进行快照而裁剪后,日志下标为0处即为有效日志,此时有两种情况

  • 日志不为空,该情况不影响心跳包逻辑的处理
  • 日志为空,在该情况下,我选择持久化lastsnapshotIndex、lastsnapshotTerm,使用此两个变量代行心跳包逻辑处理中prevLogIndex,prevLogTerm的功能

标签:快照,log,candidate,算法,follower,Raft,日志,leader,分布式
From: https://www.cnblogs.com/pinoky/p/18415050

相关文章

  • [独家原创]基于(牛顿拉夫逊)NRBO-Transformer单变量时序预测-递归预测未来数据 【24年
    [独家原创]基于(牛顿拉夫逊)NRBO-Transformer单变量时序预测-递归预测未来数据【24年新算法】(单输入单输出)你先用你就是创新!!!可以自行控制预测未来的数据个数!!!NRBO优化的超参数为:自注意力机制头数、正则化系数、初始化学习率1.程序已经调试好,无需更改代码替换数据集即可运行......
  • 十大经典排序算法
    排序算法平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性冒泡排序O(n^2)O(n)O(n^2)O(1)in-place稳定选择排序O(n^2)O(n^2)O(n^2)O(1)in-place不稳定插入排序O(n^2)O(n)O(n^2)O(1)in-place稳定希尔排序O(nlogn)O(nlog^2n)O(nlog^2n)O(1)in-place不稳定归并排序O(......
  • 【67种改进策略】优化算法改进再也不用担心了-matlab代码
    仅需一行代码,学会从入门到创新改进所有群智能优化算法   目录  引言一.佳点集初始化二.21种混沌初始化三.21种混沌参数化四.13种变异策略五.10种飞行/分布函数六.单纯形Nelder‑Mead单纯形法(Nelder‑Meadsimplex)Matlab代码下载点击链接跳转:引言根据“......
  • 图论篇--代码随想录算法训练营第五十九天打卡|Bellman_ford 算法精讲,SPFA算法,Bellman
    本系列算法用来解决有负权边的情况Bellman_ford算法精讲题目链接:94.城市间货物运输I题目描述:某国为促进城市间经济交流,决定对货物运输提供补贴。共有n个编号为1到n的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。网络......
  • 鹏哥C语言36-37---循环/分支语句练习(折半查找算法)
    #define_CRT_SECURE_NO_WARNINGS//----------------------------------------------------------------------------------------------------3.4分支,循环练习//用代码解决问题=先想办法(编程思维)+再写代码(按照语法形式)//--------------------------------------------......
  • 读构建可扩展分布式系统:方法与实践04应用服务
    1. 应用服务1.1. 任何系统的核心都在于实现应用需求的特定业务逻辑1.2. 服务是可扩展软件系统的核心1.2.1. 它们将契约定义为一个API,向客户端声明它们的能力1.3. 应用服务器高度依赖于编程语言,但通常都会提供多线程编程模型,允许服务同时处理许多请求1.4. 多服务配置......
  • 【算法】【线性表】【数组】买卖股票的最佳时机
    1 题目给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你......
  • 【算法】【线性表】【数组】买卖股票的最佳时机 II
    1 题目给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在同一天 出售。返回 你能获得的最大利润 。示例1:输入:prices=[7,1,5,3,......
  • 算法复杂度
    1.复杂度的概念   算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。   时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量⼀个算法运行所需......
  • Hbase分布式数据库
    目录简介实验环境实验步骤环境搭建下载安装修改配置文件启动Hbase了解Hbase基础语法Hbase简单实验简介Hbase是一个高可靠性、高性能、面向列、可伸缩的分布式数据库。利用Hbase技术可在廉价PCServer上搭建起大规模结构化存储集群。Hbase是非关系型数据库,它不要求数......