分布式技术原理:ZooKeeper及其算法

原创
10/27 12:24
阅读数 40

一:CAP理论

在分布式系统,有一个最基础的理论,就是CAP理论。 CAP理论,一个分布式系统最多只能同时满足一致性(Consistency)、可用性(Availability)和分区容忍性(Partition Tolerance)这三项中的两项。

1)一致性是指“所有节点同时看到相同的数据”,即更新操作成功并返回客户端完成后,所有节点在同一时间的数据完全一致,等同于所有节点拥有数据的最新版本。

2)可用性是指“任何时候,读写都是成功的”,即服务一直可用,而且是正常响应时间。我们平时会看到一些 IT 公司的对外宣传,比如系统稳定性已经做到 3 个 9、4 个 9,即 99.9%、99.99%,这里的 N 个 9 就是对可用性的一个描述,叫做 SLA,即服务水平协议。比如我们说月度 99.95% 的 SLA,则意味着每个月服务出现故障的时间只能占总时间的 0.05%,如果这个月是 30 天,那么就是 21.6 分钟。

3)分区容忍性具体是指“当部分节点出现消息丢失或者分区故障的时候,分布式系统仍然能够继续运行”,即系统容忍网络出现分区,并且在遇到某节点或网络分区之间网络不可达的情况下,仍然能够对外提供满足一致性和可用性的服务。

在通常的分布式系统中,网络分区是既成的现实,你无法改变。所以只有在可用性和一致性两者间做出选择。CAP 理论关注的是在绝对情况下,可用性和一致性并不是完全对立的,我们关注的往往是如何在保持相对一致性的前提下,提高系统的可用性。

业务上对一致性的要求会直接反映在系统设计中,典型的就是 CP 和 AP 结构。

CP 架构:对于 CP 来说,放弃可用性,追求一致性和分区容错性。 我们熟悉的 ZooKeeper,就是采用了 CP 一致性,ZooKeeper 是一个分布式的服务框架,主要用来解决分布式集群中应用系统的协调和一致性问题。其核心算法是 Zab,所有设计都是为了一致性。在 CAP 模型中,ZooKeeper 是 CP,这意味着面对网络分区时,为了保持一致性,它是不可用的。关于 Zab 协议,将会在后面的 中介绍。

AP 架构:对于 AP 来说,放弃强一致性,追求分区容错性和可用性,这是很多分布式系统设计时的选择。 和 ZooKeeper 相对的是 Eureka,Eureka 是 Spring Cloud 微服务技术栈中的服务发现组件,Eureka 的各个节点都是平等的,几个节点挂掉不影响正常节点的工作,剩余的节点依然可以提供注册和查询服务,只要有一台 Eureka 还在,就能保证注册服务可用,只不过查到的信息可能不是最新的版本,不保证一致性。

二:ACID 原理

ACID 是一种强一致性模型,强调原子性、一致性、隔离性和持久性,典型的应用是MYSQL。

三:Base 理论

Base 是三个短语的简写,即基本可用(Basically Available)、软状态(Soft State)和最终一致性(Eventually Consistent)。 分布式系统中,由于我们无法做到强一致性--即任何时刻任何状态都保持一致,那么在我们的业务系统,只需要在呈现给用户的时候,保持最终一致性就好。

1)基本可用

   基本可用是系统能够基本运行,一直提供服务。基本可用强调了分布式系统在出现不可预知故障的时候,允许损失部分可用性,相比正常的系统,可能是响应时间延长,或者是服务被降级。

2)软状态

软状态可对应ACID的原子性实现的是强制一致性,要么全做要么不做,所有用户看到的数据一致。其中的原子性(Atomicity)要求多个节点的数据副本都是一致的,强调数据的一致性。原子性可以理解为一种“硬状态”,软状态则是允许系统中的数据存在中间状态,并认为该状态不影响系统的整体可用性,即允许系统在多个不同节点的数据副本存在数据延时。

3)最终一致性

 数据不可能一直是软状态,必须在一个时间期限之后达到各个节点的一致性,在期限过后,应当保证所有副本保持数据一致性,也就是达到数据的最终一致性。

四:全局时钟和逻辑时钟

分布式系统解决了传统单体架构的单点问题和性能容量问题,另一方面也带来了很多新的问题,其中一个问题就是多节点的时间同步问题:不同机器上的物理时钟难以同步,导致无法区分在分布式系统中多个节点的事件时序。

1) 全局时钟

局时钟绝对的内部一致性,这种状态是不存在的。

2)逻辑时钟

逻辑时钟描绘了分布式系统中事件发生的时序,是为了区分现实中的物理时钟提出来的概念。 一般情况下我们提到的时间都是指物理时间,但实际上很多应用中,只要所有机器有相同的时间就够了,这个时间不一定要跟实际时间相同。更进一步解释:如果两个节点之间不进行交互,那么它们的时间甚至都不需要同步。 因此问题的关键点在于节点间的交互要在事件的发生顺序上达成一致,而不是对于时间达成一致。

五: Paxos 算法

Paxos 算法在分布式领域具有非常重要的地位,开源分布式锁组件 Google Chubby 的作者 Mike Burrows 说过,这个世界上只有一种一致性算法,那就是 Paxos 算法,其他的算法都是残次品。

1)抽屉原理

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。

2)Quorum 选举算法

基于抽屉原理,我们来看看Quorum 机制:在 N 个副本中,一次更新成功的如果有 W 个,那么我在读取数据时是要从大于 N-W 个副本中读取,这样就能至少读到一个更新的数据了。 WARO机制,简单的副本控制协议,WARO机制是和Quorum 机制对应的一种机制:当 Client 请求向某副本写数据时(更新数据),只有当所有的副本都更新成功之后,这次写操作才算成功,否则视为失败。 WARO 牺牲了更新服务的可用性,最大程度地增强了读服务的可用性,而 Quorum 就是在更新服务和读服务之间进行的一个折衷。 根据Quorum 机制,我们看到他无法保证强一致性,也就是无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。但是Quorum 机制,加上一个版本号的控制,这样可以确定最新的数据,然后从已经读到的数据中就可以确认最新写入的数据。

3)Paxos协议 在Paxos协议中,有三中角色Proposer、Acceptor 和 Learner,另外还有一个 Client,作为产生议题者。 Proposer提案者,Proposer提案者提出修改某个值,Proposer 可以有多个Acceptor批准者,Acceptor批准Proposer提出的修改,Acceptor可以有多个,且身份完全对等。 Learner学习者,Learner主要学习经过Acceptor批准后 被Proposer修改的某个值。 Client 角色,作为产生议题者,实际不参与选举过程,比如发起修改请求的来源等。

Paxos 中, Proposer 和 Acceptor 是算法核心角色,Paxos 描述的就是在一个由多个 Proposer 和多个 Acceptor 构成的系统中,如何让多个 Acceptor 针对 Proposer 提出的多种提案达成一致的过程,而 Learner 只是“学习”最终被批准的提案。 Paxos 选举过程:

1、Phase 1 准备阶段

Proposer 生成全局唯一且递增的 ProposalID,向 Paxos 集群的所有机器发送 Prepare 请求,这里不携带 value,只 ProposalID
Acceptor 收到 Prepare 请求后,判断收到的 ProposalID 是否比之前已响应的所有提案的 N 大,
如果是,则:
      在本地持久化 N,可记为 Max_N;
      回复请求,并带上已经 Accept 的提案中 N 最大的 value,如果此时还没有已经 Accept 的提案,则返回 value 为空;
       做出承诺,不会 Accept 任何小于 Max_N 的提案。
       如果否,则不回复或者回复 Error。

2、Phase 2 选举阶段

-Proposer 发送 Accept
     经过一段时间后,Proposer 收集到一些 Prepare 回复,有下列几种情况:
         若回复数量 > 一半的 Acceptor 数量,且所有回复的 value 都为空时,则 Porposer 发出 accept 请求,并带上自己指定的 value。
         若回复数量 > 一半的 Acceptor 数量,且有的回复 value 不为空时,则 Porposer 发出 accept 请求,并带上回复中 ProposalID 最大的 value,作为自己的提案内容。
          若回复数量 <= 一半的 Acceptor 数量时,则尝试更新生成更大的 ProposalID,再转到准备阶段执行。

-Acceptor 应答 Accept
	Accpetor 收到 Accpet 请求 后,判断:
         若收到的 N >= Max_N(一般情况下是等于),则回复提交成功,并持久化 N 和 value;
         若收到的 N < Max_N,则不回复或者回复提交失败。
-Proposer 统计投票
	 经过一段时间后,Proposer 会收集到一些 Accept 回复提交成功的情况,比如:
        当回复数量 > 一半的 Acceptor 数量时,则表示提交 value 成功,此时可以发一个广播给所有的 Proposer、Learner,通知它们已 commit 的value;
        当回复数量 <= 一半的 Acceptor 数量时,则尝试更新生成更大的 ProposalID,转到准备阶段执行。
         当收到一条提交失败的回复时,则尝试更新生成更大的 ProposalID,也会转到准备阶段执行。

1.如果半数以内的 Acceptor 失效,如何正常运行?

在Paxos流程中,如果出现半数以内的 Acceptor 失效,可以分为两种情况:

第一种,如果半数以内的 Acceptor 失效时还没确定最终的 value,此时所有的 Proposer 会重新竞争提案,最终有一个提案会成功提交。

第二种,如果半数以内的 Acceptor 失效时已确定最终的 value,此时所有的 Proposer 提交前必须以最终的 value 提交,也就是Value实际已经生效,此值可以被获取,并不再修改。

2. Acceptor需要接受更大的N,也就是ProposalID有什么意义?

这种机制可以防止其中一个Proposer崩溃宕机产生阻塞问题,允许其他Proposer用更大ProposalID来抢占临时的访问权。

3. 如何产生唯一的编号,也就是 ProposalID?

在《Paxos made simple》论文中提到,唯一编号是让所有的 Proposer 都从不相交的数据集合中进行选择,需要保证在不同Proposer之间不重复,比如系统有 5 个 Proposer,则可为每一个 Proposer 分配一个标识 j(0~4),那么每一个 Proposer 每次提出决议的编号可以为 5*i + j,i 可以用来表示提出议案的次数。

六:Zab 一致性协议

Zab 协议的具体实现可以分为以下两部分:

消息广播阶段

Leader 节点接受事务提交,并且将新的 Proposal 请求广播给 Follower 节点,收集各个节点的反馈,决定是否进行 Commit,根据Quorum机制,板书以上节点反馈成功,即commit;

客户端的写请求进来之后,Leader 会将写请求包装成 Proposal 事务,并添加一个递增事务 ID,也就是 Zxid,Zxid 是单调递增的,以保证每个消息的先后顺序;(Zxid 是 Zab 协议的一个事务编号,Zxid 是一个 64 位的数字,其中低 32 位是一个简单的单调递增计数器,针对客户端每一个事务请求,计数器加 1;而高 32 位则代表 Leader 周期年代的编号)

广播这个 Proposal 事务,Leader 节点和 Follower 节点是解耦的,通信都会经过一个先进先出的消息队列,Leader 会为每一个 Follower 服务器分配一个单独的 FIFO 队列,然后把 Proposal 放到队列中;

Follower 节点收到对应的 Proposal 之后会把它持久到磁盘上,当完全写入之后,发一个 ACK 给 Leader;

当 Leader 收到超过半数 Follower 机器的 ack 之后,会提交本地机器上的事务,同时开始广播 commit, Follower 收到 commit 之后,完成各自的事务提交。

崩溃恢复阶段

如果在同步过程中出现 Leader 节点宕机,会进入崩溃恢复阶段,重新进行 Leader 选举,崩溃恢复阶段还包含数据同步操作,同步集群中最新的数据,保持集群的数据一致性。

整个 ZooKeeper 集群的一致性保证就是在上面两个状态之前切换,当 Leader 服务正常时,就是正常的消息广播模式;当 Leader 不可用时,则进入崩溃恢复模式,崩溃恢复阶段会进行数据同步,完成以后,重新进入消息广播阶段。

崩溃恢复和集群启动时的选举过程是一致的,也就是说,下面的几种情况都会进入崩溃恢复阶段: 初始化集群,刚刚启动的时候 Leader 崩溃,因为故障宕机 Leader 失去了半数的机器支持,与集群中超过一半的节点断连

选主过程:

1.各个节点变更状态,变更为 Looking ZooKeeper 中除了 Leader 和 Follower,还有 Observer 节点,Observer 不参与选举,Leader 挂后,余下的 Follower 节点都会将自己的状态变更 为 Looking,然后开始进入 Leader 选举过程。

2.各个 Server 节点都会发出一个投票,参与选举在第一次投票中,所有的 Server 都会投自己,然后各自将投票发送给集群中所有机器,在运行期间, 每个服务器上的 Zxid 大概率不同。

3.集群接收来自各个服务器的投票,开始处理投票和选举 处理投票的过程就是对比 Zxid 的过程,假定 Server3 的 Zxid 最大,Server1 判断 Server3 可以成为 Leader,那么 Server1 就投票给 Server3,判 断的依据如下: 首先选举 epoch 最大的 如果 epoch 相等,则选 zxid 最大的 若 epoch 和 zxid 都相等,则选择 server id 最大的,就是配置 zoo.cfg 中的 myid 在选举过程中,如果有节点获得超过半数的投票数,则会成为 Leader 节点,反之则重新投票选举。

数据同步

崩溃恢复完成选举以后,接下来的工作就是数据同步,在选举过程中,通过投票已经确认 Leader 服务器是最大Zxid 的节点,同步阶段就是利用 Leader 前一阶段获得的最新Proposal历史,同步集群中所有的副本。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部