数据层一致性算法

背景

传统的主从同步无法同时保证数据的一致性和可用性，分布式系统中著名的CAP理论从理论上证明了这个问题。CAP理论告诉我们C、A、P三者不能同时满足，最多只能满足其中两个。

一般来说使用网络通信的分布式系统，无法舍弃P性质，那么就只能在一致性和可用性上做一个艰难的选择。既然在分布式系统中一致性和可用性只能选一个。

那么一致性算法，就是在保证一定可用性的前提下，同时保证数据的一致性；

那Paxos、Raft、Zab、gossip 等算法的作用就是在保证一定可用性的同时，对外提供强一致性或者最终一致性；

一致性算法的分类

强一致性
- 说明：保证系统改变提交以后立即改变集群的状态。
- 模型：
- - Paxos
  - Raft（muti-paxos）
  - ZAB（muti-paxos）
弱一致性
- 说明：也叫最终一致性，系统不保证改变提交以后立即改变集群的状态，但是随着时间的推移最终状态是一致的。
- 模型：
- - DNS系统
  - Gossip协议

Paxos 算法

Paxos 算法介绍

Paxos算法是莱斯利·兰伯特于1989年提出的一种基于消息传递模型的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

在一个分布式系统中，数据往往以多副本的形式存储在不同节点上，如分布式数据库系统，用户对系统的更新请求会同时发送给各个节点。但实际上系统是不可靠的，如节点可能会宕机、消息处理可能会慢、程序可能出故障，网络可能会延迟、中断等。如何在上述系统中保证在任何异常情况下，都不会破坏各个节点的数据一致性，正是Paxos要解决的问题。

Paxos算法原理

Proposer 获取一个Proposal ID n，为了保证Proposal ID唯一，可采用时间戳+Server ID生成；
Proposer 向所有Acceptors广播Prepare(n)请求；
Acceptor 比较n和minProposal，如果n>minProposal，minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回；
Proposer 接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value；
到这里可以进入第二阶段，广播Accept (n,value) 到所有节点；
Acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal。
提议者接收到过半数请求后，如果发现有返回值result >n，表示有更新的提议，跳转到1；否则value达成一致。

第一阶段是为了获取集群中存储的最新的那条数据，第二阶段是为了将这条最新的数据同步到所有节点。

在集群数据达成一致后，Proposer再次广播与上次相同的Prepare(n)请求时，由于n已经和Acceptor中保存的minProposal相等，Acceptor将不会返回acceptedProposal 和 acceptedValue，此时若用户希望执行更新操作，Proposer即可将用户需要更新的值设为本次提案的value，从而在第二阶段将value同步给所有节点。

当集群中存在多个Proposer，且提出了不同提案value时，因为消息到达顺序的不可控，有可能a节点先收到了Proposer1的提案value1，b节点先收到了Proposer2的提案value2，假设Proposer1的Proposer ID大于Proposer2的Proposer ID，则当a节点收到Proposer2的提案时，由于minProposal>n，将直接返回minProposal。此时Proposer2收到a节点的返回发现result >n，将重新进入阶段一，进行集群同步。

Paxos的应用比较广泛，例如ZooKeeper的选举算法，当然这种算法也比较复杂，实现困难。如果多个Proposer轮流进行选举申请，就会出现活锁的情况，导致选举不出Leader，另外，也是因为比较复杂，选举的效率很低，几万个服务的Zookeeper集群，选举Leader可能需要几个小时。

Multi-Paxos算法

原始的Paxos算法（Basic Paxos）只能对一个值形成决议，决议的形成至少需要两次网络来回，在高并发情况下可能需要更多的网络来回，极端情况下甚至可能形成活锁。如果想连续确定多个值，Basic Paxos搞不定了。因此Basic Paxos几乎只是用来做理论研究，并不直接应用在实际工程中。

实际应用中几乎都需要连续确定多个值，而且希望能有更高的效率。Multi-Paxos正是为解决此问题而提出。Multi-Paxos基于Basic Paxos做了两点改进：

针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。
在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。

Multi-Paxos流程

Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。

Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的Zab也是Multi-Paxos的变形。

Raft算法

raft是paxos算法的一种改进，一种简化，一种优化，一种具象化。Raft容易实现在于它的描述是非常规范的，包括了所有的实现细节。如上面的人说的有如伪代码。

paxos的描述侧重于理论，工程实现按照谷歌chubby论文中的说话，大家从paxos出现，写着写着，处理了n多实际中的细节之后，已经变成另外一个算法了，这时候正确性已经无法得到理论的保证。

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

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）：

Leader：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
Candidate：Leader选举过程中的临时角色。

Raft算法角色状态转换

Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息，它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。

Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

一、Leader选举

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

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

赢得了多数的选票，成功选举为Leader；
收到了Leader的消息，表示有其它服务器已经抢先当选了Leader；
没有服务器赢得多数的选票，Leader选举失败，等待选举时间超时后发起下一次选举。

Leader选举过程

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

Raft保证选举出的Leader上一定具有最新的已提交的日志，这一点将在三、安全性中说明。

二、日志同步

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

Raft日志同步过程

某些Followers可能没有成功的复制日志，Leader会无限的重试 AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上，就被认为可以提交（commit）了。

Raft日志同步保证如下两点：

如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志，它就会拒绝新的日志条目。

一般情况下，Leader和Followers的日志保持一致，因此 AppendEntries 一致性检查通常不会失败。然而，Leader崩溃可能会导致日志不一致：旧的Leader可能没有完全复制完日志中的所有条目。

Leader和Followers上日志不一致

上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目，也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。

Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。

Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。

三、安全性

Raft增加了如下两条限制以保证安全性：

拥有最新的已提交的log entry的Follower才有资格成为Leader。

这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。

Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况：

在阶段a，term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步写入了S2；

在阶段b，S1离线，触发一次新的选主，此时S5被选为新的Leader，此时系统term为3，且写入了日志（term, index）为（3， 2）;

S5尚未将日志推送到Followers就离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被提交了。；

在阶段d，S1又下线了，触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. term = 5 > 4，2. 最新的日志为（3，2），比大多数节点（如S2/S3/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。

增加上述限制后，即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前term（2）的日志，直到S1在当前term（4）产生的日志（4， 4）被大多数Followers确认，S1方可提交日志（4，4）这条日志，当然，根据Raft定义，（4，4）之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，4）。

四、日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot中包含以下内容：

日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
系统当前状态。

当Leader要发给某个日志落后太多的Follower的log entry被丢弃，Leader会将snapshot发给Follower。或者当新加进一台机器时，也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC（RPC细节参见七、Raft算法总结）。

做snapshot既不要做的太频繁，否则消耗磁盘带宽，也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。

做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。

五、成员变更

成员变更是在集群运行过程中副本发生变化，如增加/减少副本数、节点替换等。

成员变更也是一个分布式一致性问题，既所有服务器对新成员达成一致。但是成员变更又有其特殊性，因为在成员变更的一致性达成的过程中，参与投票的进程会发生变化。

如果将成员变更当成一般的一致性问题，直接向Leader发送成员变更请求，Leader复制成员变更日志，达成多数派之后提交，各服务器提交成员变更日志后从旧成员配置（Cold）切换到新成员配置（Cnew）。

因为各个服务器提交成员变更日志的时刻可能不同，造成各个服务器从旧成员配置（Cold）切换到新成员配置（Cnew）的时刻不同。

成员变更不能影响服务的可用性，但是成员变更过程的某一时刻，可能出现在Cold和Cnew中同时存在两个不相交的多数派，进而可能选出两个Leader，形成不同的决议，破坏安全性。

成员变更的某一时刻Cold和Cnew中同时存在两个不相交的多数派

由于成员变更的这一特殊性，成员变更不能当成一般的一致性问题去解决。

为了解决这一问题，Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。

Raft两阶段成员变更过程如下：

Leader收到成员变更请求从Cold切成Cold,new；
Leader在本地生成一个新的log entry，其内容是Cold∪Cnew，代表当前时刻新旧成员配置共存，写入本地日志，同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认；
Follower收到Cold∪Cnew的log entry后更新本地日志，并且此时就以该配置作为自己的成员配置；
如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志，Leader就提交这条log entry并切换到Cnew；
接下来Leader生成一条新的log entry，其内容是新成员配置Cnew，同样将该log entry写入本地日志，同时复制到Follower上；
Follower收到新成员配置Cnew后，将其写入日志，并且从此刻起，就以该配置作为自己的成员配置，并且如果发现自己不在Cnew这个成员配置中会自动退出；
Leader收到Cnew的多数派确认后，表示成员变更成功，后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。

六、Raft与Multi-Paxos的异同

Raft与paxos都是基于领导者的一致性算法，乍一看有很多地方相同，下面总结一下Raft与Multi-Paxos的异同。

Raft与multi-paxos中相似的概念：

Raft与multi-paxos的不同：

但是 Raft 协议做了一个约束，数据库的多个投票多条日志一定要按照顺序执行，只有前一个日志被确认了才能再确认后一个日志。导致了两个问题:

第一个问题是并发能力变差了。以前支持并发的提交，现在只能支持一个结束以后再进入下一个，所以它的性能变差了。
第二个是可用性的问题。如果采用 Paxos 协议，当一台机器新上线的时候很快就能提供服务，因为不需要等前面的数据确认就能提供服务，但是如果使用的是 Raft 协议，需要等前面的所有日志确认以后才能提供服务，所以说 Raft 协议存在可用性的风险。

ZAB算法

ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。ZAB也是对Multi Paxos算法的改进，大部分和raft相同

ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持崩溃恢复和原子广播协议，基于该协议，Zookeeper 实现了一种主备模式的系统架构来保持集群中各个副本之间数据一致性。

和raft算法的主要区别：

对于Leader的任期，raft叫做term，而ZAB叫做epoch
在状态复制的过程中，raft的心跳从Leader向Follower发送，而ZAB则相反。

名词解释

ZXID

ZXID 是 Zookeeper 集群中事务的唯一标识，保证全局有序。
ZXID 是一个 64 位整数, 高32位为周期号(epoch), 每个 Leader 被选举后都会增加 epoch 与上任 Leader 区分。低32位是 Leader 开始事务时分配的递增编号。
ZXID 中的 epoch 可以保证 Leader 崩溃重新选举后被丢弃的事务不会继续执行。

mid
每个ZooKeeper服务器，都需要在数据文件夹下创建一个名为myid的文件，该文件包含整个ZooKeeper集群唯一的ID（整数）。

例如，某ZooKeeper集群包含三台服务器，hostname分别为zoo1、zoo2和zoo3，其myid分别为1、2和3，则在配置文件中其ID与hostname必须一一对应，如下所示。在该配置文件中，server.后面的数据即为myid

zxid最大表示服务器的日志是最全的，zxid相同情况下，myid最大

zk服务器状态

Leading: 当前节点为集群 Leader，负责协调事务
Following: 当前节点为 Follower ，Follower与Leader处于数据同步阶段
Looking: 系统刚启动时或者Leader崩溃，集群没有正在运行的 Leader, 正处于选举过程
Observing: 节点跟随 Leader 保存系统最新的状态提供读服务，但不参与选举和事务投票

ZAB的角色

Leader：一个ZooKeeper集群同一时间只会有一个实际工作的Leader，它会发起并维护与各Follwer及Observer间的心跳。所有的写操作必须要通过Leader完成再由Leader将写操作广播给其它服务器。
Follower：一个ZooKeeper集群可能同时存在多个Follower，它会响应Leader的心跳。Follower可直接处理并返回客户端的读请求，同时会将写请求转发给Leader处理，并且负责在Leader处理写请求时对请求进行投票。
Observer：角色与Follower类似，但是无投票权

ZAB协议共分成了三个阶段

发现：指的就是实际的选举流程，此流程会在集群机器中选举出Leader、Follower和Observer，且Leader会维护一份可用的集群客户端通信对；
同步：在集群中选举出Leader后，Leader将本身的数据同步给集群内的其它机器，实现集群多副本，保证可用性；
广播：在集群完成选举和数据同步后，集群就可以正式对客户端提供功能了，此时客户端对集群的写请求都会经过Leader，Leader再对集群广播Proposal事务请求，完成集群对客户端的请求同步（实际上还有ack和commit等流程，但不是本篇重点，所以忽略）。

ZAB协议也可以分为两个模式：

恢复模式：ZAB协议的发现和同步阶段，在代码中可以称为LOOKING状态；
广播模式：ZAB协议的广播阶段，在代码中表现为LEADING、FOLLOWING或OBSERVING状态。

选票数据结构

logicClock 每个服务器会维护一个自增的整数，名为logicClock，它表示这是该服务器发起的第多少轮投票
state 当前服务器的状态
self_id 当前服务器的myid
self_zxid 当前服务器上所保存的数据的最大zxid
vote_id 被推举的服务器的myid
vote_zxid 被推举的服务器上所保存的数据的最大zxid

Leader选举

1.自增选举轮次

ZooKeeper规定所有有效的投票都必须在同一轮次中。每个服务器在开始新一轮投票时，会先对自己维护的logicClock进行自增操作。

2.初始化选票

每个服务器在广播自己的选票前，会将自己的投票箱清空。该投票箱记录了所收到的选票。

例：服务器2投票给服务器3，服务器3投票给服务器1，则服务器1的投票箱为(2, 3), (3, 1), (1, 1)。票箱中只会记录每一投票者的最后一票，如投票者更新自己的选票，则其它服务器收到该新选票后会在自己票箱中更新该服务器的选票。

3.发送初始化选票

每个服务器最开始都是通过广播把票投给自己。

4.接收外部投票

服务器会尝试从其它服务器获取投票，并记入自己的投票箱内。如果无法获取任何外部投票，则会确认自己是否与集群中其它服务器保持着有效连接。如果是，则再次发送自己的投票；如果否，则马上与之建立连接。

5.判断选举轮次

收到外部投票后，首先会根据投票信息中所包含的logicClock来进行不同处理：

如果外部投票的logicClock大于自己的logicClock。说明该服务器的选举轮次落后于其它服务器的选举轮次，立即清空自己的投票箱并将自己的logicClock更新为收到的logicClock，然后再对比自己之前的投票与收到的投票以确定是否需要变更自己的投票，最终再次将自己的投票广播出去。

如果外部投票的logicClock小于自己的logicClock。当前服务器直接忽略该投票，继续处理下一个投票。

如果外部投票的logickClock与自己的相等。当时进行选票PK。

6.选票PK

选票PK是基于(self_id, self_zxid)与(vote_id, vote_zxid)的对比：

对比内部票和外部投票的vote_zxid，若外部投票的vote_zxid比较大，则将自己的票中的vote_zxid与vote_myid更新为收到的票中的vote_zxid与vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱。如果票箱内已存在(self_myid,self_zxid)相同的选票，则直接覆盖

若二者vote_zxid一致，则比较二者的vote_myid，若外部投票的vote_myid比较大，则将自己的票中的vote_myid更新为收到的票中的vote_myid并广播出去，另外将收到的票及自己更新后的票放入自己的票箱

7.统计选票

如果已经确定有过半服务器认可了自己的投票（可能是更新后的投票），则终止投票。否则继续接收其它服务器的投票。

8.更新服务器状态

投票终止后，服务器开始更新自身状态。若过半的票投给了自己，则将自己的服务器状态更新为LEADING，否则将自己的状态更新为FOLLOWING。

广播模式

当集群正常运行过程中，Leader 使用广播模式保证各 Follower 节点的一致性

Zookeeper 集群中每个节点都会存储系统数据的完整副本，可以独立处理读请求。

当 Follower 收到写请求时会将其转发给 Leader, 或者 Leader直接收到写请求；

Leader 为每个写请求分配唯一的全局有序的事务ID(Zookeeper Transaction Id, ZXID)，并转化为事务 Proposal 提案发送到队列中（Leader为每个 Follower 服务器分配一个单独的队列），然后将需要广播的 Proposal 依次放到队列中取，并且根据 FIFO 策略进行消息发送。

Follower 从队列中收到Proposal提案后写事务日志（本地磁盘）但不提交，成功后返回 ACK 告知 Leader 可以进行提交。

Leader 收到过半 Follower 的 ACK 响应后（包括Leader自己，Leader对自己默认有一个ACK）发出 commit 请求执行提交

Follower收到commit命令后，按队列的顺序（zxid）进行提交，只有上一个事物提交完成之后才能进行下个事物的提交

Leader 收到过半 Follower 对 commit 请求的 ACK 响应后便认为事务已完成。

剩余的 Follower 则会放弃执行此次事务，进入数据同步阶段，与集群达成一致。Leader接收Follower发送过来的FOllOWERINFO（含有当前节点的Last的ZXID）然后往Follower发送NEWLEADER；

同步策略

Leader根据Follower发送过来的LastZXID根据数据更新策略向Follower发送更新指令。

SNAP ：如果Follower数据太老，Leader将发送快照SNAP指令给Follower同步数据；
DIFF ：Leader发送从Follower.lastZXID到Leader.lastZXID议案的DIFF指令给Follower同步数据；
TRUNC ：当Follower.lastZXID比Leader.lastZXID大时，Leader发送从Leader.lastZXID到Follower.lastZXID的TRUNC指令让Follower丢弃该段数据；

恢复模式

集群启动或 Leader 崩溃时系统进入恢复模式，选举 Leader 并将集群中各节点的数据同步到最新状态

Leader崩溃选举

初始状态下每个服务器互相广播（logicClock,mid,zxid)，初始化自身选票池（服务器A, 服务器A所选票的服务器B）

接收到其他服务器投票信息进行选票PK更新选票池。

server1接收到（1,2,0)、（1,3,0) 选票PK后选票池由（1，1）更新为（1，3）更新的票，（3，3）收到的票

server2接收到（1,1,0)、（1,3,0) 选票PK后选票池由（2，2）更新为（2，3），（3，3）

server3接收到（1,1,0)、（1,2,0) 选票PK后选票池（3，3）不变更

根据上述选票，三个服务器一致认为此时server3应该是Leader。因此server1和server2都进入FOLLOWING状态，而server3进入LEADING状态。之后Leader发起并维护与Follower间的心跳。

follower恢复选举

Follower重启，或者发生网络分区后找不到Leader，会进入LOOKING状态并发起新的一轮投票。

识别leader

服务器3收到服务器1的投票后，将自己的状态LEADING以及选票返回给服务器1。

服务器2收到服务器1的投票后，将自己的状态FOLLOWING及选票返回给服务器1。

此时服务器1知道服务器3是Leader，并且通过服务器2与服务器3的选票可以确定服务器3确实得到了超过半数的选票。因此服务器1进入FOLLOWING状态。

Leader重启选举

Leader（服务器3）宕机后，Follower（服务器1和2）发现Leader不工作了，因此进入LOOKING状态并发起新的一轮投票，并且都将票投给自己。

广播更新选票，服务器1和2根据外部投票确定是否要更新自身的选票。这里有两种情况：

服务器1和2的zxid相同。例如在服务器3宕机前服务器1与2完全与之同步。此时选票的更新主要取决于myid的大小

服务器1和2的zxid不同。在旧Leader宕机之前，其所主导的写操作，只需过半服务器确认即可，而不需所有服务器确认。换句话说，服务器1和2可能一个与旧Leader同步（即zxid与之相同）另一个不同步（即zxid比之小）。此时选票的更新主要取决于谁的zxid较大

如图所示：
服务器1的zxid为9，而服务器2的zxid为8，因此服务器2将自身选票更新为（2, 1, 9），经过上一步选票更新后，服务器1与服务器2均将选票投给服务器1，因此服务器2成为Follower，而服务器1成为新的Leader并维护与服务器2的心跳。

旧的Leader恢复后，进入LOOKING状态并发起新一轮领导选举，并将选票投给自己。

此时服务器1会将自己的LEADING状态及选票（3, 3, 9）返回给服务器3，而服务器2将自己的FOLLOWING状态及选票（3, 1, 11）返回给服务器3。

服务器3了解到Leader为服务器1，且根据选票了解到服务器1确实得到过半服务器的选票，因此自己进入FOLLOWING状态。

leader commit后宕机，follower部分commit

c1、c2 表示对提案P1、P2 对应的commit

假设A提交了C1、C2，P3未commit后宕机

FastLeaderElection算法选出B作为新的Leader，C、D、E、F、G 会主动将自己最大的zxid发送给B

B会将Follower的zxid与自身zxid间的所有被Commit过的消息同步给Follower，P3由于未被A Commit，同时幸存的所有服务器中P3未存在于大多数据服务器中，因此它不会被同步到其它Follower，已存在P3的需发送trunc通知follower丢弃该数据

同步完数据后，B会向Followers发送NEWLEADER命令并等待大多数服务器的ACK（包含自身，无需等待全部ack），然后向所有服务器广播UPTODATE命令。收到该命令后的服务器即可对外提供服务。

Gossip算法(协议)

gossip 是什么

gossip 协议（gossip protocol）又称 epidemic 协议（epidemic protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议，在分布式系统中被广泛使用，比如我们可以使用 gossip 协议来确保网络中所有节点的数据一样。

从 gossip 单词就可以看到，其中文意思是八卦、流言等意思，我们可以想象下绯闻的传播（或者流行病的传播）；gossip 协议的工作原理就类似于这个。gossip 协议利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。Gossip 其实是一种去中心化思路的分布式协议，解决状态在集群中的传播和状态一致性的保证两个问题。

Gossip协议说明

Gossip算法每个节点都是对等的，即没有角色之分。Gossip算法中的每个节点都会将数据改动告诉其他节点（类似传八卦）。有话说得好：”最多通过六个人你就能认识全世界任何一个陌生人”，因此数据改动的消息很快就会传遍整个集群。

步骤：

集群启动，如下图所示（这里设置集群有20个节点）

某节点收到数据改动，并将改动传播给其他4个节点，传播路径表示为较粗的4条线

收到数据改动的节点重复上面的过程直到所有的节点都被感染

Gossip 的特点（优势）

1）扩展性

网络可以允许节点的任意增加和减少，新增加的节点的状态最终会与其他节点一致。

2）容错

网络中任何节点的宕机和重启都不会影响 Gossip 消息的传播，Gossip 协议具有天然的分布式系统容错特性。

3）去中心化

Gossip 协议不要求任何中心节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。

4）一致性收敛- 最终一致性

Gossip 协议中的消息会以一传十、十传百一样的指数级速度在网络中快速传播，因此系统状态的不一致可以在很快的时间内收敛到一致。消息传播速度达到了 logN。

主要有三种gossip：

Push: 节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据
HTTP/2 做的优化
Push/Pull：与 Pull 类似，只是多了一步，A 再将本地比 B 新的数据推送给 B，B 则更新本地

gossip消息的种类：

meet消息：用于通知新节点加入。消息发送者通知接收者加入到当前集群，meet消息通信正常完成后，接收节点会加入到集群中并进行周期性的ping、pong消息交换；

ping消息：集群内交换最频繁的消息，集群内每个节点每秒向多个其它节点发送ping消息，用于检测节点是否在线和交换彼此状态信息。ping消息发送封装了自身节点和部分其它节点的状态数据；

pong消息：当接收到ping、meet消息时，作为响应消息回复给发送方确认消息正常通信。pong消息内部封装了自身状态数据。节点也可以向集群内广播自身的pong消息来通知整个集群对自身状态进行更新；

fail消息：当节点判定集群内另一个节点下线时，会向集群内广播一个fail消息，其他节点接收到fail消息之后把对应节点更新为下线状态；

在 cluster-node-timeout 内，某个节点一直没有返回 pong，那么就被认为 pfail

如果一个节点认为某个节点 pfail 了，那么会在 gossip ping 消息中，ping 给其他节点，如果超过半数的节点都认为 pfail 了，那么就会变成 fail

分布式事务

在处理分布式数据层数据一致性问题的时候，通过数据层的一致性协议和算法可以解决大部分最终一致性和强一致性的问题，在应用层处理分布式的事物问题，可以使用应用层常用的2pc\3pc 来解决分布式事务数据一致性的问题

满足ACID（原子性、一致性、隔离性、持久性）的一组操作，可以被称为一个事务。随着计算机系统的发展，越来越多的采用分布式的架构来对外提供服务，但是，不同的机器的处理性能、存储性能、网络状态等各有不同，让分布式集群始终对外提供可用的一致性服务一直是需要处理的问题。
为了保证数据变更请求在整个分布式环境下正确地执行，不会导致部分服务器暂时崩溃导致整个集群提供的服务和数据不再相同，在整个分布式系统处理数据变更请求的过程中，需要引入分布式事务的概念。常见的提交方式有二阶段提交（Two-phase Commit，2PC）和三阶段提交（Three-phase commit，3PC）。

二阶段提交

二阶段提交的底层实现主要分成两个阶段：

请求阶段
提交阶段

请求阶段

协调者通知每个参与者准备提交；

参与者在本地执行事务：

执行成功后，并不提交，告知协调者自己本地已经执行成功；
执行失败后，告知协调者本地作业执行故障

提交阶段

协调者根据第一阶段收集到的参与者的返回信息，决定是否提交：

如果全部的参与者都反馈成功，那么协调者通知所有参与者提交事务
如果存在参与者反馈失败，则协调者通知所有参与者取消事务

收到全部参与者的成功commit信息后，完成本次提交

举例

还是使用经理和柜员的例子。银行有一个经理和三个柜员，客户举老爷子申请存钱1000元，需要最终三个柜员将举老爷子余额+1000记录下来。

需要注意这里经理向柜员发送proposal和提交是广播出去的。

故障分析

柜员侧出现故障或拒绝Proposal

假如一个柜员暂时离开了，或者柜员这边发现今天不能存入钱了，如下图所示：

第一阶段经理侧出现故障

假如经理突然寄了，那么时间可能正好在第一阶段或第二阶段。

第一阶段如果经理寄了，经理无法收到柜员的存钱处理完成的消息

则这个存钱事务一直没有被提交，举老爷子的钱也没有增加1000元。

第二阶段经理侧出现故障

如果在发送COMMIT的消息的过程中，发送了一部分之后，经理寄了

此时数据会产生不一致。若经理重启，首先看自己的日志到哪了，然后依次去询问柜员最新的commit信息。

二阶段提交存在的问题

参与者阻塞

若某个参与者一直没有完成，则需要等待他完成。例如某个柜员业务不熟悉操作很慢，那么客户和经理需要一直等待他完成操作，才能一起进入下一步
单点故障

若协调者寄了，那么参与者长期阻塞
存在数据不一致情况

若协调者在第二阶段挂了，那么会产生数据不一致的情况。

三阶段提交

三阶段提交在二阶段算法的基础上进行了优化和改进。如下图所示，在整个三阶段提交的过程中，相比二阶段提交，增加了预提交阶段。

canCommit阶段

协调者首先询问所有的参与者的状态，当前是否可以执行业务；如果可以\不可以执行，就直接返回可以/不可以。

preCommit阶段

协调者根据参与者canCommit阶段的响应来决定是否可以继续事务的preCommit操作。preCommit阶段和二阶段提交里面的请求阶段一致