一致性

强一致性（原子一致性，顺序一致性）

• 任何一次读都能读到某个数据的最近一次写的数据。

• 系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。

简言之，在任意时刻，所有节点中的数据是一样的。

例如，对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。

顺序一致性

• 任何一次读都能读到某个数据的最近一次写的数据。
• 系统的所有进程的顺序一致，而且是合理的。即不需要和全局时钟下的顺序一致，错的话一起错，对的话一起对。

1）图a是满足顺序一致性，但是不满足强一致性的。原因在于，从全局时钟的观点来看，P2进程对变量X的读操作在P1进程对变量X的写操作之后，然而读出来的却是旧的数据。但是这个图却是满足顺序一致性的，因为两个进程P1，P2的一致性并没有冲突。从这两个进程的角度来看，顺序应该是这样的：Write(y,2) , Read(x,0) , Write(x,4), Read(y,2)，每个进程内部的读写顺序都是合理的，但是这个顺序与全局时钟下看到的顺序并不一样。

2）图b满足强一致性，因为每个读操作都读到了该变量的最新写的结果，同时两个进程看到的操作顺序与全局时钟的顺序一样，都是Write(y,2) , Read(x,4) , Write(x,4), Read(y,2)。

3）图c不满足顺序一致性，当然也就不满足强一致性了。因为从进程P1的角度看，它对变量Y的读操作返回了结果0。那么就是说，P1进程的对变量Y的读操作在P2进程对变量Y的写操作之前，这意味着它认为的顺序是这样的：write(x,4) , Read(y,0) , Write(y,2), Read(x,0)，显然这个顺序又是不能被满足的，因为最后一个对变量x的读操作读出来也是旧的数据。因此这个顺序是有冲突的，不满足顺序一致性。

弱一致性

数据更新后，如果能容忍后续的访问只能访问到部分或者全部访问不到，则是弱一致性。

最终一致性

不保证在任意时刻任意节点上的同一份数据都是相同的，但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。

简单说，就是在一段时间后，节点间的数据会最终达到一致状态。

共识（Consensus)

在介绍共识协议之前，我们要来聊聊它的三个属性。

1. 正确性（Validity）：诚实节点最终达成共识的值必须是来自诚实节点提议的值。
2. 一致性（Agreement）：所有的诚实节点都必须就相同的值达成共识。
3. 终止性（Termination）：诚实的节点必须最终就某个值达成共识。

你会发现共识算法中需要有“诚实”节点，它的概念是节点不能产生失败模型所描述的“任意失败”，或是“拜占庭失败”。因为数据库节点一般会满足这种假设，所以我们下面讨论的算法可以认为所有节点都是诚实的。

共识问题中所有的节点要最终达成共识，由于最终目标是所有节点都要达成一致，所以根本不存在一致性强弱之分。

例如，Paxos是共识（Consensus）算法而不是强一致性（Consistency）协议。共识算法没有一致性级别的区分。

一致性和共识的区别

图3 Consistency和Consensus的区别

从上面对一致性和共识的描述我们可以列出二者之间的一些联系如下：

图4 Consistency和Consensus的关系

可以说，Consistency是系统中需要保证的一个属性（即“Allowed ways”），而Consensus算法是实现Consistency的一种手段（主要是最终一致性）。当然，保证一致性的方法还有其它手段，如强一致性可通过2PC，3PC，TCC保证。

一致性协议

Quorum（本身并不能保证强一致性需要结合其他策略）

Quorum与Paxos，Raft等一致性协议有什么区别，这个问题的答案本身很简单：一致性协议大多使用了Quorum机制，但仅仅有Quorum(R+W>N)机制是保证不了一致性的。

Quorum

Quorum 在 1979 被提出，其主要数学思想来源于鸽巢原理

这个协议有三个关键值N、R和W：
N表示数据所具有的副本数。
R表示完成读操作所需要读取的最小副本数。
W表示完成写操作所需要写入的最小副本数。

该策略中，只需要保证R + W > N，就会提供强一致性的保证，因为读取数据的节点和被同步写入的节点是有重叠的（鸽巢原理）。

分布式系统通常支持多副本，副本存放在不同节点上，读写时需要对多个副本进行操作。考虑到一致性问题，可以在写操作更新所有副本，而读取时只要读其中一个副本。但是，这样写负载太重了，读很轻松，读写负载明显不平衡。
采用Quorum机制后，写操作需要即刻完成的副本数减少，读操作需要成功读取的副本数增加，一定程度上平衡了读写两种操作，系统整体性能会得到提升。比如，有5个副本，可以让写操作只要写完3个就返回。剩下的由系统内部缓慢同步完成。而读操作，则需要至少读3台，就可保证至少可以读到一个最新的数据。（鸽巢原理）

例如：N=3，W=2，R=2，那么表示系统中数据有3个不同的副本，当进行写操作时，需要等待至少有2个副本完成了该写操作系统才会返回执行成功的状态，对于读操作，系统有同样的特性。由于R + W > N，因此该系统是可以保证强一致性的。

NWR模型中的读（写）延迟由最慢的R(W)副本决定，有时为了获得较高的性能和较小的延迟，R和W的和可能小于N，这时系统不能保证读操作能获取最新的数据。

如果R + W ≤ N，这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新的实现方式，不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。

下面为不同设置的几种特殊情况。
当W = 1，R = N时，系统对写操作有较高的要求，但读操作会比较慢，若N个节点中有节点发生故障，那么读操作将不能完成。
当R = 1，W = N时，系统要求读操作高性能、高可用，但写操作性能较低，用于需要大量读操作的系统，若N个节点中有节点发生故障，那么写操作将无法完成。
当R = W = N / 2 + 1时，系统在读写性能之间取得了平衡，兼顾了性能和可用性，Dynamo系统的默认设置就是这种，即N=3，W=2，R=2。

对于NWR模型来说，存在着版本冲突的问题，为此，Amazon的Dynamo引入了Vector Clock

ZAB

Raft

raft-zh_cn/raft-zh_cn.md at master · maemual/raft-zh_cn (github.com)

系统中每个结点有三个组件：

状态机: 当我们说一致性的时候，实际就是在说要保证这个状态机的一致性。状态机会从log里面取出所有的命令，然后执行一遍，得到的结果就是我们对外提供的保证了一致性的数据
Log: 保存了所有修改记录
一致性模块: 一致性模块算法就是用来保证写入的log的命令的一致性，这也是raft算法核心内容

Raft协议的每个副本都会处于三种状态之一：Leader、Follower、Candidate。

Leader：所有请求的处理者，Leader副本接受client的更新请求，本地处理后再同步至多个其他副本；
Follower：请求的被动更新者，从Leader接受更新请求，然后写入本地日志文件
Candidate：如果Follower副本在一段时间内没有收到Leader副本的心跳，则判断Leader可能已经故障，此时启动选主过程，此时副本会变成Candidate状态，直到选主结束。

1. Leader Election

组成一个Raft集群至少需要三台机器，而Raft限制每一时刻最多只能有一个节点可以发起提案，这个限制极大的简化了一致性的实现，这个可以发起提案的节点称为Leader。因此所要解决的第一个问题便是：

• 如何保证任何时候最多只有一个Leader节点
• 以及当Leader节点异常时如何尽快的选择出新的Leader节点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SXap7YH1-1656056424530)(http://catkang.github.io/assets/img/raft_subproblem/status_trans.jpg)]

如上图所示：

• 所有的节点以Follower的角色启动；
• Leader周期性给其他节点发送心跳；
• 在超时时间内没有收到心跳包的Follower变成Candidate，将自己的Term加一，并广播Vote请求，发起新一轮选举；
• 选举结束：
  • 收到大多数节点的投票，变成Leader，并向其他节点发送自己Term的AppendEntry。在一个Term里，同一个Server只会给出一次投票，先到先得；
  • 收到相同或更大Term的AppendEntry，承认对方为Leader，变成Follower；
  • 超时，重新开始新的选举，通过随机的超时时间来减少这种情况得发生。

2. Log Replication

• 当Leader被选出来后，就可以接受客户端发来的请求了，每个请求包含一条需要被replicated state machines执行的命令。Leader会把它作为一个log entry append到日志中，然后给其它的server发AppendEntriesRPC请求。当Leader确定一个log entry被safely replicated了（大多数副本已经将该命令写入日志当中），就apply这条log entry到状态机中然后返回结果给客户端。如果某个Follower宕机了或者运行的很慢，或者网络丢包了，则会一直给这个Follower发AppendEntriesRPC直到日志一致。

  当一条日志是commited时，Leader才可以将它应用到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的节点执行。

• 到目前为止，我们都只关注了Leader崩溃的情况。Follower和Candidate崩溃后的处理方式比Leader要简单的多，并且他们的处理方式是相同的。如果Follower或者Candidate崩溃了，那么后续发送给他们的 RPCs 都会失败。Raft 中处理这种失败就是简单地通过无限的重试；如果崩溃的机器重启了，那么这些 RPC 就会完整的成功。如果一个服务器在完成了一个 RPC，但是还没有响应的时候崩溃了，那么在他重新启动之后就会再次收到同样的请求。Raft 的 RPCs 都是幂等的，所以这样重试不会造成任何问题。例如一个Follower如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求。

3. Safety

通过上述的两个子问题已经解决了大部分的难题，除了下面两个细节：

1. Leader Crash后，新的节点成为Leader，为了不让数据丢失，我们希望新Leader包含所有已经Commit的Entry。为了避免数据从Follower到Leader的反向流动带来的复杂性，Raft限制新Leader一定是当前Log最新的节点，即其拥有最多最大term的Log Entry。
2. 通常对Log的Commit方式都是Leader统计成功AppendEntry的节点是否过半数。在节点频发Crash的场景下只有旧Leader Commit的Log Entry可能会被后续的Leader用不同的Log Entry覆盖，从而导致数据丢失。造成这种错误的根本原因是Leader在Commit后突然Crash，拥有这条Entry的节点并不一定能在之后的选主中胜出。这种情况在论文中有详细的介绍。Raft很巧妙的限制Leader只能对自己本Term的提案采用统计大多数的方式Commit，而旧Term的提案则利用“Commit的Log之前的所有Log都顺序Commit”的机制来提交，从而解决了这个问题。另一篇博客中针对这个问题有更详细的阐述Why Raft never commits log entries from previous terms directly

Raft

Gossip

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

Gossip 过程是由种子节点发起，当一个种子节点有状态需要更新到网络中的其他节点时，它会随机的选择周围几个节点散播消息，收到消息的节点也会重复该过程，直至最终网络中所有的节点都收到了消息。这个过程可能需要一定的时间，由于不能保证某个时刻所有节点都收到消息，但是理论上最终所有节点都会收到消息，因此它是一个最终一致性协议。

注意：Gossip 过程是异步的，也就是说发消息的节点不会关注对方是否收到，即不等待响应；不管对方有没有收到，它都会每隔 1 秒向周围节点发消息。异步是它的优点，而消息冗余则是它的缺点。

Gossip 的特点（优势）

1）扩展性

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

2）容错

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

3）去中心化

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

4）一致性收敛

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

5）简单

Gossip 协议的过程极其简单，实现起来几乎没有太多复杂性。

Gossip 的缺陷

分布式网络中，没有一种完美的解决方案，Gossip 协议跟其他协议一样，也有一些不可避免的缺陷，主要是两个：

1）消息的延迟

由于 Gossip 协议中，节点只会随机向少数几个节点发送消息，消息最终是通过多个轮次的散播而到达全网的，因此使用 Gossip 协议会造成不可避免的消息延迟。不适合用在对实时性要求较高的场景下。

2）消息冗余

Gossip 协议规定，节点会定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，因此就不可避免的存在消息重复发送给同一节点的情况，造成了消息的冗余，同时也增加了收到消息的节点的处理压力。而且，由于是定期发送，因此，即使收到了消息的节点还会反复收到重复消息，加重了消息的冗余。

总结

Gossip协议通过反熵传播（anti-entropy）和谣言传播（rumor mongering）两种机制进行实现并保证节点数据的最终一致性。

1. 种子节点周期性的散播消息

2. 被感染节点随机选择N个邻接节点散播消息

3. 节点只接收消息不反馈结果，每次散播消息都选择尚未发送过的节点进行散播

4. 收到消息的节点不再往发送节点散播，即单向不可逆，如A -> B，那么B进行散播的时候，不再发给 A

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

问题抛出

拜占庭问题：如果有一个恶意传播消息的节点，Gossip协议的分布式系统就会出问题。

问题描述：

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。 问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。 叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。

问题的解决：

论文中指出，对于拜占庭问题来说，假如节点总数为 N，故障节点数为 F，则当 N >= 3F + 1 时，问题才能有解，由 BFT 算法进行保证。

例如，N = 3，F = 1 时。

视图更换协议

视图检查所有节点必须在同一个配置下才能正常工作。如果节点的视图配置不一致，比如主节点不一致、节点数量不一致，那统计合法票数的时候，真没法干了。

在一致性协议里，已经知道主节点在整个系统中拥有序号分配，请求转发等核心能力，支配着这个系统的运行行为。然而一旦主节点自身发生错误，就可能导致从节点接收到具有相同序号的不同请求，或者同一个请求被分配多个序号等问题，这将直接导致请求不能被正确执行。视图更换协议的作用就是在主节点不能继续履行职责时，将其用一个从节点替换掉，并且保证已经被非拜占庭服务器执行的请求不会被篡改。即，核心有2点：1，主节点故障时，可能造成系统不可用，要更换主节点；2，当主节点是恶意节点时，要更换为诚实节点，不能让作恶节点作为主节点。

最终一致性的实现方式

直接邮寄（Direct Mail）、反熵（Anti-entropy）和谣言传播（Rumor mongering）是实现最终一致性的常用三种方法。

直接邮寄（Direct Mail）

每个节点更新都会立即从其变更节点邮寄通知到所有其他节点。

主要是当节点有数据更新便开始遍历节点池，遍历发送其他所有节点消息来通知自身节点数据的更新情况

好处:实现起来比较容易，数据同步也很及时
缺点：当数据发送失败时，将数据缓存下来，然后重传。虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢数据。只采用直接邮寄是无法实现最终一致性的，

节点A发送数据给B成功。
节点A发送数据给D失败，但是节点A的缓存满了，发送的数据无法保存。
节点B和D数据不一致

反熵（Anti-entropy） (SI model) 熵:混乱的意思，反熵，就是反差异的意思

Suspective(病原)：处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。

Infective(感染)：处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点。

每个节点都会定期随机选择节点池中的一些节点，通过交换数据内容来解决两者之间的任何差异。

所有参与节点只有两种状态：Suspective(病原)、Infective(感染)
过程是种子节点会把所有的数据都跟其他节点共享，以便消除节点之间数据的任何不一致
缺点是消息数量非常庞大，且无限制；通常只用于新加入节点的数据初始化。
反熵是一种通过异步修复实现最终一致性的方法。

实现反熵的方式

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

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

● 推拉
就是同时修复自己副本和对方副本中的熵

对于反熵（anti-entropy） 这种方式，和直接邮寄（direct mail）相比的最大特点就是解决了消息丢失无法补偿容错导致的数据无法保持一致的致命问题。它通过单点的定时随机通知周边节点进行数据交互的方式保持各节点之间数据的一致性。这里需要注意的是，一致性的保持是在节点数据变更后一段时间内通过节点间的数据交互逐渐完成的最终一致，并且由于每个节点都定期广播数据到周边随机的一部分节点，因此在数据交互上是存在冗余和延迟的。

注意
反熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高，所以不建议在实际场景中频繁执行反熵，可以通过引入校验和（Checksum）等机制，降低需要对比的数据量和通讯消息等。

执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果是一个动态变化或节点数比较多的分布式环境（比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态），这时反熵就不适用了。那么当你面临这个情况要怎样实现最终一致性呢？答案就是谣言传播。

谣言传播（Rumor mongering）（SIR model）

Suspective(病原)、Infective(感染)、Removed(愈除)。

Removed(愈除):其已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

所有的节点在最开始没有产生数据变更时都假设是未知状态，它是不知道任何谣言信息的
当节点收到其他节点更新数据通知时，相当于听到了一条谣言，并将其视为热门开始传播给周边节点
当某个节点谣言盛行时，它会定期随机选择其他节点，并确保另一个节点知道
当某个节点发现周边节点都知道这个谣言时，该节点将停止将该谣言视为热点，并保留更新，而不会进一步传播
节点 A 向节点 B、D 发送新数据
节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。

共识算法

raft

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-231I5Umh-1656056424531)(https://segmentfault.com/img/remote/1460000022361105)]

Raft和它的三个子问题 | CatKang的博客
定期随机选择其他节点，并确保另一个节点知道
当某个节点发现周边节点都知道这个谣言时，该节点将停止将该谣言视为热点，并保留更新，而不会进一步传播
节点 A 向节点 B、D 发送新数据
节点 B 收到新数据后，变成活跃节点，然后节点 B 向节点 C、D 发送新数据。

共识算法

raft

[外链图片转存中…(img-231I5Umh-1656056424531)]

Raft和它的三个子问题 | CatKang的博客