分布式(5)

发布时间:2024年01月03日

目录

22.什么是Paxos算法?如何实现?

24.全局唯一ID有哪些实现方案?

25.数据库方式实现方案?有什么缺陷?


22.什么是Paxos算法?如何实现?

Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法,使其获得2013图灵奖。

三个角色?可以理解为人大代表(Proposer)在人大向其他代表(Acceptors)提案,通过后让老百姓(Learner)落实。

Paxos将系统中的角色分为提议者(Proposer),决策者(Acceptor),和最终决策学习者(Learner):Proposer:提出提案(Proposal)。Proposal信息包括提案编号(Proposal? ID)和提议的值(Value)。

Acceptor:参与决策,回应Proposers的提案。收到Proposal后可以接受提案,弱Proposal获得多数Acceptors的接受,则称该Proposal被批准。

Learner:不参与决策,从Proposers/Acceptors学习最新达成一致的提案(Value)。

在多副本状态机中,每个副本同时具有Proposer,Acceptor,Learner三种角色。

基于消息传递的三个阶段

第一阶段:Prepare阶段;Proposer向Acceptors发出Prepare请求,Acceptors针对收到的Prepare请求进行Promise承诺。

Prepare:Proposer生成全局唯一且递增的Proposal? ID(可使用时间戳加Server ID),向所有Acceptors发送Prepare请求,这里无需携带提案内容,只携带Proposal? ID即可。

Promise:Acceptors收到Prepare请求后,做出“两个承诺,一个应答”。

承诺1:不再接受Proposal? ID 小于等于(注意:这里是<=)当前请求的Prepare请求;

承诺2:不再接受Proposal? ID小于(注意:这里是<)当前请求的Propose请求;

应答:不违背以前做出的承诺下,回复已经Accept过的提案Proposal? ID最大的那个提案的Value和Proposal? ID ,没有则返回空值。

第二阶段:Accept阶段;Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理。

Propose:Proposer收到多数Acceptors的Promise应答后,从应答中选择Proposal? ID最大的提案的Value,作为本次要发起的提案。如果所有应答的提案Value均为空值,则可以自己随意决定提案Value。然后携带当前Proposal? ID,向所有Acceptors发送Propose请求。

Accept:Acceptor收到Propose请求后,在不违背自己之前做出的承诺下,接受并持久化当前Proposal? ID和提案Value。

第三阶段:Learn阶段;Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有的Learners。

23.什么是Raft算法?

不同于Paxos算法直接从分布式一致性问题出发推导出来,Raft算法则是从多副本状态机的角度提出。Raft实现了和Paxos相同的功能,他将一致性分解为多个子问题:Leader选举(Leader election),日志同步(Log? replication),安全性(Safety),日志压缩(Log compaction),成员变更(Membership? ?change)等。同时,Raft算法使用了更强的假设来减少了需要考虑的状态,使之变的易于理解和实现。

三个角色

Raft将系统中的角色分为领导者(Leader),跟从者(Follower)和候选人(Candidate):

Leader:接受客户端请求,并向Follower同步请求日志,当日志同步到大多数节点上告诉Follower提交日志。Follower:接受并持久化同步的日志,在Leader告诉日志可以提交之后,提交日志。

Candidate:Leader选举过程中的临时角色。

Raft要求系统在任意时刻最多只有一个Leader,正常工作期间只有Leader和Followers.

以子问题Leader选举为例?

Raft使用心跳(heartbeat)触发Leader选举。当服务器启动时,初始化为Follower。Leader向所有Followers周期性发送心跳。如果Follower在选举超时时间内没有收到Leader的心跳,就会等待一段随机的时间后发起一次Leader选举。

Follower将其当前term加一然后转换为Candidate。他首先给自己投票并且给集群中其他服务器发送RequestVote? RPC(RPC细节参见八,Raft算法总结)。结果有以下三种情况:

赢得了多数的选票,成功选举为Leader;

收到了Leader的消息,表示有其他服务器已经抢险当选了Leader;

没有服务器赢得多数的选票,Leader选举失败,等待选举时间超时后发起下一次选举。

选举出Leader后,Leader通过定期向所有Followers发送心跳信息维持其统治。若Follower一段时间未收到Leader的心跳则认为Leader可能已经挂了,再次发起Leader选举过程。

24.全局唯一ID有哪些实现方案?

常见的分布式ID生成方式,大致分类的话可以分为两类:

一种是类DB型的,根据设置不同起始值和步长来实现趋势递增,需要考虑服务的容错性和可用性;

另一种是类snowflake型,这种就是将64位划分为不同的段,每段代表不同的涵义,基本就是时间戳,机器ID和序列数。这种方案就是需要考虑时钟回拨的问题以及做一些buffer的缓冲设计提高性能。

25.数据库方式实现方案?有什么缺陷?

MySQL为例

我们将分布式系统中数据库的同一个业务表的自增ID设计成不一样的起始值,然后设置固定的步长,步长的值即为分库的数量或分表的数量。

以MySQL举例,利用给字段设置auto? increment? ?increment和auto? increment? offset来保证ID自增。

auto? increment offset:表示自增长字段从哪个数开始,他的取值范围是1...65535。

auto? increment? increment:表示自增长字段每次递增的量,其默认值是1,取值范围是1...65535。

缺点也很明显,首先他强依赖DB,当DB异常时整个系统不可用。虽然配置主从复制尽可能的增加可用性,但是数据一致性在特殊情况下难以保证。主从切换时不一致可能会导致重复发号。还有就是ID发号性能瓶颈限制在单台MySQL的读写性能。

使用redis实现

Redis? 实现分布式唯一ID主要是通过提供像INCR和INCRBY这样的自增原子命令,由于Redis自身的单线程的特点所以能保证生成的ID肯定是唯一有序的。

但是单机存在的性能瓶颈,无法满足高并发的业务需求,所以可以采用集群的方式来实现。集群的方式又会涉及到和数据库集群同样的问题,所以也需要设置分段和步长来实现。

为了避免长期自增后数字过大可以通过与当前时间戳组合起来使用,另外为了保证并发和业务多线程的问题可以采用Redis+Lua的方式进行编码,保证安全。

Redis实现分布式全局唯一ID,他的性能比较高,生成的数据是有序的,对排序业务有利,但是同样他依赖于redis,需要系统引进Redis组件,增加了系统的配置复杂性。

当然现在Redis的使用性很普遍,所以如果其他业务已经引进了Redis集群,则可以资源利用考虑使用Redis来实现。

文章来源:https://blog.csdn.net/qq_30624649/article/details/135359863
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。