分布式算法详解(4大常用分布式算法)

分布式算法详解(4大常用分布式算法)-mikechen

分布式算法是保证分布式一致性的基础,常用的分布式算法有Paxos、Raft、ZAB等等,下面重点详解分布式算法。

Paxos算法

Paxos算法解决的问题是如何在一个分布式系统中达成一致性决策。

例如:在一个分布式数据库系统中,多个节点需要在执行某个操作时达成一致性,如何保证这些节点的数据达成一致性就是Paxos算法需要解决的问题。

Paxos算法的核心思想是使用一个可靠的、不可篡改的日志来记录节点的决策,并通过多轮的投票协议来保证这些决策在各个节点之间达成一致。

Paxos算法中,分为3种角色:

 

分布式算法详解(4大常用分布式算法)-mikechen

  • Proposer :提议者;
  • Acceptor:决策者;
  • Learner:最终决策学习者;

1.Proposer(提议者)

只要 Proposer 发的提案被半数以上 Acceptor 接受,Proposer 就认为该提案里的 value 被选定了。

2.Acceptor(决策者)

只要 Acceptor 接受了某个提案,Acceptor 就认为该提案里的 value 被选定了。

3.Learner(最终决策学习者)

Acceptor 告诉 Learner 哪个 value 被选定,Learner 就认为那个 value 被选定。

Paxos算法主要包含以下几个阶段:

  1. 提议阶段:节点向其他节点提议一个值,并等待其他节点的回复。
  2. 学习阶段:如果一个提议被大多数节点接受,那么该提议将成为决策,并被记录在所有节点的日志中。
  3. 投票阶段:如果有多个提议同时发生,节点需要进行投票,选择其中一个提议作为决策。

Paxos算法的优点是可以保证在任何情况下都能达成一致性,并且在网络分区或节点故障等异常情况下仍能正常工作。缺点是算法本身较为复杂,实现难度较大,容易出现死锁等问题。

 

Raft

Raft算法是Paxos算法的工程实现,主要特点就是通过较为简单的算法实现分布式系统的数据一致性和高可用。

Raft算法是解决分布式系统一致性问题的,与 Paxos 实现的功能相同,相对来说更容易实现和理解。

在Raft算法中,一个集群里面的所有节点有以下三种状态:

分布式算法详解(4大常用分布式算法)-mikechen

1.跟随者(follower)

类似选民,完全被动的角色,这样的服务器等待被通知投票。

2.候选者(candidate)

候选者就是在选举过程中提名自己的实体,一旦选举成功,则成为领导者。

3.领导者(leader)

领导者的作用:处理客户端交互,日志复制等动作,Raft 要求系统在任何一个时刻最多只有一个 Leader,正常工作期间只有 Leader 和 Follower。

Raft 算法角色状态转换,如下图所示:

分布式算法详解(4大常用分布式算法)-mikechen

 

ZAB算法

ZAB算法,全称是ZooKeeper Atomic Broadcast,是由ZooKeeper提出的一种分布式一致性协议,用于解决分布式系统中的一致性问题。

在解决分布式一致性方面,Zookeeper并没有使用 Paxos ,而是采用了 ZAB 协议。

ZAB 协议对于客户端发送的写请求,全部由Leader接收,Leader将请求封装成一个事务Proposal,将其发送给所有Follwer,然后根据所有Follwer的反馈,如果超过半数成功响应,则执行 commit操作。

整个广播流程分为 3 步骤:

1、将数据都复制到 Follwer 中

分布式算法详解(4大常用分布式算法)-mikechen

2、等待Follwer回应Ack,最低超过半数即成功

分布式算法详解(4大常用分布式算法)-mikechen

3、当超过半数成功回应,则执行 commit ,同时提交自己

分布式算法详解(4大常用分布式算法)-mikechen

通过以上 3 个步骤,就能够保持集群之间数据的一致性。 实际上,在 Leader 和 Follwer 之间还有一个消息队列,用来解耦他们之间的耦合,避免同步,实现异步解耦。

ZAB算法的优点是可以保证系统的高可用性和一致性,并且在领导者选举、网络异常等情况下仍能正常工作。缺点是在高并发场景下可能会出现性能瓶颈,并且需要占用大量的内存和存储空间来记录节点状态。

 

Gossip

Gossip protocol 也叫 Epidemic Protocol ,就是流行病协议,实际上它还有很多别名,比如:“流言算法”、“疫情传播算法”等。

这个协议的作用就像其名字表示的意思一样,非常容易理解,比如:电脑病毒的传播,就是典型的所谓流行病协议。

Gossip算法主要有以下几个特点:

  1. 随机化:Gossip算法采用随机化的方式来选择节点进行通信,以避免节点之间的通信瓶颈,从而提高系统的吞吐量和可用性。
  2. 局部化:Gossip算法只与相邻节点进行通信,避免不必要的全局通信,减少网络带宽和延迟。
  3. 故障容错:Gossip算法可以自动检测故障节点,并在节点故障时重新选取相邻节点进行通信,以保证系统的高可用性和一致性。
  4. 高效性:Gossip算法的信息传播速度非常快,具有良好的可扩展性,可以适应大规模的分布式系统。

Gossip算法在分布式数据库、分布式缓存、分布式文件系统等领域得到了广泛的应用。

例如:Redis Cluster就是使用Gossip算法,使每个节点记录的信息实现最终一致性。

以上就是分布式算法的详解,更多分布式系统,请查看:史上最强分布式系统详解(非常全面)

作者简介

陈睿|mikechen,10年+大厂架构经验,大厂资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。

👇阅读更多mikechen架构文章👇

阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师

以上

关注作者「mikechen」公众号,获取更多技术干货!

后台回复架构,即可获取《阿里架构师进阶专题全部合集》,后台回复面试即可获取《史上最全阿里Java面试题总结

评论交流
    说说你的看法