首页 / 算法 / 【分布式】一致性算法总结
【分布式】一致性算法总结
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【分布式】一致性算法总结，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6089字，纯文字阅读大概需要9分钟。
内容图文
文章目录
最近结束了面试以后，对面试中问到的分布式问题还是比较有兴趣的。因此希望能够进一步学习分布式的有关内容。本文主要是整理了分布式系统中使用到的分布式算法。分布式的一个大的问题就是如何在多个集群之间完成协调一致，也就是事务的原子性。并且我们还希望有高可用高性能的实现，尽量可以避免单点问题。因此往往都会设计到主节点的选择算法。
2PC
2PC是Two-Phase Commit的缩写，二阶段提交。目前大多数SQL数据库都是采用的二阶段提交的策略完成事务，利用该协议可以非常方便的完成所有分布式事务参与者的协调，统一决定事务的提交和回滚。设计思路主要是保证在最后一个瞬间的网络是正常的就可以，尽可能将麻烦的过程前置。
- 阶段一：协调者让全部的参与者都完成准备，万事俱备，只欠东风。
- 事务询问：协调者向所有的参与者发送事务内容，询问各个从节点是否可以执行事务的提交，并等到参与者的相应。
- 执行事务：各参与者节点执行事务，并且将undo和Redo写入事务日志。
- 反馈：如果参与者成功执行了事务，反馈给协调者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。因此得到核心环节，提案生成。
基础流程
提案生成
- prepare请求：Proposer选择一个新的提案编号Mn，然后向超过一半acceptor的acceptor集合发送请求，要求该集合中的acceptor做出如下回应：
- 不能再批准任何编号小于Mn的提案
- 若果acceptor已经批准过任何提案，那向proposer反馈已批准过得提案中编号小于Mn但是最大编号的提案的值V
- 如果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。保证不发生混乱。
内容总结
以上是互联网集市为您收集整理的【分布式】一致性算法总结全部内容，希望文章能够帮你解决【分布式】一致性算法总结所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。