# 9. 分布式系统的挑战


分布式系统面临的挑战

<!-- more -->

## 1. 分布式系统中的故障
在分布式系统中，故障来自于下面的方方面面:
1. 网络分区不可避免 -- 网络不可靠
2. 时钟和时序问题，时钟无法精确同步  --- 时钟不可靠
3. 分布式系统中的一个节点必须假设，执行过程中的任何时刻都可能被暂停相当长一段时间，包括运行在某个函数中间。暂停期间，整个集群其他部分都照常运行，甚至会一致将暂停的节点宣告为故障节点，最终暂停的节点可能会回来继续执行，除非再次检查时钟，否则对刚刚过去的暂停毫无意识

让系统容忍失效并不容易，在典型的分布式环境下，没有全局变量，没有共享内存，没有约定的尝试或其他跨节点的共享状态。节点甚至不太清楚现在的准确时间。信息的流动只能通过不可靠的网络来发送。

我们将探讨如何认清分布式系统的状态本质，并据此来评估所发生的各种故障。

## 2. 故障与部分失效
在单节点上开发应用程序，通常是以一种确定性的方式运行: 要么工作，要么出错，相同的操作通常总会产生相同的结果(即确定性)，而不应该出现模棱两可的现象。这背后涉及一个非常慎重的选择: 如果发生了某种内部错误，我们宁愿使计算机全部奔溃，而不是返回一个错误的结果，错误的结果往往更难处理。因此计算机隐藏了一切模糊的物理世界，呈现出一个理想的系统模型。

然而对于分布式系统，这种理想化的标准正确模型不再适用，分布式系统中可能会出现系统的一部分工作正常，但其他某些部分出现难以预测的故障，我们称之为"部分失效"。问题的难点就在于**这种部分失效是不确定的**。正是由于这种**不确定性**和**部分失效**大大提高了分布式系统的复杂度。

故障处理是软件设计的重要组成部分，作为系统运维者，需要知道在发生故障时，系统的预期行为是什么。不能假定故障不可能发生而总是期待理想情况。可以说，**在分布式系统中，怀疑、悲观和偏执狂才能生存**。

## 3. 不可靠的网络
我们关注的是分布式无共享系统，即通过网络连接的多个节点。网络是跨节点通信的唯一方式。但网络并不保证它神秘时候到达，甚至它是否一定到达。发送之后等待响应过程中，有很多事情可能会出错:

![请求响应可能在很多地方法神错误](/images/db/network_error.png)

如上图所示，请求响应可能在很多地方法神错误:
1. 请求丢失
2. 请求在队列中，无法马上发送
3. 远程节点失效
3. 远程节点无法立即响应
4. 响应丢失
6. 请求处理已经完成，但回复被延迟处理

如果**请求没有得到响应，无法区分是(a) 请求丢失 (b)远程节点关闭 (c)响应丢失**

### 3.1 现实中的网络故障
现实中可能因为各种原因出现各种硬件故障，这些原因处理物理原因外，很大一部分是认为造成的。当网络的一部分由于网络故障而与其他部分断开，称之为网络分区。

处理网络故障并不意味着总是需要复杂的容错机制，一种简单的方法是对用户提示错误信息。但前提是**必须非常清楚接下来软件会如何应对网络故障，以确保系统最终可以恢复**。推荐有计划的人为触发网络问题，来测试系统的反应情况。

### 3.2 故障检测
系统通常都需要自动检测节点失效，然而由于网络的不确定性很难准确判断节点是否确实失效。如果超时是故障检测唯一可行办法，那**超时应该设置多长时间呢？**:
1. 较长的时间意味着更长时间才能宣告节点失效，在此期间用户只能等待或拿到错误信息
2. 较短的时间可以快速检测故障，但是很可能出现误判(只是网络波动或者性能波动而非故障)

节点宣告失效，需要转移负载，会给网络和其他节点带来额外的负担，如果系统已经处于高负载装填，很可能导致失效扩散。

#### 网络拥塞与排队
计算机网络上数据包延时的变化根源往往在于排队:
1. 高流量下，在网络交换机出现排队
2. CPU高负载下，在操作系统出现排队
3. 虚拟化下，入向的包可能会被虚拟机管理器排队缓存
4. TCP 执行流量控制意味着数据甚至在进入网络之前，已经在发送方开始排队
5. TCP 重传也会引入额外的延迟

![网络包排队](/images/db/waiter_queue.png)

以上因素都会导致网络延时的变化和不确定性，特别是当系统接近最大设计上限时，**负载过高，队列深度就会显著加大**，排队对延时的影响变得特别明显。

网络超时设置最好的办法不是设置一个不变的常量，而是持续测量响应时间及其变化，然后根据最新的响应时间分布来自动调整。可以使用 **Phi Accrual 故障检测器**，改检测器已在 Akka 和 Cassandra 中使用。

## 4. 不可靠的时钟
时钟和计时非常重要，但由于网络的不确定延迟，精确测量面临很多挑战，这使得多节点通信时**很难确定事情发生的先后顺序**。而且每台机器都维护自己本地的时间版本，可能比其他机器稍快或更慢。NTP通常用来同步机器之间的时钟，一定程度上可以同步机器之间的时钟。

### 4.1 单调时钟和墙上时钟
现在计算机内部至少有两种不同的时钟，本质上他们是服务于不同目的的:
1. 墙上时钟: 
    - 钟表时钟，可以与 NTP 同步
    - 因为时钟同步会导致时间出现突然的跳跃，特别是跳回到先前的某个时间点，导致其不适合测量时间间隔 
2. 单调时钟:
    - 名字来源于其保证总是向前，不会出现回拨，更适合测量持续时间段(时间间隔)
    - 绝对值没有任何意义，有意义的时钟的间隔
    - 如果服务器有多路CPU，则每个 CPU 可能有单独的计时器，其不与其他CPU同步，由于应用程序的线程可能会调度到不同的 CPU上，操作系统会补偿多个计时器之间的偏差，从而为应用程序提供统一的**单调递增计时**，不过最好还是对这种偏差补偿持谨慎态度
    - NTP 不会直接调整单调时钟

分布式系统中可以采用单调时钟测量一段任务的持续时间，它不假设节点间有任何的时钟同步，且可以容忍轻微测量误差。

### 4.2 时钟同步与准确性
墙上时钟需要根据 NTP服务器或其他外部时间做必要的同步，但硬件时钟和 NTP 可能会出现一些莫名其妙的现象:
1. 计算机中的石英钟不够精确，存在漂移现象，即速度加快或减慢
2. 时钟与 NTP 时间差别太大，可能会出现拒绝同步，或者同步后出现时间的突变
3. 网络延时会影响 NTP 同步的准确性
4. NPT 本身的故障
5. 闰秒
6. 虚拟机中，硬件时钟也是虚拟化的，时间可能出现跳跃

如果应用需要精确同步的时钟，最好仔细监控所有节点上的时钟偏差。如果某个节点的时钟漂移超出上限，应该将其宣告失效，并从集群中移除。

### 4.3 时间戳与事件顺序
跨节点的事件顺序，如果高度依赖时钟计时，就存在一定的技术风险，因为各个节点的时间戳很可能不能对所有事件正确排序。由于时钟精度限制，两个节点可能产生了相同的时间戳。

依赖时间戳确定的事件顺序，无法区分连续快速发生的连续写和并发写入，需要额外的**因果关系跟踪机制(版本向量)**来防止因果冲突。

因此通过保持**最新值**并丢弃其他值的**最后写入获胜(LWW)**冲突解决策略看起来不错，但是最新的定义如果取决于墙上时钟就会引入偏差。

对于排序来说，基于递增计数器而不是震荡石英晶体的**逻辑时钟**是更可靠的方式。逻辑时钟不测量一天的某个时间点或时间间隔，而是事件的相对顺序(**事件发生的相对前后顺序**)。相应的墙上时钟和单调时钟都属于**物理时钟**。

### 4.4 分布式全局快照的同步时钟(重要)
常见的快照隔离需要单调递增事务ID，单节点上，一个简单的计数器足以生成事务ID。但是当数据分布在多台机器，跨越多个数据中心时，由于需要复杂的协调以产生全局的单调递增的事务 ID(跨所有分区)。

**事务ID要求必须反映因果关系**: 事务B要读取事务A写入的值，B的事务ID，必须大于A的事务ID

考虑到大量，频繁的小包，在分布式系统中创建事务ID通常会引入瓶颈。那能否**用同步后的墙上时钟作为事务ID呢？如果时钟足够可靠其同步，自然符合事务ID属性要求: 后发生的事务具有更大的时间戳。然而问题还是时钟精度不精确。

Googgle Spanner以这种方式实现跨数据中心的快照隔离。它使用TrueTime API报告的时钟置信区间，并基于以下观察结果：如果有两个置信区间，每个置信区间包含最早和最近可能的时间戳（ $A = [A{earliest}, A{latest}]$， $B=[B{earliest}, B{latest}] $），这两个区间不重叠（即：$A{earliest} < A{latest} < B{earliest} < B{latest}$），那么B肯定发生在A之后——这是毫无疑问的。只有当区间重叠时，我们才不确定A和B发生的顺序。

​ 为了**确保事务时间戳反映因果关系**，Spanner在提交读写事务之前故意等待置信区间长度的时间。通过这样，它可以确保任何可能读取数据的事务足够晚发生，避免与先前的事务的置信区间产生重叠。为了保持尽可能短的等待时间，Spanner需要使时钟的误差范围尽可能小，为此，Google在每个数据中心都部署了一个GPS接收器或原子钟，保证所有时钟同步在约 7ms 内完成。

**借助时钟同步来处理分布式事务语义**，除了 Google 以外，目前主流数据库都没有更多的实现。

## 5. 进程暂停
在分布式锁或者 Leader 选举中，通常我们都会只用租约: 某节点获得租约之后，在租约到期之前，它就持有锁或者成为主节点，为了维持主节点身份，节点必须在到期之前定时去更新租约。

典型的流程如下所示:

```js
while(true){
    request=getIncomingRequest();
    // 确保租约还剩下至少10秒
    if (lease.expiryTimeMillis-System.currentTimeMillis()< 10000){
        // 更新租约
        lease = lease.renew();
    }
    // 租约有效
    if(lease.isValid()){
        process(request);
    }}
}
```

这段代码有什么问题？
1. 首先，他依赖于同步的时钟，租约到期时间又另一台机器所设置
2. 如果程序执行出现了暂停，例如在 lease.isValid() 消耗了30s，那么当开始处理请求时，租约已经过期了，另一个节点已经成为了主节点。后面代码也不会注意到租约到期，除非运行到下一个循环。不过到那个时候当前的这个进程已经做了一些不安全的请求处理了。

那么什么会导致线程暂停很长时间呢？
1. GC 暂停
2. 虚拟环境下的，虚拟机暂停
3. 操作系统的上下文切换或者虚拟机管理程序切换到另一虚拟机，虚拟机中断的 CPU 时间称为窃取时间
4. 线程可能暂停并等待 I/O 完成
5. 内存访问可能触发缺页异常

**分布式系统**的一个节点必须假定，**执行过程中的任何时刻都可能被暂停相当长一段时间**，包括运行在某个函数中间。暂停期间，整个集群的其他部分都在照常运行，**甚至会一致将暂停的节点宣告为故障节点**。最终，**暂停的节点可能会回来继续运行，除非再次检查时钟，否则它对刚刚过去的暂停毫无意识**。

## 6. 少数服从多数
前面我们已经了解了分布式系统面临的种种障碍。那如何去解决这些问题呢？

在分布式系统中，我们可以明确列出对系统行为(系统模型)所做的若干假设，然后以满足这些假设条件为目标来构建实际运行的系统。我们的目的是**确定可以做出哪些合理假设，可以提供哪些保证**。

### 6.1 真相由多数决定
节点不能根据自己的信息来判断自身的状态，由于节点可能随时失效，可能会暂停-家私，甚至最终无法恢复。因此分布式系统不能完全依赖于单节点。目前许多分布式算法都依靠法定票数，即在节点之间进行投票(读写 quorum)。任何决策都需要来自多个节点的最小投票数，从而减少对特定节点的依赖。这包括关于宣告节点失效的决定。

由于系统只可能存在一个多数，绝不会有两个多数在同时做出相互冲突的决定，因此系统的决议是可靠的。

### 6.2 主节点与锁
很多情况下，我们需要**在系统范围内只能有一个实例**：
1. 只有一个分区主节点
2. 只有一个事务或客户端持有锁
3. 唯一ID

在分布式系统中需要格外注意: **及时某个节点自认为它是"唯一的那个"，但不一定获得了系统法定票数的同意**。当多数节点声明节点已失效，而该节点还继续充当"唯一的那个"，如果系统设计不周就会导致负面后果。该节点会按照自认为正确的信息向其他节点发送消息，其他节点如果还选择相信它，那么系统就会出现错误的行为。

如下图所示: 不正确的分布式锁实现，客户端1的锁租约已经过期，但他自认为有效，最终导致文件破坏

![不正确的分布式锁实现](/images/db/fig8-4.png)

### 6.3 Fencing 令牌(重要)
当使用锁和租约机制来保护资源的并发访问时，必须确保过期的**唯一的那个**节点不能影响其他正常部分。有一个简单的办法可以实现:
1. 锁服务在授予锁或租约时，同时返回一个 fencing 令牌，令牌每授予一次就递增一次
2. 要求客户端每次向村粗系统发送写请求时，都必须包含所持有的 fencing 令牌
3. 存储服务器由于记录了最近已经完成了更高令牌号，因此会拒绝低版本令牌的写操作

![fencing令牌](/images/db/fencing.png)

注: 如果客户端2已经获取锁，但写请求在客户端1的写请求只有达到，会出现什么现象。

如果将ZooKeeper用作锁定服务，则可将事务标识zxid或节点版本cversion用作 fencing令牌，这两个都满足单调递增的需求。

注意这种机制要求资源本身必须主动检查所持令牌信息，如果发现已经处理过更高令牌的请求，要拒绝持有低令牌的所有写请求。总之为了避免**在锁保护外**发生请求处理，需要进行额外的检查机制。

### 6.4 拜占庭故障
​ fencing 令牌可以检测和阻止那些无意的误操作。如果节点存在**撒谎**，我们称之为拜占庭故障。在不信任的环境中需要达成共识的问题也称为拜占庭将军问题。

在我们讨论的系统中，可以安全的假设没有拜占庭式的故障。我们假设节点虽然不可靠但一定是诚实的，其一旦做出相应，则一定是完全基于其所知的全局信息和事先约定好的行为准则，响应代表了"真相"。

### 6.5 理想系统模型与现实(重要)
我们通过定义一些系统模型来形式化描述算法的前提条件。

关于**计时**，有三种常见的系统模型:
1. 同步模型:
    - 假定有上界的网络延迟
    - 有上界的进程暂停
    - 有上界的时钟误差
    - 大多数实际系统的实现模型并非同步模型，因为无限延迟和暂停确实可能发生
2. 部分同步模型:
    - 个系统在大多数情况下像一个同步系统一样运行
    - 但有时候会超出网络延迟，进程暂停和时钟漂移的界限
    - 这是一个比较现实的模型
3. 异步模型:
    - 一个算法不会对时机做任何假设，甚至里面根本没有时钟(也没有超时)
    - 不常见
4. 崩溃-中止模型:
    - 算法假定一个节点只能一种方式发生故障，即遭遇系统崩溃
    - 意味着节点可能在任何时候突然停止响应，且该节点以后永远消失，无法恢复
5. 崩溃-恢复模型:
    - 节点可能在任何时候崩溃，且可能会在一段未知的时间之后得到恢复并在此响应
    - 节点上持久性存储的数据在崩溃恢复之后不会丢失，而内存中的状态可能丢失
6. 拜占庭失效模型:
    - 节点可能发生任何事情，包括作弊和欺诈

真实的系统模型，最普遍的组合是**奔溃-恢复模型 + 部分同步模型**。

### 6.6 真实模型映射到现实世界
在奔溃-恢复模型中，算法通常假设保存到磁盘的数据可以安然无恙，但是现实可能并非如此。

**Quorum 算法要求节点必须记录之前对外所宣告的数据**。如果节点发生意外而丢弃存储的数据，会打破法定条件并破坏算法的正确性。或许此时我们需要一个新的系统模型，它假设**通常情况下数据存储非常可靠，但还是有丢失的可能**。

所以真实模型会更加复杂。