02-分布式算法

日志和复制状态机

  • 这里“日志”并不是常见的通过 log4j 或 syslog 输出的文本。而是 MySQL 中的 binlog（Binary Log）、MongoDB 中的 Oplog（Operations Log）、Redis 中的 AOF（Append Only File）、PostgreSQL 中的 WAL（Write-Ahead Log）…。它们虽然名称不同，但共同特点是只能追加、完全有序的记录序列。

两种日志复制模型

  • 主备模型（Primary-backup）：又称“状态转移”模型，主节点（Master）负责执行如“+1”、“-2”的操作，将操作结果（如“1”、“3”、“6”）记录到日志中，备节点（Slave）根据日志直接同步结果。

  • 复制状态机模型（State-Machine Replication）：又称“操作转移”模型，日志记录的不是最终结果，而是具体的操作指令，如“+1”、“-2”。指令按照顺序被依次复制到各个节点（Peer）。如果每个节点按顺序执行这些指令，各个节点最终将达到一致的状态。

  • 分布式系统的两种数据复制模型

Paxos

  • basic paxos
    • 三种节点：提案节点、决策节点、记录节点
  • Multi Paxos
    • 两种节点：主从节点，选举一次，然后统一由主节点提交
  • Gossip
    • 是一种分布式系统中节点间通信的算法，它的核心思想是通过随机选择节点交换信息，逐步将数据扩散到整个网络，最终实现系统状态的一致性。
    • Gossip 协议是分布式系统中实现去中心化、高可用、最终一致性的关键技术，尤其适合对实时性要求不高但需要高可靠性的场景。

Paxos的三种角色

  • 一个进程可能充当多个角色
    • Proposer(提议者) : 是启动共识过程的节点，它提出一个值，请求其他节点对这个值进行投票，提出值的行为称为发起“提案”（Proposal），提案包含提案编号 (Proposal ID) 和提议的值 (Value)。注意的是，Paxos 算法是一个典型的为“操作转移”模型设计的算法，为简化表述，本文把提案类比成“变量赋值”操作，但你应该理解它是“操作日志”相似的概念，后面介绍的 Raft 算法中，直接就把“提案”称做“日志”了。
    • Acceptor (决策者): 接受或拒绝提议者发起的提案，如果一个提案被超过半数的决策者接受，意味着提案被“批准”（accepted）。提案一旦被批准，意味着在所有节点中达到共识，便不可改变、永久生效。
    • Learners(记录者): 记录者不发起提案，也不参与决策提案，它们学习、记录被批准的提案。
  • 一个提案的表决者（Acceptor）会存在多个,但在一个集群中，提议者（Proposer）也可能存在多个，不同的提议者会提出不同的议案。一致性算法可以满足其他几点要求：
    • 没有提案提出则不会有提案选定
    • 每个提议者在提出提案时都会为该提案指定一个具有全局唯一性的、递增的提案编号N,即该提案在整个集群中是唯一的。
    • 每个表决者在accept某提案后，会将该提案号N记录在本地,这样每个表决者中保存的已经被accept的提案会存在一个编号最大的提案，其编号假设为maxN。每个表决者仅会accept编号大于maxN的提案
    • 在众多提案中最终只能由一个提案被选定
    • 一旦一个提案被选定，则其他服务器会主动同步（Learn）该提案到本地。

算法执行过程

  • 规定一个提议包含两个字段：[n, v]，其中 n 为序号（具有唯一性），v 为提议值。

prepare阶段

  • 下图演示了两个 Proposer 和三个 Acceptor 的系统中运行该算法的初始过程，每个 Proposer 都会向所有 Acceptor 发送 Prepare 请求。

    PaxosPerpare阶段

  • 当 Acceptor 接收到一个 Prepare 请求，包含的提议为 [n1, v1]，并且之前还未接收过 Prepare 请求，那么发送一个 Prepare 响应，设置当前接收到的提议为 [n1, v1]，并且保证以后不会再接受序号小于 n1 的提议。

  • 如下图，Acceptor X 在收到 [n=2, v=8] 的 Prepare 请求时，由于之前没有接收过提议，因此就发送一个 [no previous] 的 Prepare 响应，设置当前接收到的提议为 [n=2, v=8]，并且保证以后不会再接受序号小于 2 的提议。其它的 Acceptor 类似。

    PaxosPerpare阶段2

  • 如果 Acceptor 接收到一个 Prepare 请求，包含的提议为 [n2, v2]，并且之前已经接收过提议 [n1, v1]。如果 n1 > n2，那么就丢弃该提议请求；否则，发送 Prepare 响应，该 Prepare 响应包含之前已经接收过的提议 [n1, v1]，设置当前接收到的提议为 [n2, v2]，并且保证以后不会再接受序号小于 n2 的提议。

  • 如下图，Acceptor Z 收到 Proposer A 发来的 [n=2, v=8] 的 Prepare 请求，由于之前已经接收过 [n=4, v=5] 的提议，并且 n > 2，因此就抛弃该提议请求；Acceptor X 收到 Proposer B 发来的 [n=4, v=5] 的 Prepare 请求，因为之前接收到的提议为 [n=2, v=8]，并且 2 <= 4，因此就发送 [n=2, v=8] 的 Prepare 响应，设置当前接收到的提议为 [n=4, v=5]，并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。

    PaxosPerpare阶段3

accept阶段

  • 当一个 Proposer 接收到超过一半 Acceptor 的 Prepare 响应时，就可以发送 Accept 请求。
  • Proposer A 接收到两个 Prepare 响应之后，就发送 [n=2, v=8] Accept 请求。该 Accept 请求会被所有 Acceptor 丢弃，因为此时所有 Acceptor 都保证不接受序号小于 4 的提议。
  • Proposer B 过后也收到了两个 Prepare 响应，因此也开始发送 Accept 请求。需要注意的是，Accept 请求的 v 需要取它收到的最大提议编号对应的 v 值，也就是 8。因此它发送 [n=4, v=8] 的 Accept 请求。

learn阶段

  • Acceptor 接收到 Accept 请求时，如果序号大于等于该 Acceptor 承诺的最小序号，那么就发送 Learn 提议给所有的 Learner。当 Learner 发现有大多数的 Acceptor 接收了某个提议，那么该提议的提议值就被 Paxos 选择出来。

Raft算法

  • Raft 提出了领导者角色，通过选举机制“分享”提案权利。
  • 领导者（Leader）：负责处理所有客户端请求，将请求转换为“日志”复制到其他节点，不断地向所有节点广播心跳消息：“你们的领导还在，不要发起新的选举”。
  • 跟随者（Follower）：接收、处理领导者的消息，并向领导者反馈日志的写入情况。当领导者心跳超时时，他会主动站起来，推荐自己成为候选人。
  • 候选人（Candidate）：候选人属于过渡角色，他向所有的节点广播投票消息，如果他赢得多数选票，那么他将晋升为领导者。

leader election

raft协议状态

  • raft算法状态变更

  • leader

  • follower ：追随者

  • candidate:候选人

  • 所有节点启动时都是follower状态；在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举；如果收到多数的赞成票（含自己的一票）则切换到leader状态；如果发现其他节点比自己更新(出现掉线了？)，则主动切换到follower。

term

  • 从上面可以看出，哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。这根民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。

  • paft协议term

  • 选举过程：任期确保了领导者的唯一性。在一次任期内，只有获得多数选票的节点才能成为领导者。

  • 日志一致性：任期号会附加到每条日志条目中，帮助集群判断日志的最新程度。

  • 冲突检测：通过比较任期号，节点可以快速判断自己是否落后，并切换到跟随者状态。

选举的过程

  • 如果follower在election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举
    1. 增加节点本地的 current term ，切换到candidate状态
    2. 投自己一票
    3. 并行给其他节点发送 RequestVote RPCs
    4. 等待其他节点的回复 ，在这个过程中，根据来自其他节点的消息，可能出现三种结果
      • 收到majority的投票（含自己的一票），则赢得选举，成为leader
      • 被告知别人已当选，那么自行切换到follower
      • 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
    5. 赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。
  • 投票规则
    • 在任一任期内，单个节点最多只能投一票
    • 候选人知道的信息不能比自己的少
    • first-come-first-served 先来先得
  • 投票的消息
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // 投票的消息
    {
      "term": 5, // 候选者的当前任期号，用于通知接收方当前选举属于哪个任期。
      "candidateId": 3, // 候选者的节点 ID，标识请求投票的节点。
      "lastLogIndex": 12, // 候选者日志的最后一条日志的索引，用于比较日志的完整性。
      "lastLogTerm": 4//候选者日志的最后一条日志的任期号，用于进一步比较日志的新旧程度。
    }
    // 响应投票的消息
    {
      "term": 5, //接收方的当前任期号，用于告知候选者最新的任期号。如果候选者发现该值比自己大，会转为跟随者。
      "voteGranted": true//是否投票给候选者，true 表示同意，false 表示拒绝。
    }

log replication

  • 指令: 表示客户端请求的具体操作内容，也就是待“状态机”（State Machine）执行的操作。
  • 索引值：日志条目在仓库中的索引值，是单调递增的数字。
  • 任期编号：日志条目是在哪个任期中创建的，用于解决“脑裂”或日志不一致问题
  • 当有了leader，系统应该进入对外工作期了。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。
  • 来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。Leader会把修改复制到所有Follower,Leader 会等待大多数的 Follower 也进行了修改，然后才将修改提交,此时Leader会通知所有Follower 让它们也提交修改，此时所有节点的值达到一致。
  • // 领导者的广播消息
{
  "term": 5, // 领导者的任期号
  "leaderId": "leader-123",
  "prevLogIndex": 8, // 前一日志条目的索引
  "prevLogTerm": 4, // 前一日志条目的任期
  "entries": [
    { "index": 9, "term": 5, "command": "set x=4" }, // 要复制的日志条目
  ],
  "leaderCommit": 7// Leader 的“已提交”状态的日志条目索引号
}
  • 日志复制过程
    • 若当前节点非领导者，将请求转发至领导者；
    • 领导者接收请求后：
      • 将请求转化为日志条目，写入本地存储系统，初始状态为“未提交”（uncommitted）；
      • 生成日志复制消息（AppendEntries RPC），并广播至所有跟随者；
    • 跟随者收到日志复制消息后，验证任期（确保本地任期不大于领导者任期）、日志一致性（通过 prevLogIndex 检查日志是否匹配）。若验证通过，跟随者将日志条目追加至本地存储系统，并发送确认响应；。
    • 领导者确认日志条目已成功复制至多数节点后，将其状态标记为“已提交”（committed），并向客户端返回结果。已提交的日志条目不可回滚，指令永久生效，且可安全地“应用”（apply）至状态机。
    • 领导者向客户端返回结果，并不意味着日志复制过程已完全结束，跟随者尚不清楚日志条目是否已被大多数节点确认。Raft 的设计通过心跳或后续日志复制请求中携带更新的提交索引（leaderCommit），通知跟随者提交日志。此机制将“达成共识的过程”优化为一个阶段，减少了客户端约一半的等待时间。

Safety

Log compaction

  • 日志复制的另外一种情况
    • 如果因为日志不连续，追加失败。日志的连续性至关重要，如果日志条目没有按正确顺序应用到状态机，各个 follower 节点的状态肯定不一致。
    • 日志不连续的问题是这样解决的：follower-2 收到日志复制请求后，它会通过 prevLogIndex 和 prevLogTerm 检查本地日志的连续性。如果日志缺失或存在冲突，follower-2 返回失败响应，指明与领导者日志不一致的部分。

Membership change

  • 脑裂问题的解决
    • 每次只增加一个节点

如果突破写瓶颈

  • 一种方法是使用哈希算法将数据划分成多个独立部分（分片）。例如，将一个 100TB 规模数据的系统分成 10 部分，每部分只需处理 10TB。这种根据规则（范围或哈希）将数据分散处理的策略，被称为“分片机制”（Sharding）。分片机制广泛应用于 Prometheus、Elasticsearch 、ClickHouse 等大数据系统（详见本书第九章）。理论上，只要机器数量足够，分片机制就能支持任意规模的数据。
12分布式系统
02-分布式算法
https://x-leonidas.github.io/2022/02/01/12分布式系统/02-分布式算法/
作者
听风
发布于
2022年2月1日
更新于
2025年5月20日
许可协议