分布式算法：multi-paxos、Quorum NWR等等

分布式的一致性

在分布式系统中，一致性是一个比较重要的问题，目前用的比较多的应该是paxos算法或者Raft算法了，其实在一致性中，基本上是说数据一致性，比如系统内部一份逻辑数据存在多个物理的数据副本时，对其执行读写操作会产生什么样的效果。这儿说的就是数据一致性。但在讨论分布式数据库时，其实具体是两个方向

• 数据一致性

• 事务一致性

先介绍一下目前大致的分布式算法有哪些~后面一篇会介绍下当前数据一致性的实现~

Paxos算法

Paxos算法在过去几十年，基本是分布式共识的代名词，因为目前的很多算法都是基于它改进的，比如Fast Paxos、Cheap Paxos、Raft、ZAB原子广播协议等等。

可能大部分人都熟悉Paxos算法，其实Paxos没这么简单，它是以晦朔难懂著称，它包含两个部分。

• Basic Paxos算法：描述多个节点间如何根据某个值（提案）达成共识

• Multi-Paxos算法：描述多个Basic Paxos实例，根据一系列值达成共识

Basic Paxos

其实咱们平常所说的Paxos实现基本都是Basic Paxos的实现，Multi-Paxos晦涩难懂，不过目前实现且应用比较好的可以看看google的chubby~

话不多说，直接上图看看Basic Paxos如何实现

首先，Basic Paxos有三种角色，咱们先简单区分下

• Proposer：提议者，一般提议一个值，用于投票表决

• Acceptor：接受者，对每个提议值进行投票

• Learner：学习者，保存存储共识的值，不参与投票，类似主从模式中的从节点

准备（Prepare）阶段

注意，在准备请求中只带提案编号，不带提案值。

这个时候，当Acceptor都接受到Proposer的提案编号后，会将当前编号存储，后续请求比当前编号小的直接丢弃，大的就替换。

所以以上最终的编号是5，因为5最大

接受（Accpet）阶段

因为在准备阶段时提案确定为5，接受阶段，客户端的提案值是1，会被丢弃，最后保存的value是客户端2发送的7

所以，Basic Paxos是通过二阶段提交的方式达成共识的，当然不仅仅在Paxos算法中，其他场景也会用到二阶段提交~第二个就是Paxos的容错，它和分布式事务不一样的就是不需要等待所有的节点同意后才提交操作，它只需要一半以上的节点同意就可以提交，所以能够容忍大概1/2的故障（当然业务中基本不可能产生这么大故障）

Multi-Paxos

如果有兴趣可以看看Chubby的Mutli-Paxos的实现。

从Basic Paxos来看有这么一些问题，我们的流程是二阶段提交，在第一阶段Prepare阶段中，需要接受到大多数准备响应的提议者，才可以发起请求进入第二阶段。而Multi-Paxos是基于多个Basic Paxos实例实现一系列值得共识，那么就会可能产生以下问题：

• 网络延迟，分布式系统运行建立在rpc基础上的，准备阶段和接受阶段往返消息多，性能开销也比较大，所以可能延迟会比较高

• 提案冲突，如果多个提议者同时提交请求，可能会导致提议者收到的准备请求不均匀导致重新协商，比如10个节点集群，8个提议者一起发送请求，那么可能这些提议者都只收到2个准备响应...

所以要解决以上问题，通过优化Basic Paxos执行和引入领导者解决问题。

领导者（Leader）

引入一个leader节点，leader作为唯一提议者，这样就不会有冲突产生了，不过Multi-Paxos论文中没有说如何选举领导者，比如Chubby中的leader是通过执行Basic Paxos来选举产生的...

优化Basic Paxos执行

采用当leader处于稳定状态时，省掉准备阶段，直接进入接受阶段执行。这个就是说如果leader上面的命令是最新的，那就不用准备阶段了~

Chubby中Multi-Paxos的实现

说实话，Chubby我也不是很了解，是在了解GFS时阅读过其实现，GFS之所以可以在很庞大的集群内保持数据一致性，靠的就是Chubby这个分布式锁来实现的。

Chubby就是和我们想的那样，一个Master对应一堆Slave，这些Slave中也有Master 和 Slave，比如GFS上面，GFS Master负责维护Chuck Server，而Chunk Server负责自己的Chunk Client，所有读写都在Chunk Server上面执行，同时Chunk Server会自动和GFS Master 续租，这样请求可以不用每次都通过GFS Master，可以直接走Chunk Server处理，降低服务器压力。

其实对于Multi-Paxos比较复杂，我理解的也不深，大概知道个流程，感兴趣的最好深入阅读下论文实现，现在如果对分布式感兴趣，可以推荐看看Google三架马车（BigTable、GFS、MapReduce）~

Raft算法

Raft算法属于Multi-Paxos算法，在其思想基础上做了一些简化，目前Raft算法是分布式系统开发首选算法了，像Chuuby、Spanner开发时不用Raft的原因很简单，因为当时没有Raft论文...

但现在的系统大多数都选择了Raft算法，比如etcd、Consul、CockroachDB等等，最近弄开源之夏，像sofajraft也有项目~

raft算法共有三种状态

• Leader：领导者，工作内容分三块：处理写请求，管理日志复制和不断发送心跳信息。

• Follower：跟随者，接收处理leader的消息，当leader心跳消息超时时，就站出来，推荐自己当候选人。

• Candidate：候选人，候选人向其他节点发送请求投票，如果赢的了大多数投票就晋升leader

Raft算法把问题拆分成一个个独立的子问题，比如Leader选举（Leader Election）、日志复制（Log Replication）、安全（Safety）和成员变化（Membership Changes）等等。

其实也就是三个子问题：

• Leader选举：因为 Leader 所在的服务器可能会挂掉，那么挂掉之后，我们需要尽快确认一个新 Leader。

• 日志复制：我们需要保障分布式共识，所以 Leader 需要把日志复制到其他节点上，并且确保所有 节点的日志始终是一致的。

• 安全性：，在 Leader 挂掉，切换新 Leader 之后，我们会遇到一个挑战，新的 Leader 可能 没有同步到最新的日志写入。而这可能会导致，新的 Leader 会尝试覆盖之前 Leader 已 经写入的数据。

Leader选举 （Leader Election）

在Raft中，Leader会定期像Follower发送心跳，Follower也会设置一个超时时间，如果超过时间没有收到心跳，就会任务leader挂了，发起新的选举。

Follower选举会做两个动作：

1. 先给自己投一票

2. 向所有其他的Follower发起一个RequestVote请求，也就是要求那些Follower为自己投票。这个时候，Follower角色就转变为Candidate

在每个RequestVote字段中，除了有发起投票的服务器信息外，还有一个Term（任期）字段，这个字段本质就是一个Leader的版本信息，或者说是逻辑时钟。

每个Follower都会本地保留当前Leader是哪一任期的，当他要发起投票时，会把任期自增1，和请求一起发出去。

其他Follower在接受RequestVote请求时，会去比较任期，如果请求的任期更大，就会投票给这个Candidate，否则就拒绝这个请求。

Candidate在这个过程中会遇到三种情况：

第一种，自然是超过半数服务器给它投票。那么，它就会赢得选举，变成 Leader，并且进 入一个新的任期。

第二种，是有另外一个 Candidate 赢得了选举，变成了下一任的 Leader。这个时候，我 们还不知道自己已经输了。过了一会儿，新的 Leader 接收到了外部客户端的写入请求，就 会向我们这个 Candidate 发起日志同步的请求。或者，新的 Leader 也会向我们发送一个 心跳请求。无论是哪种请求，里面都会包含一个任期的信息，这个任期的信息比我们当前知道的最新的 Leader 大，那么我们就知道自己在投票里面输了，会把自己变成一个 Follower，并更新最新的任期和 Leader 信息。

第三种，是过了一段时间，无人获胜。我们会为这种情况设置一个超时时间，如果到了超 时时间，我们既没有赢也没有输，那么我们会对任期自增 1，再发起一轮新的投票。

投票可能无限循环的解决方案

所以这个选举有个缺点就是，当Leader选举时，可能很多个Follower都会成为Candidate，它们都会先给自己投票，然后再向其他人发起RequestVote，这样票会被很多人瓜分，导致没人拿到超过半数投票，导致一直循环。

Raft解决就是让选举的超时时间在一个区间内随机化，这样不同服务器会在不同的时间点超时，最先超时的服务器很大概率可以获得半数投票。

日志复制（Log Replication）

向Leader发送写入数据的请求，其实写入请求就是一个状态机的方案，写入请求其实就是一条操作日志的追加写。在raft通过一个AppendEntries的rpc调用实现。

日志包含三部分信息

1. 日志的索引，这是一个随着数据写入不断自增的字段。

2. 日志的具体内容，也就是具体的状态机更新的操作是什么。

3. 这一次数据写入，来自 Leader 的哪一个任期。

在追加写时还有日志校验，确保对应的follower和leader数量是一致的

在发起写入日志请求时，Leader的AppendEntries的RPC中除了最新的日志外，还有上一条日志索引和任期信息。

Follower会先对比日志索引和任期信息，在自己的日志里寻找相同索引和任期的日志所在的位置。

• 如果找到了，会把这个位置之后的日志删除掉然后追加新日志

• 如果没有，会拒绝追击新日志，同时Leader会在自己的日志中找到前一条日志，然后重新发给Follower同步。

而这个方式让我们不用担心硬件故障等做什么两阶段回滚恢复数据啥的，只要保证Leader数据就好了，所以通过安全性来保障。

安全性（Safety）

Raft的做法是在选举的RPC请求中判断是否包含有最新日志。

在 RequestVote 的请求里，除了预期的下一个任期之外，还要带上 Candidate 已提交 的日志的最新的索引和任期信息。 每一个 Follower，也会比较本地已提交的日志的最新的索引和任期信息。 如果 Follower 本地有更新的数据，那么它会拒绝投票。

在这种情况下，一旦投票通过，就意味着 Candidate 的已提交的日志，至少和一半的 Follower 一样新或者更新。而 Raft 本身写入数据，就需要至少一半成功，才会提交成 功。所以，在前面愿意给 Candidate 投票的里面，至少有一个服务器，包含了最新一次的 数据提交，而 Candidate 至少和它一样新，自然也就包含了最新一次的数据提交。

成员变更（Membership Change）

其实就是增减服务器对整个集群的影响。

在新增服务器时，可能会出现一个比较严重的问题，就是脑裂，俗称有多个leader产生。

原先有服务器 A，B，C 三台； 新增了服务器 D，E 两台； 服务器 A 的配置先更新，这个时候，它觉得需要 3 台服务器的投票就是多数通过了； 服务器 B 的配置后更新，在没有更新的时候，它觉得有 2 服务器的投票就是多数通过 了； 这样，我们就会遇到 A 和 B 都各自认为投票获得通过的情况，这个时候，我们在一个集 群里就会有两个 Leader，系统的共识就被破坏了。这就是脑裂。

过渡共识（Joint Consensus）

为了解决脑裂，Raft加入了一个过度共识的办法，无论服务器是增加还是减少，raft有两组配置，第一组就是变更之前的服务器配置，称之为old configuration，第二组配置就是我们之后的服务器配置，称之为new Configuration。

思路就是，在过渡共识过程中，Raft会做到以下几点：

• 所有日志追加写入，都会复制到新老配置的所有服务器上面

• 新老配置里的任何一个服务器，都有可能会选举成Leader节点

• 无论是选举，还是达成共识后提交日志，投票需要同时满足旧配置里半数以上服务器的 通过，而且也需要新配置里半数以上服务器的通过。

这个其实就是一个双写的迁移策略，在很多地方都会用到这种思想。写old的同时也写new服务器，然后读的时候从old到new慢慢过渡，不过有个问题就是因为新加入的服务器需要同步Leader的日志，所以如果新加入机器比较多会影响raft的写入性能，这儿的话采用服务器过渡，也就是服务器会先进行数据复制，但是不参与投票，知道复制的数据追到Leader进度时才会分配投票权。

过渡共识中Leader消失问题

就是在从old Configuration过渡成new Configuration时，如果leader在Old集群中，那么过渡完成Leader可能就消失了...

Raft是这么解决的，Leader在完成new Configuration的过渡后，会退回到Follower状态。这也就意味着，这个Leader写入数据到提交阶段，我们的Raft集群被一个不在集群内的服务器管理，这个时候进行半数投票，不包括这个管理的这个服务器就好了，这个额外的服务器只起集群管理作用，并不会影响Raft的正确性。

日志压缩（Log Compaction）

随着时间的写入，日志会越来越多，存储空间可能不够，其实这儿的压缩，所谓就是将同一个key的数据保留最新的一份快照就好了

类似Pulsar中的topic compaction，当然这个虽然解决空间问题，但也有可能大量的节点同时进行Log compaction影响write性能，不过raft本身应该不会有啥问题，只有类似Pulsar这种才可能会导致底层的bookKeeper集群写入性能波动，这儿可以记个issue，采用分层存储的方式解决该问题。

客服端交互和可线性化

客服端可能发送给Leader的请求超时了，客户端会换一个服务器重试，这种情况下可能会出现一个客服端重复请求同一服务器，所以每个客服端请求都带上一个UUID的唯一标识，Raft在服务端去重，如果对应操作执行过了，只需要返回结果，不需要再次执行~

可线性化就是已经写入的数据在下次读取时一定能读到，Raft是Leader写Leader读，这个肯定可以读到，不过在Leader切换时就不一定了。所以Raft中有个租约机制，防止因为网络分区出现新旧Leader都存活的情况，只有租约过期了才可以选举新Leader，这样永远只在一个Leader上面读。

Gossip协议

假如需要系统在极端情况下，比如只有一个节点在运行，也可以运行。那么就可以用Gossip协议了，因为Paxos和Raft都是大多数正常运行系统才能稳定运行。

Gossip三板斧

• Direct Mail 直接邮寄

• Anti-entropy 反熵

• Rumor mongering 谣言传播

Direct Mail 直接邮寄

如图所示，就是直接把数据发送给对应的节点，如果失败就缓存下来重传。很简单，但是网络性能非常高，同时如果缓存不够可能会丢数据

Anti-entropy 反熵

反熵就是，通过异步修复实现最终一致性的方法，集群中的节点每隔一段时间就选择某个其他节点，然后通过交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。

熵和高中学的化学一样，指混乱程度。目前反熵有三种方式：推、拉、推拉。

推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵。

拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵。

理解了推和拉之后，推拉这个方式就很好理解了，这个方式就是同时修复自己副本和对方副 本中的熵。

反熵的应用：Cassandra

Cassandra的Read Repair

读时修复：在读取数据时，如果不同节点间数据不一致就会进行修复

Cassandra的Hinted Handoff

集群间远程写数据时，如果写失败就缓存下来，然后定时重传解决副本数据一致性。其实这儿更像直接邮寄~

除了Cassandra，比如InfluxDB也是有反熵的实现在里面，感兴趣各位自己去了解了~这儿介绍比较简单。

反熵缺点就是需要做一致性对比，很消耗性能，是否启用反熵得在不同场景中去判断。

但是如果我们的环境节点未知，且需要动态维护，就不太适合反熵来进行应用了。所以这儿用谣言传播解决，redis目前也是这么干的~

谣言传播 Rumor mongering

其实就是一个节点有了新数据后，这个节点变成活跃状态并周期性向其他节点发送数据，直到所有节点都存储了该数据。

Quorum NWR算法

说个笑话，之前在阿里简历面时，面试官和我聊一致性算法，我说了这个算法，估计面试官没听过，可能认为我在乱说，后面给我挂了.....

最终一致性可能可以解决大多数问题，但是在一些强一致性场景下，不行，我们要实现这么一种场景，就是数据更改后用户马上可以查询到所以得考虑强一致性算法

Quroum NWR可以实现强一致性，它的出现就是希望我们可以动态调整写入或查询的方式，当公式

成立时，就可以实现强一致性了~

Quorum NWR三要素

• N 表示副本数，又叫做副本因子（Replication Factor），表示同一份数据集群中有多少副本。

• W 又称写一致性级别（Write Consistency Level），表示成功完成W个副本更新，才完成写操作。

• R 又称读一致性级别，表示读取一个数据需要读取R个副本，然后返回R个副本中最新的数据。

也就是有两种效果，如果W + R > N 时，就可以实现强一致性，否则就是最终一致性。

如何实现Quorum NWR算法

这儿也只是简单举个例子，因为我也不是特别了解InfluxDB实现。

在InfluxDB企业版中，在创建保留策略时就可以指定数据库Database对应的副本数，注意，在InfluxDB中，副本数不能超过节点数。你可以这么理解，多副本的意义在于冗余备份，如果副本数超过节点数，就意味着一个节点会存在多个副本，这样意义不大了~

InfluxDB企业版支持“any、one、quorum、all”四种写一致性级别

• any：任何一个节点写入成功后，或者接收节点已将数据写入 Hinted-handoff 缓存（也 就是写其他节点失败后，本地节点上缓存写失败数据的队列）后，就会返回成功给客户 端。

• one：任何一个节点写入成功后，立即返回成功给客户端，不包括成功写入到 Hintedhandoff 缓存。

• quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2 时才有意义，否则等效于

• all。 all：仅在所有节点都写入成功后，返回成功。

我们可以设置all，这样实现强一致性~。

PBFT算法

PBFT算法在区块链中应用广泛，比如Hyperledger Sawtooth、Ailliqa等等；如果面试区块链相关岗位时，可以说出该算法挺不错的感觉

PBFT算法是通过签名（或消息认证码MAC）约束恶意节点的行为，也就是说，每个节点都可以通过验证签名消息确认消息的发送来源，一个节点无法伪造另外一个节点的消息，采用三阶段协议基于大多数原则达成共识的~

达成共识的过程：

第一步，客户端发一个请求给主节点去执行某个操作；

第二步，主节点通信给各个子节点；

第三步，所有节点通过算法并把结果返回给客户端；

第四步，当客户端「收到结果」后，过程结束；

第四步中收到结果是的最大容错节点数

1. 假设 n 是总节点数，f 为有问题的节点，

1. 问题包括两种，一种是故障节点 f，一种是作恶节点 f。

1. 故障节点收到通信后不会返回结果，作恶节点收到通信后会返回错误的结果。在统计返回节点数时，有问题的节点 f 会被排除在外，所以只要正确通信数大于作恶节点数 f 即可保证本次通信正常，即 f + 1 个正确节点，

1. 也就是说总节点数n 包括 f + 1 个正确节点，f 个作恶节点和 f 个故障节点，即 3f + 1 = n，

1. 因此pBFT算法支持的最大容错节点数是 f = （n-1）/3，

1. 也就是超过 1/3 的节点数即可。

Pre-prepare 预准备阶段

节点A将消息广播给其他节点

由于主节点不会发布两条内容不同的通信，则如果收到节点编号相同而内容不同的通信，子节点会选择拒绝请求。

Prepare 准备阶段

其他节点收到节点A的消息后，就进入准备阶段，同时将广播包含作战指令的准备消息发送给其他将军。

由于同时有n个节点接受请求进行通信，所以在一定时间范围内，如果收到超过 2f 个不同节点的 prepare 消息，就代表 prepare 阶段已经完成。

Commit 提交阶段

当某个节点收到2F个一致的包含作战指令的准备消息后，就会进入commit阶段，f就是损坏的机器数。

和prepare同理，当收到 2f+1 个 commit 消息后（包括自己），代表大多数节点已经进入 commit 阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据。

如果主节点出现故障，会触发viewchange事件，这儿感兴趣的自己下去了解吧~当然也有不足，就是区块链中所谓的女巫攻击，也就是一个用户操纵多个账户进行攻击，这个是无法避免的~

PoW算法

Proof of Work 工作证明，通过执行hash函数，然后通过运算后的结果值，证明自己做过相关工作。

这儿就是区块链相关的了，大概就不介绍了~

其实上面这些，我也只是简单介绍了一下，比较粗糙，想最真实的了解肯定是论文第一，或者去看看各种实现，比如现在raft用的多，etcd、sofajraft等等开源项目都可以关注下。