栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

分布式一致性算法 Raft/Paxos/Zab

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

分布式一致性算法 Raft/Paxos/Zab

文章目录
  • 前言
    • CAP原理 & BASE理论
    • 一致性模型
  • 共识算法(Consensus Algorithms)/ 分布式一致性算法
    • Paxos
      • Basic Paxos
      • Multi Paxos
    • Raft 算法
    • Paxos VS Raft总结
    • ZAB 协议 ( Zookeeper Atomic Broadcast)

前言 CAP原理 & BASE理论

Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性)

  • 要想数据高可用,就得写多份数据
  • 写多分数据就会导致数据一致性问题
  • 数据一致性问题会引起性能问题

没有最好的算法:人们对性能的追求是无休止。不同的共识算法在不同场景下性能会各有优劣

一致性模型
  • 弱一致性

  • 最终一致性(一段时间达到一致性,存在中间的不一致状态)

  • 强一致

共识算法(Consensus Algorithms)/ 分布式一致性算法 Paxos

解决的问题:让整个集群的节点对某个值的变更达成一致

  • 名词解释:
    提案值:对值的操作
    提案编号:全局唯一且单调递增
    提案 = 提案值 + 提案编号
  • 3个角色
    Proposer 提案者,
    Acceptor 接收者、批准者,
    Learner 学习者、记录者
    Paxos算法中这三个角色是分开的,但是现实工程一个进程可能同时充当多种角色

Basic Paxos与Multi Paxos

Basic Paxos
  • 核心思想

    1. 每个节点都能改数据,作为Proposer发起提案
    2. 由其他节点作为Acceptor 审批提案(只同意 提案编号 是最新的提案),超过半数同意 Prepare和Accepter就最终达成了共识
    3. 达成一致后,通知其他Learner节点统一
  • 缺点
    只能单值达成共识。
    多值修改 发到多个节点 产生多个Proposer,提案编号相互否定,容易导致活锁

Multi Paxos

改进了Basic Paxos

  • 核心思想
  1. 用Basic Paxos算法 选举出一个Leader Proposer,后续的议案都由它来发起
  2. 每个值都单独运行一个Basic Paxos算法实例,多值共识时有多个Basic Paxos算法互不影响
  • 缺点
    1. Multi-Paxos 因为网络问题而脑裂,出现多 Leaders,退化成Basic Paxos
    2. Multi Paxos每个节点都可以成为leader 并发添加日志,没有顺序性要求,所以日志可能存在空洞现象;
      (leader日志不一定是最新最全的,有日志空洞,leader节点会异步的查询其他节点来填补自身日志空洞)
Raft 算法

由于Paxos的难于理解,更难以实现。为此,来自Stanford的学者设计了新的分布式协议Raft,Raft的可理解性和落地性更为简单方便
Raft本质上属于Multi Paxos的进一步优化

  • 名词解释
    任期Term:节点选举成功变为Leader后 有自己的任期Term
    TermId:任期id,全局唯一且单调递增
    日志:Leader收到请求的命令操作,保存为日志

  • 三种状态
    Leader:负责 Client 交互 和 log 复制,系统中同一时刻最多存在一个
    Follower(Acceptor):被动响应请求,从不主动发起请求
    Candidate:由Follower 向Leader转换的中间状态

  • 一致性 流程

    1. 选举一个Leader,仅允许日志最多的节点当选为leader
    2. 由Leader操作数据,并将操作保存为日志
    3. Leader把日志同步给Follower
  • Leader选举 流程

    1. 没有leader时。follower会发起选举,变成candidate竞选leader
    2. 每个节点有1票,candidate的票投给自己,超过半数票的candidate变成leader
      最新、最全日志的节点才能够当选Leader
    3. Leader节点 遇到其他任期Term比自己高的Leader则退回为follower
  • 日志限制:

    1. 只有leader能操作日志
    2. 日志必须要串行连续添加
    3. leader只能日志追加日志,不能覆盖日志
Paxos VS Raft总结
  1. Basic Paxos算法没有leader proposer角色,是一个纯粹的去中心化的分布式算法,
    但是它存在若干不足(只能单值共识 & 活锁 & 网络开销大)。
  2. 所以才有了以leader proposer为核心的Multi Paxos算法(由一个去中心化的算法变为leader-based的算法)。
  3. Raft算法相当于Multi Paxos的进一步优化,主要通过增加两个限制
    1. 日志添加次序性
    2. 选主限制(仅允许日志最多的节点当选为leader)
ZAB 协议 ( Zookeeper Atomic Broadcast)

原子广播协议:保证了发给各副本的消息顺序相同

Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的

  • 三种状态
    Looking:系统刚启动时 或者 Leader 崩溃后正处于选举状态
    Following:Follower与 Leader处于数据同步状态
    Leading:当前集群中有一个 Leader 为主进程

  • 核心思想:

    1. 保证任意时刻只有一个节点是Leader,Leader处理所有事务请求
    2. 由Leader发起去更新所有副本 Follower,更新时用的是 两段提交协议,只要多数节点 prepare 成功,就通知他们commit。
    3. 各个follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946785.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号