「训」 笔记(07)：分布式理论

本文最后更新于：1 年前

分布式理论 —— 现代架构的基石。

1 分布式概述

  • 什么是分布式？

    • 分布式系统定义：跨多个节点的计算机程序的集合
    • 使用分布式系统的五大优势：去中心化、低成本、弹性、资源共享、可靠性高
    • 分布式系统的挑战：节点故障、不可靠的网络、异构的机器与硬件环境、安全

  • 常见的分布式系统

    • 分布式存储：GFS、Ceph、HDFS、Zookeeper
    • 分布式数据库：Spanner、TiDB、HBase、MangoDB
    • 分布式计算：Hadoop、YARN、Spark

2 系统模型

2.1 故障模型

  • 六种故障模型，从处理的难易程度分类

    • Byzantine failure：节点可以任意篡改发送给其他节点的数据，是最难处理的故障
    • Authentication detectable byzantine failure (ADB)：节点可以篡改数据，但不能伪造其他节点的数据
    • Performance failure：节点未在特定时间段内收到数据，即时间太早或太晚
    • Omission failure：节点收到数据的时间无限晚，即收不到数据
    • Crash failure：节点停止响应，持续性的故障
    • Fail-stop failure：错误可检测，是最容易处理的故障

  • 故障模型举例

故障模型

2.2 拜占庭将军问题

  • 两将军问题

    定义：两支军队的将军只能派信使穿越敌方领土互相通信，以此约定进攻时间。该问题希望求解如何在两名将军派出的任何信使都可能被俘虏的情况下，就进攻时间达成共识。

    结论：两将军问题是被证实无解的电脑通信问题，两支军队理论上永远无法达成共识。

    TCP是两将军问题的一个工程解。

  • 三将军问题：

    两个“忠将” A 和 B，一个“叛徒” C，互相传递消息，消息可能丢失，也可能被篡改，当有一个将军是“叛徒”（即出现拜占庭故障）时，整个系统无法达成一致。

    由于“叛徒” C 的存在，将军 A 和将军 B 获得不同的信息。这样将军 A 获得 2 票进攻 1 票撤退的信息，将军 B 获得 1 票进攻 2 票撤退的信息，产生了不一致。

  • 四将军问题：

    将军 D 作为消息分发中枢，约定如果没收到消息则执行撤退。

    如果 D 为“叛徒”，ABC 无论收到任何消息，总能达成一致。D 为“忠将”，ABC 有 2 人将 D 的消息进行正确的传递，同样能保证最终决策符合大多数。

    进而能够证明，当有 3m+1 个将军，m 个“叛徒”时，可以进行 m 轮协商，最终达成一致。

2.3 共识和一致性

不同客户端 A 和 B 看到客户端 C 写入，因为时机的不同，产生数据读取的偏差。

  • Eventuallyconsistent（最终一致性）
    客户端 A 读到 x=0，当客户端 C 正在写入时，客户端 A 和 B 可能读到 0 或者 1。但是当 C 写入完成后，A 和 B 最终能读到一致的数据。

读请求和写请求并发时可能读到旧值

要保证所有客户端看到相同的值，需要多节点进行“协商”，达成共识，来保证线性一致性。

  • Linearizability（线性一致性）
    当客户端 A 读到更新的版本 x=1 后，及时将消息同步给其他客户端，这样其他客户端立即能获取到 x=1。

一旦某个读获取到新值，所有客户端都必须返回新值

一致性和可用性是对矛盾，如果要保证“线性”一致性，多个节点间势必需要进行协商，以寻求一致。这样增加了延迟，系统可用性便会受损。

3 理论基础

3.1 CAP 理论

一致性、可用性、分区容错性，三者无法同时达到

  • C (Consistence)：一致性，指数据在多个副本之间能够保持一致的特性（严格的一致性）。
  • A (Availability)：可用性，指系统提供的服务必须一直处于可用的状态，每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据。
  • P (Partitioning)：分区容错性，分布式系统在遇到任何网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务，除非整个网络环境都发生了故障。

CAP 诞生了三类系统：

  • CA 系统：传统单机数据库的代表
  • AP 系统：放弃强一致性，保证高可用，不少 nosql 存储系统采用，注重用户体验
  • CP 系统：放弃可用性，保证数据一致性，注重系统安全

3.2 ACID 理论

ACID 理论是针对 CA 系统而言的，通常在数据库中具有广泛意义。

事务是数据库系统中非常重要的概念，它是数据库管理系统执行过程中的一个逻辑单元，它能够保证一个事务中的所有操作要么全部执行，要么全都不执行。

数据库事务拥有四个特性：

  • 原子性（Atomicity）：原子性是指事务包含的所有操作要么全部成功，要么全部失败回滚。
  • 一致性（Consistency）：一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态，也就是说一个事务执行之前和执行之后都必须处于一致性状态。
  • 隔离性（Isolation）：隔离性是当多个用户并发访问数据库时，数据库为每一个用户开启的事务，不能被其他事务的操作所干扰，多个并发事务之间要相互隔离。
  • 持久性（Durability）：持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。

3.3 BASE 理论

BASE 理论是针对 AP 系统而言的，其来源于对大型互联网分布式实践的总结。

  • Basically Available（基本可用）：假设系统出现了不可预知的故障，但还是能用。
  • Soft state（软状态）：允许系统中的数据存在中间状态，并认为该状态不影响系统的整体可用性。
  • Eventually consistent（最终一致性）：数据最终一定能够达到一致的状态。

4 分布式事务

4.1 二阶段提交（Two-phase Commit）

为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种演算法。参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者提交操作还是中止操作。

三个假设：

  1. 协调者和参与者进行通信
  2. 预写式日志被保持在可靠的存储设备上
  3. 所有节点不会永久性损坏，即使损坏后仍然可以恢复

2PC

  1. 准备阶段（Prepare Phase）： 在该阶段，事务协调者向所有参与者发送准备请求，询问是否可以执行事务。参与者执行事务的操作，并将执行结果反馈给协调者。如果所有参与者都准备好执行事务，则进入提交阶段。如果有任何一个参与者无法准备好执行事务，则进入中止阶段。

  2. 提交阶段（Commit Phase）： 在该阶段，事务协调者向所有参与者发送提交请求，要求执行事务的提交操作。参与者执行事务的提交操作，并将执行结果反馈给协调者。如果所有参与者都成功提交事务，则整个事务提交成功。如果有任何一个参与者提交失败，则整个事务回滚。

两阶段提交需解决的问题：

  • 性能问题：需要多次网络通信，资源需要等待并锁定
  • 新协调者：如何确定状态选出新协调者
  • Commit 阶段网络分区带来的数据不一致：非所有节点都收到 Commit 请求
  • 第二阶段的提交阶段可能会出现阻塞，从而影响整个系统的性能

4.2 三阶段提交

针对两阶段提交的补充，将两阶段提交中的 Prepare 阶段，拆成两部分：CanCommit 和 PreCommit

  • CanCommit 阶段：询问是否可以执行
  • PreCommit 阶段：重新确认是否可以执行
  • DoCommit 阶段：向所有人提交事务

三阶段提交协议通过将提交阶段分为两个阶段，解决了二阶段提交可能出现的长时间阻塞问题。当某个参与者在 PreCommit 阶段失败时，协调者可以在适当的时候发起回滚，而不必一直等待，从而避免了阻塞的情况。

4.3 MVCC

多版本并发控制的方法。维持一个数据的多个版本使读写操作没有冲突。所以既不会阻塞写，也不阻塞读。提高并发性能的同时也解决了脏读的问题。

  • 悲观锁：操作数据时直接把数据锁住，直到操作完成后才会释放锁；上锁期间其他人不能修改数据。
  • 乐观锁：不会上锁，只是在执行更新时判断别人是否修改数据，只有冲突时才放弃操作。

版本的选取：

  • 物理时钟：提供 TrueTime API，有 Master 节点维持一个绝对时间，保证各个服务器之间时钟误差控制在 ϵ 内，通常 ϵ < 7ms。
  • 逻辑时钟：中心化授时的方式——时间戳预言机（TSO），好处是无需硬件的支持。

5 共识协议

5.1 Quorum NWR 模型

  • N：在分布式存储系统中，有多少份备份数据。
  • W：代表一次成功的更新操作要求至少有 w 份数据写入成功。
  • R：代表一次成功的读数据操作要求至少有 R 份数据成功读取。

为了保证强一致性，需要保证 W + R > N

Quorum NWR 模型将 CAP 的选择交给用户，是一种简化版的一致性模型。

5.2 RAFT 协议

Raft 协议是一种分布式一致性算法（共识算法），即使出现部分节点故障，网络延时等情况，也不影响各节点，进而提高系统的整体可用性。

RAFT

  • Log（日志）：节点之间同步的信息，以只追加写的方式进行同步，解决了数据被覆盖的问题。
  • Term（任期号）：单调递增，每个 Term 内最多只有一个 Leader。
  • Committed：日志被复制到多数派节点，即可认为已经被提交。
  • Applied：日志被应用到本地状态机，即执行了log中命令，修改了内存状态。

状态转移

  • Leader - 领导者：Leader 负责处理所有的客户端请求，并向 Follower 同步请求日志，当日志同步到大多数节点上后，通知 Follower 提交日志。
  • Follower - 跟随者：接受并持久化 Leader 同步的日志，在 Leader 告知日志可以提交后，提交日志。
  • Candidate - 备选者：Leader 选举过程中的临时角色，向其他节点发送请求投票信息。

Leader 选举过程：

  1. 初始全部为Follower
  2. Current Term + 1
  3. 选举自己
  4. 向其它参与者发起 RequestVote 请求，retry 直到：
    • 收到多数派请求，成为 Leader，并发送心跳
    • 收到其它 Leader 的请求，转为 Follower，更新自己的 Term
    • 收到部分，但未达到多数派，选举超时，随机 timeout 开始下一轮

切主：当Leader出现问题时，就需要进行重新选举

  1. Leader 发现失去 Follower 的响应，失去 Leader 身份
  2. 两个 Follower 之间一段时间未收到心跳，重新进行选举，选出新的 Leader，此时发生了切主
  3. Leader 自杀重启，以 Follower 的身份加入进来

5.3 Paxos 协议

Paxos 算法与 RAFT 算法区别：

  • Multi-Paxos 可以并发修改日志，而 Raft 写日志操作必须是连续的

  • Multi-Paxos 可以随机选主，不必最新最全的节点当选 Leader

  • 优势：写入并发性能高，所有节点都能写

  • 劣势：没有一个节点有完整的最新的数据，恢复流程复杂，需要同步历史记录