分布式（5）

目录

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来实现。