分布式经典理论及算法一览

2025年04月28日 3.7k 字大概 15 分钟

CAP（Consistency、Availability、Partition Tolerance）

3个性质
- 一致性（Consistency） : 所有节点访问的数据都是最新版本
- 可用性（Availability）: 可用节点可正常响应请求
- 分区容错性（Partition Tolerance） : 分布式系统出现网络分区时，仍然能够对外提供服务
“3 选 2问题” ：如果出现网络分区（并保证了P，即就算分区，系统也仍然可用），C/A只能保证一个（CP or AP）
- CP架构：保证访问请求能得到一致性的数据结果
  - zookeeper获取服务列表时，如果zk正在选举或者zk集群中半数以上的机器不可用，那么将无法获取数据。不能保证服务可用性。
- AP架构：保证请求能正常响应
  - eureka优先保证可用性，每一个节点都是平等的，只要有一台eureka存在则服务可用，只不过有可能这个服务上的信息并不是最新的信息
  - redis的复制模式是属于AP，所以它的分布式锁可能会因为网络分区被多个线程使用（锁被占用没有同步到其他节点）

BASE（Basically Available、Soft-state、Eventually Consistent）

BASE 理论本质是对 CAP 中 AP 方案的一个补充：强调在保证可用性下，最终结果具有一致性
3个理念
- Basically Available（基本可用）：保证系统出现故障仍有一定可用性
- Soft-state（软状态）：不同节点的数据可以有一段时间不同步，数据状态处于一种临界状态
- Eventually Consistent（最终一致性）：保证最终所有副本收敛一致（最终一致性有多种变体，基于最终一致下对一致性提出限制）
  - Causal consistency（因果一致性）：存在因果关系的数据顺序不能颠倒
  - Read-your-writes consistency （读己所写一致性）：自己写的数据，一定能立刻读到
  - Monotonic read consistency （单调读一致性）：读的版本不能低于之前读的版本
  - Monotonic write consistency （单调写一致性）：写的顺序应该与请求顺序一致
  - Session consistency （会话一致性）：在单个客户端会话中，一般要求上面的一致性都需要满足

Consensus（共识算法，实现分布式系统的一致性）

Paxos 算法(Basic Paxos)

算法目的：多节点共同设定同一个变量的值时，确定最终值应该是哪个，即达成共识（一旦达成共识，该值不会再被改变）。保证多副本数据强一致性与分区容错性
3个重要角色（每个节点可以同时担任多个角色）
- 提议者（Proposer）：提议者负责接受客户端的请求并发起提案
  提议者会产生的值
  - 提案号N：全局唯一且递增（比如时间戳+ip地址）
  - 设定值value：初始是客户端打算设定的值
- 接受者（Acceptor）：对提议者的提案进行投票，提案只有被超过半数接收者批准才能通过，同时需要记住自己的投票历史（以前通过的提案设定的值）
  接受者会记录的值
  - 接受过的最大提案号max_N
  - Accept过的提案的提案号ac_n和ac_value（初始均为空）
- 学习者（Learner）：学习者学习被通过的提案的值
算法流程：分为2阶段（准备阶段(prepare)，接受阶段(accept)）
1. 准备阶段
  1. 提议者生成提案号,发送prepare(N)给所有接受者
  2. 接受者收到准备请求后
    - 若N大于max_N，修改max_N，并返回promise(N)以及ac_n和ac_value。承诺不会接受编号小于N的提案
    - 若N小于max_N，不回复或回复拒绝
2. 接受阶段
  1. 一定时间后，提议者收到接受者们的请求回复
    - 若批准数量大于一半，则准备发送接受请求accept(N,value)
      - 若返回的promise携带value均为空，则使用自己的value发送接受请求
      - 存在promise的value不为空，使用ac_n最大的ac_value代替自己的value发生接受请求
    - 若批准数量少于一半，则转到准备阶段生成新提案重新尝试
  2. 接受者收到接受请求后
    - 若N>=max_N，则回复accepted并持久化N和value
    - 若N小于max_N，不回复或回复拒绝
  3. 一定时间后，提议者收到接受者们的接受回复
    - 若接受数量大于一半，说明达成共识（最后系统每个节点一定是这个共识的值），此时提议者可以广播给所有提议者/学习者达成共识的value
    - 若接受数量少于一半，则转到准备阶段生成新提案重新尝试
两阶段提案如何确定共识成立（两个多数派必相交）
- 假设提议者a和提议者b的提案号和设定值分别为(1,va),(2,vb)，则接受者只会出现如下情况
  - 超过一半的promise(2)：最终共识值一定是vb。a即使之前提案被通过，他的accept最终也不会被接受
  - 超过一半的接受者accept(1,va)：最终共识值一定是va。说明prepare(2)来晚了，虽然接受者接受提案，但是返回了之前接受的va，所以提议者b最终提案的值从vb修改成了va
活锁问题如何解决
1. 问题定义
  - 假设提议者a和提议者b的提案号和设定值分别为(1,va),(2,vb)
  - 一开始a发生准备请求，通过，接着b发送准备请求，也通过
  - a再发送接受请求，被拒绝，此时a重新尝试，发送准备请求（3，va），通过
  - b这时才发送接受请求(2,vb),被拒绝，b重新尝试，发送新的准备请求（4，vb），通过
  - 此时a发送的接受请求又被拒绝了便再次尝试，这样反复循环，陷入活锁现象（虽然一直锁住的概率不大）
2. 一种简单的解决方法是，对于该变量，初始先选举一个Leader（领导者），只有领导者可以提出提案，则不存在活锁问题
Multi Paxos 思想
- 定义：注重如何对多个变量/实例达成共识（该思想有多种算法实现，如Raft、ZooKeeper以及Chubby等，但核心思想是共通的）
- 思想：选举一个全局leader负责对所有实例提案（需要考虑leader如何续期），全局leader可以对所有实例一个一个达成共识，则又变成basic paxos算法

Raft 算法（Multi Paxos 思想的一种实现）

基本介绍

raft名称的由来：确保节点间的共识即确保大多数节点的日志(Log)一致
- 一个木筏（Raft，分布式系统）是由多根整齐一致的原木（Log，日志）组成的，原木由木质材料（Log entry，日志项）组成
- 一个合格的raft需要保证其大多数的log一致，即需要保证日志的每一个commit的log entry内容一致，这样log的每个日志项应用(apply)到状态机后，各个节点状态机才会一致
raft核心思想：raft集群通过选举一个leader节点来处理所有外来操作（只有leader存活，raft集群才能对外服务）
- 因此raft算法就是围绕如何选主，如何复制日志来进行
3种重要节点角色（状态）
- Leader: 接收客户端发起的操作请求，写入本地日志后同步至集群（通过判断是否被大多数节点写入日志来决定是否执行（commit）
- Follower: 从 leader 接收log entry
- Candidate: 如果 follower 在一定时间内没有收到 leader 的心跳，则切换为Candidate发起选举，直到发现新leader

选主

何时选举leader
1. 每个leader都会有一个任期（term，全局严格递增），每个follower也会标识其所属leader的任期
2. 每个follower都会有一个随机超时时间（ttl），一旦超时则将自身所属任期+1，转为Candidate并发起选举（并投自己一票）
  - leader在任期间会持续向所有节点发送心跳包刷新ttl
3. 如果当前任期无法获得大多数（N/2+1，N为配置的集群节点数）节点的投票，立刻开始下一个任期的选举
如何成为leader
1. 候选人发起投票时，会携带自己最新的(term,index)；每个节点一个任期只能投一票，且只能投给日志项不旧于自身的节点
  - 保证最终的leader一定是具有相对完整日志的节点（拥有所有committed的日志，因为其日志不落后于大多数节点）
2. 候选人获得大多数票才能成为leader
3. 任何状态下，若如果收到>=自己当前任期的leader心跳包，说明出现当前leader，则Candidate/old leader把自己转为follower

日志

日志项的组成

log index：日志索引
term：创建这条日志项的领导者的任期编号
客户端指令

日志一致性的实现

日志一致性的2个保证：当不同的节点日志集合中的两个日志条目拥有相同的 term 和 index时
1. 它们一定存储了相同的指令：
2. 它们之前的所有日志条目也全部相同
  - leader与每个节点同步日志时，会携带上一条日志的 (term, index)
  - follower只有上一条匹配，才能接受leader的新日志项
  - 否则需要把前面不匹配的都覆盖掉
commit操作
- 日志项只有被大多数节点持久化（写入日志）才能被leader标记为commit，日志项只有被commit后才能被状态机应用(apply)
- 日志项一旦被commit，保证其操作一定生效
- 每个leader只能commit所属任期的日志项，不能直接commit以往任期的
  - 安全性保证：防止被commit的日志项因为leader宕机后被新leader覆盖
  - 当前任期的日志项被commit，本质间接commit之前的所有日志项（大多数节点都写入该日志项前，必须保证前面的日志项都与leader一致）
- commitIndex：所有已提交日志项的最高索引
  - 节点commit日志项时，会刷新commitIndex
  - 状态机apply日志项实际是使用所有index<=commitIndex的日志项

日志压缩

快照（Snapshot）：快照当前状态机，并丢弃过期旧日志
leader会将snapshot发给日志落后太多的follower

集群成员变更

单节点变更（single-server changes，易于实现，常用）
- 思想：一次只变更一个节点
  - 单节点的加入/离开，不会导致系统脑裂
  - 新配置、旧配置的集合的大多数必定存在一个节点重叠，因此最终只存在一个大多数
- 切换步骤：leader向新节点同步以往数据后，生成新集群配置同步到所有节点
联合共识（Joint Consensus）
- 划分3个集合，防止脑裂
  - C-old：旧集群集合
  - C-new：新集群集合
  - C-old，new：C-old ∪C-new（其大多数必须同时满足C-old的大多数和C-new的大多数）
- 切换步骤
  1. leader会先生成C-old，new并立刻apply，同时包装成日志让其他节点立刻apply，当大多数节点切换为C-old，new状态时，将该日志commit
    - 未commit前，leader是由c-old大多数确定
    - commit后，leader由c-old,new的大多数决定,不再可能是c-old状态的节点（得不到c-new集合的投票）
  2. leader接着将 C-new 包装为日志同步给其它节点。节点发现自己不在c-new时退出集群，大多数节点切换为C-new状态时，将该日志commit并响应客户端成功
    - 未commit前，leader无论是C-old，new状态还是C-new状态，都需要c-new的大多数确定，leader唯一

raft强一致性读（线性一致性）的实现

强一致性的2个要求
- 状态机必须apply到读请求到达时的commitindex才行
- 必须是当前的leader执行读请求，否则旧leader读取的可能是旧值
raft各种强一致性读
1. Raft Log Read：把读操作写成日志，当日志被apply时才返回客户端。性能极差
2. Read Index：读请求到达时记录的commitindex，确认leader仍有领导权后且状态机apply到记录的commitindex才执行
3. Lease Read：设定一个比选举超时更短的Lease（租期），租期内leader可认为自己具有领导权，无需确认。有一定不确定性
4. Follower Read：follower可执行读请求，接受读请求时向leader确认leader的commitindex，当follower自身的状态机达到记录点时，执行读请求

Gossip 算法

基本思想
- 追求可用性，满足最终一致性即可，不求强一致性（存在一个可用节点即可提供服务，AP架构）
- 让节点将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致
通讯方式
- push 模式：将节点自身数据发送给其他随机/指定节点，协助目标节点同步
- pull 模式：节点向其他随机/指定节点获取数据来实现自身的同步
- push-pull 模式：即上述推拉结合
传播策略
- 直接邮寄（Direct Mail）：直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传(可能因缓存满而丢数据,无法实现最终一致性)
- 反熵（Anti-entropy）：通过在节点之间交换数据的摘要来实现信息传播。在每个Gossip周期内，节点向随机/指定目标节点发送其本地数据的摘要。目标节点收到后，通过比较并向源节点请求缺失数据（需要节点两两交换和比对自己所有数据，工作量大，一般用于新节点加入时同步更新数据）
- 谣言传播（Rumor mongering）：节点获取新数据时，转为活跃态，并周期性向随机/指定节点发送新数据。目标节点收到信息后，会继续传播信息，直到信息在整个系统中被广泛传播。（具有较低的通信开销和较高的可扩展性，但传播速度较慢，用于节点间数据增量的同步）

参考

Paxos共识算法详解
 如何透彻理解 Paxos 算法？
深度解析 Raft 分布式一致性协议
 In Search of an Understandable Consensus Algorithm(Extended Version)
Raft算法（三）：如何解决成员变更的问题？