分布式系统理论序幕

---

• 分布式系统

  • 分布式系统是其组件分布在连网的计算机上，组件之间通过传递消息进行通信和协调的系统。
  • 为什么要分布式
    • 高可用，可拓展，性价比
  • 三个特点：不共享内存（需要网络传输），不共享时钟，不共享操作系统
  • 三个问题：网络问题，时钟问题，部分失效partial failure
  • 请求结果存在三态：成功，失败，超时
  • 三大方向：分布式存储系统，分布式计算系统，分布式调度系统
    • 各个方向都有一些特定的算法，但是分布式共识问题是分布式系统中最基本的问题：如何让分布式系统中的节点达成共识

• 共识

  • 什么是共识
  • 为什么要达成共识
    • 在共识的帮助下，分布式系统就可以像单一节点一样工作——所以共识问题是分布式系统最基本的问题。

• 模型

  • 网络模块
    • 同步：响应时间是有限的
    • 异步：响应时间无限的
  • 故障类型
    • Fail-stop failures 节点宕机并停止响应 (也就是常说的 not Byzantine)
    • Byzantine failures 源自“拜占庭将军问题”，节点响应的消息无法预料，可能矛盾或者无意义。也就是除了通信故障还可能存在消息篡改和伪造。
  • 消息模型
    • 口信型消息oral messages（未签名（口头的）的消息）
    • 签名型消息signed messages

• 异步系统中的共识问题

  • FLP不可能结论
  • 分布式共识算法需要具有的两个属性：安全性(safety)和活性(liveness)
    • 安全性：所有正确的进程都认同同一个值
    • 活性：分布式系统最终会认同某一个值
    • 每一个共识算法要么牺牲掉一个属性，要么放宽对网络异步的假设。
  • FLP结论的启示
    • 不再尝试寻找异步通信系统中，共识问题的完全正确的解法。可以找到一些方法，绕开FLP不可能，满足大部分情况下都能达成共识
      • 故障屏蔽Fault masking
        • 故障屏蔽假设故障的进程最终会恢复，并找到一种重新加入分布式系统的方式。如果没有收到来自某个进程的消息，就一直等待直到收到预期的消息。
        • 例如，两阶段提交事务使用持久存储，能够从崩溃中恢复。
      • 故障检测Failure detectors
      • 随机性算法Non-Determinism

• 同步系统中的共识问题

  • 我们熟知的 Paxos 在异步系统中，由于活锁的存在，并没有完全解决共识问题（liveness不满足）。但 Paxos 被广泛应用在各种分布式系统中，就是因为在达成共识之前，系统并没有那么“异步”，还是有极大概率达成共识的。
  • 同步系统中，如果 N 个进程中最多有 f 个会出现崩溃故障，那么经过 f + 1 轮消息传递后即可达成共识。 《Authenticated Algorithms for Byzantine Agreement》

• 分布式理论发展历程

  • 费林分类法（Flynn’s Taxonomy），MIMD引出并行和分布式系统

  • 分布式系统的三个问题与三个方向

  • 逻辑时钟。Lamport的《Time, Clocks and the Ordering of Events in a Distributed System》

  • 拜占庭将军问题。Lamport的《Byzantine Generals Problem》

  • 分布式状态机副本

  • 分布式快照

  • FLP结论。《Impossibility of Distributed Consensus with One Faulty Process》

    • 证明了：在一个异步系统中，即使只有一个进程出了故障，也没有算法能够保证达成共识。
    • 注意：不是说只要有一个进程故障就不能达成共识，而是说无法确保达成共识。

  • Paxos算法

  • PBFT

  • 分布式系统的基本问题：共识

• 拜占庭将军问题

  • 分布式共识问题
    • 什么是共识
      • 系统中的多个节点对某个值达成一致
    • 为什么要达成共识
  • 容错算法分为两类
  • 有无恶意行为区分使用BFT还是CFT

• Poxas是属于CFT的一种

• Poxas重要性

  • Chubby作者MikeBurrows说过，这世界上只有一种一致性共识算法，那就是Paxos

---

分布式计算中，共识Consensus问题是最重要的，最基本的问题。共识使得分布式系统表现出一致的行为，就像是单一节点一样。Lamport提出的拜占庭将军问题（The Byzantine Generals Problem），借助拜占庭将军的故事，很好地抽象了分布式系统面临的共识问题，并且探讨和论证了解决办法。

拜占庭将军问题描述的是最为复杂的一种分布式故障场景，不仅含有通信故障（消息丢失，重复），而且包含恶意行为（篡改消息，伪造消息）。解决拜占庭将军问题的算法称之为拜占庭容错算法（Byzantine Fault Tolerance，BFT）。对于解决不含有恶意行为场景下的容错算法，统称为非拜占庭容错算法，也就是故障容错算法（Crash Fault Tolerance, CFT）。事实上，计算机分布式系统中，最常用的就是CFT。

• 拜占庭容错算法 BFT
  • 节点间存在通信故障，恶意行为的场景下，如何达成共识。
  • 这种故障场景，称之为拜占庭故障
  • 常用于开放式分布式系统，如区块链技术
  • 常见算法：口信型消息算法，签名型消息算法，PBFT算法，PoW算法
• 非拜占庭容错算法，故障容错算法 CFG
  • 节点间不存在恶意行为的场景下（非拜占庭故障），如何达成共识
  • 常见算法：Paxos算法，Raft算法，ZAB算法