Java教程

【分布式】一致性算法总结

本文主要是介绍【分布式】一致性算法总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 2PC
  • 3PC
  • Paxos
    • 基础流程
      • 优化
  • Raft
  • ZAB
    • 消息广播
    • 崩溃恢复

最近结束了面试以后,对面试中问到的分布式问题还是比较有兴趣的。因此希望能够进一步学习分布式的有关内容。本文主要是整理了分布式系统中使用到的分布式算法。分布式的一个大的问题就是如何在多个集群之间完成协调一致,也就是事务的原子性。并且我们还希望有高可用高性能的实现,尽量可以避免单点问题。因此往往都会设计到主节点的选择算法。

2PC

2PC是Two-Phase Commit的缩写,二阶段提交。目前大多数SQL数据库都是采用的二阶段提交的策略完成事务,利用该协议可以非常方便的完成所有分布式事务参与者的协调,统一决定事务的提交和回滚。设计思路主要是保证在最后一个瞬间的网络是正常的就可以,尽可能将麻烦的过程前置。

  • 阶段一:协调者让全部的参与者都完成准备,万事俱备,只欠东风。
  1. 事务询问:协调者向所有的参与者发送事务内容,询问各个从节点是否可以执行事务的提交,并等到参与者的相应。
  2. 执行事务:各参与者节点执行事务,并且将undo和Redo写入事务日志
  3. 反馈:如果参与者成功执行了事务,反馈给协调者yes,否则返回no。
  • 阶段二:提交事务。东风,发令枪

提交事务:如果收到了全部参与者的反馈都是yes,执行事务的提交。协调者向全部的参与者节点发送Commit请求。参与者收到Commit以后提交事务,完成提交以后释放整个事务执行期间占用的事务资源,并且向协调者发送Ack消息。协调者收到全部的参与者的Ack以后,完成事务。

中断事务:收到了任何一个参与者的No,或者在等待超时以后没有收到全部参与者的yes,进行中断流程。 协调者向全部的参与节点发送Rollback请求,参与者收到rollback以后,利用Undo信息执行回滚,并释放资源,向协调者发送Ack。协调者收到全部的参与者的Ack以后,完成事务。

满足了强一致性,优点:原理简单,容易实现;缺点:存在同步阻塞,所有的参与者都被阻塞等待统一行动。存在单点问题,一旦协调者挂了,在阶段二中被卡死。脑裂问题,在发送了Commit以后如果因为局部网络异常崩溃,导致只有部分参与者收到了Commit,就会导致数据不一致。

在这里插入图片描述

3PC

三阶段提交,主要是对阶段二进行了拆分,形成了CanCommit,PreCommit,DoCommit三个阶段。
在这里插入图片描述

  • CanCommit:协调者询问参与者是否可以执行事务提交操作,参与者予以反馈,并进入准备准备状态。
  • PreCommit:如果全是yes,协调者发送PreCommit请求,进入Prepared阶段,参与者收到以后,执行事务,并且将Undo和Redo写入事务日志,返回Ack操作。如果收到了No或者等待超时,协调者发送abort指令,参与者结束事务。
  • do Commit:协调者收到了全部的ack,进入Commit状态,发送do commit请求,参与者收到Commit以后提交事务,完成提交以后释放整个事务执行期间占用的事务资源,并且向协调者发送Ack消息。否则,发送abort指令,参与者执行回滚,返回ack。

需要注意的是,在进入阶段三以后,如果协调者出现问题或者网络出现问题,参与者在等待超期以后会继续事务的提交

优点:降低了参与者的阻塞范围,且能够在单点故障以后达成一致。但是依然存在脑裂问题

Paxos

具有高容错特性的一致性算法。分为接收者(Accepter)和提出者(Proposer)。一个接收者必须接受收到的第一个提案,接收者只认可接收到的最新的议案(即议案编号最新),当某个提案被一半以上接收者认可后,那么该议案成功。有一篇讲的还不错的文章,paxos详解

对于这个算法核心是提案的特点,如果编号为M,value值为V的提案 [M, V]被选定,那么所有比M0编号高,且被选中的提案必须也是V0。因此得到核心环节,提案生成。

基础流程

提案生成

  1. prepare请求:Proposer选择一个新的提案编号Mn,然后向超过一半acceptor的acceptor集合发送请求,要求该集合中的acceptor做出如下回应:
    • 不能再批准任何编号小于Mn的提案
    • 若果acceptor已经批准过任何提案,那向proposer反馈已批准过得提案中编号小于Mn但是最大编号的提案的值V
  2. 如果proposer收到了半数以上的acceptor的响应结果,则它可以产生编号为Mn,值为Vn的提案,这里的Vn是指的所有响应中编号最大的提案的值。若半数以上的acceptor未批准过任何的提案,则Vn的值由Proposer任意选择

在提案确定之后,proposer会向acceptor集合再次发送该提案,称此请求为accept请求

批准阶段

Acceptor会收到来自proposer的两种请求:

  • Prepare请求:Acceptor可以在任何时候响应一个prepare请求;
  • Accept请求: 若acceptor为响应过任何编号大于Mn的请求,那么它就可以接受这个编号为Mn的请求。

每个proposer可以任意时刻抛弃提案,因此accepter最好可以进行回应,以便及时丢弃。同时考虑到系统的活性问题,比如proposer不断地提出一系列单增提案,会导致死循环。因此一般选择一个主Proposer提出提案。

优点:解决了无限等待和脑裂问题。

优化

当某个副本节点被升级为Master以后,使用新的N编号广播一个prepare消息,每个未达成一致地Instance将各自最后接受的提案值打包,并且作为promise返回。master对这些未决的Instance执行propose和accept。除非master发现了一个更大的reject,说明集群中由另一个master在进行prepare,需要重新prepare->promise。

Raft

这个算法在redis的集群策略中被使用了。我觉着是一个很有意思的算法。

主要是集群选择master的过程,正常情况下,master和slave之间存在心跳机制。如果slave在一定的时间内无法收到心跳,进入主观下线判断,这时候给其他的slave发送咨询,如果收到过半的主管下线反馈,认为客观下线自己会成为candidate,然后发送投票。这时其他节点需要对这个请求进行反馈,对于每一个纪元,每个节点只会给收到的第一个请求进行投票,其余的都静默。当一个节点收到半数以上投票时候,升级为主节点。和其余的节点重新建立心跳机制。

ZAB

主要是被ZooKeeper使用,成为ZAB原子消息广播协议。ZooKeeper只允许唯一的一个Leader进行事务请求的处理。ZAB协议包括两个部分,崩溃回复和消息广播,前者用于选择leader服务器,后者用于leader服务器的消息同步。

消息广播

消息广播的过程类似于二阶段提交的过程,但是删除了中断逻辑。所有的follower服务器要不正常反馈leader提出事务,要不抛弃leader。因此,我们可以在leader收到过半ack响应以后就开始提交事务。但是这会导致leader崩溃退出引发的不一致性,这就需要崩溃恢复模式来解决这个问题。并且广播是基于FIFO特性的TCP协议进行网络通信的,很容易保证消息接收与发送的顺序性。在事务广播前,leader会为事务指派一个全局单调递增唯一ID,称为事务ID。因为ZAB协议保证每一个消息严格的因果关系,因此需要按照ZXID进行排序和处理。具体的就是,leader和每个follower直接分配了一个单独的队列,保证顺序的正确性。follower在接受到事务以后,先以事务日志的形式落盘,然后返回ack。

崩溃恢复

ZAB协议需要保证在leader服务器上提交的事务最终要被所有的服务器执行提交;保证丢弃那些旨在leader服务器上被提出的事务。

如果从集群中选举出来的机器具有最大的ZXID编号的话,可以保证这个新选举出来的leader具有所有已经提交的提案(因为这个任务一定是被提交的,且不会是master的一厢情愿),并且省去了检查提交和丢弃的工作。在完成选举以后,leader服务会首先确认事务日志中所有的proposal是不是都已经被集群中过半的机器提交了。leader每一个follower都准备一个队列,将没有被这些follower提交的事务进行同步。

具体的,这里巧妙使用了64位的ZXID,高32位是epoch编号,低32位是递增的事务。当新的leader产生时候,解析出epoch并加一,后32位置为0。保证不发生混乱。

这篇关于【分布式】一致性算法总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!