分布式一致性算法Paxos、Raft 及 Zookeeper ZAB

这篇具有很好参考价值的文章主要介绍了分布式一致性算法Paxos、Raft 及 Zookeeper ZAB。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

国科大学习生活(期末复习资料、课程大作业解析、学习文档等): 文章专栏(点击跳转)
大数据开发学习文档(分布式文件系统的实现,大数据生态圈学习文档等): 文章专栏(点击跳转)

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB

1. 什么是分布式一致性算法?

分布式一致性算法是用于在分布式系统中确保数据一致性的一类算法。在分布式计算环境中,数据通常会分布在多个节点或副本中,并且这些节点可能由于网络延迟、故障或其他原因而导致数据的不一致。因此,分布式一致性算法的目标是确保分布式系统中的所有节点最终都能达到一致的状态。
分布式一致性算法可以分为两种主要类型:强一致性和弱一致性。

  1. 强一致性算法(Strong Consistency):强一致性算法保证在任何时刻,系统中的任意节点都可以看到相同的数据副本,并且对数据的任何操作都会立即反映在系统的其他部分。常见的强一致性算法包括Paxos和Raft。
  2. 弱一致性算法(Weak Consistency):弱一致性算法允许在分布式系统中的不同节点之间存在一定时间上的数据不一致,以提高系统的可用性和性能。弱一致性算法通常以最终一致性为目标,即系统最终会达到一致的状态。常见的弱一致性算法包括Gossip协议和CRDTs(Conflict-free Replicated Data Types)。

分布式一致性算法的选择取决于系统的需求和特定的应用场景。强一致性算法提供了严格的一致性保证,但可能会对性能产生较大的影响。而弱一致性算法可以在某些场景下提供更高的性能,但对数据的一致性要求较低
因此,在设计分布式系统时,需要根据实际需求综合考虑一致性和性能之间的权衡。

1.1 Paxos一致性协议

Paxos是一种分布式系统中的一致性算法,用于解决分布式系统中节点之间的数据一致性问题。它是由Leslie Lamport于1990年提出的。在 Paxos 算法中,把数据修改用提案标识:Proposal:提案,即分布式系统的修改请求,可以表示为[提案编号N,提案内容value]

在 Paxos 算法中有三种角色:Proposer,Acceptor,Learners(注意,每个节点都可以身兼数职)

  • Proposer :发起提案,只要 Proposer 发的提案被半数以上 Acceptor 接受,Proposer 就认为该提案里的 value 被选定了。
  • Acceptor : 只要 Acceptor 接受了某个提案,Acceptor 就认为该提案里的 value 被选定了。不同意比自己以前接收过的提案编号要小的提案,例如A以前给N号提案表决过,那么再收到小于等于N号的提案时就直接拒绝了
  • Learners : Acceptor 告诉 Learner 哪个 value 被选定,Learner 就认为那个 value 被选定。类似记录被通过提案的记录员,负责记录提案

Paxos算法的核心思想是通过多个轮次的消息传递和投票来达成共识。算法的主要流程可以概括如下:

  1. 准备阶段(Prepare):提议者(Proposer)向接受者(Acceptor)发送Prepare请求,在接受者中选择一个提案编号(Proposal Number)作为准备的回应。
  2. 承诺阶段(Promise):如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求,且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应Propose反馈给 Proposer,同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。
  3. 学习阶段(Learner):如果提议者(Proposer)收到了大多数接受者(Acceptor)的承诺(Promise),那么它会向所有节点发送确定的请求(Accept请求),要求它们接受提案。接受者在接收到大多数的接受请求后,就可以接受该提案。
    分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

通过多个轮次的消息传递,Paxos算法最终可以使得所有节点达成一致,并选择一个确定的提案作为共识结果。

Paxos示例1:
分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享
分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享
分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

Paxos示例2:
分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

Paxos算法是一种高度复杂的算法,尤其是在实现细节和各种优化策略方面。它是分布式系统中的重要工具,用于确保数据的一致性和可靠性。

1.2 Paxos算法缺陷

在网络复杂的情况下,一个应用Paxos算法的分布式系统,可能很久无法收敛,甚至陷入活锁的情况:

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

为解决这种问题的出现,下面我们来介绍另一种一致性算法:Raft。

1.3 Raft一致性协议

Raft 是一种分布式一致性算法,用于在分布式系统中实现数据的一致性和高可用性。它由 Diego Ongaro 和 John Ousterhout 在 2013 年提出,并于 2014 年发表的论文中详细描述了算法的设计原则和机制。

根据Paxos的改进:整个系统只有一个Proposer,称之为Leader
若集群中没有Leader,则在集群中选出一个节点并声明它为第M任Leader。集群的Acceptor只表决最新的Leader发出的最新的提案,其他步骤和Paxos相同。Raft 和 Paxos 一样只要保证 n/2+1 节点正常就能够提供服务;Raft 把算法流程分为三个子问题:

  • 选举(Leader election)
  • 日志复制(Log replication)
  • 安全性(Safety)
    分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

Raft 算法的领导者选举机制具有以下过程:

  1. 初始状态:当一个 Raft 集群启动时,所有节点都处于 Follower 状态。每个节点都等待接收来自 Leader 的心跳消息。
  2. Follower 成为 Candidate:如果一个 Follower 在一段时间内未收到来自 Leader 的心跳消息,它将成为 Candidate,并开始发起选举。
  3. 发起选举:一旦成为 Candidate,节点将增加自己的当前任期号(term),然后发送包含该任期号和候选人 ID 的请求给其他节点。每个节点只能投一次票,因此在一次选举中只会有一个 Candidate 获胜。
  4. 投票过程:每个节点在收到来自 Candidate 的选举请求后,会根据以下条件进行投票决策:
    • 如果该节点已经投过票给了其他 Candidate,并且该 Candidate 的任期号更大,则拒绝投票。
    • 如果该节点的日志更新较新,没有落后于 Candidate 的日志,则支持该 Candidate 并重置自己的选举超时计时器。
  5. 选举胜出条件:一个 Candidate 可以成为新的 Leader,需要满足以下条件之一:
    • 收到了大多数节点的选票,并且得票数超过了一半。
    • 在选举过程中,其他节点成为了 Leader(新的 Leader 后来者居上)。
  6. 成为 Leader:当一个 Candidate 赢得选举后,它将成为新的 Leader。它会发送心跳消息给所有节点来维持自己的领导地位,并准备接收客户端的操作请求。

通过这样的领导者选举机制,Raft 算法保证了集群中只存在一个 Leader,使得整个系统能够稳定运行。而选举过程中使用的随机化和选举超时机制,确保了快速选出新的 Leader,从而减少系统的不可用时间。

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

相对于其他一致性算法,如 Paxos,Raft 更加易于理解和实现。它的设计模块化,便于扩展和维护。它的目标是提供一个可靠的分布式一致性算法,以简化构建分布式系统的难度。
Raft动态图片演示链接
一定要看!
一定要看!
一定要看!重要的事情说三遍,演示超级详细!!!

2. 什么是Zookeeper?

Zookeeper是一个用于构建分布式应用的开源协调服务。它提供高度可靠的分布式协调功能,使得分布式应用可以在大规模集群中进行协作和同步。

Zookeeper可以被广泛应用于分布式系统中的各种场景,如分布式锁、领导选举、配置管理、命名服务等。它被许多分布式系统和框架使用,比如Hadoop、Kafka等。Zookeeper的简单和可靠性使得它成为构建可扩展和弹性的分布式系统的重要工具之一。

2.1 ZAB一致性协议

ZAB(ZooKeeper Atomic Broadcast)是 Apache ZooKeeper 分布式协调服务中使用的一种原子广播协议。它旨在实现分布式系统中的一致性和可靠性。
ZAB 协议将 ZooKeeper 服务集群中的节点分为两个角色:Leader 和 Follower。Leader 负责接收并处理客户端请求,然后将请求广播给集群中的所有节点(包括自己)。Follower 则对 Leader 发送的消息进行复制和追随,以保持整个集群的数据一致性。

选举参数
在介绍选举流程之前,需要介绍几个参数,

  • myid: 服务器ID,这个是在安装Zookeeper时配置的,myid越大,该服务器在选举中被选为Leader的优先级会越大。ZAB算法中通过myid来规避了多个节点可能有相同zxid问题,(注意可以对比之前的Raft算法,Raft算法中通过随机的timeout来规避多个节点可能同时成为Leader的问题)。
  • zxid: 事务ID,这个是由Zookeeper集群中的Leader节点进行Proposal时生成的全局唯一的事务ID,由于只有Leader才能进行Proposal,所以这个zxid很容易做到全局唯一且自增。因为Follower没有生成zxid的权限。zxid越大,表示当前节点上提交成功了最新的事务,这也是为什么在崩溃恢复的时候,需要优先考虑zxid的原因。
  • epoch: 投票轮次,每完成一次Leader选举的投票,当前Leader节点的epoch会增加一次。在没有Leader时,本轮此的epoch会保持不变。

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享

另外在选举的过程中,每个节点的当前状态会在以下几种状态之中进行转变。

LOOKING: 竞选状态。
FOLLOWING: 随从状态,同步Leader 状态,参与Leader选举的投票过程。
OBSERVING: 观察状态,同步Leader 状态,不参与Leader选举的投票过程。
LEADING: 领导者状态。

ZAB 协议的核心机制包括两个阶段:崩溃恢复阶段(Leader 选举)和消息广播阶段。

  1. 崩溃恢复阶段(Leader 选举):

    • 选举算法:在初始启动或 Leader 崩溃的情况下,ZAB 协议会启动选举算法来选举新的 Leader。节点将发送选举请求(包含自己的 ID 和选举轮次)给所有节点,并等待其他节点的投票。某个节点收到投票请求后,会比较选举轮次和节点 ID 来决定是否投票。最终,根据投票数量和选举规则,选举出新的 Leader 节点。

    • 同步数据:新选出的 Leader 需要将自己的数据状态同步给其他节点,以确保整个集群达到一致性。Leader 会将自己的数据变更记录(事务日志)发送给所有的 Follower 节点,然后等待大多数节点确认接收。

  2. 消息广播阶段

    • Leader 的操作:一旦选举成功,Leader 负责接收客户端的操作请求,并将这些请求转换为事务日志,然后将日志广播给所有的 Follower 节点。
    • Follower 的复制:Follower 节点接收到 Leader 发送的事务日志后,会将其复制到本地的存储中,并发送确认消息给 Leader。当 Leader 收到大多数节点的确认消息后,可以确认该日志已经被复制成功。
    • 提交和应用:在大多数节点确认接收到某个事务日志后,Leader 可以将该事务日志提交,并将结果应用到自己的状态中。然后 Leader 会通知所有的节点该事务的提交结果,以保持整个集群状态的一致性。

Zookeeper选举机制示例:
注:示例中的服务器ID即为上文中的myid、事务ID即为上文zxid中的count、逻辑时钟即为上文中的epoch

分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享
分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享
分布式一致性算法Paxos、Raft 及 Zookeeper ZAB,大数据开发学习文档,国科大学习生活,分布式,zookeeper,云原生,经验分享
ZAB一致性协议讲解视频B站链接

强烈建议观看,毕竟纯文字的形式对于知识的理解不如演示动画的形式来的快

ZAB 协议通过 Leader 选举和日志复制的方式实现了数据的一致性和可靠性。它确保了在集群中只有一个 Leader,避免了数据冲突。同时,ZAB 协议提供了恢复机制,以应对 Leader 崩溃或网络分区等异常情况。这使得 ZooKeeper 可以作为高性能、高可用性的分布式协调服务在实际应用中被广泛使用。

参考文献:
文章名:一文彻底搞懂ZAB算法,看这篇就够了!!!
文章名:Zookeeper核心知识及分布式一致性算法


21点19分 2023年12月15日
近期课程压力变小,于是重新开始学习大数据开发框架知识
书写学习文档一方面是为了督促自己更好的学习,另一方面也是给自己的学习之路留下个痕迹。


身为初学者,难免有表述不准确的地方,欢迎大家积极讨论交流。
不积跬步 无以至千里!文章来源地址https://www.toymoban.com/news/detail-763355.html

到了这里,关于分布式一致性算法Paxos、Raft 及 Zookeeper ZAB的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 分布式系统中的那些一致性(CAP、BASE、2PC、3PC、Paxos、ZAB、Raft)

    本文介绍 CAP、BASE理论的正确理解、Paxos 算法如何保证一致性及死循环问题、ZAB 协议中原子广播及崩溃恢复以及 Raft 算法的动态演示。 下面还有投票,一起参与进来吧👍 工作过几年的同学,尤其是这几年,大家或多或少都参与过分布式系统的开发,遇到过各式各样“分布式

    2024年02月05日
    浏览(52)
  • 分布式系统共识机制:一致性算法设计思想

    这次以一个宏观的角度去总结 自己学习过的一致性算法。一致性算法的目标就是让分布式系统里的大部分节点 保持数据一致。 区块链中的共识算法,pow、pos这类就属于这个范围,但他们仅仅是在区块链领域内应用的,下面介绍一致性算法是在分布式系统中 应用广泛的,当然

    2023年04月16日
    浏览(55)
  • 分布式系统的一致性级别划分及Zookeeper一致性级别分析

    在谈到Zookeeper的一致性是哪种级别的一致性问题,以及CAP原则中的C是哪一种一致性级别时有些疑惑。 下面是大多数文章中提到的一致性级别 一致性(Consistency)是指多副本(Replications)问题中的数据一致性。可以分为强一致性、顺序一致性与弱一致性。 1.1 强一致性(Stric

    2024年04月12日
    浏览(60)
  • 聊聊分布式架构09——分布式中的一致性协议

    目录 01从集中式到分布式 系统特点 集中式特点 分布式特点 事务处理差异 02一致性协议与Paxos算法 2PC(Two-Phase Commit) 阶段一:提交事务请求 阶段二:执行事务提交 优缺点 3PC(Three-Phase Commit) 阶段一:CanCommit 阶段二:PreCommit 阶段三:doCommit 优缺点 Paxos算法 拜占庭将军问题

    2024年02月08日
    浏览(51)
  • 【分布式】一致性哈希和哈希槽

    当我们拥有了多台存储服务器之后,现在有多个key,希望可以将这些个key均匀的缓存到这些服务器上,可以使用哪些方案呢? 1.1 直接哈希取模 这是一种最容易想到的方法,使用取模算法hash(key)% N,对key进行hash运算后取模,N是机器的数量。key进行hash后的结果对3取模,得

    2024年02月03日
    浏览(49)
  • 分布式数据库-事务一致性

    version: v-2023060601 author: 路__ 分布式数据库的“强一致性”应该包含两个方面: serializability(串行) and linearizability(线性一致) ,上述图为“Highly Available Transactions: Virtues and Limitations”论文中对于一致性模型的介绍。图中箭头表示一致性模型之间的关系。对于异步网络上的分

    2024年02月08日
    浏览(53)
  • RocketMQ分布式事务 -> 最终一致性实现

    · 分布式事务的问题常在业务与面试中被提及, 近日摸鱼看到这篇文章, 阐述的非常通俗易懂, 固持久化下来我博客中, 也以便于我二刷 转载源 : 基于RocketMQ分布式事务 - 完整示例 本文代码不只是简单的demo,考虑到一些异常情况、幂等性消费和死信队列等情况,尽量向可靠业务

    2024年02月15日
    浏览(56)
  • 分布式系统架构设计之分布式数据存储的扩展方式、主从复制以及分布式一致性

    在分布式系统中,数据存储的扩展是为了适应业务的增长和提高系统的性能。分为水平扩展和垂直扩展两种方式,这两种方式在架构设计和应用场景上有着不同的优势和局限性。 水平扩展是通过增加节点或服务器的数量来扩大整个系统的容量和性能。在数据存储领域,水平扩

    2024年02月03日
    浏览(76)
  • 本地消息表模式保障分布式系统最终一致性

    订单表 消息表 process_queue 库存系统 return_queue 说明 成功 失败 / / / 订单库回滚 成功 成功 失败 / / 订单系统重发消息 成功 成功 成功 失败 / Broker自动重试,注意接口幂等 成功 成功 成功 库存不足退回 / Broker通知回掉,订单/消息作废 成功 成功 成功 成功 失败 订单系统重发消

    2024年04月28日
    浏览(45)
  • Elasticsearch分布式一致性原理剖析(一)-节点篇

    “Elasticsearch分布式一致性原理剖析”系列将会对Elasticsearch的分布式一致性原理进行详细的剖析,介绍其实现方式、原理以及其存在的问题等(基于6.2版本)。 ES目前是最流行的分布式搜索引擎系统,其使用Lucene作为单机存储引擎并提供强大的搜索查询能力。学习其搜索原理,则

    2024年01月24日
    浏览(75)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包