CAP理论

简述CAP理论

  • **数据一致性 (Consistency)**：如果系统对一个写操作返回成功，那么之后的读请求都必须读到这个新数据；如果返回失败，那么所有读操作都不能读到这个数据。对调用者而言数据具有强一致性。
  • **服务可用性 (Availability)**：所有读写请求在一定时间内得到响应，可终止、不会一直等待。
  • **分区容错性 (Partition Tolerance)**：在网络分区的情况下，被分解的节点仍能正常对外服务。

如果选择了CA而放弃了P，那么当发生分区现象时，为了保证C，系统需要禁止写入，当有写入请求时，系统返回error，这又和A冲突了，因为A要求返回no error和no timeout。因此，分布式系统理论上不可能选择CA架构，只能选择CP或者AP架构。

反证：
如果CAP三者可同时满足，由于允许P的存在，则一定存在节点之间的丢包，如此则不能保证C。因为允许分区容错，写操作可能在节点1上成功，在节点2上失败，这时候对于Client1（读取节点1）和Client2（读取节点2），就会读取到不一致的值，出现不一致的情况。如果要保持一致性，写操作必须同时失败，也就是降低系统的可用性。

Base理论

简述BASE理论

BASE理论是CAP理论的一种妥协，由于CAP只能二取其一，BASE理论降低了发生分区容错时对可用性和一致性的要求。

  1. **基本可用 (Basically Available)**：允许可用性降低（可能响应延长、可能服务降级）。
  2. **软状态 (Soft State)**：指允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性。
  3. **最终一致性 (Eventual Consistency)**：节点数据同步可以存在时延，但在一定的期限后必须达成数据的一致，状态变为最终状态。

数据一致性模型

数据一致性模型有哪些

强一致性：当更新操作完成之后，任何多个后续进程的访问都会返回最新的更新过的值。这种是对用户最友好的，即用户上一次写什么，下一次就保证能读到什么。根据 CAP 理论，这种实现需要牺牲可用性。

弱一致性：系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体承诺多久之后可以读到。用户读到某一操作对系统数据的更新需要一段时间，我们将这段时间称为“不一致性窗口”。

最终一致性：最终一致性是弱一致性的特例，强调的是所有的数据副本，在经过一段时间同步之后，最终都能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。到达最终一致性的时间，就是不一致窗口时间，在没有故障发生的前提下，不一致窗口的时间主要受通信延迟、系统负载和复制副本的个数影响。

最终一致性模型根据其提供的不同保证可以划分为更多的模型，包括因果一致性和会话一致性等。

因果一致性：要求有因果关系的操作顺序得到保证，非因果关系的操作顺序则无所谓。

进程 A 在更新完某个数据项后通知了进程 B，那么进程 B 之后对该数据项的访问都应该能够获取到进程 A 更新后的最新值，并且如果进程 B 要对该数据项进行更新操作的话，务必基于进程 A 更新后的最新值。

例如在微博或者微信进行评论的时候，比如你在朋友圈发了一张照片，朋友给你评论了，而你对朋友的评论进行了回复，这条朋友圈的显示中，你的回复必须在朋友之后，这是一个因果关系，而其他没有因果关系的数据，可以允许不一致。

会话一致性：将对系统数据的访问过程框定在一个会话当中，约定了系统能保证在同一个有效的会话中实现“读已之所有”的一致性。就是在你的一次访问中，执行更新操作之后，客户端能够在同一个会话中始终读取到该数据项的最新值。实际开发中有分布式的 Session 一致性问题，可以认为是会话一致性的一个应用。

Quorum、WARO机制

**WARO (Write All Read One)**：一种简单的副本控制协议。写操作时，只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。优先保证读，任何节点读到的数据都是最新数据，牺牲了更新服务的可用性。只要有一个副本宕机，写服务就不会成功。但只要有一个节点存活，仍能提供读服务。

Quorum 机制：假设有10个副本，一次成功更新了三个，那么至少需要读取八个副本的数据，可以保证读到最新的数据。无法保证强一致性，即无法实现任何时刻任何用户或节点都可以读到最近一次成功提交的副本数据。需要配合一个获取最新成功提交的版本号的 metadata 服务，这样可以确定最新已经成功提交的版本号，然后从已经读到的数据中就可以确认最新写入的数据。

假如一共n个副本，要更新m个，那就需读取n-m+1个副本。

PAXOS算法

一种共识算法。

Paxos算法是用于解决分布式系统中就某个值（决议）达成一致性问题的一种协议。典型应用场景是确保分布式数据库中各个节点在执行相同操作序列后能保持最终一致性。在Paxos中，系统包含三种角色：Proposer（提议者）、Acceptor（接受者） 和 Learner（记录员）。

  • Proposer：负责提出提案。只要其提案被半数以上的 Acceptor 接受，就认为该提案的值（value）已被选定。
  • Acceptor：负责响应提案。一旦接受了某个提案，就认为该提案的值被选定。
  • Learner：不参与提案过程，负责学习被选定的值，通常由 Acceptor 通知其哪个值被最终确认。

Paxos算法的两个阶段

阶段一：Prepare（准备阶段）

(a) Proposer 选择一个唯一的提案编号 N，并向半数以上的 Acceptor 发送编号为 N 的 Prepare 请求。
(b) Acceptor 收到 Prepare 请求后：

  • 如果该节点已有已提交的 value 记录，且记录的编号大于 N，则拒绝响应；
  • 如果记录的编号小于或等于 N，则返回该记录的 value 及编号；
  • 如果没有已提交记录，则判断本地是否已有编号 N1：
    • 如果 N1 > N，拒绝响应；
    • 否则，将本地编号更新为 N（如无编号则记录 N），并响应 Prepare。

阶段二：Accept（接受阶段）

(a) 如果 Proposer 收到半数以上 Acceptor 对 Prepare 请求的响应，则它会发送一个针对 [N, V] 提案的 Accept 请求给半数以上的 Acceptor。其中 V 是收到的响应中编号最大的 value；如果所有响应中均不包含 value，则 V 由 Proposer 自行决定。
(b) Acceptor 收到 Accept 请求后：

  • 如果本地记录的编号小于或等于 N，则接受该提案，提交记录 value；
  • 否则拒绝该请求。

如果 Proposer 收到大多数 Acceptor 的 Accept 响应，则认为该 value 被选定，并通知 Learner 进行记录，同时同步给未响应的 Acceptor 以达成一致。

活锁问题

Paxos 可能遇到活锁（livelock）问题：当多个 Proposer 同时不断提出编号递增的提案，并互相覆盖对方的 Accept 请求，导致系统无法最终选定一个值。例如，一个 Proposer 在 Accept 阶段被拒绝后，会增大提案编号 N 并重新发起 Prepare，而此时另一个 Proposer 也执行相同操作，造成 Accept 持续失败，算法无法完成。

Multi-Paxos 优化

Multi-Paxos 是对基础 Paxos 的扩展，用于高效确定多个值（即多个决议）。其核心思想是：

  • 在第一次成功 Accept 后，系统在接下来的一段时间内，不再接受其他节点的 Prepare 请求，从而避免重复的准备阶段。
  • 此时，该节点成为 Leader，后续提案可以直接进入 Accept 阶段，提升效率。
  • 只有当 Accept 请求被拒绝，或 Leader 失效时，节点才重新发起 Prepare 请求，竞争 Leader 资格，以继续提案流程。

_2025-10-04_212830_141.png

问题解析

Q: PAXOS解决了什么问题？
A: Paxos算法解决的核心问题是：在一个可能发生机器宕机、网络延迟或消息丢失的不可靠分布式环境中，如何让网络中的所有节点就某个值（Value）达成一致。它通过为每一条指令执行一次共识过程，解决了分布式状态机的指令序列一致性问题。

“解决了指令问题”的含义：
在分布式系统（如分布式数据库）中，为了保证所有节点的最终状态一致，它们必须按照相同的顺序执行相同的指令集。Paxos的作用就是在每一条指令上执行一次共识过程，来确定“下一条要执行的指令是什么”。这样，即使有节点故障或网络问题，整个系统也能就指令序列达成一致，从而保证状态机的一致性。可以说，Paxos是实现分布式状态机复制的基石。

Q: 状态机和数据库的区别？
A: 状态机的核心是“过程”和“状态转移”，它按确定顺序应用指令来改变状态，数据通常带有版本号。数据库的核心是“数据的存储、查询和管理”，是状态机状态的持久化载体。状态机定义变化规则，数据库保存变化结果。

Q: 有请求就有编号是什么意思？
A: 这是Paxos的核心设计，指每个提案都必须附带一个全局唯一且递增的编号。Acceptor根据这个编号来判断优先级：它只响应编号高于它已承诺编号的请求，并拒绝编号更低或相等的请求。这建立了全局顺序，避免了冲突，确保了高优先级提案能胜出。

Q: 为什么哪个值最先被确定，就一定会被持久化？
A: 因为一个值被“确定”意味着它被半数以上的Acceptor接受。任何后续提案都必须与半数以上的Acceptor通信，这两个半数集合必然存在交集。交集内的Acceptor会强制后续提案者继承已被确定的值，从而保证了该值一旦被确定，就会被永久保持，无法被更改或覆盖。

Q: 一个节点如何知道集群中存在哪些“其他节点”？
A: 这不是Paxos算法解决的，而是通过系统配置实现。主要有两种方式：静态配置（在配置文件中预先列出所有节点的地址）或动态服务发现（节点在启动时向一个中心化的注册中心注册和查询）。Paxos算法在已知的节点集合上运行。

raft算法

Raft 算法是一种用于实现分布式系统一致性的共识算法。它通过明确的角色划分和阶段分离，相比 Paxos 更易于理解。其核心目标是管理一个复制状态机，并通过日志复制保证所有节点最终状态一致。

核心概念

1. 三种节点状态
一个节点在任意时刻处于以下三种状态之一：

  • Leader（领导者）：处理所有客户端请求。如果客户端将请求发给 Follower，Follower 会将请求重定向给 Leader。
  • Follower（跟随者）：被动角色，不会发送任何请求，仅响应来自 Leader 或 Candidate 的 RPC 请求。
  • Candidate（候选人）：用于选举产生新的 Leader 的临时状态。

2. 任期（Term）

  • Term 是一个单调递增的编号，标志着 Leader 的统治时期。
  • 每个 Term 至多只有一个 Leader（也可能因选举失败而没有）。
  • Term 编号存储在日志条目（log entry）中，标识该条目是哪个任期内写入的。
  • 每次 RPC 通信都会携带 Term 编号。若节点发现收到的 RPC 中 Term 比本地大，则更新本地 Term 并切换为 Follower；若收到的 Term 比本地小，则拒绝该 RPC。

3. 两种 RPC 通信

  • RequestVote RPC：由 Candidate 在选举期间发起，用于拉取选票。
  • AppendEntries RPC：由 Leader 发起，用于复制日志条目和发送心跳（不包含日志的心跳也是一种 AppendEntries RPC）以维持权威。

4. 日志序列

  • 每个节点维护一份持久化的日志序列（Log），日志由多个有序的条目组成。
  • 一致性算法保证所有节点上的日志序列最终保持一致。
  • 每个日志条目包含：
    • 命令（客户端请求的操作）
    • 任期号（Term）
    • 索引号（Log Index）

5. 状态机

  • 当日志条目被安全地复制到多数节点后，Leader 将其提交（commit）。
  • 提交意味着将日志条目中的命令应用到状态机中，从而改变系统状态。
  • Leader 通过后续的 AppendEntries RPC（携带最后提交的索引 lastIndex）通知所有 Follower 提交相应的日志条目到各自的状态机。

选举机制

何时触发选举？

  1. 集群初始化：所有节点启动时均为 Follower。随后，每个节点随机设置一个选举超时时间（Election Timeout）。
  2. Leader 故障：Follower 在选举超时时间内未收到来自 Leader 的心跳（即 AppendEntries RPC），则会主动触发选举。

选举过程（从发起选举的节点视角）

  1. 状态转换：节点增加本地的当前任期号（Term），并切换至 Candidate 状态。
  2. 自投票：首先投票给自己。
  3. 发起拉票：并行向集群中其他所有节点发送 RequestVote RPCs。
  4. 等待与处理结果：
    • 4.1 赢得选举：如果收到来自多数节点的投票，则该节点赢得选举，立即切换为 Leader 状态，并立刻向所有节点发送心跳消息以确立权威。
    • 4.2 他人胜出：如果在等待过程中，收到来自其他节点的 RPC，且其中包含的 Term 大于或等于 自己的当前 Term，并表明已有合法 Leader，则该节点承认结果，切换回 Follower 状态。
    • 4.3 选举超时：如果一段时间内既未赢得选举，也未收到新 Leader 的心跳，则保持 Candidate 状态，增加任期号，然后重新发起新一轮选举。

其他节点的投票逻辑

  • 每个节点在一个任期内最多只能投一票，遵循先来先得的原则。
  • Candidate 必须包含足够新的日志信息才会获得投票。具体来说，投票者会比较自己和 Candidate 最后一条日志的 (lastTerm, lastIndex)：
    • 如果 Candidate 的最后日志任期号更大，则投票。
    • 如果任期号相同，但 Candidate 的日志索引更大或相等，则投票。
    • 否则拒绝投票。这一机制确保了新选出的 Leader 一定包含所有已提交的日志条目。

lastIndex:最后一条数据的数据的索引号

lastTerm:本地最新的任期号

日志复制

日志同步流程

  1. 客户端请求：客户端向 Leader 发送命令。

  2. 本地追加：Leader 将命令作为一个新的日志条目追加到自己的日志序列中。

  3. 广播复制：Leader 通过 AppendEntries RPC 将新条目并行发送给所有 Follower。该 RPC 包含前一个日志条目的索引（prevLogIndex）和任期号（prevLogTerm），用于日志一致性检查。

  4. Follower 一致性检查：

    • 匹配成功：如果 Follower 在本地日志中找到了与 prevLogIndex 和 prevLogTerm 匹配的条目，则接受新条目，将其追加到本地日志。
    • 匹配失败：如果找不到匹配的条目，则拒绝该请求。Leader 收到拒绝后，会减小 prevLogIndex，重发 RPC，逐步回溯直到找到一致的日志点。此后，Leader 会强制覆盖 Follower 该点之后的所有日志，使其与自己的日志保持一致。

    强制覆盖： 直接删除index不连续的日志

  5. 提交与应用：

    • 一旦新的日志条目被复制到多数节点上，Leader 就认为该条目是已提交（Committed） 的。
    • Leader 首先在本地状态机中应用（执行）该条目，然后将结果返回给客户端。
    • 在后续的 AppendEntries RPC（包括心跳）中，Leader 会携带最新的已提交索引 lastIndex。
    • Follower 收到后，将本地日志中所有索引小于等于 lastIndex 的已提交条目应用到自己的状态机。

安全性约束

  • 领导人完整性原则（Leader Completeness）：新选举出的 Leader 一定拥有所有已提交的日志条目。这是通过选举时的投票限制（Candidate 的日志必须至少和投票者一样新）来保证的。
  • 提交前序任期条目：Leader 不能直接提交前任期的日志条目，只能通过提交当前任期的日志条目来间接提交之前任期的条目。这是为了防止已被提交的日志条目被后续的领导者覆盖。

安全原则

  • 选举安全原则（Election Safety）：对于一个给定的任期号，最多只会有一个领导人被选举出来。
  • 状态机安全原则（State Machine Safety）：如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会应用一个不同的日志条目。这确保了所有状态机最终执行相同的命令序列。
  • 领导人完全性原则（Leader Completeness）：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中。
  • 日志匹配原则（Log Matching）：如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全相同。

如果需要将此内容整理为流程图或与其他算法进行对比，可继续提出。

raft算法示意图：

Q: 随机超时是什么意思？
A: 它是Raft触发选举的机制。每个Follower在启动或收到心跳后，会设置一个随机的选举超时时间（如150-300ms）。在此期间如果未收到心跳，它就会超时并切换为Candidate发起选举。随机性确保了多个Follower不会同时竞选，避免了选票被瓜分，从而提高了选举成功率。

Q: 心跳是什么？
A: 心跳是Leader周期性发送给所有Follower的、不包含日志条目的 AppendEntries RPC。它的主要目的是维持Leader的权威，通过让Follower重置其选举超时定时器，来阻止它们发起新的选举。同时，心跳也用于通知Follower已提交的日志索引。

Q: 如何避免出现>=2个leader？
A: Raft通过多重安全机制来严格避免脑裂：

  • 任期机制： 节点只响应任期号不低于自己的请求。发现更高任期的节点会立即切换为Follower。
  • 大多数投票原则： 一个Candidate必须获得集群半数以上的投票才能当选。由于任意两个“大多数”集合必然相交，不可能在同一任期内产生两个Leader。
  • 一节点一票： 每个节点在一个任期内只能投一次票。
  • 选举限制： Follower只会投票给日志不比自己旧的Candidate，这确保了Leader的日志完整性。

问题解析：

1. PAXOS解决了什么问题？

Paxos算法解决的核心问题是： 在一个可能发生机器宕机、网络延迟或消息丢失的不可靠分布式环境中，如何让网络中的所有节点就某个值（Value）达成一致，并且这个值一旦被确定，就是不可变的、永久的。

“解决了指令问题”的含义：
在分布式系统（如分布式数据库）中，为了保证所有节点的最终状态一致，它们必须按照相同的顺序执行相同的指令集。Paxos的作用就是在每一条指令上执行一次共识过程，来确定“下一条要执行的指令是什么”。这样，即使有节点故障或网络问题，整个系统也能就指令序列达成一致，从而保证状态机的一致性。可以说，Paxos是实现分布式状态机复制的基石。

2. 状态机和数据库的区别

这是一个很好的概念性问题，它们关注点不同：

  • 状态机：
    • 核心是“过程”和“状态转移”。它从一个初始状态开始，接收一系列输入（命令/指令），每个命令都会使状态机从一个确定的状态转移到另一个确定的状态。
    • 强调确定性： 相同的初始状态和相同的命令序列，必须得到相同的最终状态。
    • 数据是状态的一部分： 状态机中的数据（即状态）通常带有版本号或任期号（在Paxos/Raft中就是日志索引和任期Term）。每次更改状态（应用一条新指令），版本号都会递增。这保证了状态变更的顺序性和可追溯性。
  • 数据库：
    • 核心是“数据的存储、查询和管理”。它更关注数据的持久化、一致性（ACID特性）、查询效率和事务处理。
    • 是状态机的一种持久化载体： 你可以将一个状态机的“状态”存储在一个数据库中。状态机负责决定“状态如何变化”，而数据库负责“将变化后的状态安全地存下来”。
    • 版本号可能不是核心机制： 数据库本身可能使用MVCC（多版本并发控制）等技术，但其核心接口是读写数据，而不是严格按顺序应用指令。

简单比喻：

  • 状态机就像一台录像机，它严格按顺序播放录像带（指令序列），屏幕上的画面（状态）随之变化。画面本身带有时间戳（版本号）。
  • 数据库就像一本笔记本，你可以随时翻到某一页去读或写。虽然它有页码，但其主要功能是记录内容，而不是定义翻页的规则。

在Paxos/Raft中，我们正是用日志来记录那个不可变的指令序列，而状态机负责按日志顺序执行这些指令，从而保证所有节点的状态一致。

3. “有请求就有编号”是什么意思？

这句话精炼地概括了Paxos算法的核心设计之一：通过编号（提案编号 N）来建立全局顺序和确定优先级。

具体解释如下：

在Paxos的Prepare阶段，Proposer会生成一个全局唯一且递增的提案编号N，然后发给Acceptor。

对于Acceptor来说，这个编号N是判断是否响应的唯一依据，其承诺规则可以简化为：

  • “如果收到的请求编号 N > 我已承诺的最小编号，我就响应，并承诺不再接受任何编号小于 N 的提案。”
  • 你问题中的表述 **“请求编号 <= 现有编号 就拒绝”** 是从反面说的，更准确的描述是：**Acceptor会记录它已响应过的最大Prepare请求编号 max_n。如果收到一个编号为 N 的Prepare请求，且 N <= max_n，则它会拒绝这个请求。** 只有当 N > max_n 时，它才会响应并更新 max_n = N。

为什么这么做？
这解决了分布式环境中的“活锁”和“冲突”问题。编号建立了绝对的优先级：高编号的提案可以覆盖低编号的提案，从而确保即使有多个Proposer在竞争，最终也能有一个提案（通常是编号最大的那个）成功被接受，使系统达成一致。

4. 为什么哪个值最先被确定，就一定会被持久化？

这个结论源于Paxos算法的安全性和“大多数派”原则。

  1. “确定”的定义： 在Paxos中，一个值V被“确定”，意味着它已经被半数以上的Acceptor节点接受。
  2. “持久化”的保证： 任何后续的Proposer想要提出提案，都必须先执行Prepare阶段，并向半数以上的Acceptor发送请求。
  3. 关键推理（交集原则）： 由于两次“半数以上”的集合必然存在至少一个公共的Acceptor（数学上的交集不为空），这个公共的Acceptor已经接受了之前被确定的值V。
  4. 算法的强制规定： 根据Paxos算法规则，这个公共Acceptor在响应新的Prepare请求时，必须将它已经接受过的值（也就是V）返回给新的Proposer。而新的Proposer在生成提案时，必须选择收到的响应中编号最高的那个值作为自己的提案值。

因此，流程是这样的：

  • 值V被确定 → 半数以上Acceptor接受了V。
  • 新Proposer发起提案 → 向半数以上Acceptor执行Prepare。
  • 必然存在一个Acceptor既接受了V，又响应了新Proposer → 这个Acceptor会把V返回给新Proposer。
  • 新Proposer必须使用V作为提案值 → 新提案成功被接受后，被确定的值依然是V。

所以，一旦一个值被确定，无论发生任何节点故障、重启或新的提案，这个值都会被后续的提案所继承和巩固，从而实现了“持久化”。这是Paxos算法最核心的安全保证。

5. 一个节点如何知道集群中存在哪些“其他节点”？

这并不是Paxos算法本身解决的问题，而是分布式系统在配置和初始化阶段需要解决的。主要有以下几种方式：

  1. 静态配置： 最常见的方式。在系统启动前，就在每个节点的配置文件中明确列出集群中所有节点的网络地址（IP和端口）。这样，每个节点启动时，都清楚地知道需要与哪些“其他节点”进行通信。
    • 例如：在 cluster.conf 中写入 node1=192.168.1.101:8000, node2=192.168.1.102:8000, node3=192.168.1.103:8000。
  2. 动态服务发现： 在更复杂的云环境中，节点的IP可能是不固定的。这时，节点会使用一个外部的服务发现系统（如 ZooKeeper, Etcd, Consul 或 Kubernetes Service）。
    • 流程： 节点启动后，向服务发现系统进行注册。当它需要与其他节点通信时（比如发起Paxos提案），它先去服务发现系统查询当前所有已注册的健康节点列表。
  3. 广播/组播： 在某些局域网环境中，节点可以通过广播或组播消息来发现彼此。一个节点上线后发送广播消息“我来了”，其他节点收到后将其加入自己的节点列表。

总结： “判断其他节点”是一个运维和架构层面的问题，通过预先静态配置或运行时动态发现来解决。而Paxos算法是在已知节点集合的基础上，来解决这些节点之间如何达成共识的问题。