Paxos、Raft、ZAB算法_知知之之的博客-程序员资料_paxos raft zab

技术标签: 其他  分布式  

Paxos算法

Paxos算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法。基于Paxos协议的数据同步与传统主备方式最大的区别在于:Paxos只需超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。

Paxos将系统中的角色分为提议者 (Proposer),决策者 (Acceptor),和最终决策学习者 (Learner):

  • Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
  • Acceptor:参与决策,回应Proposers的提案。收到Proposal后可以接受提案,若Proposal获得多数Acceptors的接受,则称该Proposal被批准。
  • Learner:不参与决策,从Proposers/Acceptors学习最新达成一致的提案(Value)。

在多副本状态机中,每个副本同时具有Proposer、Acceptor、Learner三种角色。

Paxos算法通过一个决议分为两个阶段(Learn阶段之前决议已经形成):

  1. 第一阶段:Prepare阶段。Proposer向Acceptors发出Prepare请求,Acceptors针对收到的Prepare请求进行Promise承诺。
  2. 第二阶段:Accept阶段。Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理。
  3. 第三阶段:Learn阶段。Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有Learners。

Basic-Paxos

Basic-Paxos解决的问题:在一个分布式系统中,如何就一个提案达成一致。

Mulit-Paxos

Mulit-Paxos解决的问题:在一个分布式系统中,如何就一批提案达成一致。

Raft算法

Raft角色

Raft算法是Paxos算法的一种简化实现。包括三种角色:leader,candidate和follower。

  • follow:所有节点都以follower的状态开始,如果没有收到leader消息则会变成candidate状态。
  • candidate:会向其他节点拉选票,如果得到大部分的票则成为leader,这个过程是Leader选举。
  • leader:所有对系统的修改都会先经过leader。

Raft算法过程

Raft有两个基本过程:

  • Leader选举: 每个candidate随机经过一定时间都会提出选举方案,最近阶段中的票最多者被选为leader。
  • 同步log: leader会找到系统中log(各种事件的发生记录)最新的记录,并强制所有的follow来刷新到这个记录。

Raft和Multi-Paxos的区别

Raft是基于对Multi-Paxos的两个限制形成的:

发送的请求的是连续的, 也就是说Raft的append 操作必须是连续的, 而Paxos可以并发 (这里并发只是append log的并发, 应用到状态机还是有序的)。
Raft选主有限制,必须包含最新、最全日志的节点才能被选为leader. 而Multi-Paxos没有这个限制,日志不完备的节点也能成为leader。

Raft可以看成是简化版的Multi-Paxos。

Multi-Paxos允许并发的写log,当leader节点故障后,剩余节点有可能都有日志空洞。所以选出新leader后, 需要将新leader里没有的log补全,在依次应用到状态机里。

ZAB算法

在做分布式系统时,我们常常需要维护管理集群的配置信息、服务的注册发现、共享锁等功能,而ZooKeeper正是解决这些问题的一把好手。ZAB(ZooKeeper Atomic Broadcast)则是为ZooKeeper设计的一种支持崩溃恢复的原子广播协议。

很多人会误以为ZAB协议是Paxos的一种特殊实现,事实上他们是两种不同的协议。ZAB和Paxos最大的不同是,ZAB主要是为分布式主备系统设计的,而Paxos的实现是一致性状态机(state machine replication)

尽管ZAB不是Paxos的实现,但是ZAB也参考了一些Paxos的一些设计思想,比如:

  • leader向follows提出提案(proposal)

  • leader 需要在达到法定数量(半数以上)的follows确认之后才会进行commit

  • 每一个proposal都有一个纪元(epoch)号,类似于Paxos中的选票(ballot)

ZAB特性

  1. 一致性保证

    1. 可靠提交(Reliable delivery) -如果一个事务 A 被一个server提交(committed)了,那么它最终一定会被所有的server提交

    2. 全局有序(Total order) - 假设有A、B两个事务,有一台server先执行A再执行B,那么可以保证所有server上A始终都被在B之前执行

    3. 因果有序(Causal order) - 如果发送者在事务A提交之后再发送B,那么B必将在A之前执行

  2. 只要大多数(法定数量)节点启动,系统就行正常运行

  3. 当节点下线后重启,它必须保证能恢复到当前正在执行的事务

ZAB的具体实现

  • ZooKeeper由client、server两部分构成

  • client可以在任何一个server节点上进行读操作

  • client可以在任何一个server节点上发起写请求,非leader节点会把此次写请求转发到leader节点上。由leader节点执行

  • ZooKeeper使用改编的两阶段提交协议来保证server节点的事务一致性

ZXID

ZooKeeper会为每一个事务生成一个唯一且递增长度为64位的ZXID,ZXID由两部分组成:低32位表示计数器(counter)和高32位的纪元号(epoch)。epoch为当前leader在成为leader的时候生成的,且保证会比前一个leader的epoch大

实际上当新的leader选举成功后,会拿到当前集群中最大的一个ZXID,并去除这个ZXID的epoch,并将此epoch进行加1操作,作为自己的epoch

历史队列(history queue)

每一个follower节点都会有一个先进先出(FIFO)的队列用来存放收到的事务请求,保证执行事务的顺序

可靠提交由ZAB的事务一致性协议保证 全局有序由TCP协议保证 因果有序由follower的历史队列(history queue)保证

ZAB工作模式

  • 广播(broadcast)模式

  • 恢复(recovery)模式

广播(broadcast)模式

  • leader从客户端收到一个写请求

  • leader生成一个新的事务并为这个事务生成一个唯一的ZXID,

  • leader将这个事务发送给所有的follows节点

  • follower节点将收到的事务请求加入到历史队列(history queue)中,并发送ack给ack给leader

  • 当leader收到大多数follower(超过法定数量)的ack消息,leader会发送commit请求

  • 当follower收到commit请求时,会判断该事务的ZXID是不是比历史队列中的任何事务的ZXID都小,如果是则提交,如果不是则等待比它更小的事务的commit

恢复模式

恢复模式大致可以分为四个阶段

  • 选举

  • 发现

  • 同步

  • 广播

恢复过程的步骤大致可分为

  1. 当leader崩溃后,集群进入选举阶段,开始选举出潜在的新leader(一般为集群中拥有最大ZXID的节点)

  2. 进入发现阶段,follower与潜在的新leader进行沟通,如果发现超过法定人数的follower同意,则潜在的新leader将epoch加1,进入新的纪元。新的leader产生

  3. 集群间进行数据同步,保证集群中各个节点的事务一致

  4. 集群恢复到广播模式,开始接受客户端的写请求

当 leader在commit之后但在发出commit消息之前宕机,即只有老leader自己commit了,而其它follower都没有收到commit消息 新的leader也必须保证这个proposal被提交.(新的leader会重新发送该proprosal的commit消息)

当 leader产生某个proprosal之后但在发出消息之前宕机,即只有老leader自己有这个proproal,当老的leader重启后(此时左右follower),新的leader必须保证老的leader必须丢弃这个proprosal.(新的leader会通知上线后的老leader截断其epoch对应的最后一个commit的位置)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_35973945/article/details/125103616

智能推荐

创建 VSTO 工作簿的 ClickOnce 安装包_vsto clickonce_苹果 apple的博客-程序员资料

准备工作事先创建一个Excel文件命名为“演示文档.xlsm”的,以实现通过运行名称为“演示”的宏,将A1单元格的内容复制到A2单元格中。1.在“sheet1”的A1单元格输入“1.0.0.0”,作为excel文件的版本号。2.通过开发工具中的Visual Basic,为工作簿添加模块,输入以下代码,建立宏Sub 演示() Range("A2") = Range("A1")End Sub3.文档另存为“演示文档.xlsm”。一、创建Excel VSTO工作簿的新项目...

unity3d collider自动调整大小_Unity 3D | 美术向系列教程2_地形系统介绍_weixin_39544101的博客-程序员资料

Hello . 大家好今天给大家带来U3D美术向系统教程我是麦田1前言刚发第二篇2019就过去了,提前祝大家元旦不加班吧。Unity太过于基础的就不去讲解了,网上视频教程一大把,比如界面之类的。可以去B站看看。今天水第一篇基础,地形系统。地形系统大家了解了解就Ok,当个玩具玩一玩,比较正规项目不会去用他,太费了。不排除一种情况,即地编制作大地形时候使用,再将地形转为Mesh减面。下一期将...

VSTO开发指南(VB2013版) 第一章 Office对象模型_Unknowncheats的博客-程序员资料_vsto开发

完美地将visual basic和office 办公软件结合起来。来自微软公司VSTO小组的权威专家所编著。全书共712页,内容极其全面而深入,猛一看,厚地犹如庞然大物。看完离大神就不远了哦<^ . ^>!!!!!《VSTO开发指南》是2008年2月电子工业出版社出版的图书,作者是(美国)Eric Carter Eric Lippert实例1:从Excel程序到...

解决xubuntu 11.10下使用Sublime Text 2无法输入中文的问题_枫之逆的博客-程序员资料_为什么text2里面输不了字符

我使用的是xubuntu11.10,使用sublime text2的时候发现无法输入中文,不断切换输入法还是不行,很坑爹的,这也不是快捷键的问题。从网上找了一个解决方案是说安装scim,然后使用scim-brige方式,并调整一下配置就可以在sublime text2里面输入中文,但我参照那个方法还是无法输入中文。后来又找了资料,另一种方案是安装上fcitx。最终成功了,把我的解决办法如下:

VSTO:使用C#开发Excel、Word【17】_初仔仔的博客-程序员资料

使用Range对象Range对象表示电子表格中的单元格范围。范围可以包含一个单元格,多个连续的单元格,甚至多个不连续的单元格。您可以在Excel中选择时按住Ctrl键选择多个不连续的单元格。获取特定Cell或Cells范围对象Excel提供了多种获取Range对象的方法。 Range对象是您要在Excel工作表中处理单元格或单元格范围时使用的对象。在Application对象的描述中提到了两种...

介绍PHP7中十个需要避免的坑_Anna_xuan的博客-程序员资料

推荐(免费):PHP71、不要使用 mysql_ 函数这一天终于来了,从此你不仅仅“不应该”使用mysql_函数。PHP 7已经把它们从核心中全部移除了,也就是说你需要迁移到好得多的mysqli_函数,或者更灵活的PDO实现。2、不要编写垃圾代码这一条可能易于理解,但是会变得越来越重要,因为PHP 7的速度提升可能会隐藏你的一些问题。不要仅仅满足于你的站点速度,因为迁移到PHP 7才让它变快。作为一名开发者,你应该总是确保按需加载脚本,尽可能连接它们,编写高效的数据库查询,尽可能使用缓存,以及其它

随便推点

BOM操作常用方法_取经中的稳健少女的博客-程序员资料_bom技巧

window对象浏览器弹出框:open("http://163.com","我的网页","width=200,height=200") 视窗宽高:nnerWidth,innerHeight 和document.documentElement.clientWidth clienHeight一样浏览器窗口宽高:outerWidth,outerHeight 获取当前窗口相对屏幕的坐标:sc...

VSTO开发Powerpoint插件_agrinJPG的博客-程序员资料_ppt插件开发

不怎么熟悉VSTO的Powerpoint开发,只是突然需要用一下,但是网上相关太少了,所以这里简单记录一下。VSTO(Visual Studio Tools for Office )是VBA的替代,是一套用于创建自定义Office应用程序的Visual Studio工具包。VSTO使你可以用Visual Basic 或者Visual C#扩展Office应用程序(例如Word、Excel、InfoPath和Outlook)。你可以使用强大的Visual Studio开发环境来创建你的定制程序,而不是使

ROS2学习笔记(五)-- ROS2命令行操作常用指令总结(一)_溪风沐雪的博客-程序员资料_ros2 pkg create

简介:在前面的章节中,我们先简单学习了ROS2的话题发布和订阅,两种操作都是通过python代码实现的,而在实际应用过程中,我们会经常用到命令行操作来辅助调试,更进一步的可以使用GUI工具辅助调试,比如前边用到的rqt中的Image View工具,这一节在现有功能基础上介绍一部分常用的命令行操作指令。

Tensorflow中的subclass_weixin_44504134的博客-程序员资料_subclass='training

Loss以交叉熵为例:tf的loss api一般通过如 tf.metrics.SparseCategoricalCrossentropy(from_logits=True) 创建instance函数,或者不需要pass in参数的情况下:tf.metrics.sparse_categorical_crossentropy, 然后通过metrics(y_true, y_pred)来call这个函数Subclass损失函数需要重写 __init__()和 call() 两个函数__init__

创建 VSTO 外接程序的windows安装包_vsto环境安装包有什么用_苹果 apple的博客-程序员资料

一、创建Excel VSTO 外接程序的新项目(一)新建解决方案和Excel VSTO 外接程序项目创建一个Excel VSTO外接程序的新项目,选择“Excel VSTO外接程序(Visual Basic)”模板,命名为“外接程序安装”。VS将显示解决方案名称为“外接程序安装”,包含“外接程序安装”项目。(二)设计Excel VSTO外接程序主要是设计菜单项和代码。1.在“外接程序安装”项目上,点击右键,选择“添加”——“类”,在“添加新项-外接程序安装”界面,选择“office/sh_1671465600

PL/SQL Developer恢复默认窗口布局(2019年V13.0.0最新版PL/SQL Developer)_快乐李同学(李俊德-大连理工大学)的博客-程序员资料_plsql重置窗口布局

1.问题背景:我们刚接触PL/SQL时,可能不小心关闭了我们需要的窗口,又不知道在哪里再次恢复默认窗口布局,按照以下教程就可正常恢复PL/SQL Developer恢复默认窗口布局。2.解决方案:(1)在Configure-Preferences-User Interface-Appearance里面,有两个Reset选项。(2)Reset Toolbars和Reset Doc...

推荐文章

热门文章

相关标签