精华内容
下载资源
问答
  • 分布式事务与一致性算法Paxos raft zab
                   

    说明:以下内容总结自网络

    1.CAP原理

    • 要想数据高可用,就得写多份数据

    • 写多分数据就会导致数据一致性问题

    • 数据一致性问题会引起性能问题

    2.一致性模型

    1. 弱一致性

    2. 最终一致性(一段时间达到一致性)

    3. 强一致

    • 1、2 异步冗余;3是同步冗余

    3.  扩展服务的方案

    • 数据分区: uid % 16

    • 数据镜像:让多有的服务器都有相同的数据,提供相当的服务(冗余存储,一般3份为好)

    4.两种方案的事务问题

    1. A向B汇钱,两个用户不在一个服务器上

    2. 镜像:在不同的服务器上对同一数据的写操作如何保证一致性。

    5. 解决一致性事务问题的技术

    1. Master -Slave

    • 读写请求由Master负责

    • 写请求写到Master后,由Master同步到Slave上

      • 由Master push or Slave pull

      • 通常是由Slave 周期性来pull,所以是最终一致性

    问题: 若在 pull 周期内(不是期间?),master挂掉,那么会导致这个时间片内的数据丢失

    • 若不想让数据丢掉,Slave 只能成为 ReadOnly方式等Master恢复

    • 若容忍数据丢失,可以让 Slave代替Master工作

    如何保证强一致性?

    • Master 写操作,写完成功后,再写 Slave,两者成功后返回成功。若 Slave失败,两种方法

      1. 标记 Slave 不可用报错,并继续服务(等恢复后,再同步Master的数据,多个Slave少了一个而已)

      2. 回滚自己并返回失败

    2. Master-Master

    • 数据同步一般是通过 Master 间的异步完成,所以是最终一致

    • 好处: 一台Master挂掉,另外一台照样可以提供读写服务。当数据没有被赋值到别的Master上时,数据会丢失。

    • 对同一数据的处理问题:Dynamo的Vector Clock的设计(记录数据的版本号和修改者),当数据发生冲突时,要开发者自己来处理

    3.两阶段提交  Two  Phase Commit   _ 2PC

    1. 第一阶段:针对准备工作

      • 协调者问所有节点是否可以执行提交

      • 参与者开始事务,执行准备工作:锁定资源(获取锁操作)

      • 参与者响应协调者,如果事务的准备工作成功,则回应"可以提交",否则,拒绝提交

    2. 第二阶段:

      • 若都响应可以提交,则协调者项多有参与者发送正式提交的命令(更新值),参与者完成正式提交,释放资源,回应完成。协调者收到所有节点的完成响应后结束这个全局事务.。若参与者回应拒绝提交,则协调者向所有的参与者发送回滚操作,并释放资源,当收到全部节点的回滚回应后,取消全局事务

    3. 存在的问题:若一个没提交,就会进行回滚

      • 第一阶段:若消息的传递未接收到,则需要协调者作超时处理,要么当做失败,要么重载

      • 第二阶段:若参与者的回应超时,要么重试,要么把那个参与者即为问题节点,提出整个集群

      • 在第二阶段中,参与者未收到协调者的指示(也许协调者挂掉),则所有参与者会进入“不知所措” 的状态(但是已经锁定了资源),所以引入了三段提交

    4. 三段提交:把二段提交的第一阶段 break 成了两段

    1. 询问

    2. 锁定资源(获取锁)

    3. 提交

    • 核心理念:在询问的时候并不锁定资源,除非所有人都同意了,才开始锁定

    • 好处:当发生了失败或超时时,三段提交可以继续把状态变为Commit 状态,而二段提交则不知所措?

    5. Raxos 算法(少数服从多数)

    • 解决的问题:在一个可能发生异常的分布式系统中如何就某个值达成一致,让整个集群的节点对某个值的变更达成一致

    • 任何一个节点都可以提出要修改某个数据的提案,是否通过这个提案取决于这个集群中是否有超过半数的节点同意(所以节点数总是单数)—— 版本标记。虽然一致性,但是只能对一个操作进行操作啊??

    • 当一个Server接收到比当前版本号小的提案时,则拒绝。当收到比当前大的版本号的提案时,则锁定资源,进行修改,返回OK.   也就是说收到超过一半的最大版本的提案才算成功。

    核心思想

    1. 在抢占式访问权的基础上引入多个acceptor,也就是说当一个版本号更大的提案可以剥夺版本号已经获取的锁。

    2. 后者认同前者的原则:

      • 在肯定旧epoch 无法生成确定性取值时,新的 epoch 会提交自己的valu

      • 一旦 旧epoch形成确定性取值,新的 epoch肯定可以获取到此取值,并且会认同此取值,不会被破坏。

    步骤

    1. P1 请求Acceptor的 #1,Acceptor 这时并没有其他线程获取到锁,所以把锁交给 P1,并返回这时 #1 的值为null

    2. 然后 P1 向 第一个 Acceptor 提交 #1 的值,Acceptor 接受并返回 OK

    3. 这个时候,P2向Acceptor请求#1上的锁,因为版本号更大,所以直接抢占了 P1 的锁。这时 Acceptor 返回了 OK并且返回了 #1 的值

    4. 这时 P1 P向 后面两个 Acceptor 提交 #1 的值,但是由于中间的那个Acceptor 版本号已经更改为 2 了,所以拒绝P1。第三个 Acceptor 接受了,并且返回了 OK

    5. 由于后者认同前者的原则,这时 P1 已经形成确定性取值了 V1 了,这时新的 P2 会认同此取值,而不是提交自己的取值。所以,P2会选择最新的那个取值 也就是V1 进行提交。这时Acceptor 返回 OK

    6.ZAB 协议 ( Zookeeper Atomic  Broadcast) 原子广播协议:保证了发给各副本的消息顺序相同

    定义:原子广播协议 ZAB 是一致性协议,Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的。Zookeeper 使用单一主进程 Leader用于处理客户端所有事务请求,采用 ZAB 协议将服务器状态以事务形式广播到所有 Follower 上,由于事务间可能存在着依赖关系,ZAB协议保证 Leader 广播的变更序列被顺序的处理,一个状态被处理那么它所依赖的状态也已经提前被处理

    核心思想:保证任意时刻只有一个节点是Leader,所有更新事务由Leader发起去更新所有副本 Follower,更新时用的是 两段提交协议,只要多数节点 prepare 成功,就通知他们commit。各个follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务

    协议状态

    1. Looking:系统刚启动时 或者 Leader 崩溃后正处于选举状态

    2. Following:Follower 节点所处的状态,Follower与 Leader处于数据同步状态

    3. Leading:Leader 所处状态,当前集群中有一个 Leader 为主进程

    • ZooKeeper启动时所有节点初始状态为Looking,这时集群会尝试选举出一个Leader节点,选举出的Leader节点切换为Leading状态;当节点发现集群中已经选举出Leader则该节点会切换到Following状态,然后和Leader节点保持同步;当Follower节点与Leader失去联系时Follower节点则会切换到Looking状态,开始新一轮选举;在ZooKeeper的整个生命周期中每个节点都会在Looking、Following、Leading状态间不断转换。

    • 选举出Leader节点后 ZAB 进入原子广播阶段,这时Leader为和自己同步每个节点 Follower 创建一个操作序列,一个时期一个 Follower 只能和一个Leader保持同步

    阶段

    1. Election: 在 Looking状态中选举出 Leader节点,Leader的LastZXID总是最新的(只有lastZXID的节点才有资格成为Leade,这种情况下选举出来的Leader总有最新的事务日志)。在选举的过程中会对每个Follower节点的ZXID进行对比只有highestZXID的Follower才可能当选Leader

      • 每个Follower都向其他节点发送选自身为Leader的Vote投票请求,等待回复;

      • Follower接受到的Vote如果比自身的大(ZXID更新)时则投票,并更新自身的Vote,否则拒绝投票;

      • 每个Follower中维护着一个投票记录表,当某个节点收到过半的投票时,结束投票并把该Follower选为Leader,投票结束;

    2. Discovery:Follower 节点向准 Leader推送 FollwerInfo,该信息包含了上一周期的epoch,接受准 Leader 的 NEWLEADER 指令

    3. Sync:将 Follower 与 Leader的数据进行同步,由Leader发起同步指令,最终保持数据的一致性

    4. Broadcast:Leader广播 Proposal 与 Commit,Follower 接受 Proposal 与 commit。因为一个时刻只有一个Leader节点,若是更新请求,只能由Leader节点执行(若连到的是 Follower 节点,则需转发到Leader节点执行;读请求可以从Follower 上读取,若是要最新的数据,则还是需要在 Leader上读取)

      • 消息广播使用了TCP协议进行通讯所有保证了接受和发送事务的顺序性。广播消息时Leader节点为每个事务Proposal分配一个全局递增的ZXID(事务ID),每个事务Proposal都按照ZXID顺序来处理(Paxos 保证不了)

      • Leader节点为每一个Follower节点分配一个队列按事务ZXID顺序放入到队列中,且根据队列的规则FIFO来进行事务的发送。

    5. Recovery :根据Leader的事务日志对Follower 节点数据进行同步更新

      • 同步策略:

        1. SNAP :如果Follower数据太老,Leader将发送快照SNAP指令给Follower同步数据;

        2. DIFF :Leader发送从Follolwer.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据;

        3. TRUNC :当Follower.lastZXID比Leader.lastZXID大时,Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令让Follower丢弃该段数据;(当老Leader在Commit前挂掉,但是已提交到本地)

      • Follower将所有事务都同步完成后Leader会把该节点添加到可用Follower列表中;

      • Follower接收Leader的NEWLEADER指令,如果该指令中epoch比当前Follower的epoch小那么Follower转到Election阶段

    7. Raft 算法

    • Raft 算法也是一种少数服从多数的算法,在任何时候一个服务器可以扮演以下角色之一:

      1. Leader:负责 Client 交互 和 log 复制,同一时刻系统中最多存在一个

      2. Follower:被动响应请求 RPC,从不主动发起请求 RPC

      3. Candidate : 由Follower 向Leader转换的中间状态

    • 在选举Leader的过程中,是有时间限制的,raft 将时间分为一个个 Term,可以认为是“逻辑时间”:

      1. 每个 Term中至多存在1个 Leader

      2. 某些 Term由于不止一个得到的票数一样,就会选举失败,不存在Leader。则会出现 Split Vote  ,再由候选者发出邀票

      3. 每个 Server 本地维护 currentTerm

    • 选举过程:

      1. 自增 CurrentTerm,由Follower 转换为 Candidate,设置 votedFor 为自身,并行发起 RequestVote RPC,不断重试,直至满足下列条件之一为止:

        • 获得超过半数的Server的投票,转换为 Leader,广播 HeatBeat

        • 接收到 合法 Leader 的 AppendEnties RPC,转换为Follower

        • 选举超时,没有 Server选举成功,自增 currentTerm ,重新选举

      2. 当Candidate 在等待投票结果的过程中,可能会接收到来自其他Leader的 AppendEntries RPC ,如果该 Leader 的 Term 不小于本地的 Current Term,则认可该Leader身份的合法性,主动降级为Follower,反之,则维持 candida 身份继续等待投票结果

      3. Candidate 既没有选举成功,也没有收到其他 Leader 的 RPC (多个节点同时发起选举,最终每个 Candidate都将超时),为了减少冲突,采取随机退让策略,每个 Candidate 重启选举定时器

    • 日志更新问题:

      如果在日志复制过程中,发生了网络分区或者网络通信故障,使得Leader不能访问大多数Follwers了,那么Leader只能正常更新它能访问的那些Follower服务器,而大多数的服务器Follower因为没有了Leader,他们重新选举一个候选者作为Leader,然后这个Leader作为代表于外界打交道,如果外界要求其添加新的日志,这个新的Leader就按上述步骤通知大多数Followers,如果这时网络故障修复了,那么原先的Leader就变成Follower,在失联阶段这个老Leader的任何更新都不能算commit,都回滚,接受新的Leader的新的更新。

    • 流程:

      1. Client 发送command 命令给 Leader

      2. Leader追加日志项,等待 commit 更新本地状态机,最终响应 Client

      3. 若 Client超时,则不断重试,直到收到响应为止(重发 command,可能被执行多次,在被执行但是由于网络通信问题未收到响应)

        • 解决办法:Client 赋予每个 Command唯一标识,Leader在接收 command 之前首先检查本地log

    9. paxos 算法与 raft 算法的差异

    1. raft强调是唯一leader的协议,此leader至高无上

    2. raft:新选举出来的leader拥有全部提交的日志,而 paxos 需要额外的流程从其他节点获取已经被提交的日志,它允许日志有空洞

    • 相同点:得到大多数的赞成,这个 entries 就会定下来,最终所有节点都会赞成

    NWR模型

    • N: N个备份

    • W:要写入至少 w 份才认为成功

    • R : 至少读取 R 个备份

    • W+ R > N    ——>    R > N - W(未更新成功的) ,代表每次读取,都至少读取到一个最新的版本(更新成功的),从而不会读到一份旧数据

    • 问题:并非强一致性,会出现一些节点上的数据并不是最新版本,但却进行了最新的操作

    • 版本冲突问题:矢量钟 Vector Clock : 谁更新的我,我的版本号是什么(对于同一个操作者的同一操作,版本号递增)

    参考资料:

    http://www.tuicool.com/articles/IfQR3u3

    http://blog.csdn.net/chen77716/article/details/7309915

    http://www.infoq.com/cn/articles/distributed-system-transaction-processing/

    http://www.jdon.com/artichect/raft.html

    http://blog.csdn.net/cszhouwei/article/details/38374603


               
    展开全文
  • 一致性算法——PaxosRaftZAB 1.1 CAP理论 分布式系统的CAP理论:理论首先把分布式系统中的三个特性进行了如下归纳: ● 一致性(C):在分布式系统中的所有数据备份,在同一时刻是否同样的值。(等同于所有节点...

    一致性算法——Paxos、Raft、ZAB

    1.1 CAP理论

    在这里插入图片描述

    分布式系统的CAP理论:理论首先把分布式系统中的三个特性进行了如下归纳:
    ● 一致性(C):在分布式系统中的所有数据备份,在同一时刻是否同样的值。(等同于所有节点访问同一份最新的数据副本)

    ● 可用性(A):在集群中一部分节点故障后,集群整体是否还能响应客户端的读写请求。(对数据更新具备高可用性)

    ● 分区容错性(P):以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。

    1.2 什么是一致性?

    有两种一致性模型,分别是弱一致性和强一致性

    1)弱一致性

    (1)最终一致性

    ​ DNS 域名系统英文Domain Name System,缩写DNS

    在这里插入图片描述
    在域名解析服务提供商上添加域名解析,一般都是10分钟以内之后才能通过域名访问到当前添加的网站,因为你的域名解析ip服务只在当前供应商的服务器上添加,同步到全球或者全国需要一定的时间,在其他地区或者其他DNS服务器就有可能访问不到当前网站,需要等待一段时间。

    2 )强一致性

    (1)同步

    (2)Paxos

    (3)Raft(multi-paxos)

    (4)ZAB(multi-paxos)

    1.3 Paxos

    1)明确问题

    一致性算法的为什么会出现,因为数据不能存在单节点上,但是存在集群中有一致性的问题(网络、宕机等原因)。

    但是有其他的算法比如说主从,但是主从的可用性极低,一旦有一个节点宕机则无法对外提供服务。

    所以需要在保持一致性的同时尽可能的提高可用性。

    2)基本思想

    多数派:
    每次写入都要保证写入N/2的节点,每次读保证从何大于N/2个几点中读取
    多数派加顺序存取:
    在其基础上,因为有集群的概念,所以还有一个系统正确性需要保证,所以顺序非常重要!
    

    在这里插入图片描述

    3)Basic Paxos

    Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人现在在微软研究院)于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。

    在这里插入图片描述

    (1)角色介绍:

    Client:产生议题者或者是请求发起者 ,类似于民众

    Proposer :提议者,接收民众的建议并提出议案,在冲突时有调节作用,类似于议员

    Acceptor:决策者或者是投票者,国会成员或者议员等

    Learner:最终决策记录者 备份,对集群一致性没有影响

    (2)基本流程:

    在这里插入图片描述

    (3)全票通过的场景

    在这里插入图片描述

    (4)部分Accepter通过

    但是达到了1/2以上的节点,提案通过,反之则不通过
    在这里插入图片描述

    (5)proposer宕机或者失败

    当前提案不会通过,但是有其他的proposer处理(客户端需要有重试机制)

    在这里插入图片描述

    (6)活锁问题的产生

    https://www.cnblogs.com/sunnyCx/p/8108366.html

    在这里插入图片描述

    timeout解决

    4)Multi Paxos

    (1)Basix Paxos问题

    实现难
    效率低(2轮RPC,来回验证,效率低)
    活锁
    

    (2)区别

    Leader:唯一propser,选举产生
    所有的请求都经过leader
    

    (3)基本流程

    在这里插入图片描述

    (4)简化角色

    在这里插入图片描述

    1.4 Raft

    http://thesecretlivesofdata.com/raft/

    1)角色

    (1)Leader

    (2)Follwer

    (3)Candidate

    2)三个场景

    (1)Leader Election

    (2)Log Repliction

    (3)Safety

    10.5 ZAB

    1.基本与Raft相同
    2.叫法的区别:zab将某一个leader的周期成为epoch,而Raft称之为term
    3.心跳方向为leader向follower。ZAB则相反
    

    1)协议原理

    ZAB主要包括消息广播和崩溃恢复两个过程,进一步可以分为三个阶段,分别是发现(Discovery)、同步(Synchronization)、广播(Broadcast)阶段。ZAB的每一个分布式进程会循环执行这三个阶段,称为主进程周期。

    · 发现,选举产生PL(prospective leader),PL收集Follower epoch(cepoch),根据Follower的反馈,PL产生newepoch(每次选举产生新Leader的同时产生新epoch)。

    · 同步,PL补齐相比Follower多数派缺失的状态、之后各Follower再补齐相比PL缺失的状态,PL和Follower完成状态同步后PL变为正式Leader(established leader)。

    · 广播,Leader处理客户端的写操作,并将状态变更广播至Follower,Follower多数派通过之后Leader发起将状态变更落地(deliver/commit)。

    在正常运行过程中,ZAB协议会一直运行于阶段三来反复进行消息广播流程,如果出现崩溃或其他原因导致Leader缺失,那么此时ZAB协议会再次进入发现阶段,选举新的Leader。

    2)运行状态

    每个进程都有可能处于如下三种状态之一

    · LOOKING:Leader选举阶段。

    · FOLLOWING:Follower服务器和Leader服务器保持同步状态。

    · LEADING:Leader服务器作为主进程领导状态。

    展开全文
  • 目录前言一、paxosbasic paxos证明角色过程缺陷Multi-paxospaxos的区别过程二、RaftRaft和multi-paxos的区别问题定义角色定义选举过程日志同步过程网络故障处理ZABraft区别 前言 对于分布式中,多个节点的数据强...

    前言

    对于分布式中,多个节点的数据强一致性问题,通常采用如下策略或算法为解决方案。

    • 主从同步
    • paxos
      • basic paxos
      • multi paxos
      • fast paxos
    • Raft
    • ZAB

    一、paxos

    basic paxos

    paxos 首先假设通信是安全的

    证明

    角色

    • Proposer 提议发起者,处理客户端请求,将客户端的请求发送到集群中,以便决定这个值是否可以被批准。
    • Acceptor 提议批准者,负责处理接收到的提议,他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
    • learner 记录者,负责记录提案。

    过程

    client Proposer Acceptor1 Acceptor2 Acceptor3 Learneras request(value) 客户端发起一个提案为value的请求 为提案value生成一个编号n 提出编号为n的提案 提出编号为n的提案 提出编号为n的提案 n>当前Acceptor记录的最大编号 接受这个提案 n>当前Acceptor记录的最大编号 接受这个提案 n>当前Acceptor记录的最大编号 接受这个提案 alt [第一阶段:prepare] 同意提案的响应过半数 则继续第二阶段 否则响应client为错误 提交提案内容acceprt(n,value) 提交提案内容acceprt(n,value) 提交提案内容acceprt(n,value) n>=当前Acceptor记录的最大编号 接受这个提案 提交(n,value)到learner记录 n>=当前Acceptor记录的最大编号 接受这个提案 提交(n,value)到learner记录 n>=当前Acceptor记录的最大编号 接受这个提案 提交(n,value)到learner记录 accpet数量过半,则value达成共识 响应client的请求 alt [第二阶段:accept] client Proposer Acceptor1 Acceptor2 Acceptor3 Learneras

    缺陷

    • 效率低下
    • 难以实现
    • paxos存在活锁问题,多个proposer提出提案,且n不断增长,则任何一个提案都无法被达成。
    • 如果learner不止一个,则learner间数据同步依然是个问题

    Multi-paxos

    multi paxos 是paxos算法的优化,升级版。以便该算法能够被应用在现实中。
    lamport 对multi-paxos 的具体实现其实是并没有细节的指定的, 只是简单提了一下. 所以有各种不同的multi-paxos 的实现

    和paxos的区别

    multi-paxos对角色进行了新的抽象

    • Leader/master:唯一的proposer ,
      • multi-paxos规定只能有一个提案提出者,所有请求都需要经过leader。
      • 这个策略保证了提案的有序,所以简化掉了paxos的prepare阶段。
    • node: 去掉了各种角色,统一为节点,更接近计算机实现
      • 通过一定的策略竞选出某个节点为第n任主节点,则其它节点为从节点
      • 从节点负责接收主节点的数据,也就是提案,可以理解为数据库的主从同步。

    过程

    1. 发起者(leader)直接告诉其他节点,准备递交协议号为I+1的协议
    2. 收到了大部分从节点的回复后,主节点就直接回复client成功写入

    二、Raft

    因为paxos难以理解,难以实现,所以raft应运而生。
    可以说raft是multi-paxos的优化升级版,更易理解,且补充了实现方案。
    paxos 是对于一个问题达成一致的协议
    而raft 本身是对一堆连续的问题达成一致的协议
    raft是etcd的采用的共识算法

    动画演示 http://thesecretlivesofdata.com/raft/
    官网:https://raft.github.io/

    Raft和multi-paxos的区别

    raft 是基于对multi paxos 的两个限制形成的

    • 发送的请求的是连续的, 也就是说raft 的append 操作必须是连续的. 而paxos 可以并发的. (其实这里并发只是append log 的并发提高, 应用的state machine 还是必须是有序的)
    • 选主是有限制的, 必须有最新, 最全的日志节点才可以当选. 而multi-paxos 是随意的 所以raft 可以看成是简化版本的multi paxos(这里multi-paxos 因为允许并发的写log, 因此不存在一个最新, 最全的日志节点, 因此只能这么做. 这样带来的麻烦就是选主以后, 需要将主里面没有的log 给补全, 并执行commit 过程)

    问题定义

    raft将共识问题划分成三个子问题,实现了这三个子问题,则实现了共识问题。

    • 选主
    • log同步
    • safety 在所有的操作中,集群共识一直是一致。

    角色定义

    • leader 接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上后告诉Follower提交日志。
    • follower 接受并持久化Leader同步的日志,在Leader告之日志可以提交之后,提交日志。
    • candidate follower在精选leader时,会先变成candidate

    选举过程

    1. 一个follower节点总是在等待超时,在超时前接收到leader的心跳,则重置超时。如果超时,则变为candidate节点开始竞选,任期(term)+1,Vote count为1(自己投了自己)。并向其他节点发送竞选通知。
    2. 如果得到选票响应超过半数,则该节点变为leader节点。并周期向其他节点发送心跳。
    3. 如果得到选票响应不超过半数,则等待随机时间。如果期间内没有给其他节点投票,则发起第二轮选举。

    日志同步过程

    client leader node1 node2 客户端向leader发送请求 内容为set 1 记录log:set 1 同步log:set 1 同步log:set 1 响应 响应 如果响应数大于半数 确认log:set 1 success 确认log:set 1 确认log:set 1 client leader node1 node2

    网络故障处理

    1.网络分区
    则每个分区都会产生一个leader,但只有节点较多的分区能够保存数据成功。
    在分区恢复后,任期较低的leader节点变为follower,并从leader节点同步日志。


    ZAB

    zab 与raft基本相同,也是multi-paxos的一种实现
    是zookeeper的实现算法

    与raft区别

    • zab中一个leader周期叫做epoch raft中叫做term
    • zab心跳包由从节点发往主节点,raft是主节点发往从节点
    展开全文
  • Zab Paxos raft

    2016-12-05 15:17:54
    《分布式系统理论进阶 - Paxos》介绍了一致性协议Paxos,今天我们来学习另外两个常见的一致性协议——RaftZab。通过与Paxos对比,了解RaftZab的核心思想、加深对一致性协议的认识。   Raft Paxos偏向于理论...

    2016-10-26 21:50 by bangerlee, 495 阅读, 0 评论, 收藏编辑

    引言

    《分布式系统理论进阶 - Paxos》介绍了一致性协议Paxos,今天我们来学习另外两个常见的一致性协议——Raft和Zab。通过与Paxos对比,了解Raft和Zab的核心思想、加深对一致性协议的认识。

     

    Raft

    Paxos偏向于理论、对如何应用到工程实践提及较少。理解的难度加上现实的骨感,在生产环境中基于Paxos实现一个正确的分布式系统非常难[1]

    Raft[2][3]在2013年提出,提出的时间虽然不长,但已经有很多系统基于Raft实现。相比Paxos,Raft的买点就是更利于理解、更易于实行。

     

    为达到更容易理解和实行的目的,Raft将问题分解和具体化:Leader统一处理变更操作请求,一致性协议的作用具化为保证节点间操作日志副本(log replication)一致,以term作为逻辑时钟(logical clock)保证时序,节点运行相同状态机(state machine)[4]得到一致结果。Raft协议具体过程如下:

    1. Client发起请求,每一条请求包含操作指令
    2. 请求交由Leader处理,Leader将操作指令(entry)追加(append)至操作日志,紧接着对Follower发起AppendEntries请求、尝试让操作日志副本在Follower落地
    3. 如果Follower多数派(quorum)同意AppendEntries请求,Leader进行commit操作、把指令交由状态机处理
    4. 状态机处理完成后将结果返回给Client

    指令通过log index(指令id)和term number保证时序,正常情况下Leader、Follower状态机按相同顺序执行指令,得出相同结果、状态一致。

     

    宕机、网络分化等情况可引起Leader重新选举(每次选举产生新Leader的同时,产生新的term)、Leader/Follower间状态不一致。Raft中Leader为自己和所有Follower各维护一个nextIndex值,其表示Leader紧接下来要处理的指令id以及将要发给Follower的指令id,LnextIndex不等于FnextIndex时代表Leader操作日志和Follower操作日志存在不一致,这时将从Follower操作日志中最初不一致的地方开始,由Leader操作日志覆盖Follower,直到LnextIndex、FnextIndex相等。

     

    Paxos中Leader的存在是为了提升决议效率,Leader的有无和数目并不影响决议一致性,Raft要求具备唯一Leader,并把一致性问题具体化为保持日志副本的一致性,以此实现相较Paxos而言更容易理解、更容易实现的目标。

     

    Zab

    Zab[5][6]的全称是Zookeeper atomic broadcast protocol,是Zookeeper内部用到的一致性协议。相比Paxos,Zab最大的特点是保证强一致性(strong consistency,或叫线性一致性linearizable consistency)。

     

    和Raft一样,Zab要求唯一Leader参与决议,Zab可以分解成discovery、sync、broadcast三个阶段:

    • discovery: 选举产生PL(prospective leader),PL收集Follower epoch(cepoch),根据Follower的反馈PL产生newepoch(每次选举产生新Leader的同时产生新epoch,类似Raft的term)
    • sync: PL补齐相比Follower多数派缺失的状态、之后各Follower再补齐相比PL缺失的状态,PL和Follower完成状态同步后PL变为正式Leader(established leader)
    • broadcast: Leader处理Client的写操作,并将状态变更广播至Follower,Follower多数派通过之后Leader发起将状态变更落地(deliver/commit)

    Leader和Follower之间通过心跳判别健康状态,正常情况下Zab处在broadcast阶段,出现Leader宕机、网络隔离等异常情况时Zab重新回到discovery阶段。

     

    了解完Zab的基本原理,我们再来看Zab怎样保证强一致性,Zab通过约束事务先后顺序达到强一致性,先广播的事务先commit、FIFO,Zab称之为primary order(以下简称PO)。实现PO的核心是zxid。

     

    Zab中每个事务对应一个zxid,它由两部分组成:<e, c>,e即Leader选举时生成的epoch,c表示当次epoch内事务的编号、依次递增。假设有两个事务的zxid分别是z、z',当满足 z.e < z'.e 或者 z.e = z'.e && z.c < z'.c 时,定义z先于z'发生(z < z')。

     

    为实现PO,Zab对Follower、Leader有以下约束:

    1. 有事务z和z',如果Leader先广播z,则Follower需保证先commit z对应的事务
    2. 有事务z和z',z由Leader p广播,z'由Leader q广播,Leader p先于Leader q,则Follower需保证先commit z对应的事务
    3. 有事务z和z',z由Leader p广播,z'由Leader q广播,Leader p先于Leader q,如果Follower已经commit z,则q需保证已commit z才能广播z'

    第1、2点保证事务FIFO,第3点保证Leader上具备所有已commit的事务。

     

    相比Paxos,Zab约束了事务顺序、适用于有强一致性需求的场景。

     

    Paxos、Raft、Zab再比较

    除Paxos、Raft和Zab外,Viewstamped Replication(简称VR)[7][8]也是讨论比较多的一致性协议。这些协议包含很多共同的内容(Leader、quorum、state machine等),因而我们不禁要问:Paxos、Raft、Zab和VR等分布式一致性协议区别到底在哪,还是根本就是一回事?[9]

     

    Paxos、Raft、Zab和VR都是解决一致性问题的协议,Paxos协议原文倾向于理论,Raft、Zab、VR倾向于实践,一致性保证程度等的不同也导致这些协议间存在差异。下图帮助我们理解这些协议的相似点和区别[10]

    相比Raft、Zab、VR,Paxos更纯粹、更接近一致性问题本源,尽管Paxos倾向理论,但不代表Paxos不能应用于工程。基于Paxos的工程实践,须考虑具体需求场景(如一致性要达到什么程度),再在Paxos原始语意上进行包装。

     

    小结

    以上介绍分布式一致性协议Raft、Zab的核心思想,分析Raft、Zab与Paxos的异同。实现分布式系统时,先从具体需求和场景考虑,Raft、Zab、VR、Paxos等协议没有绝对地好与不好,只是适不适合。

     

    [1] Paxos made live - An engineering perspective, Tushar Chandra, Robert Griesemer and Joshua Redstone, 2007

    [2] In Search of an Understandable Consensus Algorithm, Diego Ongaro and John Ousterhout, 2013

    [3] In Search of an Understandable Consensus Algorithm (Extended Version), Diego Ongaro and John Ousterhout, 2013

    [4] Implementing Fault-Tolerant Services Using the State Machine, Fred B. Schneider, 1990

    [5] Zab:High-performance broadcast for primary-backup systems, FlavioP.Junqueira,BenjaminC.Reed,andMarcoSerafini, 2011

    [6] ZooKeeper's atomic broadcast protocol: Theory and practice, Andr´e Medeiros, 2012

    [7] Viewstamped Replication A New Primary Copy Method to Support Highly-Available Distributed Systems, Brian M.Oki and Barbar H.Liskov, 1988

    [8] Viewstamped Replication Revisited, Barbara Liskov and James Cowling, Barbara Liskov and James Cowling ,2012

    [9] Can’t we all just agree? The morning paper, 2015

    [10] Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab, Robbert van Renesse, Nicolas Schiper and Fred B. Schneider, 2014

     

    http://www.cnblogs.com/bangerlee/p/5991417.html

    展开全文
  • PaxosZABRaft对比

    2020-09-20 09:59:38
    什么是Raft? Raft一种用来管理日志复制的一致性算法 分为三个角色:leader(集群主节点)、follower(跟随节点)、candidate(无leader情况下会有follower升级为这个) 升级顺序:follower->candidate->leader ...
  • PaxosZABRAFT协议

    2018-06-05 08:06:00
    这三个都是分布式一致性协议,ZAB基于Paxos修改后用于ZOOKEEPER协议,RAFT协议出现在ZAB协议之后,与ZAB差不多,也有很大区别。 1. Paxos 分布式节点分为3种角色, Proposer, Acceptor, Learner Proposer:提出...
  • 其他参考: 分布式事务与一致性算法Paxos &...今天我对 Paxos, Zab, Raft 一一做了细致的了解。趁着还比较熟悉的时间节点,对这三个协议的异同做一个对比。 下面是这三个协议描述的链接地址: 希望...
  • paxos zab raft个人理解

    千次阅读 2017-05-16 20:33:43
    paxos zab raft
  • paxoszab and raft(转载编辑)

    千次阅读 2015-11-06 14:14:32
    PAXOS VS ZAB 2014-07-24 10:39 810人阅读 评论(2) 收藏 举报 我们已经在上面的分析中,我们已经看到observer模型在多机场景下的问题,所以,paxos模型的目标就是解决这个问题,他解决这个问题的方法就是quorum...
  • PaxosRaftZAB

    2019-07-21 00:12:34
    https://blog.csdn.net/qq_34370153/article/details/80998622
  • raft 的选主,日志复制,安全性保障。raft 相比于 paxos, zab的实现 差异对比。毕竟风骚, 毕竟大潮。
  • 一致性算法PaxosZAB

    2021-06-15 08:04:17
    一致性算法的出现是为了解决一致性问题,一致性问题是指对于一组服务器(集群),给定一组操作,需要使用一种协议使得它们的结果最终达成一致,常用的一致性算法有 PaxosRaftZAB 算法等。 如何构建一个既兼顾...
  • Paxos,Raft,ZAB

    2020-12-25 22:32:11
    文章目录Paxos前言一、背景二、一致性强一致性的算法——主从同步强一致性的算法——多数派强一致性的算法——Basice Paxos强一致性的算法——Multi Paxos强一致性的算法——Raft强一致性的算法——ZAB总结 ...
  • 为什么需要一致性 数据不能存在单个节点(主机)上,否则可能出现单点故障。 多个节点(主机)需要... Raft(muti-paxosZAB(muti-paxos) 弱一致性 说明:也叫最终一致性,系统不保证改变提交以后
  • PaxosRaftZab一致性协议-RaftRaft是一个一致性算法,旨在易于理解。它提供了Paxos的容错和性能。不同之处在于它被分解为相对独立的子问题,它清楚地解决了实际系统所需的所有主要部分。我们希望Raft能够为更...
  • 分布式一致性算法(PaxosRaftZAB) 仅用作自己记录 CAP理论 一般来说,对于一个分布式系统,不能同时满足以下三点: Consistency (一致性) Availability (可用性) Partition Tolerance (分区容错性) 典型...
  • 分布式系统协议PaxosRaftZAB 文章转载自:https://zhuanlan.zhihu.com/p/147691282 首先得放在开头,分布式系统的一致性协议一直是分布式系统的难题,本人没有阅读过 Lamport 老人家的论文原文(估计直接读也...
  • multi-paxosraftzab协议的核心区别

    千次阅读 2020-08-23 10:45:15
    ”由此可见,实际上raftzab等一致性算法都是在paxos的基础上通过增加或者调整一些限制条件演进而来的。本文就是结合自己的理解,来分析这些算法在演进过程中所做的取舍。本文不打算再具体介绍每种算法的过程,如果...
  • PaxosZAB协议

    2020-04-02 01:30:04
    一、Paxos协议 为保证分布式系统的高可靠和高可用性,数据在系统中一般存储多个副本。当某个副本所在的节点出现故障时,分布式系统能够自动将服务切换到其他的副本,从而实现自动容错。同一份数据的多个副本中往往有...
  • 很多人喜欢把 Paxos 说成是一致性协议,但是一致性这个词其实会给大家误导,会把这个一致性和 ACID 的一致性...本篇面试内容划重点:PaxosRaft 的主要内容。 Paxos 协议 Paxos 是最基础的分布式共识算法,...
  • 分布式事务与一致性算法Paxos & raft & zab
  • raft 协议和 zab 协议区别4. NWR5. Gossip6. 一致性 Hash6.1. 一致性 Hash 特性6.2. 一致性 Hash 原理 一致性算法 1. Paxos Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是...

空空如也

空空如也

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

paxosraftzab