3 分布式系统

3.1 基本概念

3.1.1 异常

1. 异常类型

1. 服务器宕机: 内存数据丢失, 需要考虑如何通过读取持久化数据来恢复内存数据.
2. 网络异常: 原则: 网络永远是不可靠的. 任何一个消息只有收到对方的回复才可以确认发送成功. 系统设计时总是假设网络将会出现异常并采取相应处理措施.
3. 磁盘故障: 多台服务器存储数据.

2. 超时

RPC 有 3 种状态:

• 成功
• 失败
• 超时(未知状态): 通过不断读取之前操作的状态来验证是否成功, 或将操作设计为「幂等」。

3.1.2 一致性

副本是分布式存储系统容错技术的唯一手段. 如何保证副本之间的一致性是整个分布式系统的理论核心.

1. 客户端: 读写操作是否符合某种特性.
2. 存储系统: 多个副本之间是否一致.

从客户端角度, 一致性包含 3 种:

1. 强一致性
2. 弱一致性
3. 最终一致性: 弱一致性的一种特例. 有个 「不一致窗口」的概念。

其他常见变体：

1. 读写一致性
2. 会话一致性
3. 单调读（Monotonic Read）一致性
4. 单调写（Monotonic Write）一致性

从存储系统看，一致性包含：

• 副本一致性
• 更新顺序一致性

3.1.3 衡量指标

1. 性能：吞吐和延时一般是矛盾的。

1. 每秒读操作数 QPS （Query Per Second）
2. 写操作数 （TPS，Transaction Per Second）
3. 平均延时或 99.9% 延时

2. 可用性：几个 9
3. 一致性：在同一个数据中心，推荐强一致性，不会对性能和可用性造成太大影响。
4. 可扩展性：最好线性可扩展。

3.2 性能分析

3.3 数据分布

分布式存储系统的一个基本要求就是透明性，包含数据分布透明性，数据迁移透明性，数据复制透明性，故障处理透明性。

3.3.1 哈希分布

哈希取模。

可能的问题：

1. 分布不均。大客户数据量大。
2. 服务器数量改变，几乎所有数据都要重新分布，带来大量数据迁移。

1. 将哈希值和服务器的对应关系作为元数据，交给专门的元数据服务器来管理。集群扩容时，可以将部分哈希值分配给新加入的机器并迁移相应数据。
2. 一致性哈希（Distributed Hash Table， DHT）算法。给每个系统中每个节点分配一个随机 token， 这些 token 构成一个哈希环。执行数据存放操作时，先计算 Key 的哈希值，然后存放到顺时针方向第一个大于或等于该哈希值的 token 所在的节点。节点加入、删除时只会影响到在哈希环中相邻的节点，而对其他节点没影响。

3.3.2 顺序分布

在 分布式 表格系统较为常见，将大表顺序划分为连续的范围，每个范围为一个子表。

3.3.3 负载均衡

3.4 复制

3.4.1 复制的概述

主副本将写请求复制到其他备副本，常见的做法是同步操作日志（Commit Log）。主副本首先将操作日志同步到备副本，备副本回放操作日志，完成后通知主副本。接着，主副本修改本机，等到所有操作都完成后再通知客户端写成功。

NWR 复制协议：

• N：副本数量
• W：写操作副本数
• R：读操作副本数

NWR 协议中多个副本不再区分主备，客户端根据一定的策略往其中的 W 个副本写入数据，读取其中的 R 个副本。只要 W + R > N, 可以保证读到的副本中至少有一个包含了最新的更新. 问题在于: 不同副本的操作顺序可能不一致, 从多个副本读取时可能出现冲突.

3.4.2 一致性与可用性

CAP 理论: 一致性 (Consistency), 可用性(Availability) 以及分区可容忍性 (Tolerance of network Partition) 三者不能同时满足.

• 分区可容忍性: 机器故障、网络故障、机房停电等异常情况下仍然能够满足一致性和可用性

分布式系统要求能自动容错，也就是说：分区可容忍性总是要满足的，因此，一致性和写操作的可用性不能同时满足。

• 如果采用强一致性，保证一致性，然而，当主备副本间出现故障时，写操作被阻塞，系统可用性无法得到满足。
• 如果采用异步复制，保证可用性，就无法做到一致性。

要在一致性和可用性之间权衡，某些场景不允许丢数据，另外一些场景，丢数据是允许的，可用性更重要。

如 Oracle 的 DataGuard 复制组件包含 3 种模式：

• 最大保护模式：即强同步复制模式
• 最大性能模式：异步复制模式。
• 最大可用性模式：上述两种模式的折中。正常情况下相当于最大保护模式，如果主备网络出现故障，切换为最大性能模式。（强同步（可退化）？）

3.5 容错

往往通过 租约（Lease）协议实现。

3.5.1 常见故障

Google 某数据中心第一年运行故障

系统设计：

1. 对单台服务器故障进行容错处理
2. 机架：避免将数据的所有副本都分布到同一个机架内。

3.5.2 故障检测

心跳。A->B 发心跳，收不到心跳的情况：

1. B 故障
2. B 非故障：

1. A 和 B 网络有问题
2. B 过于繁忙而无法响应。

如上，所以需要对「机器 B 是否应该被认为发生故障且停止服务」达成一致。通过 租约（Lease）机制检测故障，租约就是带有超时时间的一种授权。A -> B 发放租约，B 持有租约的有效期内才允许提供服务，否则主动停止服务。B 的租约快要到期的时候向 A 重新申请租约。

3.5.3 故障恢复

有单层和双层结构。

单层：假设 3 副本，A 故障：

1. 临时故障：总控等待一段时间，如果 A 重新上线，则是临时的。
2. 永久故障：如硬盘损坏。需要执行增加副本操作，即选择某个节点拷贝 A 的数据，成为 A 的备副本。

总控也可能出现故障，所以也要 HA，状态实时同步到备机，通过维护一套 如 Paxos 协议实现 分布式锁服务。

3.6 可扩展性

实现手段：

1. 增加副本个数
2. 增加缓存提高读取能力
3. 将数据分片
4. 将数据复制到多个数据中心

3.6.1 总控节点

用于维护数据分布信息，执行工作机管理，数据定位，故障检测和恢复，负载均衡等全局调度工作。

1. 总控节点除了执行全局调度，还需要维护文件系统目录树，内存容量可能会是瓶颈
2. 总控如果只需维护数据分片的位置信息，一般不会成为瓶颈

设计时要减少总控节点负载，如 GFS 舍弃小文件的支持，且把对数据的读写控制权限下放到工作机 ChunkServer，通过客户端缓存元数据减少对总控节点的访问。

如果总控成为瓶颈，那么可以采用两级结构。在总控和工作机之间加一层 元数据节点，每个元数据节点只维护一部分而不是整个分布式文件系统的元数据。这样，总控只需要维护元数据节点的元数据，不可能成为瓶颈。

3.6.2 数据库扩容

可扩展性实现手段：

1. 主从复制
2. 垂直拆分
3. 水平拆分

传统 DB 扩容面临以下问题：

• 扩容不够灵活
• 扩容不够自动化
• 增加副本时间长

3.6.3 异构系统

同构系统：每个组内的节点服务完全相同的数据，增加副本需要迁移的数据量太大

异构系统：将数据划分为很多大小接近的分片，每个分片的多个副本可以分布到集群中的任何一个存储节点。如果发生故障，原有服务将由整个集群而不是某几个固定的存储节点来恢复。由于整个集群都参与到故障节点的恢复过程，故障恢复时间很短，而且集群规模越大，优势越明显。

3.7 分布式协议

最具代表性：

• 两阶段提交（Two-phase Commit，2PC）：保证跨多个节点操作的原子性
• Paxos：确保多个节点对某个投票（如哪个节点为主节点）达成一致

3.7.1 两阶段提交协议

实现分布式事务。

两类节点：

1. 协调者（coordinator，CN）
2. 事务参与者（participants，cohorts 或 workers 或 DN）

协议中假设每个节点都会记录操作日志并持久化，即使节点发生故障也不会丢失。

过程：

1. 请求阶段（Prepare Phase）。协调者通知事务参与者准备提交或取消事务，然后进入表决过程。表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地执行成功）或者取消（事务参与者本地执行失败）
2. 提交阶段（Commit Phase）。协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者通知所有的参与者取消事务。参与者在接收到协调者发来的消息后执行相应的操作。

2 种故障：

• 事务参与者发生故障。给每个事务设置一个超时时间，超时则失败。
• 协调者发生故障。搞个备用协调者。如果都发生永久性故障，事务参与者将无法完成任务而一直等待。

总之，2PC 是阻塞协议，执行过程中要锁住其他更新，且不能容错。大部分分布式存储都放弃对分布式事务的支持。

3.7.2 Paxos 协议

3.7.3 Paxos 与 2PC

起的作用并不同。

Paxos 用法：

1. 实现全局的锁服务或者命名和配置服务，如 Zookeeper
2. 将用户数据复制到多个数据中心。

针对 2PC 的问题，常见做法是 2PC 和 Paxos 结合起来，通过 2PC 保证多个数据分片上的操作的原子性，通过 Paxos 协议实现一个数据分片的多个副本间的一致性。另外，通过 Paxos 协议解决 2PC 协议中协调者宕机问题。

3.8 跨机房部署

延时大，且不稳定。

难点：数据同步和服务切换。

跨机房部署有 3 个方案：

• 集群整体切换
• 单个集群跨机房
• Paxos 选主副本

3.8.1 集群整体切换

最常见方案。

机房之间的数据同步可能为：强同步或异步。

如果异步，备机房数据总是落后于主机房。当主机房故障时，有 2 中选择：

1. 将服务切换到备机房，忍受数据丢失的风险
2. 停止服务，直到主机房恢复为止。

因此，如果数据同步为异步，主备机房切换为 手工，允许用户根据业务的特点选择「丢数据」或「停止服务」。

如果强同步，那么主备机房数据一致。可以采用自动切换。

3.8.2 单个集群跨机房

整个集群跨机房，只有一个总控，需要同所有机房的工作节点保持通讯。当总控节点故障时，分布式锁服务将检测到，并将机房 2 的备份节点切换为总控节点。

总控节点做数据分布时，需要考虑机房信息，尽量将同一个数据分片的多个副本分布到多个机房。

3.8.3 Paxos 选主

每个数据分片的多个副本构成一个 Paxos 复制组。

如：B1-B4 是复制组，B1 为主副本，当 B1 故障时，其他副本将尝试切换为主副本，Paxos 协议保证只有一个副本会成功。

• 优点：降低对总控的依赖
  
• 缺点：复杂度太高