共识算法

共识算法
一致性协议


说到共识算法，大家首先想到的应该都是 Raft、Paxos、Zab 算法这类理解起来比较困难的强一致性算法。
但是还有一个弱一致性的共识算法比较好理解，Gossip 协议。

为了保证各个节点的数据的一致性，必然就涉及到数据的更新操作。



Gossip protocol 也叫 Epidemic Protocol （流行病协议）
Gossip 设计了两种可能的消息传播模式：反熵（Anti-Entropy）和传谣（Rumor-Mongering），


因为这个网站里面直接有非常仿真的动画模拟 gossip 协议的同步过程，一个动图胜过千言万语。
地址先放在这里，大家可以自己访问玩儿一下：
https://flopezluis.github.io/gossip-simulator/


gossip 协议在概念上非常简单，编码也非常简单。它们背后的基本想法是这样的：
一个节点想与网络中的其他节点分享一些信息。然后，它定期从节点集合中随机选择一个节点并交换信息，收到信息的节点也做同样的事情。

Gossip协议是基于六度分隔理论（Six Degrees of Separation）哲学的体现，简单的来说，一个人通过6个中间人可以认识世界任何人


Gossip协议执行过程：
种子节点周期性的散播消息 【假定把周期限定为 1 秒】。
被感染节点随机选择N个邻接节点散播消息【假定fan-out(扇出)设置为6，每次最多往6个节点散播】。
节点只接收消息不反馈结果。
每次散播消息都选择尚未发送过的节点进行散播。
收到消息的节点不再往发送节点散播：A -> B，那么B进行散播的时候，不再发给 A。

Goosip 协议的信息传播和扩散通常需要由种子节点发起。整个传播过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。
Gossip协议是一个多主协议，所有写操作可以由不同节点发起，并且同步给其他副本。Gossip内组成的网络节点都是对等节点，是非结构化网络。


消息类型
Gossip 协议的消息传播方式有两种：Anti-Entropy(反熵传播)和Rumor-Mongering(谣言传播)。

反熵传播是以固定的概率传播所有的数据。所有参与节点只有两种状态：Suspective(病原)、Infective(感染)。这种节点状态又叫做simple epidemics(SI model)。过程是种子节点会把所有的数据都跟其他节点共享，以便消除节点之间数据的任何不一致，它可以保证最终、完全的一致。缺点是消息数量非常庞大，且无限制；通常只用于新加入节点的数据初始化。

谣言传播是以固定的概率仅传播新到达的数据。所有参与节点有三种状态：Suspective(病原)、Infective(感染)、Removed(愈除)。这种节点状态又叫做complex epidemics(SIR model)。过程是消息只包含最新 update，谣言消息在某个时间点之后会被标记为 removed，并且不再被传播。缺点是系统有一定的概率会不一致，通常用于节点间数据增量同步。


通信方式
Gossip 协议最终目的是将数据分发到网络中的每一个节点。根据不同的具体应用场景，网络中两个节点之间存在三种通信方式：推送模式、拉取模式、Push/Pull。
Push: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
Pull：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地
Push/Pull：与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地


优势：

扩展性：允许节点的任意增加和减少，新增节点的状态 最终会与其他节点一致。
容错：任意节点的宕机和重启都不会影响 Gossip 消息的传播，具有天然的分布式系统容错特性。
去中心化：无需中心节点，所有节点都是对等的，任意节点无需知道整个网络状况，只要网络连通，任意节点可把消息散播到全网。
一致性收敛：消息会以“一传十的指数级速度”在网络中传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。
简单
同样也存在以下缺点：

消息延迟：节点随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网；不可避免的造成消息延迟。
消息冗余：节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤；不可避免的引起同一节点消息多次接收，增加消息处理压力。

Gossip协议由于以上的优缺点，所以适合于AP场景的数据一致性处理，常见应用有：P2P网络通信、Apache Cassandra、Redis Cluster、Consul。




Raft算法（易于理解的一致性算法）
https://blog.csdn.net/daaikuaichuan/article/details/98627822
Raft 是一种为了管理复制日志的一致性算法。
一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。
这里的一致性针对分布式系统


一致性算法是从复制状态机的背景下提出的，复制状态机通常都是基于复制日志实现的，这个日志可以理解为一个比喻，相当于一个指令。

多个节点上，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态。

典型应用就是一个独立的的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

Raft 相较于 Paxos 确实更易于理解。为了提升可理解性，Raft 将一致性算法分解成了几个关键模块，例如领导人选举、日志复制和安全性。

和一致性最相关的就是前面 2 个模块：领导人选举和日志复制。

领导人选举
Raft 通过选举一个高贵的领导人，然后给予他全部的管理复制日志的责任来实现一致性。

而每个 server 都可能会在 3 个身份之间切换：领导者，候选者，跟随者

而影响他们身份变化的则是 选举。当所有服务器初始化的时候，都是 跟随者，这个时候需要一个 领导者，所有人都变成 候选者，直到有人成功当选 。

领导者周期性地向所有跟随者发送心跳包来维持自己的权威

如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。

要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后请求其他服务器为自己投票。那么会产生 3 种结果：
a. 自己成功当选b. 其他的服务器成为领导者c. 僵住，没有任何一个人成为领导者

每一个 server 最多在一个任期内投出一张选票（有任期号约束），先到先得。
要求最多只能有一个人赢得选票。
一旦成功，立即成为领导人，然后广播所有服务器停止投票阻止新的领导产生。

僵住怎么办？ Raft 通过使用随机选举超时时间（例如 150 - 300 毫秒）的方法将服务器打散投票。每个候选人在僵住的时候会随机从一个时间开始重新选举。


日志复制
一旦一个领导人被选举出来，他就开始为客户端提供服务。
客户端发送日志给领导者，随后领导者将日志复制到其他的服务器。如果跟随者故障，领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。

4 个步骤：
客户端提交
复制数据到所有跟随者
跟随者回复 确认收到
领导者回复客户端和所有跟随者 确认提交。

可以看到，直到第四步骤，整个事务才会达成。中间任何一个步骤发生故障，都不会影响日志一致性。

领导选举基于一个随机的时间来保证不会冲突（如果冲突的话）。而日志复制则类似于 2PC。

通常 5 个节点，只要不超过 2 个节点死亡都不会影响系统的运行。保证了系统的可用性，通过领导者的日志复制，实现了系统的一致性。


安全性
拥有最新的已提交的log entry的Follower才有资格成为leader。
Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

Raft解决方法是每次成员变更只允许增加或删除一个成员（如果要变更多个成员，连续变更多次）。


主要是分为leader选举、日志复制、日志压缩、成员变更等。


Raft发起选举的情况有如下几种：
刚启动时，所有节点都是follower，这个时候发起选举，选出一个leader；
当leader挂掉后，时钟最先跑完的follower发起重新选举操作，选出一个新的leader。
成员变更的时候会发起选举操作。

Raft中选举中给候选人投票的前提
Raft确保新当选的Leader包含所有已提交（集群中大多数成员中已提交）的日志条目。这个保证是在RequestVoteRPC阶段做的，candidate在发送RequestVoteRPC时，会带上自己的last log entry的term_id和index，follower在接收到RequestVoteRPC消息时，如果发现自己的日志比RPC中的更新，就拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。


Raft网络分区下的数据一致性怎么解决
发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follwer了，那么Leader只能正常更新它能访问的那些Follower，而大多数的Follower因为没有了Leader，他们重新选出一个Leader，然后这个 Leader来接受客户端的请求，如果客户端要求其添加新的日志，这个新的Leader会通知大多数Follower。如果这时网络故障修复 了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算commit，都回滚，接受新的Leader的新的更新（递减查询匹配日志）。

Raft的日志有什么特点？日志由有序编号（log index）的日志条目组成，每个日志条目包含它被创建时的任期号（term）和用于状态机执行的命令。


Raft和Paxos的区别和优缺点？
Raft的leader有限制，拥有最新日志的节点才能成为leader，multi-paxos中对成为Leader的限制比较低，任何节点都可以成为leader。
Raft中Leader在每一个任期都有Term号。


Prevote（预投票）是一个类似于两阶段提交的协议，第一阶段先征求其他节点是否同意选举，如果同意选举则发起真正的选举操作，否则降为Follower角色。这样就避免了网络分区节点重新加入集群，触发不必要的选举操作。

Raft日志压缩是怎么实现的？增加或删除节点呢？？
在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃（以前的数据已经落盘了）。
snapshot里面主要记录的是日志元数据，即最后一条已提交的 log entry的 log index和term。

raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。

https://blog.csdn.net/huaishu/article/details/86998872?spm=1001.2101.3001.6650.7&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-7-86998872-blog-115201470.pc_relevant_aa_2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-7-86998872-blog-115201470.pc_relevant_aa_2&utm_relevant_index=12





Raft 和 Zab 的区别
Raft定义了term来表示选举轮次
ZooKeeper定义了electionEpoch来表示

Raft：term大的优先，然后entry的index大的优先
ZooKeeper：peerEpoch大的优先，然后zxid大的优先

ZooKeeper有2个轮次，一个是选举轮次electionEpoch，另一个是日志的轮次peerEpoch（即表示这个日志是哪个轮次产生的）。而Raft则是只有一个轮次，相当于日志轮次和选举轮次共用了。

ZooKeeper是不会出现这种情况的，因为ZooKeeper在每次leader选举完成之后，都会进行数据之间的同步纠正，所以每一个轮次，大家都日志内容都是统一的

而Raft在leader选举完成之后没有这个同步过程，而是靠之后的AppendEntries RPC请求的一致性检查来实现纠正过程，则就会出现上述案例中隔了几个轮次还不统一的现象

ZooKeeper中的每个server，在某个electionEpoch轮次内，可以投多次票，只要遇到更大的票就更新，然后分发新的投票给所有人。这种情况下不存在split vote现象，同时有利于选出含有更新更多的日志的server，但是选举时间理论上相对Raft要花费的多。


Raft：比较简单，该server启动后，会收到leader的AppendEntries RPC,这时就会从RPC中获取leader信息，识别到leader，即使该leader是一个老的leader，之后新leader仍然会发送AppendEntries RPC,这时就会接收到新的leader了（因为新leader的term比老leader的term大，所以会更新leader）

ZooKeeper：该server启动后，会向所有的server发送投票通知，这时候就会收到处于LOOKING、FOLLOWING状态的server的投票（这种状态下的投票指向的leader），则该server放弃自己的投票，判断上述投票是否过半，过半则可以确认该投票的内容就是新的leader。

Raft：目前只是follower在检测。follower有一个选举时间，在该时间内如果未收到leader的心跳信息，则follower转变成candidate，自增term发起新一轮的投票，leader遇到新的term则自动转变成follower的状态
ZooKeeper：leader和follower都有各自的检测超时方式，leader是检测是否过半follower心跳回复了，follower检测leader是否发送心跳了。一旦leader检测失败，则leader进入LOOKING状态，其他follower过一段时间因收不到leader心跳也会进入LOOKING状态，从而出发新的leader选举。一旦follower检测失败了，则该follower进入LOOKING状态，此时leader和其他follower仍然保持良好，则该follower仍然是去学习上述leader的投票，而不是触发新一轮的leader选举


Raft：对于之前term的过半或未过半复制的日志采取的是保守的策略，全部判定为未提交，只有当当前term的日志过半了，才会顺便将之前term的日志进行提交
ZooKeeper：采取激进的策略，对于所有过半还是未过半的日志都判定为提交，都将其应用到状态机中
Raft的保守策略更多是因为Raft在leader选举完成之后，没有同步更新过程来保持和leader一致（在可以对外处理请求之前的这一同步过程）。而ZooKeeper是有该过程的

Raft的copycat实现为：每个follower开通一个复制数据的RPC接口，谁都可以连接并调用该接口，所以Raft需要来阻止上一轮次的leader的调用。每一轮次都会有对应的轮次号，用来进行区分，Raft的轮次号就是term，一旦旧leader对follower发送请求，follower会发现当前请求term小于自己的term，则直接忽略掉该请求，自然就解决了旧leader的干扰问题
ZooKeeper：一旦server进入leader选举状态则该follower会关闭与leader之间的连接，所以旧leader就无法发送复制数据的请求到新的follower了，也就无法造成干扰了


请求处理的一般流程
这个过程对比Raft和ZooKeeper基本上是一致的，大致过程都是过半复制

先来看下Raft：
client连接follower或者leader，如果连接的是follower则，follower会把client的请求(写请求，读请求则自身就可以直接处理)转发到leader
leader接收到client的请求，将该请求转换成entry，写入到自己的日志中，得到在日志中的index，会将该entry发送给所有的follower(实际上是批量的entries)
follower接收到leader的AppendEntries RPC请求之后，会将leader传过来的批量entries写入到文件中（通常并没有立即刷新到磁盘），然后向leader回复OK
leader收到过半的OK回复之后，就认为可以提交了，然后应用到leader自己的状态机中，leader更新commitIndex，应用完毕后回复客户端
在下一次leader发给follower的心跳中，会将leader的commitIndex传递给follower，follower发现commitIndex更新了则也将commitIndex之前的日志都进行提交和应用到状态机中


再来看看ZooKeeper：
client连接follower或者leader，如果连接的是follower则，follower会把client的请求(写请求，读请求则自身就可以直接处理)转发到leader
leader接收到client的请求，将该请求转换成一个议案，写入到自己的日志中，会将该议案发送给所有的follower(这里只是单个发送)
follower接收到leader的议案请求之后，会将该议案写入到文件中（通常并没有立即刷新到磁盘），然后向leader回复OK
leader收到过半的OK回复之后，就认为可以提交了，leader会向所有的follower发送一个提交上述议案的请求，同时leader自己也会提交该议案，应用到自己的状态机中，完毕后回复客户端
follower在接收到leader传过来的提交议案请求之后，对该议案进行提交，应用到状态机中


Raft对请求先转换成entry，复制时，也是按照leader中log的顺序复制给follower的，对entry的提交是按index进行顺序提交的，是可以保证顺序的
ZooKeeper在提交议案的时候也是按顺序写入各个follower对应在leader中的队列，然后follower必然是按照顺序来接收到议案的，对于议案的过半提交也都是一个个来进行的


Raft：重启之后，由于leader的AppendEntries RPC调用，识别到leader，leader仍然会按照leader的log进行顺序复制，也不用关心在复制期间新的添加的日志，在下一次同步中自动会同步
ZooKeeper：重启之后，需要和当前leader数据之间进行差异的确定，同时期间又有新的请求到来，所以需要暂时获取leader数据的读锁，禁止此期间的数据更改，先将差异的数据先放入队列，差异确定完毕之后，还需要将leader中已提交的议案和未提交的议案也全部放入队列，即ZooKeeper的如下2个集合数据

一旦leader发给follower的数据出现超时等异常
Raft：会不断重试，并且接口是幂等的
ZooKeeper：follower会断开与leader之间的连接，重新加入该集群，加入逻辑前面已经说了


分区的应对
目前ZooKeeper和Raft都是过半即可，所以对于分区是容忍的。如5台机器，分区发生后分成2部分，一部分3台，另一部分2台，这2部分之间无法相互通信
其中，含有3台的那部分，仍然可以凑成一个过半，仍然可以对外提供服务，但是它不允许有server再挂了，一旦再挂一台则就全部不可用了。
含有2台的那部分，则无法提供服务，即只要连接的是这2台机器，都无法执行相关请求。

所以ZooKeeper和Raft在一旦分区发生的情况下是是牺牲了高可用来保证一致性，即CAP理论中的CP。但是在没有分区发生的情况下既能保证高可用又能保证一致性，所以更想说的是所谓的CAP二者取其一，并不是说该系统一直保持CA或者CP或者AP，而是一个会变化的过程。在没有分区出现的情况下，既可以保证C又可以保证A，在分区出现的情况下，那就需要从C和A中选择一样。ZooKeeper和Raft则都是选择了C。


ZAB协议，全称 Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。它是专门为分布式协调服务——Zookeeper，设计的一种支持崩溃恢复和原子广播的协议。

发现：要求zookeeper集群必须选举出一个 Leader 进程，同时 Leader 会维护一个 Follower 可用客户端列表。将来客户端可以和这些 Follower节点进行通信。
同步：Leader 要负责将本身的数据与 Follower 完成同步，做到多副本存储。这样也是提现了CAP中的高可用和分区容错。Follower将队列中未处理完的请求消费完成后，写入本地事务日志中
广播：Leader 可以接受客户端新的事务Proposal请求，将新的Proposal请求广播给所有的 Follower。


所有的事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被叫做 Leader服务器。其他剩余的服务器则是 Follower服务器。
Leader服务器 负责将一个客户端事务请求，转换成一个 事务Proposal，并将该 Proposal 分发给集群中所有的 Follower 服务器，也就是向所有 Follower 节点发送数据广播请求（或数据复制）
分发之后Leader服务器需要等待所有Follower服务器的反馈（Ack请求），在Zab协议中，只要超过半数的Follower服务器进行了正确的反馈后（也就是收到半数以上的Follower的Ack请求），那么 Leader 就会再次向所有的 Follower服务器发送 Commit 消息，要求其将上一个 事务proposal 进行提交。


Zab 协议包括两种基本的模式：崩溃恢复 和 消息广播
崩溃恢复
一旦 Leader 服务器出现崩溃或者由于网络原因导致 Leader 服务器失去了与过半 Follower 的联系，那么就会进入崩溃恢复模式。
前面我们说过，崩溃恢复具有两个阶段：Leader 选举与初始化同步。当完成 Leader 选 举后，此时的 Leader 还是一个准 Leader，其要经过初始化同步后才能变为真正的 Leader。

初始化同步
具体过程如下：
为了保证 Leader 向 Learner 发送提案的有序，Leader 会为每一个 Learner 服务器准备一 个队列；
Leader 将那些没有被各个 Learner 同步的事务封装为 Proposal；
Leader 将这些 Proposal 逐条发给各个 Learner，并在每一个 Proposal 后都紧跟一个 COMMIT 消息，表示该事务已经被提交，Learner 可以直接接收并执行
Learner 接收来自于 Leader 的 Proposal，并将其更新到本地；
当 Learner 更新成功后，会向准 Leader 发送 ACK 信息；
Leader 服务器在收到来自 Learner 的 ACK 后就会将该 Learner 加入到真正可用的 Follower 列表或 Observer 列表。没有反馈 ACK，或反馈了但 Leader 没有收到的 Learner，Leader 不会将其加入到相应列表。


恢复模式的两个原则
当集群正在启动过程中，或 Leader 与超过半数的主机断连后，集群就进入了恢复模式。 对于要恢复的数据状态需要遵循两个原则。

1. 已被处理过的消息不能丢
当 Leader 收到超过半数 Follower 的 ACKs 后，就向各个 Follower 广播 COMMIT 消息， 批准各个 Server 执行该写操作事务。当各个 Server 在接收到 Leader 的 COMMIT 消息后就会在本地执行该写操作，然后会向客户端响应写操作成功。

但是如果在非全部 Follower 收到 COMMIT 消息之前 Leader 就挂了，这将导致一种后 果：部分 Server 已经执行了该事务，而部分 Server 尚未收到 COMMIT 消息，所以其并没有 执行该事务。当新的 Leader 被选举出，集群经过恢复模式后需要保证所有 Server 上都执行 了那些已经被部分 Server 执行过的事务。

被丢弃的消息不能再现
当在 Leader 新事务已经通过，其已经将该事务更新到了本地，但所有 Follower 还都没 有收到 COMMIT 之前，Leader 宕机了（比前面叙述的宕机更早），此时，所有 Follower 根本 就不知道该 Proposal 的存在。当新的 Leader 选举出来，整个集群进入正常服务状态后，之 前挂了的 Leader 主机重新启动并注册成为了 Follower。若那个别人根本不知道的 Proposal 还保留在那个主机，那么其数据就会比其它主机多出了内容，导致整个系统状态的不一致。 所以，该 Proposa 应该被丢弃。类似这样应该被丢弃的事务，是不能再次出现在集群中的， 应该被清除。


消息广播
当集群中的 Learner 完成了初始化状态同步，那么整个 zk 集群就进入到了正常工作模式 了。

如果集群中的 Learner 节点收到客户端的事务请求，那么这些 Learner 会将请求转发给 Leader 服务器。然后再执行如下的具体过程：
Leader 接收到事务请求后，为事务赋予一个全局唯一的 64 位自增 id，即 zxid，通过 zxid 的大小比较即可实现事务的有序性管理，然后将事务封装为一个 Proposal。
Leader 根据 Follower 列表获取到所有 Follower，然后再将 Proposal 通过这些 Follower 的 队列将提案发送给各个 Follower。
当 Follower 接收到提案后，会先将提案的 zxid 与本地记录的事务日志中的最大的 zxid 进行比较。若当前提案的 zxid 大于最大 zxid，则将当前提案记录到本地事务日志中，并 向 Leader 返回一个 ACK。
当 Leader 接收到过半的 ACKs 后，Leader 就会向所有 Follower 的队列发送 COMMIT 消息，向所有 Observer 的队列发送 Proposal。
当 Follower 收到 COMMIT 消息后，就会将日志中的事务正式更新到本地。当 Observer 收到 Proposal 后，会直接将事务更新到本地。
无论是 Follower 还是 Observer，在同步完成后都需要向 Leader 发送成功 ACK。