从Paxos到Zookeeper(二)

2024-09-05 20:58
文章标签 zookeeper paxos

本文主要是介绍从Paxos到Zookeeper(二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

这个月公司风波很多,比较忙,心态也有些变化,一个月没更了,终归还是要沉淀下来工作学习呀,继续学习Paxos。前面已经介绍了2PC和3PC,并了解了它们各自的特点以及解决的分布式问题,接着,我们来介绍Paxos:一种基于消息传递且具有高度容错性的一致性算法,是目前公认的解决分布式一致性问题最有效的算法。

1、背景

在常见的分布式系统中,设计者必须要考虑的一个问题就是节点宕机或网络异常,这意味着系统将在某个时间点损失某些可用节点,Paxos要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证无论发生以上任何异常,都不会破坏系统的一致性。

拜占庭将军问题

拜占庭帝国有许多军队,不同军队的将军之间必须制定一个统一的行动计划,从而做出进攻或者撤退的决定,同时,各个将军在地理上都是被分隔开来的,只能依靠军队的通讯员来进行通讯,然而通讯员中可能存在叛徒,这些叛徒可以任意篡改消息,从而达到欺骗将军的目的。

这就是著名的“拜占庭将军问题”。从理论上来说,在分布式计算领域,试图在异步系统和不可靠通道来达到一致性状态是不可能的,而在实际工程实践中,可以假设不存在拜占庭问题,Lamport在1990年根据一个叫Paxos的小岛的议会方式得到启发,并提出了Paxos算法(这篇论文在1990年投稿时居然还被拒了-_-!,六年后才被重新翻出来)。

2、Paxos算法详解

Paxos作为一种提高分布式系统容错性的一致性算法,一直以来总是被很多人抱怨其算法理论太难以理解,于是便下载了Lamport另一篇论文Paxos Made Simple,估计Lamport也是了解到了像我们这种资质平平的,并不能读懂他的神作(通篇故事形式描述Paxos)The Part-Time Parliament,接着,我们将从对一致性问题的描述来讲解该算法需要解决的实际需求。

问题描述

假设有一组可以提出的进程集合,那么对于一个一致性算法来说需要保证以下几点:

  • 在这些被提出的提案中,只有一个会被选定;
  • 如果没有提案被提出,那么就不会有被选定的提案;
  • 当一个提案被选定后,进程应该可以获取被选定的提案信息;

在Paxos中,有三种参与角色,Proposer、Acceptor和Learner,在具体的实现中,一个进程可能充当不止一种角色,在这里我们并不关心进程如何映射到各种角色,假设不同参与者之间可以通过收发消息来进行通信,那么:

  • 每个参与者以任意的速度执行,可能会因为出错而停止,也可能重启,同时,即使一个提案被选定后,所有的参与者也都有可能失败或者重启,因此除非那些失败或重启的参与者可以记录某些信息,否则将无法确定最终的值。
  • 消息在传输过程中可能会出现不可预知的延迟,也可能会重复或丢失,但是消息不会损坏,即消息内容不会被篡改。

提案选定

首先应该考虑的是如何选定唯一的提案,最简单的方式是只允许唯一的Acceptor,但是一旦这个节点挂了,系统也就奔溃了(单点问题);因此我们应该使用多个Acceptor来避免单点问题,这里就引出了投票方案:Proposer可以向一个Acceptor集合发送提案,同样的,集合中的每个Acceptor都可以批准该提案,当有足够多的Acceptor批准该提案时,我们就可以认为该提案被选定了,这里的足够多定义为Acceptor总数的一半以上,同时规定每个Acceptor最多只能批准一个提案,这样就能保证只有一个提案被选定了。

推导过程

在没有消息失败和消息丢失的情况下,如果我们希望即使在只有一个提案被提出的情况下,仍然可以选出一个提案,因此可以得到如下规则:

P1:一个Acceptor必须批准它收到的第一个提案(不然在仅一个提案时,每个Acceptor都拒绝接受,则没有提案会被选取);

由P1会引出一个新的问题,假设多个Proposer各自提出不同的提案,各个Acceptor也都各自接受,但却没有票数优势的提案,如下图所示:

           

在这种场景下,是无法选定一个提案的,并且,即使只有两个提案,各自被差不多一半的Acceptor批准,而一个Acceptor又在此时出了错,同样会导致无法确定应该选定哪个提案,比如Acceptor A和B接受提案1,而C,D,E接受提案2,而E节点又宕机,这个时候无法确定应该选择哪个提案。这个时候就需要一个Acceptor能够批准不止一个提案,这里的提案=(编号,value),当具有某个value值的提案被半数以上的Acceptor批准后,也就可以认定该提案被选定了。即,虽然允许多个提案被选定,但是这些提案必须具有相同的value值,归纳为:

P2:如果编号为M0、V0的提案被选定了,那么所有比编号M0更高的,且被选定的提案,其Value=V0;

这里P2的证明非常冗长复杂(数学归纳法),其实总结一下,就是每次选取的提案一定要是编号最大的,而且在当前的Acceptor集合中,不存在批准过提案版本(编号)小于当前版本的Acceptor,这就生成了如下的提案生成算法。

Proposer生成提案

  • Proposer选择一个新的提案编号Mn,然后向某个Acceptor集合成员发送请求,要求该集合中的Acceptor作出如下回应:1、保证不再批准旧版本的提案;2、如果Acceptor已经批准过任何提案,那么其就向Proposer反馈当前Acceptor已经批准旧版本提案,但是value值相同;
  • 如果Proposer收到来自半数以上的Acceptor的响应结果,那么它就可以产生(Mn,Vn)的提案;如果没有收到半数以上的响应,此时Vn的值就可以任由Proposer选择;

在确定了提案后,Proposer会将该提案再次发送给Acceptor集合,并期望得到批准,这个请求的过程即为Accept请求,但此时接受Accept请求的Acceptor集合不一定是之前响应的Acceptor集合了,但是由于Acceptor集合是半数以上,则至少会有一个共同的Acceptor。

Acceptor批准提案

一个Acceptor可能会收到来自Proposer的两种请求,分别是Prepare请求和Accept请求,对这两类请求做出响应的条件分别如下:

  • Prepare请求:Acceptor可以在任何时候响应一个Prepare请求;
  • Accept请求:在不违背Accept现有承诺的前提下,可以任意响应Accept请求;

翻译一下就是,只要这个Acceptor尚未响应过任何编号大于Mn的Prepare请求,那么它就可以接收这个编号为Mn的提案,如果收到的请求编号小于当前响应的请求的最大编号,则可以忽略而不破坏算法安全性。

接着就可以对提案选定的过程进行一个概述了(类似2PC):

阶段一:

  • Proposer选择一个提案编号Mn,然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求;
  • 如果一个Acceptor收到一个编号为Mn的Prepare请求,且编号大于该Acceptor已经响应的所有Prepare编号,那么它就会将已批准过的最大编号提案反馈给Proposer,同时承诺不再批准小于Mn的提案,这里比较拗口,翻译一下就是,如果一个Acceptor已经响应了1,2,3,5,再收到编号为6的提案后,就会将5作为响应反馈给Proposer;

阶段二:

  • 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应,则生成一个(Mn,Vn)提案,并发送给Acceptor,其中Vn等于收到响应中编号最大的提案的值,若响应中不包含任何提案,则Vn可以为任意值;
  • 如果Acceptor收到这个针对(Mn,Vn)的Accept请求,只要该Acceptor尚未对编号大于Mn的Parepare请求做出响应,它就可以通过这个提案;

在实际运行过程中,一个Proposer可能会产生多个提案,但只要Proposer遵循如上规则,就一定能保证算法执行的正确性,通过接收最大编号的提案,可以保证其在提案选定上的正确性;

提案的获取

提案产生后便是选定的过程,Learner获取提案有以下三种方案:

  • 一旦Acceptor批准了一个提案,就将该提案发送给所有的Learner,通信次数至少为Acceptor与Learner的个数乘积;
  • 将Learner划分为主Learner和普通的Learner,然后将所有的Acceptor对提案的批准情况发送给主Learner,然后由主Learner告知普通的Learner某个提案的选定情况;通信次数为Learner与Acceptor的个数之和,但却又引入了单点问题--主Learner可能存在故障;
  • 在第二个方案的基础上,将主Learner扩展为一个集合,个数越多,可靠性越高,但同时,通信的复杂度也就更高。

主Proposer的作用

试想这样一种情况,P1提出了M1,完成了阶段一,同时,P2提出了M2也完成了阶段一,这个时候Acceptor集合会丢弃M1,因为M2的编号大于M1,于是P1又提出了M3,这样Acceptor又会丢弃M2,这样循环下去会导致Proposer提出了一系列的提案,但是都无法被选定,陷入死循环。

为了保证Paxos的可持续性,必须选择一个主Proposer,并规定只有主Proposer才能提出提案,这样一来,只要主Proposer与过半的Acceptor通信正常,那么但凡主Proposer提出一个编号更高的提案,就会被批准;同时,如果发现当前算法流程中有一个编号更大的提案正在接收批准,那么它会丢弃当前的提案,通过主Proposer可以保持Paxos算法的活性。

总结

Paxos在2PC和3PC的基础上引入了“过半”的概念,即少数服从多数,,同时支持分布式节点角色的轮换,这一点是至关重要的,极大的避免了分布式单点的出现,在二阶段的基础上,解决了无限期等待和数据不一致(脑裂)的情况,是目前最优秀的分布式一致性协议之一。

这篇关于从Paxos到Zookeeper(二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140046

相关文章

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种,单机模式和集群模式以及伪集群模式。 ■ 单机模式:Zookeeper只运行在一台服务器上,适合测试环境; ■ 伪集群模式:就是在一台物理机上运行多个Zookeeper 实例; ■ 集群模式:Zookeeper运行于一个集群上,适合生产环境,这个计算机集群被称为一个“集合体”(ensemble) Zookeeper通过复制来实现

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3

ZooKeeper 中的 Curator 框架解析

Apache ZooKeeper 是一个为分布式应用提供一致性服务的软件。它提供了诸如配置管理、分布式同步、组服务等功能。在使用 ZooKeeper 时,Curator 是一个非常流行的客户端库,它简化了 ZooKeeper 的使用,提供了高级的抽象和丰富的工具。本文将详细介绍 Curator 框架,包括它的设计哲学、核心组件以及如何使用 Curator 来简化 ZooKeeper 的操作。 1

zookeeper相关面试题

zk的数据同步原理?zk的集群会出现脑裂的问题吗?zk的watch机制实现原理?zk是如何保证一致性的?zk的快速选举leader原理?zk的典型应用场景zk中一个客户端修改了数据之后,其他客户端能够马上获取到最新的数据吗?zk对事物的支持? 1. zk的数据同步原理? zk的数据同步过程中,通过以下三个参数来选择对应的数据同步方式 peerLastZxid:Learner服务器(Follo

设置zookeeper开机自启动/服务化

设置启动zk的用户为zookeeper 设置启动zk的用户为zookeeper用户,而非root用户,这样比较安全。 可以使用root用户进行zookeeper的管理(启动、停止…),但对于追求卓越和安全的的人来说,采用新非root用户管理zookeeper更好。 步骤: 1. 创建用户和用户组 2. 相关目录设置用户和用户组属性 3. 采用zookeeper用户启动进程 设置z

Zookeeper集群是如何升级到新版本的

方案1:复用老数据方案 这是经过实践的升级方案,该方案是复用旧版本的数据,zk集群拓扑,配置文件都不变,只是启动的程序为最新的版本。 参考文章: Zookeeper集群是如何升级到新版本的 方案2:重新建立数据方案 该方案的思路是:先停掉一台follower的机器上的服务,然后加入一个新版本的zk(zk的数据目录是空的),然后启动新zk,之后新zk会把旧集群中的数据同步过来。之后再操作另

Zookeeper基本原理

1.什么是Zookeeper?         Zookeeper是一个开源的分布式协调服务器框架,由Apache软件基金会开发,专为分布式系统设计。它主要用于在分布式环境中管理和协调多个节点之间的配置信息、状态数据和元数据。         Zookeeper采用了观察者模式的设计理念,其核心职责是存储和管理集群中共享的数据,并为各个节点提供一致的数据视图。在Zookeeper中,客户端(如

一、什么是Zookeeper

原文: GitHub:https://github.com/wangzhiwubigdata/God-Of-BigData关注公众号,内推,面试,资源下载,关注更多大数据技术~大数据成神之路~预计更新500+篇文章,已经更新50+篇~ 张大胖所在的公司这几年发展得相当不错,业务激增,人员也迅速扩展,转眼之间,张大胖已经成为公司的“资深”员工了,更重要的是,经过这些年的不懈努力,他终于

三、Zookeeper典型应用场景及实践

因编辑原因图片不显示,请戳GitHub原文: https://github.com/wangzhiwubigdata/God-Of-BigData关注公众号,内推,面试,资源下载,关注更多大数据技术~大数据成神之路~预计更新500+篇文章,已经更新50+篇~ Zookeeper 从设计模式角度来看,是一个基于观察者模式设计的分布式服务管理框架,它负责存储和管理大家都关心的数据,然后接受

分布式系统理论进阶 - Paxos

GitHub:https://github.com/wangzhiwubigdata/God-Of-BigData 关注公众号,内推,面试,资源下载,关注更多大数据技术~大数据成神之路~预计更新500+篇文章,已经更新50+篇~ 引言 《分布式系统理论基础 - 一致性、2PC和3PC》一文介绍了一致性、达成一致性需要面临的各种问题以及2PC、3PC