精华内容
下载资源
问答
  • 文章目录前言Raft算法选举Raft算法数据一致性 前言 Raft算法为主从结构, 其...这两天想到一个问题, raft算法的成员共识性问题。我之前的理解是: Raft有共识性问题。 当未实现所有日志提交的Follower,之后被选举为新

    前言

    18年写过一个Raft的实现, 开源在https://github.com/srctar/raft。时隔两年, 回顾一下。

    Raft算法为主从结构, 其分布式一致性来源于集群的写全委托给LeaderLeader进程自身保证顺序与一致性, 并发起投票要求Follower追加写, 一旦过半赞成写请求(同时附加写的动作), 则该写完成。
    .
    需要注意的是, 集群的写是线性一致性/强一致性的, 同时基于Follower转发的集群的读也是现行一致性/强一致性的。并非ZAB的顺序一致性

    这两天想到一个问题, raft算法的成员共识性问题。我之前的理解是:

    Raft有共识性问题。 当未实现所有日志提交的Follower,之后被选举为新的leader之后, 源于raft日志的leader覆盖规则, 将导致数据丢失。

    ↑↑上面这个想法是错误的↑↑Raft算法的安全性保证(阻止不包含最新Term和日志编号的Follower成为Leader、复制旧Leader数据)达成共识,确保了成员数据的一致性(相应的,ZAB使用主从相互拷贝的形式,达成集群共识)。


    关于Raft, 我对其做了一个Java版的实现, 地址在: https://github.com/srctar/raft。 欢迎阅读。
    目前实现了 raft 协议的下述功能:

    • 集群选举.
    • 数据一致性.
    • 集群配置(集群节点信息, 以及集群的数目)更改.
    • 紧急提交.
    • 日志压缩.

    Raft算法选举

    选举流程参考网站:http://thesecretlivesofdata.com/raft/
    本文的部分图片以及理论基础参考: https://blog.csdn.net/luoyhang003/article/details/61915666
    如下Gif:

    在这里插入图片描述
    选举主要注意两点:

    1. 心跳超时(不管是初始态还是运行态);
    2. 只要当前机器尚未投票(包括自己), 就一定投票给申请投票者,同时重置心跳准备再次超时。

    由于是多线程操作, 时序图与流程图皆不好画, 请参阅文字:

    Raft为集群状态定义为: ELECTION(选举态), PROCESSING(运行态)
    .
    每个Raft节点有三个状态:FOLLOWERLEADERCANDIDATE(选举者)

    1. 独立线程心跳超时(一般是100ms);
      a. 独立线程可以位于FOLLOWER, 也可以位于刚启动的集群节点,还可以位于宕机、网络中断的节点。
      b. LEADER节点无该独立线程(它负责给别的节点发心跳)。
      c. -
    2. 该线程休眠 150~300ms高于心跳超时时间100ms
      a.此操作非常重要,用以防止选票分散,进而导致长期超时
      b.休眠中的线程可以接受投票。
      c. -
    3. 投自己一票,并向集群中的节点申请投票。
      a. 节点处于集群选举中ELECTION,且未给任何节点投票,节点默认接受投票申请。
      b. -
    4. 当某节点收到过半赞许,节点立马转化为 LEADER。 关闭心跳线程, 同时给其它节点发送心跳。
      a. 节点处于运行态 PROCESSING, 且自身是LEADER显然,一定有个老leader网断了,然后又网好了。 只要对方的Term大于自己, 那自己立马转化为FOLLOWER
      b. -
    5. 选举态的节点收到心跳, 转化为FOLLOWER, 同时重设心跳线程。
      a. 注意, 节点处于选举态 ELECTION, 需要心跳发送者的Term高于自己,否则返回拒绝(APPEND_ENTRIES_DENY)
      b. 节点处于运行态 PROCESSING, 需要匹配心跳者是否是集群LEADER。是则重置心跳线程, 否则直接拒绝。
      c. -

    如上选举算法设计, 合理的确保下如下表格中的case, 能快速选上leader、且非过半宕机时,集群可用:

    Case 担忧点 解决方案
    正常启动选Leader 选不上 重选/启动时参与选举有线程休眠时间150~300ms, 此时接受投票一定赞同,确保选举
    不过半的Follower宕机/失联 可用性 可用, Leader不宕机,不影响选举, 不过半宕机,不影响数据投票
    过半Follower宕机 可用性 Leader不宕机,还能接受数据, 过半宕机,影响数据投票, 集群不可用
    不过半宕机, 包含Leader 可用性 可用, 心跳超时再选举, 通常一轮就能选出新Leader,集群正常服务
    不过半宕机, 包含Leader 可用性 不可用, 选不出Leader
    Leader失联 集群状态 其他机器依旧能选上新Leader, 期序Term累加,旧Leader恢复之后接受心跳转为Follower
    Leader宕机 集群状态 其他机器依旧能选上新Leader, 重启之后接受心跳转为Follower

    Raft算法数据一致性

    此处讲解的一致性, 分为两点:

    1. Raft 集群正常运行态的数据一致性;
    2. Raft 集群宕机恢复后的数据一致性。

    正常运行态的强一致性

    正常运行态, Raft的写满足强一致性/线性一致性在这里插入图片描述
    但是读也能满足到线性一致性。


    Raft协议定义, 读由Follower转发给Leader, 因此能够保证最新commited读, 这种Case下,也无须关心过半不赞同的回滚策略。数据不提交即可。

    但是针对这个算法, 也有优化, 例如对比FollowerLeadercommitIndex, 一致的话由Follower读, 也是线性一致的。

    Raft集群的数据共识(集群恢复时)

    本节讲的是集群某些机器宕机, 数据也没有来得及同步的情况下, 集群如何保证的数据一致性。
    ↓↓↓↓↓↓↓↓注意下面例子,Raft是解决了的, 实际并不存在↓↓↓↓↓↓↓↓

    极端情况,新Leader上位,集群状态却如下图:

    如上图,相对于新的leader:

    1. a、b 丢失了部分数据
    2. c、d 多出来部分数据
    3. e、f 既丢失, 又多出来了数据

    毕竟Raft的同步逻辑,过半提交则为提交, 之后Leader一直重试保证数据一致。
    像b, 网络不佳,就是没同步上;
    像d, 它就是上一个leader,自身提交前,还没来得及集群同步,网断了;

    那类似这种情况, Raft集群的数据共识是怎么达成的呢? 如下方案:

    1. 选举限制。 除了匹配Term外, 还匹配日志版本, 大于等于自身日志版本的投票才会被授予。以此确保多数赞成的数据是最新的。
    2. 尝试复制老旧Leader上已提交(过半赞成)的日志,因为已提交, 则至少当前被复制条目以及之前的日志都是可以被提交的。

    如上操作确保了只有持有最新日志的节点才能成为Leader, 且它将会尝试复制老旧Leader的日志数据。
    此项操作通过排序和重发布确保数据的有序性, 但是会一定程度的增加系统复杂度。

    Raft算法的其他集群变更、日志压缩功能

    这部分功能没有实现, 具体可参阅 https://blog.csdn.net/luoyhang003/article/details/61915666

    展开全文
  • Raft是一种为了管理日志复制的分布式一致性算法。Raft出现之前,Paxos 一直是分布式一致性算法的标准。Paxos 难以理解,更难以实现。Raft 的设计目标是简化 Paxos,使得算法既容易理解,也容易实现。 Paxos 和 ...

    一、 Raft简介

     

    1.1 Raft简介

    Raft 是一种为了管理日志复制的分布式一致性算法。Raft 出现之前,Paxos 一直是分布式一致性算法的标准。Paxos 难以理解,更难以实现。Raft 的设计目标是简化 Paxos,使得算法既容易理解,也容易实现。

    Paxos 和 Raft 都是分布式一致性算法,这个过程如同投票选举领袖(Leader),参选者(Candidate)需要说服大多数投票者(Follower)投票给他,一旦选举出领袖,就由领袖发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。

    Raft 可以解决分布式 CAP 理论中的 CP,即 一致性(C:Consistency) 和 分区容忍性(P:Partition Tolerance),并不能解决 可用性(A:Availability) 的问题。

    1.2 分布一致性

    分布式一致性 (distributed consensus) 是分布式系统中最基本的问题,用来保证一个分布式系统的可靠性以及容错能力。简单来说,分布式一致性是指多个服务器的保持状态一致

    在分布式系统中,可能出现各种意外(断电、网络拥塞、CPU/内存耗尽等等),使得服务器宕机或无法访问,最终导致无法和其他服务器保持状态一致。为了应对这种情况,就需要有一种一致性协议来进行容错,使得分布式系统中即使有部分服务器宕机或无法访问,整体依然可以对外提供服务。

    以容错方式达成一致,自然不能要求所有服务器都达成一致状态,只要超过半数以上的服务器达成一致就可以了。假设有 N 台服务器, 大于等于 N / 2 + 1 台服务器就算是半数以上了 。

    1.3 复制状态机

    复制状态机(Replicated State Machines) 是指一组服务器上的状态机产生相同状态的副本,并且在一些机器宕掉的情况下也可以继续运行。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令,所以产生的结果也是相同的。

    图片

    复制状态机通常都是基于复制日志实现的,如上图。每一个服务器存储一个包含一系列指令的日志,并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令,所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的,每一次执行操作都产生相同的状态和同样的序列。

    保证复制日志相同就是一致性算法的工作了。在一台服务器上,一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求,尽管有些服务器会宕机。一旦指令被正确的复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端。因此,服务器集群看起来形成一个高可靠的状态机。

    实际系统中使用的一致性算法通常含有以下特性:

    安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。

    可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信,就可以保证可用。因此,一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。

    不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。

    通常情况下,一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。

    1.4 RAFT应用

    通过 RAFT 提供的复制状态机,可以解决分布式系统的复制、修复、节点管理等问题。Raft 极大的简化当前分布式系统的设计与实现,让开发者只关注于业务逻辑,将其抽象实现成对应的状态机即可。基于这套框架,可以构建很多分布式应用:

    分布式锁服务

    分布式存储系统,比如分布式消息队列、分布式块系统、分布式文件系统、分布式表格系统等,比如大名鼎鼎的 Redis 就是基于 Raft 实现分布式一致性

    高可靠元信息管理,比如各类 Master 模块的 HA

     

    二、 Raft基础

     

    Raft 将一致性问题分解成了三个子问题:选举 Leader、日志复制、安全性。

    在后续章节,会详细讲解这个子问题。现在,先了解一下 Raft 的一些核心概念。

     

    2.1 服务器角色

    在 Raft 中,任何时刻,每个服务器都处于这三个角色之一 :

    Leader - 领导者,通常一个系统中是一主(Leader)多从(Follower)。Leader 负责处理所有的客户端请求。

    Follower - 跟随者,不会发送任何请求,只是简单的 响应来自 Leader 或者 Candidate 的请求

    Candidate - 参选者,选举新 Leader 时的临时角色。

    图片

    图示说明:

    • Follower 只响应来自其他服务器的请求。在一定时限内,如果 Follower 接收不到消息,就会转变成 Candidate,并发起选举。

    • Candidate 向 Follower 发起投票请求,如果获得集群中半数以上的选票,就会转变为 Leader。

    • 在一个 Term 内,Leader 始终保持不变,直到下线了。Leader 需要周期性向所有 Follower 发送心跳消息,以阻止 Follower 转变为 Candidate。

    2.2 任期

    图片

    Raft 把时间分割成任意长度的 任期(Term),任期用连续的整数标记。每一段任期从一次选举开始。Raft 保证了在一个给定的任期内,最多只有一个领导者。

    如果选举成功,Leader 会管理整个集群直到任期结束。

    如果选举失败,那么这个任期就会因为没有 Leader 而结束。

    不同服务器节点观察到的任期转换状态可能不一样:

    服务器节点可能观察到多次的任期转换。

    服务器节点也可能观察不到任何一次任期转换。

    任期在 Raft 算法中充当逻辑时钟的作用,使得服务器节点可以查明一些过期的信息(比如过期的 Leader)。每个服务器节点都会存储一个当前任期号,这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号。

    如果一个服务器的当前任期号比其他人小,那么他会更新自己的编号到较大的编号值。

    如果一个 Candidate 或者 Leader 发现自己的任期号过期了,那么他会立即恢复成跟随者状态。

    如果一个节点接收到一个包含过期的任期号的请求,那么他会直接拒绝这个请求。

    数据可视化的应用场景越来越广泛,数据可以呈现为更多丰富的可视化形式,使用户能够更加轻易、便捷的获取并理解数据传达的信息。

    2.3 RPC

    Raft 算法中服务器节点之间的通信使用 远程过程调用(RPC)。基本的一致性算法只需要两种 RPC:

    RequestVote RPC - 请求投票 RPC,由 Candidate 在选举期间发起。

    AppendEntries RPC - 附加条目 RPC,由 Leader 发起,用来复制日志和提供一种心跳机制。

     

    三、选举Leader

     

    3.1 选举规则

    Raft 使用一种心跳机制来触发 Leader 选举。Leader 需要周期性的向所有 Follower 发送心跳消息,以此维持自己的权威并阻止新 Leader 的产生。

    每个 Follower 都设置了一个随机的竞选超时时间,一般为 150ms ~ 300ms,如果在竞选超时时间内没有收到 Leader 的心跳消息,就会认为当前 Term 没有可用的 Leader,并发起选举来选出新的 Leader。开始一次选举过程,Follower 先要增加自己的当前 Term 号,并转换为 Candidate

    Candidate 会并行的向集群中的所有服务器节点发送投票请求(RequestVote RPC),它会保持当前状态直到以下三件事情之一发生:

    自己成为 Leader

    其他的服务器成为 Leader

    没有任何服务器成为 Leader

    3.1.1自己成为 Leader

    当一个 Candidate 从整个集群半数以上的服务器节点获得了针对同一个 Term 的选票,那么它就赢得了这次选举并成为 Leader。每个服务器最多会对一个 Term 投出一张选票,按照先来先服务(FIFO)的原则。要求半数以上选票的规则确保了最多只会有一个 Candidate 赢得此次选举。

    一旦 Candidate 赢得选举,就立即成为 Leader。然后它会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。

    3.1.2 其他的服务器成为 Leader

    等待投票期间,Candidate 可能会从其他的服务器接收到声明它是 Leader  的 AppendEntries RPC。

    如果这个 Leader 的 Term 号(包含在此次的 RPC 中)不小于 Candidate 当前的 Term,那么 Candidate 会承认 Leader 合法并回到 Follower 状态。

    如果此次 RPC 中的 Term 号比自己小,那么 Candidate 就会拒绝这个消息并继续保持 Candidate 状态。

    3.1.3 没有任何服务器成为 Leader

    如果有多个 Follower 同时成为 Candidate,那么选票可能会被瓜分以至于没有 Candidate 可以赢得半数以上的投票。当这种情况发生的时候,每一个 Candidate 都会竞选超时,然后通过增加当前 Term 号来开始一轮新的选举。然而,没有其他机制的话,选票可能会被无限的重复瓜分。

    Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况,就算发生也能很快的解决。为了阻止选票起初就被瓜分,竞选超时时间是一个随机的时间,在一个固定的区间(例如 150-300 毫秒)随机选择,这样可以把选举都分散开。

    以至于在大多数情况下,只有一个服务器会超时,然后它赢得选举,成为 Leader,并在其他服务器超时之前发送心跳包。

    同样的机制也被用在选票瓜分的情况下:每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时时间,然后在超时时间内等待投票的结果;这样减少了在新的选举中另外的选票瓜分的可能性。

    理解了上面的选举规则后,我们通过动图来加深认识。

    3.2 单Candidate选举

    1) 下图表示一个分布式系统的最初阶段,此时只有 Follower,没有 Leader。Follower A 等待一个随机的选举超时时间之后,没收到 Leader 发来的心跳消息。因此,将 Term 由 0 增加为 1,转换为 Candidate,进入选举状态。

    图片

    2)此时,A 向所有其他节点发送投票请求。

    图片

    3) 其它节点会对投票请求进行回复,如果超过半数以上的节点投票了,那么该 Candidate 就会立即变成 Term 为 1 的 Leader。

    图片

    4) Leader 会周期性地发送心跳消息给所有 Follower,Follower 接收到心跳包,会重新开始计时。

    图片

    3.3 多 Candidate 选举

    1) 1如果有多个 Follower 成为 Candidate,并且所获得票数相同,那么就需要重新开始投票。例如下图中 Candidate B 和 Candidate D 都发起 Term 为 4 的选举,且都获得两票,因此需要重新开始投票。

    图片

    2) 当重新开始投票时,由于每个节点设置的随机竞选超时时间不同,因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低。

    图片

     

    四、日志复制

     

    4.1 日志格式

    日志由含日志索引(log index)的日志条目(log entry)组成。每个日志条目包含它被创建时的 Term 号(下图中方框中的数字),和一个复制状态机需要执行的指令。如果一个日志条目被复制到半数以上的服务器上,就被认为可以提交(Commit)了。

    日志条目中的 Term 号被用来检查是否出现不一致的情况。

    日志条目中的日志索引(一个整数值)用来表明它在日志中的位置。

    图片

    Raft 日志同步保证如下两点;图示说明:

    如果不同日志中的两个日志条目有着相同的日志索引和 Term,则它们所存储的命令是相同的

    这个特性基于这条原则:Leader 最多在一个 Term 内、在指定的一个日志索引上创建一条日志条目,同时日志条目在日志中的位置也从来不会改变。

    如果不同日志中的两个日志条目有着相同的日志索引和 Term,则它们之前的所有条目都是完全一样的

    这个特性由 AppendEntries RPC 的一个简单的一致性检查所保证。在发送 AppendEntries RPC 时,Leader 会把新日志条目之前的日志条目的日志索引和 Term 号一起发送。如果 Follower 在它的日志中找不到包含相同日志索引和 Term 号的日志条目,它就会拒绝接收新的日志条目。

    4.2 日志复制流程

    图片

     

    Leader 负责处理所有客户端的请求。

    Leader 把请求作为日志条目加入到它的日志中,然后并行的向其他服务器发送 AppendEntries RPC 请求,要求 Follower 复制日志条目。

    Follower 复制成功后,返回确认消息。

    当这个日志条目被半数以上的服务器复制后,Leader 提交这个日志条目到它的复制状态机,并向客户端返回执行结果。

    注意:如果 Follower 崩溃或者运行缓慢,再或者网络丢包,Leader 会不断的重复尝试发送 AppendEntries RPC 请求 (尽管已经回复了客户端),直到所有的跟随者都最终复制了所有的日志条目。

    下面,通过一组动图来加深认识:

    1)来自客户端的修改都会被传入 Leader。注意该修改还未被提交,只是写入日志中。

    图片

    2)Leader 会把修改复制到所有 Follower。

    图片

    3)Leader 会等待大多数的 Follower 也进行了修改,然后才将修改提交。

    图片

    4)此时 Leader 会通知的所有 Follower 让它们也提交修改,此时所有节点的值达成一致。

     

    图片

    4.3 日志一致性

    一般情况下,Leader 和 Followers 的日志保持一致,因此日志条目一致性检查通常不会失败。然而,Leader 崩溃可能会导致日志不一致:旧的 Leader 可能没有完全复制完日志中的所有条目。

    4.3.1 Leader 和 Follower 日志不一致的可能

    Leader 和 Follower 可能存在多种日志不一致的可能。

    图片

    图示说明:上图阐述了 Leader 和 Follower 可能存在多种日志不一致的可能,每一个方框表示一个日志条目,里面的数字表示任期号 。

    当一个 Leader 成功当选时,Follower 可能出现以下情况(a-f):

    存在未更新日志条目,如(a、b)。

    存在未提交日志条目,如(c、d)。

    或两种情况都存在,如(e、f)。

    例如,场景 f 可能会这样发生,某服务器在 Term2 的时候是 Leader,已附加了一些日志条目到自己的日志中,但在提交之前就崩溃了;很快这个机器就被重启了,在 Term3 重新被选为 Leader,并且又增加了一些日志条目到自己的日志中;在 Term 2 和 Term 3 的日志被提交之前,这个服务器又宕机了,并且在接下来的几个任期里一直处于宕机状态。

    4.3.2 Leader 和 Follower 日志一致的保证

    Leader 通过强制 Followers 复制它的日志来处理日志的不一致,Followers 上的不一致的日志会被 Leader 的日志覆盖。

    Leader 为了使 Followers 的日志同自己的一致,Leader 需要找到 Followers 同它的日志一致的地方,然后覆盖 Followers 在该位置之后的条目。

    Leader 会从后往前试,每次日志条目失败后尝试前一个日志条目,直到成功找到每个 Follower 的日志一致位点,然后向后逐条覆盖 Followers 在该位置之后的条目。

     

    五、安全性

     

    前面描述了 Raft 算法是如何选举 Leader 和复制日志的。

    Raft 还增加了一些限制来完善 Raft 算法,以保证安全性:保证了任意 Leader 对于给定的 Term,都拥有了之前 Term 的所有被提交的日志条目。

     

    5.1 选举限制

    拥有最新的已提交的日志条目的 Follower 才有资格成为 Leader。

    Raft 使用投票的方式来阻止一个 Candidate 赢得选举除非这个 Candidate 包含了所有已经提交的日志条目。Candidate 为了赢得选举必须联系集群中的大部分节点,这意味着每一个已经提交的日志条目在这些服务器节点中肯定存在于至少一个节点上。如果 Candidate 的日志至少和大多数的服务器节点一样新(这个新的定义会在下面讨论),那么他一定持有了所有已经提交的日志条目。

    RequestVote RPC 实现了这样的限制:RequestVote RPC 中包含了 Candidate 的日志信息, Follower 会拒绝掉那些日志没有自己新的投票请求。

    5.1.1 场如何判断哪个日志条目比较新?

    Raft 通过比较两份日志中最后一条日志条目的日志索引和 Term 来判断哪个日志比较新。

    先判断 Term,哪个数值大即代表哪个日志比较新。

    如果 Term 相同,再比较 日志索引,哪个数值大即代表哪个日志比较新。

    5.1.2 提交旧任期的日志条目

    一个当前 Term 的日志条目被复制到了半数以上的服务器上,Leader 就认为它是可以被提交的。如果这个 Leader 在提交日志条目前就下线了,后续的 Leader 可能会覆盖掉这个日志条目。

    图片

    图示说明:上图解释了为什么 Leader 无法对旧 Term 的日志条目进行提交。

    • 阶段 (a) ,S1 是 Leader,且 S1 写入日志条目为 (Term 2,日志索引 2),只有 S2 复制了这个日志条目。

    • 阶段 (b),S1 下线,S5 被选举为 Term3 的 Leader。S5 写入日志条目为 (Term 3,日志索引 2)。

    • 阶段 (c),S5 下线,S1 重新上线,并被选举为 Term4 的 Leader。此时,Term 2 的那条日志条目已经被复制到了集群中的大多数节点上,但是还没有被提交。

    • 阶段 (d),S1 再次下线,S5 重新上线,并被重新选举为 Term3 的 Leader。然后 S5 覆盖了日志索引 2 处的日志。

    • 阶段 (e),如果阶段 (d) 还未发生,即 S1 再次下线之前,S1 把自己主导的日志条目复制到了大多数节点上,那么在后续 Term 里面这些新日志条目就会被提交。这样在同一时刻就同时保证了,之前的所有旧日志条目就会被提交。

    Raft 永远不会通过计算副本数目的方式去提交一个之前 Term 内的日志条目。只有 Leader 当前 Term 里的日志条目通过计算副本数目可以被提交;一旦当前 Term 的日志条目以这种方式被提交,那么由于日志匹配特性,之前的日志条目也都会被间接的提交。

    当 Leader 复制之前任期里的日志时,Raft 会为所有日志保留原始的 Term,这在提交规则上产生了额外的复杂性。在其他的一致性算法中,如果一个新的领导人要重新复制之前的任期里的日志时,它必须使用当前新的任期号。

    Raft 使用的方法更加容易辨别出日志,因为它可以随着时间和日志的变化对日志维护着同一个任期编号。另外,和其他的算法相比,Raft 中的新领导人只需要发送更少日志条目(其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号)。

     

    六、日志压缩

     

    在实际的系统中,不能让日志无限膨胀,否则系统重启时需要花很长的时间进行恢复,从而影响可用性。Raft 采用对整个系统进行快照来解决,快照之前的日志都可以丢弃。

    每个副本独立的对自己的系统状态生成快照,并且只能对已经提交的日志条目生成快照。快照包含以下内容:

    日志元数据。最后一条已提交的日志条目的日志索引和 Term。这两个值在快照之后的第一条日志条目的 AppendEntries RPC 的完整性检查的时候会被用上。

    系统当前状态。

    当 Leader 要发送某个日志条目,落后太多的 Follower 的日志条目会被丢弃,Leader 会将快照发给 Follower。或者新上线一台机器时,也会发送快照给它。

    图片

    生成快照的频率要适中,频率过高会消耗大量 I/O 带宽;频率过低,一旦需要执行恢复操作,会丢失大量数据,影响可用性。推荐当日志达到某个固定的大小时生成快照。生成一次快照可能耗时过长,影响正常日志同步。可以通过使用 copy-on-write 技术避免快照过程影响正常日志同步。

    说明:本文仅阐述 Raft 算法的核心内容,不包括算法论证、评估等

     

    七、参考资料

     

    1.Raft 一致性算法论文原文

    2.Raft 一致性算法论文译文

    3.Raft 作者讲解视频

    4.Raft 作者讲解视频对应的 PPT

    5.分布式系统的 Raft 算法

    6.Raft 算法详解

    7.Raft: Understandable Distributed Consensus 

    8.sofa-jraft - 蚂蚁金服的 Raft 算法实现库(Java 版)

     

    ​作者:vivo 互联网服务器团队-ZhangPeng

    展开全文
  • 区块链的共识算法和分布一致性算法 转载自某要花钱的网课

    区块链的共识算法和分布一致性算法

    转载自某要花钱的网课
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 1、共识算法 https://www.jianshu.com/p/8e4bbe7e276c 2、一文搞懂Raft算法 https://www.cnblogs.com/xybaby/p/10124083.html 3、解读Raft算法 解读Raft
    展开全文
  • 从分布式一致性算法到区块链共识算法(二) 注意:本文所介绍内容来源于文献:[1]靳世雄,张潇丹,葛敬国,史洪彬,孙毅,李鸣,林业明,姚忠将.区块链共识算法研究综述[J].信息安全学报,2021,6(02):85-100. 本文是对该...
  • # 分布式一致性算法RaftPaxos自1990年提出以后,相当长时间内几乎已成为分布式一致性算法的代名词。但因其难以理解和实现,目前知名实现仅有Chubby、Zookeeper、libpaxos几种,其中Zookeeper使用的ZAB对Paxos做了...
  • # 分布式一致性算法PaxosPaxos是一种基于消息传递的分布式一致性算法,由Leslie Lamport(莱斯利·兰伯特)于1990提出。是目前公认的解决分布式一致性问题的最有效算法之一。### 要解决的问题及应用场景Paxos算法要...
  • 提高互惠[0,1]值偏好关系的一致性或共识性算法
  • 从分布式一致性算法到区块链共识算法 一致性问题 一致性问题是分布式领域最为基础也是最重要的问题。 如果分布式系统能实现“一致”, 对外就可以呈现为一个完美的、可扩展的“虚拟节点”,相对物理节点具备更优越...
  • 共识算法

    2018-09-25 10:03:46
    协议规范(共识算法)由相关的共识规则组成,这些规则可以划分为两个大的核心:工作量 证明与最长链机制。所有规则(共识)的最终体现就是比特币的最长链。共识算法的目的就是保证比特币不停地在最长链条上运转,...
  • 分布式一致共识算法

    万次阅读 2019-04-05 10:28:08
    分布式一致共识算法 UTXO 与账户余额模型 区块链技术是近几年逐渐变得非常热门的技术,以比特币为首的密码货币其实已经被无数人所知晓,但是却很少有人会去研究它们的底层技术,也就是作为一个分布式网络比特币...
  • 摘要:本篇文章是【区块链之技术进阶】的第七篇文章,在之前的文章中咱们多多少少提及了共识算法等相关知识,但是却没有具体地更加深入地了解,本文就为大家掰一掰区块链共识机制与分布式一致性算法,两者究竟有什么...
  • 方法二:非确定性算法 如前所述,为了解决 FLP 不可能性,大部分拜占庭容错协议最终都要基于同步性假设的前提。然而,解决 FLP 不可能性还可以另辟蹊径:非确定性算法。 当当当当,中本聪共识! 认真听讲...
  • 通过相对船体表征分布式共识算法的收敛
  • Raft是分布式环境下的一致性算法,它通过少数服从多数的选举来维持集群内数据的一致性。它与RBFT算法名称有点像,然而Raft算法里不能存在拜占庭节点,而RBFT则能容忍BFT节点的存在。Raft非常类似于paxos协议(参见我...
  • 分布式系统 ...Paxos的前提假设是不存在拜占庭将军问题,即:信道是安全的(信道可靠),发出的信号不会被篡改,否则该算法就不可靠。 如何保证消息没被篡改:数字签名等、 Paxos能达成一致的原因:过...
  • 共识算法和一致

    千次阅读 2018-04-08 14:48:12
    描述的是结果状态,共识则是一种手段。达成某种共识并不意味着就保障了一致。讲,各个节点通常都是相同的确定状态机模型(又称为状态机复制问题,state-machine replication),从相...
  • 所谓分布式共识(consensus),与CAP理论中的一致(consistency)其实是异曲同工,就是在分布式系统中,所有节点对同一份数据的认知能够...保证集群共识算法就叫共识算法,它与一致协议这个词也经常互相通用。
  • 什么是共识算法

    万次阅读 多人点赞 2019-04-05 10:28:26
    本文尝试从源头开始,告诉大家区块链共识算法的来龙去脉。包含以下三部分: 什么是共识算法 著名的共识设计理论 经典的共识算法设计 什么是共识算法 背景 分布式系统集群设计中面临着一个不可回避的问题,一致...
  • Raft是分布式环境下的一致性算法,它通过少数服从多数的选举来维持集群内数据的一致性。它与RBFT算法名称有点像,然而Raft算法里不能存在拜占庭节点,而RBFT则能容忍BFT节点的存在。Raft非常类似于paxos协议(参见...
  • # 分布式一致性算法2PC和3PC为了解决分布式一致性问题,产生了不少经典的分布式一致性算法,本文将介绍其中的2PC和3PC。2PC即Two-Phase Commit,译为二阶段提交协议。3PC即Three-Phase Commit,译为三阶段提交协议。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,170
精华内容 468
关键字:

共识性算法