架构与头脑：4大主流分布式算法介绍（图文并茂、算法拆解）
介绍本文聚焦高并发场景下分布式同等性算法的分析和讨论
分布式场景下困扰我们的3个焦点问题（CAP）：同等性、可用性、分区容错性。
1、同等性（Consistency）： 无论服务如何拆分，所有实例节点同一时间看到是雷同的数据
2、可用性（Availability）： 不管是否乐成，确保每一个哀求都能吸收到响应
3、分区容错性（Partition Tolerance）： 体系任意分区后，在网络故障时，仍能操纵
https://img-blog.csdnimg.cn/img_convert/2ac7fe5a194c975c0367bbc8b146158f.png
而我们最为关注的是如何在高并发下保障 Data Consistency（数据同等性），因为在很多焦点金融业务场景（如 付出、下单、跨行转账）中，为了避免资金问题，是需要强同等性结果的。而分布式同等性算法就是保障 Data Consistency的强大利刃，它的目标是确保分布式体系中多个节点在读取或修改同一份数据时，产生雷同结果的关键机制。这些算法对于包管分布式体系的同等性和可靠性至关重要。常用的分布式算法：
[*] Paxos算法
[*] Raft算法
[*] ZAB（ZooKeeper Atomic Broadcast）算法
2 主流分布式算法
2.1 Paxos算法
Paxos算法是一种用于分布式体系中保障同等性的算法，由Leslie Lamport于1990年提出，被广泛应用于分布式体系中的同等性问题，如分布式数据库、分布式存储体系等。该算法的主要目标是在一个由多个节点组成的分布式体系中，协调某个数据值并告竣同等性，典型的少数服从多数的案例。
2.1.1 根本概念
1. 提案： 由提案号（id）和提案内容（value）组成，其中id主要用于实现Paxos算法，而value对应在现实的分布式体系中为所需要修改数据的命令 或者 log信息。
2. 角色： Paxos算法中抽象出来的概念，对应着现实分布式环境中的差别分工。主要角色包罗提议者（Proposer）、答应者（Acceptor）和学习者（Learner）。
[*] 提议者负责提出值的提案
[*] 接受者负责接受提案并投票
[*] 学习者负责学习已经告竣同等的值
https://img-blog.csdnimg.cn/img_convert/b29e3ff933af4c3d7fc1fab8cf9f1341.png
Proposer 提案者提案者负责提出提案 (Proposal)，Proposal信息包罗提案编号 (Proposal ID) 和提议的值 (Value)。提案的value，可以是任何举动或者操纵，好比传统转账场景，将用户的账号余额从0改为100，Paxos 协议同一抽象为value。 Proposer可以有多个，差别的Proposer可以提出差别的甚至互斥的value，好比提案者A消耗（将变量Money-100），提案者B也消耗（将变量Money-200），但对同一轮Paxose而言，最多只有一个value可以被答应，否则就乱套了。
Acceptor 答应者Acceptor 从含义上来说就是除了当前Proposer以外的其他机器，他们之间完全平等和独立，Proposer需要夺取超过半数（N/2+1）的 Acceptor 答应后，其提案才能通过，它提倡的“value”操纵才能被所有机器（包罗Proposer、Acceptor、Learner）所接受。
Learner 学习者Learner 不参与选举，而是学习被答应的 value，在Paxos中，Learner主要参与相干的状态机同步流程。这里Leaner的流程就参考了Quorum议会机制，某个value需要获得超过半数的Acceptor 答应，才能真正被Learner学习到。
2.1.2 算法流程
1. 预备阶段（Prepare阶段）：提议者（Proposer）向所有Acceptor节点发起Prepare哀求，携带全局唯一且递增的提案编号N，要求它们告诉提议者已经接受的最高提议号。如果接受者接受了轮次小于当前轮次的提案，那么它会更新自己的状态，拒绝当前轮次的提案。
2. 答应阶段（Promise阶段） ：Acceptor节点吸收到prepare哀求后，会查抄该哀求的提议号是否比它已经接受的提议号更高。如果是，那么节点会更新自己的状态，答应不再接受轮次小于当前轮次的提案。
Acceptor收到Prepare哀求后，有两种情况：
[*] 如果Acceptor首次吸收Prepare哀求, 设置MaxN=N， 同时响应ok
[*] 果Acceptor不是首次吸收Prepare哀求，则：若哀求过来的提案编号N小于即是前次持久化的提案编号ResN，则不响应或者响应error。若哀求过来的提案编号N大于前次持久化的提案编号MaxN, 则更新MaxN=N，同时给出精确的响应。
https://img-blog.csdnimg.cn/img_convert/c768c507eaa3d8928312c1868bddcfb3.png
3. 答应响应阶段（Acknowledge阶段） ：在这个阶段，接受者会查抄自己是否接受了当条件案。如果是，那么接受者会返回一个答应响应，告诉提议者当条件案已经被接受。4. 提议的接受与决策 ：当Acceptor节点吸收到一个提议哀求时，它会查抄该提议的值是否比它已经接受的值更高。如果是，那么它会接受该提议，并向其他节点发送接受消息。当一个提议被大多数节点接受后，该提议就成为了决策，并被所有节点执行。
Proposer 获得 Accept 复兴的信息之后，做如下判断：
[*] 复兴数量 > Acceptor 数量的1/2时，代表提交 value 乐成，发送广播给所有的 Proposer、Learner，通知它们已提交的 value。
[*] 复兴数量 <= Acceptor 数量的1/2时，则重新开始，更新生成更大的提案号，跳转到预备阶段执行。
[*] 收到响应error时，同样更新生成更大的提案号，转到预备阶段执行。
https://img-blog.csdnimg.cn/img_convert/d231f891453c0406b56edf4066803320.png
5. 学习阶段（Learn阶段） ：学习者会向所有接受者发送一个学习哀求，接受者会返回已经接受的最大提案，使学习者能够学习到已经告竣同等的值。
2.1.3 应用
Paxos算法具有高度容错特性，可以在某个节点宕机、网络异常、消息延迟等问题的情况下，快速且精确地在集群内部对某个数据告竣同等。所以在很多业务场景中得到应用。好比：
[*] Zookeeper使用一个类Multi-Paxos的共识算法作为底层存储协同的机制。
[*] Google公司在其分布式锁中应用了Multi-Paxos算法。
2.2 Raft算法
2.2.1 根本概念
Raft 算法是同等性算的一种，用来解决分布式同等性问题。它提供了一种在计算体系集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列雷同的状态转换。其主要目标是解决分布式体系中的领导者选举、日记复制和安全性等关键问题。
2.2.2 领导者选举与超机遇制
在Raft算法中，服务器可以处于三种状态：领导者（leader）、跟随者（follower）和候选者（candidate）。正常情况下，集群中只包含一个 leader ，其余服务器都是 follower 。跟随者通过投票选出领导者，只有得到“大多数”跟随者投票的服务器能成为领导者；领导者负责将命令同步给跟随者，只有被“大多数”跟随者确认的命令才能提交。
1. 跟随者(Follower)Fllower是所有节点的初始状态，内部都会有一个随机超时时间。这个超时时间，规定了在倒计时结束后仍然收不到Leader的心跳，Follower就会变革为Candidate。
2. 候选者(candidate)Follower在变革为Candidate后，超时时间重置，倒计时结束时就会向其他节点提名自己的实，拉取选票。如果能获得半数以上（1/2以上,包含自己投给自己的）的选票，则当选为Leader，这个过程就叫做Leader选举。所以节点最好是单数，避免极度情况下出现一个集群选举出两个Leader的脑裂问题。
3 .领导者(leader)Raft集群通过Leader与客户端进行交互，Leader不绝处理写哀求与发送心跳给Follower，Follower在收到Leader的心跳后，其超时时间会重置，即重新开始倒计时。正常工作期间只有 Leader 和 Follower，且Leader至多只能有一个。
角色状态转换过程
https://img-blog.csdnimg.cn/img_convert/05a876ccb448a04283659f505e119680.png
2.3 ZAB（ZooKeeper Atomic Broadcast）算法
2.3.1 根本概念
ZAB（Zookeeper Atomic Broadcast）是Zookeeper原子消息广播协议，是Zookeeper包管数据同等性的焦点算法。该算法借鉴了Paxos算法，但又不像Paxos那样是一种通用的分布式同等性算法，而是特殊为Zookeeper计划的支持崩溃恢复的原子广播协议。在Zookeeper中，主要依靠ZAB协议来实现数据同等性。基于该协议，Zookeeper实现了一种主备模型（即Leader和Follower模型）的体系架构，包管集群中各个副本之间数据的同等性。通过一台主进程（Leader）负责处理外部的写事件哀求，然后将数据同步到其他Follower节点，如果超过半数乐成ACK，则主进程执行 Commit操纵。
2.3.2 广播流程
https://img-blog.csdnimg.cn/img_convert/81fc31188fc22ba23748de8154e89f9c.png
ZAB 协议的消息广播过程使用的是一个原子广播协议，雷同一个 二阶段(2PC) 提交过程。对于客户端发送的写哀求，全部由 Leader 吸收，Leader 将哀求封装成一个事件 Proposal，将其发送给所有 Follwer ，然后，根据所有 Follwer 的反馈，如果超过半数乐成响应，则执行 Commit 操纵（先提交自己，再发送 Commit 给所有 Follwer）
3 总结
分布式同等性算法是确保分布式体系中多个节点在读取或修改同一份数据时，产生雷同结果的关键机制。这些算法对于包管分布式体系的同等性和可靠性至关重要。现在常见以下是一些常用的分布式同等性算法：
[*] Paxos算法：由Lamport宗师提出，是一种基于消息通报的分布式同等性算法。它旨在解决在一个可能发生故障的分布式体系中，如何快速精确地在集群内对某个值告竣同等，并包管整个体系的同等性。
[*] Raft算法：一种相对易于明确的分布式同等性算法，它将同等性问题的复杂性分解为若干个相对独立的子问题。Raft通过选举和日记复制的方式确保数据的同等性。
[*] ZAB（ZooKeeper Atomic Broadcast）算法：是ZooKeeper中使用的原子广播协议，用于实现分布式体系中的状态同步。ZAB协议包罗恢复模式和广播模式，确保ZooKeeper集群中的各个节点能够保持数据的同等性。
别的，另有其他分布式同等性算法，如Gossip协议等，这些算法在差别的分布式体系场景中有各自的应用和优势。
在选择分布式同等性算法时，需要考虑体系的规模、节点的数量、通讯开销、数据同等性要求以及容错性等因素。差别的算法可能适用于差别的场景，因此需要根据具体情况进行选择和调整。
文章转载自：Hello-Brand
原文链接：https://www.cnblogs.com/wzh2010/p/18031245
体验地址：引迈 - JNPF快速开辟平台_低代码开辟平台_零代码开辟平台_流程计划器_表单引擎_工作流引擎_软件架构
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]