分布式理论

CAP理论

轻松理解CAP理论 - 知乎 (zhihu.com)

Consistency Availability Partition tolerance:

①一致性：对于客户端的每次读操作，要么读到的是最新的数据，要么读取失败。换句话说，一致性是站在分布式系统的角度，对访问本系统的客户端的一种承诺：要么我给您返回一个错误，要么我给你返回绝对一致的最新数据，不难看出，其强调的是数据正确。

②可用性：任何客户端的请求都能得到响应数据，不会出现响应错误。换句话说，可用性是站在分布式系统的角度，对访问本系统的客户的另一种承诺：我一定会给您返回数据，不会给你返回错误，但不保证数据最新，强调的是不出错。

③分区容忍性：由于分布式系统通过网络进行通信，网络是不可靠的。当任意数量的消息丢失或延迟到达时，系统仍会继续提供服务，不会挂掉。换句话说，分区容忍性是站在分布式系统的角度，对访问本系统的客户端的再一种承诺：我会一直运行，不管我的内部出现何种数据同步问题，强调的是不挂掉。

note：其实这里有个关于CAP理论理解的误区。不要以为在所有时候都只能选择两个特性。在不存在网络失败的情况下（分布式系统正常运行时），C和A能够同时保证。只有当网络发生分区或失败时，才会在C和A之间做出选择。

例子

理解CAP理论最简单的方式是想象两个副本处于分区两侧，即两个副本之间的网络断开，不能通信。

• 如果允许其中一个副本更新，则会导致数据不一致，即丧失了C性质。
• 如果为了保证一致性，将分区某一侧的副本设置为不可用，那么又丧失了A性质。
• 除非两个副本可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。

平衡

在CAP理论提出十二年之后，其作者又出来辟谣。“三选二”的公式一直存在着误导性，它会过分简单化各性质之间的相互关系：

• 首先，由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲C或A。
• 其次，C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生，而每一次的决策可能因为具体的操作，乃至因为牵涉到特定的数据或用户而有所不同。
• 最后，这三种性质都可以在程度上衡量，并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。

所以一致性和可用性并不是水火不容，非此即彼的。Paxos、Raft等分布式一致性算法就是在一致性和可用性之间做到了很好的平衡的见证。

一致性模型

分布式系统一致性分类，你知道几种？ - 腾讯云开发者社区-腾讯云 (tencent.com)

学术界的一致性模型主要从两个角度去分类：

以数据为中心的一致性模型；

以客户为中心的一致性模型。

以数据为中心的一致性模型

a.严格一致性（Strict Consistency）

严格一致性要求任何写操作都能立刻同步到其他所有进程，任何读操作都能读取到最新的修改。要实现这一点，要求存在一个全局时钟，但是，在分布式场景下很难做到，所以严格一致性在实际生产环境中目前无法实现。

b.顺序一致性（Sequential Consistency）

既然全局时钟导致严格一致性很难实现，顺序一致性放弃了全局时钟的约束，改为分布式逻辑时钟实现。顺序一致性是指所有的进程以相同的顺序看到所有的修改。读操作未必能及时得到此前其他进程对同一数据的写更新。但是每个进程读到的该数据的不同值的顺序是一致的。

c.因果一致性（Causal Consistency）

因果关系是指Lamport在分布式时钟事件序论文中描述的happen-before关系及其传递闭包。因果一致性是一种弱化的顺序一致性。所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同进程可以以不同的顺序看到并发的写操作。

d.FIFO一致性（FIFO Consistency）

在因果一致性模型上的进一步弱化，FIFO一致性要求所有进程以某个单一进程提出写操作的顺序看到这些写操作，但是不同进程可以以不同的顺序看到不同的进程提出的写操作。通俗来讲，就是要求在一个进程内，所有的写操作必须对外可以被看到的时候，必须是一致的，但是两个进程的写操作的顺序被看到是时候可以不同，是不受保证的，就算是有因果关系也不保证。

以用户为中心的一致性模型

在实际业务要求中，很多时候并不要求系统内所有的数据都保持一致，例如在线的日记本，业务只要求基于这一个用户满足一致性即可，不需要关心整体。这就是所谓的以用户为中心的一致性。

a.单调读一致性（Monotonic-read Consistency）

单调读一致性是指如果一个进程读取数据项a的值，那么该进程对a执行的任何后续读操作总是得到第一次读取的那个值或更新的值。

b.单调写一致性（Monotonic-write Consistency）

单调写一致性是指一个进程对数据项a执行的写操作必须在该进程对a执行任何后续写操作前完成。

c.写后读一致性（Read-your-writes Consistency）

写后读一致性是指一个进程对数据项a执行一次写操作的结果总是会被该进程对a执行的后续读操作看见。

d.读后写一致性（Writes-follow-reads Consistency）

读后写一致性是指同一进程对数据项a执行的读操作之后的写操作，保证发生在于a读取值相同或比其更新的值上。

业界常用的一致性模型

上面两个分类主要从学术角度进行分类，在实际情况中，大家简化了分类，主要分成了如下三个分类。

弱一致性（Weak）：写入一个数据a成功后，在数据副本上可能读出来，也可能读不出来。不能保证多长时间之后每个副本的数据一定是一致的。

最终一致性（Eventually）：写入一个数据a成功后，在其他副本有可能读不到a的最新值，但在某个时间窗口之后保证最终能读到。可以看做弱一致性的一个特例。这里面的重点是这个时间窗口。

强一致性（Strong）：数据a一旦写入成功，在任意副本任意时刻都能读到a的最新值。

最终一致性还可以继续细分，大家更喜欢把除了弱一致性和强一致性的其他一致性全部归为最终一致性。

弱一致性和最终一致性的副本同步是采用异步的方式，而强一致性一般要求同步更新副本，然后才能返回成功，否则很难满足任意副本任意时刻都能读到最新值，异步的通常意味着更好的吞吐量，但也意味着更复杂的架构，更复杂的开发、调试。同步意味着简单，但也意味着响应时间更长，吞吐量的更低。

BASE理论

BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的简写，BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于CAP定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual consistency）。

基本可用

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性——但请注意，这绝不等价于系统不可用，以下两个就是“基本可用”的典型例子。

• 响应时间上的损失：正常情况下，一个在线搜索引擎需要0.5秒内返回给用户相应的查询结果，但由于出现异常（比如系统部分机房发生断电或断网故障），查询结果的响应时间增加到了1~2秒。
• 功能上的损失：正常情况下，在一个电子商务网站上进行购物，消费者几乎能够顺利地完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面。

软状态

也称为弱状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

最终一致性

最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

Quorum机制

读、写阶段策略

对于ZAB和RAFT，Quorum机制只在正常的Leader任期（广播阶段）内有效，对于同步/读阶段，两者都是以自身的Proposal为准，而不会关注其它机器的情况，其中ZAB是因为自身拥有了最新的Proposal，所以不需要关心；对于Paxos协议，Quorum机制在读阶段和写阶段（相当于ZAB的广播阶段）都有效，因而在读阶段需要和其它Acceptor进行沟通，以确认哪些该提交，哪些该作废。

Quorum机制是“抽屉原理”的一个应用。

定义如下：假设有N个副本，更新操作wi 在W个副本中更新成功之后，才认为此次更新操作wi 成功。称成功提交的更新操作对应的数据为：“成功提交的数据”。对于读操作而言，至少需要读R个副本才能读到此次更新的数据。其中，W+R>N ，即W和R有重叠。一般，W+R=N+1。

假设系统中有5个副本，W=3，R=3。初始时数据为(V1，V1，V1，V1，V1）–成功提交的版本号为1，当某次更新操作在3个副本上成功后，就认为此次更新操作成功。数据变成：(V2，V2，V2，V1，V1）–成功提交后，版本号变成2，因此，最多只需要读3个副本，一定能够读到V2(此次更新成功的数据)。而在后台，可对剩余的V1 同步到V2，而不需要让Client知道。

Quorum机制分析

Quorum机制无法保证强一致性

所谓强一致性就是：任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。强一致性是程度最高的一致性要求，也是实践中最难以实现的一致性。

因为，仅仅通过Quorum机制无法确定最新已经成功提交的版本号。

比如，上面的V2 成功提交后（已经写入W=3份），尽管读取3个副本时一定能读到V2，如果刚好读到的是(V2，V2，V2），则此次读取的数据是最新成功提交的数据，因为W=3，而此时刚好读到了3份V2。如果读到的是（V2，V1，V1），则无法确定是一个成功提交的版本，还需要继续再读，直到读到V2的达到3份为止，这时才能确定V2 就是已经成功提交的最新的数据。

如何读取最新的数据？—在已经知道最近成功提交的数据版本号的前提下，最多读R个副本就可以读到最新的数据了。

如何确定 最高版本号 的数据是一个成功提交的数据？—继续读其他的副本，直到读到的 最高版本号副本 出现了W次。

基于Quorum机制选择 primary

中心节点(服务器)读取R个副本，选择R个副本中版本号最高的副本作为新的primary。

新选出的primary不能立即提供服务，还需要与至少与W个副本完成同步后，才能提供服务—为了保证Quorum机制的规则：W+R>N

至于如何处理同步过程中冲突的数据，则需要视情况而定。

比如，(V2，V2，V1，V1，V1），R=3，如果读取的3个副本是：(V1，V1，V1)则高版本的 V2需要丢弃。

如果读取的3个副本是（V2，V1，V1），则低版本的V1需要同步到V2。

多副本状态机

将多副本管理的模型抽象出来，可得到一个通用的模型：多副本状态机 (Replicated State Machine) 。

多副本状态机是指多台机器具有完全相同的状态，并且运行完全相同的确定性状态机。

通过使用这样的状态机，可以解决很多分布式系统中的容错问题。因为多副本状态机通常可以容忍半数节点故障，且所有正常运行的副本节点状态都完全一致，所以可以使用多副本状态机来实现需要避免单点故障的组件。

多副本状态机在分布式系统中被用于解决各种容错问题。如集中式的选主或是互斥算法中的协调者 (Coordinator)。集中式的领导者或互斥算法逻辑简单，但最大的问题是协调者的单点故障问题，通过采用多副本状态机来实现协调者实现了高可用的“单点”，回避了单点故障。

分布式协议

问：

一：

CP和AP的协议有哪些，请具体描述一下所有协议，和区别

CP（Consistency Protocol）和AP（Availability and Partition Tolerance）是分布式系统中两种不同的数据一致性协议。CP协议注重数据的强一致性，而AP协议则强调可用性和分区容忍性。

常见的CP协议包括：

1. 2PC（Two-Phase Commitment）：这是一种集中式的事务管理协议，通过协调器进行提交或回滚操作来实现所有节点的数据强一致性。
2. Paxos：这是一种去中心化的一致性协议，它保证系统能够在故障情况下仍然能够保持一致性。Paxos算法使用多个阶段（Proposal、Prepare和Accept）来达成一致，并且可以处理多个提案。
3. RAFT：RAFT也是一种去中心化的一致性协议，与Paxos类似。它将状态机复制为一组日志条目，并确保在节点发生故障时继续运行。

常见的AP协议包括：

1. BASE（Basically Available, Soft State, Eventually Consistent）：基本上可用、软状态、最终一致性。这种架构通过放松一致性要求以换取高可用性来实现系统的设计。在此方案下，更新可能需要更长时间才能在整个系统上进行传播，但最终系统将保持一致。
2. Gossip协议：这是一种去中心化的协议，它使用节点之间的随机沟通来传播信息和更新。在这种方案下，不同节点的状态可能会有所不同，但最终会达到一致性。
3. NoSQL数据库：NoSQL数据库强调高可用性和分区容忍性，并且通常放松了数据一致性的要求。例如，Cassandra数据库使用基于时间戳的多版本并发控制（MVCC）来实现最终一致性。

总之，CP协议注重数据的强一致性，而AP协议则强调可用性和分区容忍性。具体选择哪种协议取决于系统设计者的需求和目标。

CP

1、Paxos协议

Paxos算法详解 - 知乎 (zhihu.com)

Basic Paxos、Fast Paxos、Multi-Paxos – Proposal ID（一致性保证）

二、Paxos算法流程

Paxos算法解决的问题正是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。

Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，Paxos算法使所有提案中的某一个提案，在所有进程中达成一致。系统中的多数派同时认可该提案，即达成了一致。最多只针对一个确定的提案达成一致。

Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
• Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。

在多副本状态机中，每个副本同时具有Proposer、Acceptor、Learner三种角色。

Paxos算法中的角色

Paxos算法通过一个决议分为两个阶段（Learn阶段之前决议已经形成）：

1. 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
2. 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
3. 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。

Paxos算法流程

Paxos算法流程中的每条消息描述如下：

• Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。
• Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。

两个承诺：

\1. 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。

\2. 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。

一个应答：

不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。

• Propose: Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案 均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。
• Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。
• Learn: Proposer收到多数Acceptors的Accept后，决议形成，将形成的决议发送给所有Learners。

Paxos算法伪代码描述如下：

Paxos算法伪代码

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

下面举几个例子，实例1如下图：

Paxos算法实例1

图中P代表Prepare阶段，A代表Accept阶段。3.1代表Proposal ID为3.1，其中3为时间戳，1为Server ID。X和Y代表提议Value。

实例1中P 3.1达成多数派，其Value(X)被Accept，然后P 4.5学习到Value(X)，并Accept。

Paxos算法实例2

实例2中P 3.1没有被多数派Accept（只有S3 Accept），但是被P 4.5学习到，P 4.5将自己的Value由Y替换为X，Accept（X）。

Paxos算法实例3

实例3中P 3.1没有被多数派Accept（只有S1 Accept），同时也没有被P 4.5学习到。由于P 4.5 Propose的所有应答，均未返回Value，则P 4.5可以Accept自己的Value (Y)。后续P 3.1的Accept (X) 会失败，已经Accept的S1，会被覆盖。

Paxos算法可能形成活锁而永远不会结束，如下图实例所示：

Paxos算法形成活锁

回顾两个承诺之一，Acceptor不再应答Proposal ID小于等于当前请求的Prepare请求。意味着需要应答Proposal ID大于当前请求的Prepare请求。

两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。

三、Multi-Paxos算法

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

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

1. 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。
2. 在所有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的变形。

2、ZAB

• Zookeeper Atomic Broadcast
• Zookeeper 原子广播协议 – AP == ZXID（一致性保证

读 -

绝大多数的书和博客都没明确指出的是：对于ZooKeeper来说，Quorum机制只在一个Leader的广播阶段有效，对于新旧Leader的变更期间是无效的！对于发现和同步阶段，不同的算法，基于不同的考量，会选择不同的机制。由参考博客5可知，对于RAFT算法，在读阶段（相当于ZAB的发现和同步），即便前一任Leader提出的Proposal已经被半数的机器所接受，只要还没被commit，在极端情况下，都有可能被覆盖掉。因为新Leader只关注自身还没被commit的Proposal，而不关心其它机器的未commit的Proposal。

实际上，对于分布式数据的一致性问题，如果站在调用者（客户端）的角度来思考，当客户端发出的写操作请求，在集群执行该请求期间，恰巧发生了Leader更换，那么客户端最终收到的返回一定是一个不确定的结果（可能成功，也可能失败）。因而对于集群本身来讲，针对具体的业务场景，是采用消极的全部丢弃，还是采用积极地全部内部补偿，或者是介于消极和积极之间的某种策略，我认为都是合理的。但总的来说，无论这些算法采用什么样的策略，保证集群数据的一致性是必要的前提。

如果集群中的 Learner 节点收到客户端的事务请求，那么这些 Learner 会将请求转发给 Leader 服务器。然后再执行如下的具体过程：

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

3、Raft

深度解析 Raft 分布式一致性协议 - 掘金 (juejin.cn)

Raft详解

CP – term（一致性保证）

名词：选举，心跳，

核心

Raft 核心算法其实就是由这三个子问题组成的：选主（Leader election）、日志复制（Log replication）、安全性（Safety）。这三部分共同实现了 Raft 核心的共识和容错机制。

解决问题

Raft 也提供了几个工程实践中必须面对问题的解决方案。

第一个是关于日志无限增长的问题。Raft 将操作包装成为了日志，集群每个节点都维护了一个不断增长的日志序列，状态机只有通过重放日志序列来得到。但由于这个日志序列可能会随着时间流逝不断增长，因此我们必须有一些办法来避免无休止的磁盘占用和过久的日志重放。这一部分叫日志压缩（Log compaction）。

第二个是关于集群成员变更的问题。一个 Raft 集群不太可能永远是固定几个节点，总有扩缩容的需求，或是节点宕机需要替换的时候。直接更换集群成员可能会导致严重的脑裂问题。Raft 给出了一种安全变更集群成员的方式。这一部分叫集群成员变更（Cluster membership change）。

此外，我们还会额外讨论线性一致性的定义、为什么 Raft 不能与线性一致划等号、如何基于 Raft 实现线性一致，以及在如何保证线性一致的前提下进行读性能优化。

安全限制限制

保证日志复制的一致性

选举限制：
每个 candidate 必须在 RequestVote RPC 中携带自己本地日志的最新 (term, index)，如果 follower 发现这个 
candidate 的日志还没有自己的新，则拒绝投票给该 candidate。（日志可以未commit）
提交限制：
**Leader 只允许 commit 包含当前 term 的日志。**

线性一致性

Commit Index 和 Apply Index

一个提案只要被 leader commit 就可以响应客户端了，Raft 并没有限定提案结果在返回给客户端前必须先应用到状态机。所以从客户端视角当我们的某个写操作执行成功后，下一次读操作可能还是会读到旧值。

ZAB、RAFT、PAXOS核心区别

multi-paxos、raft和zab协议的核心区别 - 腾讯云开发者社区-腾讯云 (tencent.com)

由此，本文总结了这三种算法的三个核心的区别（欢迎拍砖）：

• Leader候选机器的差异

ZAB是具有最大ZXID编号（包括未commit的Proposal）的机器才有资格成为新的Leader；而RAFT则是具有最大已commit编号（不包括未commit的Proposal）的机器才有资格成为新的Leader；PAXOS则是任意机器都可以成为新的Leader。由此可见，对于ZAB协议，新任Leader无需考虑自身还未被commit的Proposal是该被舍弃还是该被继续提交（因为全都需要被继续提交，积极策略）；对于RAFT协议，新的Leader只会关心自身机器上还未commit的Proposal，因而即使某一个Proposal已经被其它半数以上的机器确认，也可能会被覆盖（消极策略）；对于PAXOS，由于任意机器都可以成为新的Leader，因而新的Leader需要和其它Acceptor进行通信，以确认哪些Proposal该提交，哪些该舍弃（本质上新旧Leader相当于同时有多个Leader的场景，介于积极和消极之间）。

• Quorum机制的作用范围差异

对于ZAB和RAFT，Quorum机制只在正常的Leader任期（广播阶段）内有效，对于同步/读阶段，两者都是以自身的Proposal为准，而不会关注其它机器的情况，其中ZAB是因为自身拥有了最新的Proposal，所以不需要关心；对于Paxos协议，Quorum机制在读阶段和写阶段（相当于ZAB的广播阶段）都有效，因而在读阶段需要和其它Acceptor进行沟通，以确认哪些该提交，哪些该作废。

• Leader数量的差异（不考虑极端情况）

ZAB和RAFT都是单Leader，而PAXOS则支持多Leader（当然，工业应用中，绝大多数还是采用单Leader策略）。

• 新Leader处理旧Leader还未commit消息的差异

《ZooKeeper Distributed Process COORDINATION》这本书说到，当新的Leader在恢复阶段，会尝试将本服务器上还未同步的消息同步给所有Follower，不过同步时使用的epoch将不再是旧Leader的epoch，而是新Leader的epoch，这意味着新的Leader需要修改自身的日志记录中的epoch值；相反，RAFT论文中说到，新的Leader不会直接将本服务器上旧term的未commit消息直接同步给Follower，而是通过将本服务器上新term的新的消息同步给Follower并最终commit的机制，来间接提交旧term的未commit的消息（Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property）。当然，RAFT不用新term提交旧消息的另一个原因是用旧的term便于进行日志追踪（reason about）。

AP

1、Distro

nacos的一致性协议distro介绍-阿里云开发者社区 (aliyun.com)

一致性算法 - Distro协议在Nacos的实践 - 腾讯云开发者社区-腾讯云 (tencent.com)

关键点

distro协议网上的资料比较少，因为它是阿里“自创的协议“，通过源码总结一下distro协议的关键点：

• distro协议是为了注册中心而创造出的协议；
• 客户端与服务端有两个重要的交互，服务注册与心跳发送；
• 客户端以服务为维度向服务端注册，注册后每隔一段时间向服务端发送一次心跳，心跳包需要带上注册服务的全部信息，在客户端看来，服务端节点对等，所以请求的节点是随机的；
• 客户端请求失败则换一个节点重新发送请求；
• 服务端节点都存储所有数据，但每个节点只负责其中一部分服务，在接收到客户端的“写“（注册、心跳、下线等）请求后，服务端节点判断请求的服务是否为自己负责，如果是，则处理，否则交由负责的节点处理；
• 每个服务端节点主动发送健康检查到其他节点，响应的节点被该节点视为健康节点；
• 服务端在接收到客户端的服务心跳后，如果该服务不存在，则将该心跳请求当做注册请求来处理；
• 服务端如果长时间未收到客户端心跳，则下线该服务；
• 负责的节点在接收到服务注册、服务心跳等写请求后将数据写入后即返回，后台异步地将数据同步给其他节点；
• 节点在收到读请求后直接从本机获取后返回，无论数据是否为最新。

场景

通过几个特殊场景来加深一下理解

• 某服务一段时间未发生心跳，被服务端摘除，该服务恢复后继续发送心跳，重新被注册；
• 服务端某节点宕机，不回复其他服务端节点的健康检查请求，则会被其他节点从健康节点列表中剔除，其他节点重新分配负责节点，依靠客户端的心跳重新建立完整的服务数据；
• A机房部署2节点，B机房部署3节点，组成一个集群，5个节点分别负责相应的服务，某时刻，两机房网络不通，导致A机房两个节点组成一个集群，B机房三个节点组成一个集群，即“脑裂问题”，在强一致性协议中，此时只可能A机房可用，B机房不可用，distro协议不处理脑裂问题，这种情况需要再细分两种：（1）客户端与A、B机房都联通，则一段时间随机请求的心跳之后，A、B集群中仍然有全量的服务，A、B正常（2）部分客户端与A联通，部分客户端与B联通，则部分服务注册到A，部分注册到B，A内部可以调用，B内部也可以调用，AB不可相互调用，这种极端情况比起强一致的情况要好一些，强一致协议会导致与A连通的服务可用，与B联通的服务不可用，A也调用不了B。

2、Gossip

分布式原理：一文了解 Gossip 协议 - 知乎 (zhihu.com)

一致性算法-Gossip协议详解一 - 简书 (jianshu.com)

集群部署

ChatGPT

一：集群

多节点集群部署方案有哪些，Redis，MySQL，ElasticSearch，Eureka，Nacos，Zookeeper等组件集群部署的区别有哪些

多节点集群部署是实现高可用性、负载均衡和容错性的重要手段之一。以下是一些常见的组件集群部署方案：

1. Redis：Redis支持主从复制、哨兵模式和Cluster模式等多种部署方式，其中Cluster模式是最具代表性的分布式部署方式，可以在不同节点上运行多个Redis实例，构成一个逻辑上的集群。Redis Cluster采用哈希槽分片算法，将数据存储到不同的节点上，并提供了自动故障迁移和重新平衡的功能。
2. MySQL：MySQL可以使用主从复制、多主互备、MySQL Group Replication和MySQL NDB Cluster等方式进行部署。其中主从复制和多主互备都是基于异步复制机制，可以实现读写分离和高可用性；而MySQL Group Replication则是基于事务日志复制的半同步复制，提供更高的数据一致性和可靠性；MySQL NDB Cluster则是一个完全分布式的高性能互联网数据库，支持内存中数据存储和并行查询处理等高级特性。
3. Elasticsearch：Elasticsearch可以使用多节点、分片和副本等机制实现集群部署，从而实现数据分布式存储和搜索。在分布式场景下，每个索引会被分成多个分片，每个分片可以独立地搜索和路由查询请求，并支持多个副本机制提供高可用性和容错性。
4. Eureka：Eureka是Netflix开源的服务注册中心，支持单节点、多节点和高可用部署。在多节点场景下，Eureka使用集群方式管理服务注册信息，并提供自我保护机制以避免网络分区造成的数据不一致问题。
5. Nacos：Nacos是阿里巴巴开源的注册中心和配置中心，支持Server-Server模式和Client-Server模式。在Server-Server模式下，Nacos使用Raft协议实现选举和复制机制，确保在故障或者节点变更时能够自动同步元数据；在模式下，则是通过客户端向服务器注册、发现和配置服务。
6. Zookeeper：Zookeeper是一个分布式的协调服务，可以用于分布式锁、配置管理、命名服务等功能。Zookeeper基于Paxos算法实现分布式一致性，将数据存储在内存中，并提供强一致性和高可用性。

组件集群部署的区别主要体现在数据一致性、性能、可靠性和可扩展性等方面。不同的应用场景可能需要考虑这些因素的权衡，选择合适的部署方式。

二：

分布式事务

分布式事务

什么是分布式事务：

seate：XA 、AT 规范实现2PC（preCommit、Commit、3PC（canCommit、preCommit、doCommit） + RollBack

TCC：预锁定资源、用锁定资源执行业务、回滚锁定资源

SAGA：编排式、协调式事务

Seata 分布式事务 XA 与 AT 全面解析-腾讯云开发者社区-腾讯云 (tencent.com)

10分钟说透Saga分布式事务-腾讯云开发者社区-腾讯云 (tencent.com)

什么是2PC

全局事务 | 凤凰架构 (icyfenix.cn)

XA 将事务提交拆分成为两阶段过程：

• 准备阶段：又叫作投票阶段，在这一阶段，协调者询问事务的所有参与者是否准备好提交，参与者如果已经准备好提交则回复 Prepared，否则回复 Non-Prepared。这里所说的准备操作跟人类语言中通常理解的准备并不相同，对于数据库来说，准备操作是在重做日志中记录全部事务提交操作所要做的内容，它与本地事务中真正提交的区别只是暂不写入最后一条 Commit Record 而已，这意味着在做完数据持久化后并不立即释放隔离性，即仍继续持有锁，维持数据对其他非事务内观察者的隔离状态。
• 提交阶段：又叫作执行阶段，协调者如果在上一阶段收到所有事务参与者回复的 Prepared 消息，则先自己在本地持久化事务状态为 Commit，在此操作完成后向所有参与者发送 Commit 指令，所有参与者立即执行提交操作；否则，任意一个参与者回复了 Non-Prepared 消息，或任意一个参与者超时未回复，协调者将自己的事务状态持久化为 Abort 之后，向所有参与者发送 Abort 指令，参与者立即执行回滚操作。对于数据库来说，这个阶段的提交操作应是很轻量的，仅仅是持久化一条 Commit Record 而已，通常能够快速完成，只有收到 Abort 指令时，才需要根据回滚日志清理已提交的数据，这可能是相对重负载的操作。

什么是3PC

• 三段式提交把原本的两段式提交的准备阶段再细分为两个阶段，分别称为 CanCommit、PreCommit，把提交阶段改称为 DoCommit 阶段。
• 其中，新增的 CanCommit 是一个询问阶段，协调者让每个参与的数据库根据自身状态，评估该事务是否有可能顺利完成。将准备阶段分为二的理由是这个阶段是重负载的操作，一旦协调者发出开始准备的消息，每个参与者都将马上开始写重做日志，它们所涉及的数据资源即被锁住，如果此时某一个参与者宣告无法完成提交，相当于大家都白做了一轮无用功。
• 所以，增加一轮询问阶段，如果都得到了正面的响应，那事务能够成功提交的把握就比较大了，这也意味着因某个参与者提交时发生崩溃而导致大家全部回滚的风险相对变小。
• 因此，在事务需要回滚的场景中，三段式的性能通常是要比两段式好很多的，但在事务能够正常提交的场景中，两者的性能都依然很差，甚至三段式因为多了一次询问，还要稍微更差一些。

什么是TCC

CC 较为烦琐，它是一种业务侵入式较强的事务方案，要求业务处理过程必须拆分为“预留业务资源”和“确认/释放消费资源”两个子过程。如同 TCC 的名字所示，它分为以下三个阶段。

• Try：尝试执行阶段，完成所有业务可执行性的检查（保障一致性），并且预留好全部需用到的业务资源（保障隔离性）。
• Confirm：确认执行阶段，不进行任何业务检查，直接使用 Try 阶段准备的资源来完成业务处理。Confirm 阶段可能会重复执行，因此本阶段所执行的操作需要具备幂等性。
• Cancel：取消执行阶段，释放 Try 阶段预留的业务资源。Cancel 阶段可能会重复执行，也需要满足幂等性。

什么是SAGE

分布式事务 | 凤凰架构 (icyfenix.cn)

SAGA 由两部分操作组成。

• 大事务拆分若干个小事务，将整个分布式事务 T 分解为 n 个子事务，命名为 T1，T2，…，Ti，…，Tn。每个子事务都应该是或者能被视为是原子行为。如果分布式事务能够正常提交，其对数据的影响（最终一致性）应与连续按顺序成功提交 Ti等价。
• 为每一个子事务设计对应的补偿动作，命名为C1，C2，…，Ci，…，Cn。Ti与 Ci必须满足以下条件：
  • Ti与 Ci都具备幂等性。
  • Ti与 Ci满足交换律（Commutative），即先执行 Ti还是先执行 Ci，其效果都是一样的。
  • Ci必须能成功提交，即不考虑 Ci本身提交失败被回滚的情形，如出现就必须持续重试直至成功，或者要人工介入。

RPC协议

面试题 ：有了 HTTP 协议，为什么还要有 RPC ？ | JavaGuide(Java面试 + 学习指南)

介绍：RPC基础知识总结 | JavaGuide(Java面试 + 学习指南)

纯裸 TCP 是能收发数据，但它是个无边界的数据流，上层需要定义消息格式用于定义 消息边界 。于是就有了各种协议，HTTP 和各类 RPC 协议就是在 TCP 之上定义的应用层协议。

RPC 本质上不算是协议，而是一种调用方式，而像 gRPC 和 Thrift 这样的具体实现，才是协议，它们是实现了 RPC 调用的协议。目的是希望程序员能像调用本地方法那样去调用远端的服务方法。同时 RPC 有很多种实现方式，不一定非得基于 TCP 协议。

从发展历史来说，HTTP 主要用于 B/S 架构，而 RPC 更多用于 C/S 架构。但现在其实已经没分那么清了，B/S 和 C/S 在慢慢融合。 很多软件同时支持多端，所以对外一般用 HTTP 协议，而内部集群的微服务之间则采用 RPC 协议进行通讯。

RPC 其实比 HTTP 出现的要早，且比目前主流的 HTTP1.1 性能要更好，所以大部分公司内部都还在使用 RPC。

HTTP2.0 在 HTTP1.1 的基础上做了优化，性能可能比很多 RPC 协议都要好，但由于是这几年才出来的，所以也不太可能取代掉 RPC。

汲取