概览

分布式协议是分布式系统的基石，它是一系列规则和约定，用于指导分布式系统中各个节点之间的通信和协调，确保系统能在面对故障、延迟，不可靠网络环境，甚至恶意行为时，仍然能保持整个系统的一致性、可靠性和可用性。

大体上分布式算法分为两类：

• 拜占庭容错算法

(Byzantine Fault Tolerance, BFT)，应对不仅存在故障行为，还存在恶意行为的分布式算法。常见于金融，区块链领域。常见算法如PBFT、PoW(Proof of Work)等。

• 非拜占庭容错算法

应对只存在故障行为，不存在恶意行为的分布式算法，也叫故障容错法(Crash Fault Tolerance, CFT)。常见算法如Paxos、Raft、ZAB等。

我们这篇文章主要涉及CFT，暂不讨论更复杂的BFT。

CAP理论

CAP理论是一个思考框架，它对分布式系统的特性做了高度抽象，可以帮助我们在设计分布式系统的模型时，根据业务特点对一致性、可用性和分区容错性进行权衡。

CAP理论涉及三个指标：

• C（Consistency）：一致性，所有节点同时看到相同的数据，即每次写入，都是要保证所有节点都写入成功。

• A（Availability）：可用性，任何时候，读写都是成功的，强调服务可用，但不能保证每个节点的数据都是最新的。

• P（Partition Tolerance）：分区容错性，当部分节点故障或者网络错误时，系统仍然可用。分区容错也是一个分布式系统区别于单机必然要满足的条件。

CAP 理论可以表述为，一个分布式系统最多只能同时满足一致性可用性和分区容错性这三项中的两项。如下图：

由于分布式系统必须要满足分区容错性，则根据CAP理论，一个分布式系统只能是CP型，或AP型。

• CP：放弃高可用，追求强一致，即无论何时，在所有节点上存储的数据都是一致的。如果出现网络分区，为了防止不一致，系统将拒绝写入。典型如Zookeeper、Etcd、HBase等。

• AP：放弃强一致，追求高可用。则为了保证高可用，在网络分区时，访问多个节点的数据可能不一致。典型如Cassandra、DynamoDB等。

需要注意的是，无论是CP或者是AP，都是在出现分区故障，即P不满足时，需要权衡的点。如果P是正常的，那么AC是都可以保证的（这也是系统在绝大多数时间的状态）。

BASE理论

BASE理论，即基本可用(Basically Available)、软状态(Soft state)、最终一致(Eventually consistent)，三个词的简称。是对CAP理论中A和C的权衡，指牺牲一部分的可用性，获得打折的一致性。该理论在十分强调高可用的互联网领域应用非常广泛。

• 基本可用(Basically Available)：指的是在分布式系统出现故障时，允许损失部分功能的可用性，保障核心基本功能的可用。比如：流量削峰、延迟响应、体验降级、过载保护。

• 软状态(Soft state)：指允许在数据到达最终一致前，存在中间状态。

• 最终一致(Eventually consistent)：即系统中的所有数据副本，在经过一段时间的同步后，都能到达一致的状态。

对于CP来说可以看作是最终一致的特例，即不存在延迟时间的最终一致。在分布式系统设计中，如果不允许存在延迟一致性的场景，比如分布式锁，就需要使用强一致的CP型；如果允许短暂的不一致，只要能最终一致，比如点赞数的统计，那么就可以采用BASE理论，设计一个高可用，但又能达到最终一致的系统。

实现最终一致的具体方法，常见有如下几种：

• 读时修复：在读取数据时，如果检测到多个节点的数据不一致，则进行数据修复。比如Cassandra的Read Repiar，在查询数据时，自动修复不一致的副本。

• 写时修复：在写入数据时，写入到某些节点失败，则进行数据修复。比如Cassandra的Hinted Handoff，在远程写数据时，如果失败就在本地保存数据，然后定时进行数据重传。这种方式由于不涉及多个节点的一致性对比，所以性能消耗较低。

• 异步修复：定时对多个节点进行对账。

Paxos算法

Paxos是最经典的分布式共识算法，后续衍生的一系列今天常用的共识算法如Raft、ZAB等，都是基于Paxos改进的。Paxos算法主要包括两部分：

• Basic-Paxos：描述多节点之间如何就某个值(提案Value)，达成共识。

• Multi-Paxos：描述执行多个Basic Paxos，就一系列的值达成共识。

Basic-Paxos

Basic-Paxos中一个分布式集群里存在三种角色：

• 提议者(Proposer)：提议一个值，用于投票表决。实际就是接收到客户端请求的节点。

• 接受者(Accepter)：对每次提议，进行投票，并存储接受的值。一般集群中的所有节点，都会扮演接受者的角色，参数共识协商。

• 学习者(Learner)：被告知协商的结果，只接受达成共识的值。一般来说，学习者都是作为数据容灾备份的节点。

达成共识的过程（二阶段提交），以两个客户端同时X的值为例：

1. 准备阶段(Prepare)：

首先，客户端在连接某个节点写入X值时，该节点会作为提议者，向所有的接受者发送带有提案编号的准备请求。如下图所示，两个提案者同时向所有接受者发送准备请求，客户端1的提案编号为1，客户端2的提案编号为5，而准备请求中，只包含提案的编号。

然后当A、B、C三个接受者收到准备请求时，会判断准备请求中的提案编号，是否比本地接收过的最大提案编号大。是则返回准备响应，并承诺提案，后续不会接受提案编号更小的提案；否则忽略该准备请求。

如下图中，A、B先收到了客户端1的提案，C先收到了客户端2的提案，由于本地之前都没有收到过X的提案，所以直接返回准备响应，A、B承诺后续不会接受编号小于1的提案，C则承诺后续不会接受编号小于5的提案。

接下来A、B又收到了客户端2的提案，发现提案编号5大于之前保存的提案编号1，于是也返回准备响应，并承诺以后不再接受编号小于5的提案；C则收到了客户端1发送的1号提案，发现比之前收到的5号提案小，于是忽略该请求，不做响应。

2. 接受阶段(Accept)

经过之前的准备阶段，提案者收到来自接受者的准备响应，在收到大多数的接受者的准备响应后，会发送接受请求，接受请求中会包含自己的提案中给X设置的值。

在上面的例子中，客户端1收到了来自A、B的准备响应，超过了接受者的半数，于是将自己1号提案的X的值3写入接受请求中，发给所有接受者；而客户端2收到了A、B、C全部三个接受者的准备响应，于是也将自己5号提案的值7写入接受请求中，也发送给所有接受者。

然后A、B、C三个接受者收到两个提案者的接受请求时，会再次判断提案编号是否大于自己承诺过的最大提案编号，是的话就接受该值，否则拒绝该值。所以客户端1的提案被拒绝，客户端2的提案将被接受。

如果集群中有学习者，那么在接受者通过了某个提案时，就会通知所有的学习者。当学习者发现集群中大多数的接受者都通过了某个提案，那么它自己就会接受这个值。

通过以上过程，整个集群就对某个值达成了共识。可以看到Basic Paxos通过二阶段提交，保证接受者接受的值一定是最新的提案编号。并且Paxos的容错能力，来源于"大多数"的约定，所以当少于一半的接受者出现故障时，共识协商仍然可以正常工作。

Multi-Paxos

由上所说，Basic-Paxos只能对单个值进行共识协商，无法对多个值实现共识。Paxos作者提出可以通过多次执行Basic-Paxos算法的方式对多个值进行协商（每收到一次写入请求，就执行一次Basic-Paxos算法），但这会存在两个问题：

1. 如果多个提议者同时提交提案，那么可能导致集群中的接受者数量小于半数，导致所有的提案全部失败。

2. Basic-Paxos的两个阶段需要进行两轮RPC通讯，如果同时多个提议者进行提案，那么会有大量的网络往返消息，严重影响性能。

对于问题1，Multi-Paxos提出了引入领导者(Leader)节点的方案。可以通过选举，选举出一个领导者。作为唯一的提议者，这样就不存在多个提议者同时提交提案的情况，也就不会导致问题1了。

对于问题2，Multi-Paxos提出：当领导者稳定时，可以省略掉准备阶段，直接进入接收阶段的优化方式。由于只有一个领导者，那么领导者发送的提案编号一定是最新的，所以不需要通过二阶段提交防止接受者接受了更旧的提案，直接进入接受阶段即可。

由于Multi-Paxos在论文中并没有描述详细的实现，所以对具体的细节，比如如何选举Leader，不同产品有不同的实现，比如ZAB、Raft、Chubby的实现等。

Raft算法

Raft是Multi-Paxos的一种实现，做了一些简化和限制，相对Paxos更简单一些。用一句话来概括Raft，那就是通过一切以领导者为准的方式，实现一系列值的共识和保持各个节点的数据一致。

Raft算法简化为了三个核心问题，选主、日志复制，和安全保证。而安全保证又体现在前两条的选举安全，和日志提交安全上，接下来我们详细讨论。

选主

节点类型

Raft集群中会有三种类型的节点：

• Leader：领导者，集群的主节点，是客户端所有请求的真正处理者，接收客户端发起的所有读写请求，写入本地日志后还要做同步日志到集群其它节点的工作。

• Follower：跟随者，集群的从属节点，主要工作就是从 Leader 处接收更新请求，写入本地日志文件。如果客户端的操作请求发送给了 Follower，则会由 Follower 重定向给 Leader。

• Candidate：候选者，在选主期间存在的角色，如果 Follower 在一定时间内没有收到 Leader 的心跳，则判断 Leader 可能已经故障，此时启动选主过程（Leader Election），本节点将切换为Candidate角色参与选举。

任期(Term)

每一次选主时，都会产生一个任期(Term)，直到下一次选主时，该任期结束，每个任期都有一个严格递增的整数作为标识。

每当候选者Candidate触发Leader Election时都会增加Term值，如果一个Candidate赢得选举，他将在本term中担任Leader的角色。但是并不是每一个任期期间都一定存在一个 Leader，有时候会由于选举超时导致选不出Leader，这时Candicate会再次递增Term号并开始新一轮选举。

选主过程

Raft的选主基于一种心跳机制。首先，集群中的每个节点在刚刚启动时都是Follower身份，如果集群存在Leader，则Leader节点需要周期性的发送心跳包给所有的Follower来保持权威。当一个Follower在一段时间内没有收到来自leader的心跳包，则它会认为集群中此时没有Leader，那么这个Follower会转换自己的身份到Candidate，并将自己的Term值加1，同时发起选举，向其他所有Follower节点发送RequestVote请求，(请求中会包含自己的Term值和最后一条日志的Term值)，进行拉票。

当集群刚刚启动，所有的节点都是Follower节点，当开始选举时，那么如果每个Follower节点的等待Leader心跳的超时时间都是一样的，就会导致所有Follower节点将会在同时发起选举，造成Follower节点个数小于半数，那么就无法选出一个Leader，Raft算法通过一个随机定时器，让每个节点的心跳超时时间都是一个一定范围内的随机值，并且当某次选举失败时，也会等待一个随机时间间隔，再发起选举，以此降低多个节点同时发起选举的可能性。

Follower节点在收到来自Candidate节点的RequestVote请求后，会采用先到先得的方式，把票投给相同任期内第一个向自己发送RequestVote的Candidate，并把自己的Term值改为收到的Term值。如果收到了Term值小于自己的Term值的RequestVote请求，那么则会拒绝掉该拉票请求。除此之外，Follower还会检查RequestVote请求中，Candidate的最后一条日志的Term值，如果比自己的最后一条日志Term值小，也会拒绝投票给该Candidate。

然后Candidate在选举超时时间之前，如果能得到大多数节点的投票，那么它就宣布自己成为该任期内的新Leader，向所有Follower发送心跳来维持权威。

那么当其他的Candidate收到来自新Leader的心跳后，并且发现其任期不小于自己的任期Term值，则会降级为Follower，开始数据同步。

节点间通讯方式

Raft算法中，节点间通过RPC通讯，主要用到以下两类RPC方法：

• RequestVote RPCs：由Candidate发起，在选举时给自己拉票。

• AppendEntries RPCs：由Leader节点发起，向Follower节点复制日志，和同步心跳证明自己的存活。

节点角色转换时机

我们总结一下节点如何进行角色转换的，集群初始时所有节点角色都是Follower，集群稳定时除了Leader外的所有节点都是Follower：

Follower -> Candidate：

Follower根据自己随机的超时时间没有收到Leader发来的心跳后，转换为Candidate角色，将自己的Term值加1，并发送RequestVote请求给所有Follower

Candidate -> Leader：

Candidate发送RequestVote请求后，如果收到了大多数Follower的投票后，则转换自己为Leader

Candidate -> Follower：

当收到新Leader发来的AppendEntries心跳请求，并发现其Term值比自己大，则转换为Follower

Leader -> Follower：

当Leader收到了其他Leader的AppendEntries心跳请求，并发现其Term值比自己大，则会降为Follower

日志复制

日志结构

在Raft中，节点上的数据副本是以日志形式记录的，日志是由日志项组成的，每条日志项实际就对应着每次客户端的写入数据。这也是Raft和Multi-Paxos的区别之一，Multi-Paxos不要求日志是连续的，而在Raft中日志必须是连续的。

如下为日志和日志项，可以看到无论在Leader还是Follower节点上，日志都是大量日志项线性拼接组成的。每条日志项中主要包含三个信息：

• 指令：由客户端请求指定的，状态机需要执行的指令

• 索引值：该日志项在整个日志中的索引值

• 任期编号：记录创建这条日志项的Leader的任期编号

复制日志过程

Raft的日志复制过程同样也是一个二阶段提交，使用的上述Multi-Paxos中我们提到的优化方式，由于只有Leader节点可以进行提案，所以去除了准备请求阶段，直接进入接受请求阶段。

具体过程就是Leader节点本地创建一个新日志项，然后发送AppendEntries请求给所有Follower，等待大多数节点复制成功的响应后，再将日志项提交到自己的状态机，并返回成功给客户端。

1. Leader接收到客户端写入请求后，创建一个新日志项，并附加到本地日志中

2. Leader通过AppendEntries RPC请求所有Follower完成新日志项的复制

3. 大多数Follower响应成功后，Leader将该日志项提交到自己的状态机中

4. Leader返回执行成功给客户端

5. Follower会随着下一次的AppendEntries请求(不管是心跳或者日志项复制请求)，发现Leader已经提交了某条日志项，那么它本地也会将该日志项提交到自己的状态机中

处理日志的不一致

在Raft算法中，Leader通过强制让Follower复制自己的日志项来保证强一致，一旦Follower出现于Leader的不一致，Leader强制覆盖掉Follower上与Leader不一致的日志项。

具体过程如下：

1. Leader发送AppendEntries请求给Follower，会携带当前复制的日志项的前一条日志项，对应的索引以及任期编号

2. Follower收到请求，会根据请求中的前一条日志项的索引和任期编号，检查本地是否有前一条日志项，如果没有，则说明该Follower和Leader不一致了，就会拒绝复制新日志项，返回错误信息给Leader

3. Leader收到Follower的错误响应，会递减要复制的日志项的索引，重新发送AppendEntries请求给该Follower

4. 重复这个过程，直到Follower找到了和Leader一致的前一条日志，从这里开始复制，如果本地在该日志项后面有日志项，则会完全被Leader发来的日志项覆盖掉，返回成功给Leader

5. 接下来Leader把剩余的所有日志项，连带新日志项，全部同步给Follower

可以看到Leader节点通过当前日志项的前一条日志项的索引和任期编号，找到Follower和Leader同步的日志项的起始位置，然后将Leader的日志项完全覆盖Follower的日志项，而Leader的日志项则从来不会被覆盖或删除。

成员变更

成员变更，指的是当Raft集群中需要对节点进行替换，或者增加或减少节点的操作。

成员变更时Leader选举的问题

由于Raft依赖于”大多数“来保障安全，所以如果在集群增加节点时进行了Leader选举，是有可能选出两个Leader节点的情况出现的。所以Raft集群的成员变更，使用了单节点变更的方法，来保证安全。

我们以一个三节点Raft集群，变更为五节点，来展开说明这个问题。

如上图，该Raft集群的旧配置是A、B、C三个节点，A为Leader。当我们增加D、E两个新节点时，如果C、D、E和A、B之间发生了网络分区，则A、B两个节点依旧组成了旧集群配置里的大多数，则A仍然是Leader。但是C、D、E三个节点进行了Leader选举之后，由于满足新集群配置的大多数，所以也可以选举出一个新Leader，则此时整个集群里同时出现了2个Leader的情况。

那么如何解决这个问题。首先如果业务可以中断，那就可以先关闭所有节点，然后让所有节点以新配置重新启动，那么就可以让A、B也加载到新加的D、E两个节点，则Leader选举不会有问题。但是很显然，大部分的业务都不能允许中断的情况。

单节点变更

单节点变更，就是一次只变更一个节点，多个节点变更则通过多次执行单节点变更完成，如下：

添加一个新节点的具体过程如下：

1. 首先Leader需要向新节点同步自己的所有数据

2. 然后Leader将新的集群配置，也作为一个日志项，复制给当前集群中所有Follower节点

3. 最后Leader本地把新集群配置的日志项在本地提交到状态机，完成新节点的加入

然后我们分析下通过单节点变更，如何解决上述出现双Leader的问题。首先，出现双Leader的问题在于，旧集群的大多数节点，和新集群的大多数节点，是没有重合的，这样就造成如果出现网络分区，旧集群和新集群都可以满足大多数的原则从而选出Leader。而当我们进行单节点变更时，不管要满足新集群的大多数，还是满足旧集群的大多数，一定会有重合的节点，这也就避免了双Leader的产生，因为重合的节点不可能把票即投给旧集群又把票投给新集群。

比如对于一个三节点集群A、B、C来说，他的大多数是2个节点。当它变更为四节点时，则大多数是3个节点。由于2+3=5个节点，而集群中只有4个节点，所以如果要选出两个Leader，必然有一个节点即投给了旧集群，也投给了新集群，而根据Raft算法这是不可能的事情。

Gossip算法

Gossip算法不能像Raft或Paxos一样保证强一致性，但是他可以保证极高的可用性。那么根据BASE理论，它可以实现最终一致性。它的实现原理就像名字流言蜚语一样，通过随机的，带有传染性的方式，将信息散步到整个集群，并最终使整个集群所有节点的数据达成一致。

实现Gossip的三板斧：直接邮寄(Direct Mail)、反熵(Anti-entropy)，和谣言传播(Rumor mongering)。

• 直接邮寄

就是直接向其他节点发送写入数据，当数据发送失败时，就本地缓存起来，并定时重传。

直接邮寄实现较为容易，但是由于缓存队列可能会因为满了而丢数据，所以光靠直接邮寄无法实现最终一致。

• 反熵

反熵，指降低系统中的混乱程度的意思。就是集群中的节点，每隔一段时间就随机选择某个其他节点，并通过交换自己或对方的所有数据的方式，进行数据修复，从而实现最终一致。具体实现可以有推、拉、推拉三种方式。推就是把自己的全部数据推给对方，修复对方的数据；拉就是拉取对方的全部数据，修复自己的数据；推拉就是同时进行推和拉，同时修复双方的数据。

具体实现熵，可以构造一个闭环的顺序每两个节点间执行反熵，从而让所有节点的数据达成一致。反熵在InfluxDB、Cassandra中都有广泛的应用。

由于反熵执行时，需要两两交换和对比双方的所有数据，所以性能成本会很高，不应该频繁使用。可以通过计算校验和等方式进行优化。

• 谣言传播

就是当某个节点收到新数据后，该节点会周期性地将数据散播到其他节点，其他节点收到数据后，也进行散播，直到所有节点都存储了该数据。这种方式主要是应对集群节点是动态变化的，或者是节点数量非常多的情况。

Quorum NWR算法

Quorum NWR不像Paxos或Raft的强一致，也不是Gossip的最终一致，而是一个可以自定义一致性级别的算法，并且还可以实时地灵活调整系统的一致性。

Quorum NWR算法的三个要素：

• N：副本数，或者复制因子。表示同一份数据有多少个副本（副本数一般小于等于节点数），比如3就代表一份数据要有三个副本。

• W：写一致性级别。表示写入时需要写入的副本数。比如2就代表写入时，需要完成两个副本的更新才算写入成功。

• R：读一致性级别。表示读取一份数据时，需要读取的副本数。比如2就代表读取时，需要读取两个副本，并取其中最新的那份数据。

所以根据NWR的不同组合能产生不同的一致性效果：

• W + R > N时：此时读取的副本中一定会包含写入的副本，所以能保证强一致性，一定能获取最新的数据

同时，可以调整W和R来优化读写能力，比如设置W = N，则读性能会较好，只需要读任意一个节点即可；设置R = N，则写性能较好，只需要写入一个节点即可；如果设置W = (N+1) / 2、R = (N+1) / 2，则容错性最好，可以容忍少数节点 (N-1) / 2 的故障

• W + R < N时：此时只能保证最终一致性，可能会返回旧数据

Quorum NWR算法可以很好的弥补AP型系统强一致的痛点，给业务提供按需选择一致性的灵活度。

ZAB协议

ZAB协议是Zookeeper实现的协议。也是基于Multi-Paxos思想的优化。由于Multi-Paxos能保证达成共识后的值不再改变，但是保证不了多个操作的顺序性，这是不满足Zookeeper的需求的（比如创建节点/test和创建节点/test/1两个操作如果顺序反了，就会执行失败）。

原子广播协议

ZAB的实现影响了后续诞生的Raft协议，所以二者有很多相似之处，比如都是多数派选举投票算法。而对于操作的顺序性，是通过原子广播协议来保证的。

ZAB实现的是基于主备模式的原子广播协议，ZAB也会存在主节点，和备份节点，所有副本数据都以主节点为准，客户端的写入操作也需要连接主节点，主节点同样采用二阶段提交，向备份节点同步数据，当大多数备份节点返回成功时，主节点再提交到本地并返回客户端成功。当主节点崩溃时，保存最完备数据的节点会成为新的主节点。而原子广播协议，可以理解为主节点广播一组消息，而消息的顺序是固定的。此外，ZAB还使用一个FIFO队列，保证消息处理的顺序性。

选举过程

ZAB协议同样给不同节点分配不同角色：

• Leader：领导者节点

• Follower：跟随者节点

• Observer：观察者，无选举投票权

而在选举的过程中，节点会存在四种状态：

• Looking状态：选举状态，节点在认为集群中没有Leader时，会进入该状态

• Leader状态：表示已经完成选主，且自己就是主

• Following状态：已经完成选主，自己是跟随者

• Observing状态：观察者的状态，因为观察者没有投票权，所以它一直都是这个状态

投票过程中，每个节点都有一个唯一的三元组 (server_id, server_zxID, epoch)，其中server_id表示本节点的唯一 ID；server_zxID表示本节点存放的数据 ID，数据 ID 越大表示数据越新，选举权重越大；epoch 表示当前选取轮数。

ZAB 算法选主的原则是：server_zxID最大者即数据最新的节点成为Leader；若server_zxID相同，则server_id最大者会成为 Leader。在选举开始时，每个节点都会推选自己，把自己的选票信息广播出去。节点收到其他选票时，会做对比，比较server_zxID和server_id，然后根据上述判断规则，更新自己的选票，并再次广播出去。

所以，如果所有节点的数据都是一样新，那么server_id最大的往往会成为Leader，所以ZAB算法Leader的稳定性会比较高。

但是也因为不像Raft那样每个节点都只会投给第一个向自己拉票的节点，而是同时广播，所以集群中的信息量为n*(n-1)，容易出现广播风暴，比较server_id和server_zxID也会使选举的耗时变长。

总结

这篇文章主要是学习了分布式理论，和各种CFT类型的分布式协议和算法。它们各自采用不同的机制和策略来确保数据的一致性、可靠性和可用性。Paxos以其理论基础而闻名，但实现复杂；Raft则以易于理解和实现而受到青睐；ZAB则专注于数据的原子广播和顺序操作，Quorum NWR则足够灵活。通过深入理解这些协议的特点和适用场景，我们可以根据系统需求选择合适的协议，从而构建高效、稳定的分布式系统。

接下来我们可以仔细学习下当前最受欢迎的强一致性共识算法Raft的代码实现。

问题

一. 如何提高Raft集群的写入性能？

1. 批量写入，多个写请求合为一条日志项，减少网络传输

2. 使用更快的网络，或者降低节点之间的距离，可以所有节点都部署在一个机房，甚至一台物理机上

3. 如果允许读到旧数据，可以受用读写分离，读请求走Follower节点

4. 将Leader节点主动转移到性能更高的节点上

5. 使用更快的存储，比如SSD，甚至内存

6. 减少Raft集群的节点个数，减少数据的复制

7. 使用消息队列对写请求进行削峰

8. 拆分集群，将写操作，通过代理分发到不同的Raft集群，突破单集群的限制

二. 如何降低反熵过程的性能消耗？

1. 可以用现在的时间换未来的时间，将数据组织成一颗哈希树，反熵执行时逐层进行哈希校验，不需要比较所有数据项。

2. 反熵执行过程中，不进行全部数据的对比，而是随机取几块数据对比，通过延长最终一致的时间来提高性能。

参考资料

[1] 极客时间《分布式协议与算法实战》

[2] 极客时间《分布式技术原理和算法解析》

[2] "Raft: In Search of an Understandable Consensus Algorithm"