拜占庭将军问题

简介

  • 在可能存在叛军的情况下，采用合适的通讯协议，让多个将军达成共识，执行统一的作战计划
  • 二忠一叛难题
  • 它是分布式领域最复杂的容错模型
  • 莱斯利·兰伯特（Leslie Lamport）The Byzantine Generals Problem

二忠一叛难题

  • 总共有三个将军，其中一个作为指挥官
  • 通过信使相互传递作战指令，进攻或者撤退
  • 所有忠诚的将军必须执行统一的作战计划，忠诚的将军必须执行忠诚的指挥官发布的指令
  • 假如 LIEUTENANT2 叛变，LIEUTENANT1 收到的作战指令就是“进攻，撤退”
  • 假如 COMMANDER 叛变，LIEUTENANT1 和 LIEUTENANT2 收到的作战指令都是“进攻，撤退”

口信消息型解法

  • 叛变人数为 m 需要已知
  • 则所有参与者的人数至少为 3m+1
  • 第一轮由指挥官发送作战指令
  • 第二轮由各位将军相互发送指令
  • 收到指令的将军按照少数服从多数的原则执行指令
  • 按照这个公式，前面的例子叛军为 1 人的情况，则需要 1 个指挥官和 3 个将军

假如 LIEUTENANT3 叛变了，那么首先指挥官向各位将军发送“进攻”的指令，由于 3 号将军叛变了，所以最终 1 号将军收到的指令是 2 个进攻，1 个撤退，2 号将军同样收到 2 个进攻，1 个撤退，这样忠诚的将军将会执行一致的指令

假如 COMMANDER 叛变了，分别向 1 号将军发送了“进攻”，向 2 号将军发送了“撤退”，向 3 号将军发送“进攻”，那么通过第二轮的协商后，1，2，3 号将军得到的指令都是“进攻，进攻，撤退”，这样按照少数服从多数的原则，忠诚的将军最终执行了一致的作战指令。

口信消息型解法非常简单有效，但是有一些缺点，就是必须知道叛军的数量，而且对参与协商的人数有限制

签名消息型解法

  • 忠诚将军的签名无法伪造，对他签名的任何变更都将被发现
  • 任何人都能验证将军签名的真假
  • 对于开始三个将军的例子而言，假如 2 号将军叛变，那么 1 号将军在收到 2 号将军篡改的指挥官的指令后，就能发现消息被篡改，从而执行跟指挥官执行相同的指令
  • 假如指挥官叛变，分别给 1 号将军和 2 号将军发送“进攻”和“撤退”的指令，那么通过第二轮协商后，1 号将军收到的指令是“进攻，撤退”，2 号将军同样收到“进攻，撤退”的指令，此时他们只需要实现约定好规则，将指令排序后取其中的某一个值就能实现忠诚将军永远执行相同的指令

小结

  • 将军相当于计算机的服务节点
  • 忠诚的将军相当于正常服务的节点
  • 叛变的将军相当于故障的节点
  • 实际上在分布式系统常常面临的问题比拜占庭问题要简单很多，因为这个场景可能会丢失消息，重复消息，但是很少会出现错误消息或者伪造消息的情况
  • 分布式系统中，最长用的是非拜占庭容错算法，即故障容错算法（Crash Fault Tolerance, CFT）
  • CFT 解决的是分布式系统中存在故障，但不存在恶意节点的场景下的共识问题
  • CFT 的常见实现有 Paxos 算法，Raft 算法等

分布式共识算法

Paxos

  • 在过去的几十年里，Paxos 是分布式共识算法的代名词
  • Basic Paxos：多个节点间就某个值达成共识
  • Multi-Paxos：执行多个 Basic Paxos 实例，就一系列值达成共识

Raft

  • Raft 算法是现在分布式系统开发的首选共识算法
  • 本质上说，Raft 算法是通过一切以领导者为准的方式，保证一系列值得共识和各节点日志的一致性

成员角色

  • 领导者(Leader): 处理写请求，管理日志复制，发送心跳，宣告领导地位
  • 跟随者(Follower): 接收和处理 Leader 的消息，等待 Leader 的心跳，如果 Leader 心跳超时，就主动成为候选人，并发起一轮新的选举
  • 候选人(Candidate): 向其他节点发送投票请求，如果赢得大多数选票，就晋升为 Leader

选举过程

假设有 3 个节点 A,B,C，初始阶段任期编号都为 0，Raft 实现了随机超时，也就是每个节点等待 Leader 心跳的超时时间是随机的。

由于节点 A 的超时时间最短，所以最先因为没有等到 Leader 的心跳而发生超时，此时 A 变成候选人，并增加自己的任期编号为 1，向 B 和 C 发起选举请求。

B 和 C 在收到 A 的请求后，由于在任期编号为 1 的这届任期内，还没有收到其他的投票请求，B 和 C 将自己本地的任期编号改为候选人 A 发起的任期编号，并将赞同票投给 A。

节点 A 顺利赢得了大多数选票，成功晋升为 Leader。并且周期性的向 B 和 C 发送心跳信息，防止 Follower 节点发生新的选举，导致“篡权”。

选举总结

  • Leader 周期性的向所有 Follower 发送心跳信息
  • 如果在指定时间内，Follower 没有收到 Leader 的心跳，那么它就认为当前没有领导者，推举自己为 Candidate，并发起选举
  • 在一次选举中，赢得大多数选票的 Candidate 晋升为 Leader
  • 在一个任期内，Leader 一直都是 Leader，直到它自身出现问题不能发送心跳，或者因为网络原因导致其他节点没能在规定时间内收到心跳发起新的选举
  • 在一次选举中，每个服务节点最多只能对一个人气编号投出一张选票，并且按照先来先服务的原则投票。比如 C 先收到任期编号为 1 的 A 的请求，又收到请求编号为 1 的 B 的请求，那么 C 会把选票投给 A
  • 当任期编号相同时，日志完整性更高（也就是最后一条日志项对应的任期编号值更大）的 Follower 拒绝投票给日志完整性低的 Candidate
  • 选票瓜分导致选举失败：同一任期内，多个候选人同时发起选举，导致选票被瓜分，所有候选人都不能达到赢得大多数选票
  • 随机超时时间：为了避免同一时间出现多个候选人，Raft 算法采用随机超时时间的机制，保证大多数情况下，只有一个服务节点先发起选举，而不是同时发起选举，从而减少发生选票瓜分导致选举失败的可能

日志复制

在 Raft 算法中，副本数据是以日志的形式存在的，Leader 接收来自客户端的写请求后，处理写请求的过程就是一个复制和应用日志项到状态机的过程。副本数据是以日志的形式存在，日志由日志项组成。日志项是一种数据格式，包含指令和一些附加信息，比如索引值（Log index）、任期编号（Term）

  • 指令：一条由客户端请求指定的、状态机需要执行的指令
  • 索引值：日志项对应的索引值，是一个连续的、单调递增整数
  • 任期编号：创建这条日志项的 Leader 的任期编号

Raft 的日志复制过程其实就是一个优化后的二阶段提交，Leader 进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到其他节点上，如果 Leader 收到大多数的节点的复制成功响应后，它将日志应用到自己的状态机，并返回成功给客户端。如果 Leader 没有收到大多数节点的复制成功响应，那么直接返回错误给客户端，此时 Leader 并没有进行二阶段提交，通知 Follower 应用日志项，而是当 Leader 在下一次发送心跳或者日志复制的 RPC 请求时，会包含 Leader 当前最大的和将要被提交的日志项的索引值，收到消息后的 Follower 发现自己还有未应用的日志项，则会应用。Leader 通过日志复制 RPC 的一致性校验，找到 Follower 节点上，与自己相同日志项的最大索引值，也就是说，在这个索引值之前的日志，Leader 和 Follower 是一致的，之后就是不一致的了。Leader 强制 Follower 更新覆盖不一致的日志项，实现日志一致性。

  • PrevLogEntry：表示当前要复制的日志项前一条日志的索引值
  • PrevLogTerm：表示当前要复制的日志项，前一条日志对应的任期编号
  • Leader 通过日志复制 RPC 消息，发送当前最新的日志项到 Follower，此时 PrevLogEntry 为 5，PrevLogTerm 为 3
  • Follower 收到消息后，在自己的日志中找不到 Index 为 5，Term 为 3 的日志项，所以拒绝日志复制
  • Leader 收到拒绝响应后，会递减要复制的日志项的索引值，并发送新的消息给 Follower
  • 直到 Folloer 在本地日志中找到对应 PrevLogEntry 和 PrevLogTerm 的日志，则从此时开始日志的复制