3 分布式系统
3.1 基本概念
3.1.1 异常
1. 异常类型
- 服务器宕机: 内存数据丢失, 需要考虑如何通过读取持久化数据来恢复内存数据.
- 网络异常: 原则: 网络永远是不可靠的. 任何一个消息只有收到对方的回复才可以确认发送成功. 系统设计时总是假设网络将会出现异常并采取相应处理措施.
- 磁盘故障: 多台服务器存储数据.
2. 超时
RPC 有 3 种状态:
- 成功
- 失败
- 超时(未知状态): 通过不断读取之前操作的状态来验证是否成功, 或将操作设计为「幂等」。
3.1.2 一致性
副本是分布式存储系统容错技术的唯一手段. 如何保证副本之间的一致性是整个分布式系统的理论核心.
- 客户端: 读写操作是否符合某种特性.
- 存储系统: 多个副本之间是否一致.
从客户端角度, 一致性包含 3 种:
- 强一致性
- 弱一致性
- 最终一致性: 弱一致性的一种特例. 有个 「不一致窗口」的概念。
其他常见变体：
- 读写一致性
- 会话一致性
- 单调读（Monotonic Read）一致性
- 单调写（Monotonic Write）一致性
从存储系统看，一致性包含：
- 副本一致性
- 更新顺序一致性
3.1.3 衡量指标
- 性能：吞吐和延时一般是矛盾的。
- 每秒读操作数 QPS （Query Per Second）
- 写操作数 （TPS，Transaction Per Second）
- 平均延时或 99.9% 延时
- 可用性：几个 9
- 一致性：在同一个数据中心，推荐强一致性，不会对性能和可用性造成太大影响。
- 可扩展性：最好线性可扩展。
3.2 性能分析
3.3 数据分布
分布式存储系统的一个基本要求就是透明性，包含数据分布透明性，数据迁移透明性，数据复制透明性，故障处理透明性。
3.3.1 哈希分布
哈希取模。
可能的问题：
- 分布不均。大客户数据量大。
- 服务器数量改变，几乎所有数据都要重新分布，带来大量数据迁移。
- 将哈希值和服务器的对应关系作为元数据，交给专门的元数据服务器来管理。集群扩容时，可以将部分哈希值分配给新加入的机器并迁移相应数据。
- 一致性哈希（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 某数据中心第一年运行故障
| 发生频率 | 故障类型 | 影响范围 |
| 0.5 | 数据中心过热 | 5min 内大部分机器断电，一到 2 天恢复 |
| 1 | 配电装置（PDU）故障 | 500-1000 台机器瞬间下线，6H 恢复 |
| 1 | 机架调整 | 大量告警，500-1000 台机器断电，6H 恢复 |
| 1 | 网络重新布线 | 大约 5% 机器下线超过 2 天 |
| 20 | 机架故障 | 40-80 台机器瞬间下线， 1-6H 恢复 |
| 5 | 机架不稳定 | 40-80 台机器发生 50% 丢包 |
| 12 | 路由器重启 | DNS 和对外虚 IP 服务失效几分钟 |
| 3 | 路由器故障 | 需要立即切换流量，持续约 1H |
| 几十 | DNS 故障 | 持续约 30s |
| 1000 | 单机故障 | 机器无法提供服务 |
| 几千 | 硬盘故障 | 硬盘数据丢失 |
系统设计：
- 对单台服务器故障进行容错处理
- 机架：避免将数据的所有副本都分布到同一个机架内。
3.5.2 故障检测
心跳。A->B 发心跳，收不到心跳的情况：
- B 故障
- B 非故障：
- A 和 B 网络有问题
- B 过于繁忙而无法响应。
如上，所以需要对「机器 B 是否应该被认为发生故障且停止服务」达成一致。通过 租约（Lease）机制检测故障，租约就是带有超时时间的一种授权。A -> B 发放租约，B 持有租约的有效期内才允许提供服务，否则主动停止服务。B 的租约快要到期的时候向 A 重新申请租约。
3.5.3 故障恢复
有单层和双层结构。
单层：假设 3 副本，A 故障：
- 临时故障：总控等待一段时间，如果 A 重新上线，则是临时的。
- 永久故障：如硬盘损坏。需要执行增加副本操作，即选择某个节点拷贝 A 的数据，成为 A 的备副本。
总控也可能出现故障，所以也要 HA，状态实时同步到备机，通过维护一套 如 Paxos 协议实现 分布式锁服务。
3.6 可扩展性
实现手段：
- 增加副本个数
- 增加缓存提高读取能力
- 将数据分片
- 将数据复制到多个数据中心
3.6.1 总控节点
用于维护数据分布信息，执行工作机管理，数据定位，故障检测和恢复，负载均衡等全局调度工作。
- 总控节点除了执行全局调度，还需要维护文件系统目录树，内存容量可能会是瓶颈
- 总控如果只需维护数据分片的位置信息，一般不会成为瓶颈
设计时要减少总控节点负载，如 GFS 舍弃小文件的支持，且把对数据的读写控制权限下放到工作机 ChunkServer，通过客户端缓存元数据减少对总控节点的访问。
如果总控成为瓶颈，那么可以采用两级结构。在总控和工作机之间加一层 元数据节点，每个元数据节点只维护一部分而不是整个分布式文件系统的元数据。这样，总控只需要维护元数据节点的元数据，不可能成为瓶颈。
3.6.2 数据库扩容
可扩展性实现手段：
- 主从复制
- 垂直拆分
- 水平拆分
传统 DB 扩容面临以下问题：
- 扩容不够灵活
- 扩容不够自动化
- 增加副本时间长
3.6.3 异构系统
同构系统：每个组内的节点服务完全相同的数据，增加副本需要迁移的数据量太大
异构系统：将数据划分为很多大小接近的分片，每个分片的多个副本可以分布到集群中的任何一个存储节点。如果发生故障，原有服务将由整个集群而不是某几个固定的存储节点来恢复。由于整个集群都参与到故障节点的恢复过程，故障恢复时间很短，而且集群规模越大，优势越明显。
3.7 分布式协议
最具代表性：
- 两阶段提交（Two-phase Commit，2PC）：保证跨多个节点操作的原子性
- Paxos：确保多个节点对某个投票（如哪个节点为主节点）达成一致
3.7.1 两阶段提交协议
实现分布式事务。
两类节点：
- 协调者（coordinator，CN）
- 事务参与者（participants，cohorts 或 workers 或 DN）
协议中假设每个节点都会记录操作日志并持久化，即使节点发生故障也不会丢失。
过程：
- 请求阶段（Prepare Phase）。协调者通知事务参与者准备提交或取消事务，然后进入表决过程。表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地执行成功）或者取消（事务参与者本地执行失败）
- 提交阶段（Commit Phase）。协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务，协调者才通知所有的参与者提交事务，否则协调者通知所有的参与者取消事务。参与者在接收到协调者发来的消息后执行相应的操作。
2 种故障：
- 事务参与者发生故障。给每个事务设置一个超时时间，超时则失败。
- 协调者发生故障。搞个备用协调者。如果都发生永久性故障，事务参与者将无法完成任务而一直等待。
总之，2PC 是阻塞协议，执行过程中要锁住其他更新，且不能容错。大部分分布式存储都放弃对分布式事务的支持。
3.7.2 Paxos 协议
3.7.3 Paxos 与 2PC
起的作用并不同。
Paxos 用法：
- 实现全局的锁服务或者命名和配置服务，如 Zookeeper
- 将用户数据复制到多个数据中心。
针对 2PC 的问题，常见做法是 2PC 和 Paxos 结合起来，通过 2PC 保证多个数据分片上的操作的原子性，通过 Paxos 协议实现一个数据分片的多个副本间的一致性。另外，通过 Paxos 协议解决 2PC 协议中协调者宕机问题。
3.8 跨机房部署
延时大，且不稳定。
难点：数据同步和服务切换。
跨机房部署有 3 个方案：
- 集群整体切换
- 单个集群跨机房
- Paxos 选主副本
3.8.1 集群整体切换
最常见方案。
机房之间的数据同步可能为：强同步或异步。
如果异步，备机房数据总是落后于主机房。当主机房故障时，有 2 中选择：
- 将服务切换到备机房，忍受数据丢失的风险
- 停止服务，直到主机房恢复为止。
因此，如果数据同步为异步，主备机房切换为 手工，允许用户根据业务的特点选择「丢数据」或「停止服务」。
如果强同步，那么主备机房数据一致。可以采用自动切换。
3.8.2 单个集群跨机房
整个集群跨机房，只有一个总控，需要同所有机房的工作节点保持通讯。当总控节点故障时，分布式锁服务将检测到，并将机房 2 的备份节点切换为总控节点。
总控节点做数据分布时，需要考虑机房信息，尽量将同一个数据分片的多个副本分布到多个机房。
3.8.3 Paxos 选主
每个数据分片的多个副本构成一个 Paxos 复制组。
如：B1-B4 是复制组，B1 为主副本，当 B1 故障时，其他副本将尝试切换为主副本，Paxos 协议保证只有一个副本会成功。
- 优点：降低对总控的依赖
- 缺点：复杂度太高
