《数据密集型应用系统设计》第八章《分布式系统的挑战》笔记

本章描述分布式系统中可能出现的各种问题。

故障与部分失效

单机上的程序，以一种确定性的方式运行：要么工作，要么出错。

然而涉及到多台节点时，会出现系统的一部分正常，一部分异常的情况，称为“部分故障（partial failure）”。

正是由于这种不确定性和部分失效大大提高了分布式系统的复杂性。

不可靠的网络

分布式系统中的多个节点以网络进行通信，但是网络并不保证什么时候到达以及是否一定到达。等待响应的过程中，很多事情可能出错：

• 请求可能丢失。
• 请求在某个队列里等待，无法马上发送。
• 远程节点因为崩溃、宕机等原因已经失效。
• 远程节点因为某些原因暂时无法响应。
• 远程节点接收并且处理了请求，但是回复却丢失了。
• 远程节点已经完成了请求，但是回复被延迟了。

在上图中，请求没有得到响应，但是无法区分是因为什么原因，可能有：请求丢失、远程节点关闭、响应丢失等情况。

从以上可以知道，异步网络中的消息没有得到响应，但是无法判断具体的原因。

处理这种问题通常采用超时机制：在等待一段时间之后，如果没有收到回复则选择放弃，并且认为响应不会到达。

检测网络故障

如果超时是检测网络故障的唯一可行方法，那么这个超时时间应该如何选择？

太小：出现误判的情况。太大：意味着要很长时间才能宣布节点失效了。

假设有一个虚拟的系统，网络可以保证数据报在一个最大延迟范围内：要么在时间d内交付完成，要么丢失。此外，非故障节点在时间r内完成请求的处理。此时，就可以确定成功的请求总是在2d+r时间内完成，因此这个时间是一个理想超时时间。

同步网络和异步网络

既然同步网络可以在规定的延迟时间内完成数据的发送，且不会丢失数据包，那么为什么分布式系统没有选择同步网络，在硬件层面就解决网络问题？

原因在于，固定电话网络中的电路与TCP连接存在很大的不同：电路方式总是预留固定带宽，在电路建立之后其他人无法使用；而TCP连接的数据包则会尝试使用所有可用的网络带宽。TCP可以传送任意大小可变的数据块，会尽力在最短时间内完成数据传送。

不可靠的时钟

很多操作依赖时间，但是时间也是靠不住的，本节就是说这部分的内容。

计算机的时钟分为两种，墙上时钟（time-of-day clock）和单调时钟（monotonic clock），但是两者在使用上是有区别的。

墙上时钟根据某个日历（也称为墙上时间，wall-clock time）返回当前的日期和时间。比如Linux的系统调用clock_gettime(CLOCK_REALTIME)返回自1970年1月1日以来的秒数和毫秒数。

单调时钟更适合用于测试持续时间段（时间间隔），Linux的系统调用clock_gettime(CLOCK_MONITONIC)返回的就是单调时钟。单调时钟的名字源于它们总是保证向前走而不会出现回拨现象。

可以在一个时间点读取单调时钟的值，完成某项工作然后再次检查时钟，时钟之间的插值就是两次检查的时间间隔。

但是，单调时钟的绝对值没有任何意义。

单调时钟不需要同步，而墙上时钟需要根据NTP服务器或外部时间源做调整。

依赖时钟的同步

某些操作强依赖时钟的同步，这里往往容易出现问题，这一节就是列举这些问题。

时间戳与事件顺序

一个常见的功能：跨节点的事件排序，如果高度依赖时钟计时，就存在一定的技术风险。比如，两个客户端同时写入数据库，谁先到达，哪个操作是最新的？

上图中，客户端A写入x=1的时间是42.004秒，而客户端B写入x+=1即x=2虽然在后面发生但是时间是42.003秒。节点2在收到这两个事件时，会根据时间戳错误的认为x=1是最新的值，丢弃了x=2的值。

这种冲突解决方式称为“最后写入获胜（Last Write Win）”，但是这样保持“最新”值并丢弃其他值的做法，由于“最新”的定义强依赖于墙上时钟，则会引入偏差。

时钟的置信区间

不应该把墙上时间视为一个精确的时间点，而更应该被视为带有置信区间的时间范围。比如，系统有95%的置信度认为目前时间在[10.3,10.5]秒之间。

比如Google Spanner中的TrueTime API，在查询当前时间时，会得到两个值：[不早于，不晚于]分别代表误差的最大偏差范围。

进程暂停

另外一个分布式系统中危险使用时钟的例子：假设数据库每个分区只有一个主节点，只有主节点可以接收写入，那么其它节点该如何确信该节点没有被宣告失效，可以继续安全写入呢？

一种思路是主节点从其它节点获得一个租约，类似一个带有超时的锁。某一个时间只有一个节点可以拿到租约，某节点获得租约之后，在租约到期之前，它就是这段时间内的主节点。为了维持主节点的身份，节点必须在到期之前定期去更新租约。如果节点发生了故障，则续约失败，这样另一个节点到期之后就可以接管。

典型流程类似这样：

这段代码有几个问题：

• 依赖于同步的时钟，租约到期时间由另一台机器锁设置，并和本地时间进行比较。如果两者有比较大的误差则可能出现问题。
• 代码中假定了检查点的system.currentTimeMillis()和请求处理process(request)间隔很短。但是，如果进程由于GC等原因被暂停，也有可能发生问题。

知识、真相与谎言

以上阐述了分布式系统中的网络、时钟都不是很靠谱，那么分布式系统中什么信息才具有较大的可信度呢？

在分布式系统中，我们可以明确列出对系统行为（系统模型）的若干假设，然后以满足这些假设条件来为目标构建实际运行的系统。在给定系统模型下，可以验证算法的正确性。这也意味着即使底层模型仅提供少数几个保证，也可以在系统软件层面实现可靠的行为保证。

真相由多数决定

节点不能根据自己的信息来判断自身的状态。由于节点可能随时会失效，可能会暂停、假死，甚至最终无法恢复，因此分布式系统不能完全依赖于单个节点。目前，许多分布式算法都依靠法定票数，即在节点之间进行投票。任何决策都需要来自多个节点的最小投票数，从而减少对特定节点的依赖。

这其中也包括宣告某个节点失效。如果有法定数量的节点声明另一个节点失效，即使该节点仍然感觉自己存活，也必须接受失效的裁定进行下线操作。

主节点与锁

有很多情况下，需要在系统范围内确保只有一个实例，比如：

• 只允许一个节点做为数据库分区的主节点，以防止出现脑裂现象。
• 只允许一个事务或客户端持有特定资源的锁，以防止同时写入。

在分布式系统中，即使某个节点自认为自己是“唯一的那个”，但并不一定系统中的多数节点都这么认为。当系统中的多数节点认为某节点已经失效，但是该节点还继续充当“唯一的那个”节点工作时，就可能出现问题。

如下图中所示，客户端1的锁租约已经到期，但是仍然自认为有效，导致了数据被破坏。

Fencing与锁

当使用锁和租约机制来保护资源的并发访问时，必须确保过期的“唯一的那个”节点不影响其他正常部分。要实现这一点，可以使用fencing（栅栏，隔离之意）技术。

假设每次锁服务在授予锁或租约时，还会返回一个fencing令牌，该令牌每次授予都会递增。然后，客户端每次向存储系统发起写请求时，都必须包含所持有的fencing令牌。

如下图所示，客户端1获得锁租约的时候得到了令牌33，随后陷入长时间暂停直到租约到期。此时客户端2获得了新的锁租约和令牌34。客户端1恢复之后尝试进行写请求，但是此时带上的令牌33小于34，所以被拒绝写操作。

拜占庭故障

fencing令牌可以用于检测并阻止无意的误操作，但是当节点有意故意破坏系统时，在发送消息时就可以故意伪造令牌了。

在不信任的环境中需要达成共识的问题被称为拜占庭将军问题。

理论系统模型与现实

算法的实现不能过分依赖特定的硬件和软件配置。这就要求我们对预期的系统错误进行形式化描述，通过定义一些系统模型来形式化描述算法的前提条件。

在计时方面，有三种常见的模型：

• 同步模型：同步模型假定有上界的网络延迟，有上界的进程暂停和有上界的时钟误差。注意，这并不意味着完全同步的时钟或网络延迟为0.只是意味着清楚的了解网络延迟、暂停和时钟漂移不会超过某个固定的上界。
• 部分同步模型：部分同步意味着系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延时，进程暂停和时钟漂移的预期上界。这是一个比较现实的模型：大多数情况下，网络和进程比较稳定，但是必须考虑到任何关于时机的假设都有偶尔违背的情况，而一旦发生，网络延迟、暂停和时钟偏差都可能会变得非常大。
• 异步模型：在这个模型中，一个算法不会对时机做任何假设，甚至里面根本没有时钟（也没有超时机制）。

除了计时模型，还需要考虑到节点失效，有以下三种常见的节点失效系统模型：

• 崩溃中止模型：在这个模型中，算法假设一个节点以一种方式发生故障，即遭遇系统崩溃。这意味着节点可能在任何时候突然停止响应，且该节点以后永远消失，无法恢复。
• 崩溃恢复模型：节点可能在任何时候发生崩溃，且可能在一段（未知的）时间之后得到恢复并再次响应。在崩溃恢复模型中，节点上持久化存储的数据会在崩溃之后保存，而内存中的状态会丢失。
• 拜占庭失效模型：节点可能发生任何问题，包括试图作弊和欺骗其它节点。

算法的正确性

为了定义算法的正确性，需要描述它的属性信息，例如对于fencing令牌生成算法，有如下属性：

• 唯一性：两个令牌请求不能获得相同的值。
• 单调递增：如果请求x返回了令牌t1，请求y返回了令牌t2，且x在y开始之前先完成，那么t1<t2。
• 可用性：请求令牌的节点如果不发生崩溃那么一定能收到响应。

安全性（safety）和活性（liveness）

有必要区分两种不同的属性：安全性和活性。在上面的例子中，唯一性和单调递增属于安全性，可用性属于活性。

两种性质有何区别？活性的定义中通常包含暗示“最终”一词（最终一致性就是一种活性）。

安全性可以理解为“没有发生意外”，活性类似“预期的事情最终一定会发生”。

• 如果违反了安全性，可以明确指向发生的特定的时间点（例如，唯一性如果被违反，可以定位到具体哪个操作产生了重复令牌）。且一旦违反了安全性，违规行为无法撤销，破坏已实际发生。
• 活性则反过来，可能无法明确某个具体的时间点（例如一个节点发送了一个请求，但还没有收到回应），但总是希望在未来某个时间点可以满足要求（即收到回复）。

区分安全性和活性的一个好处是可以帮助简化处理一些具有挑战性的系统模型。通常对于分布式算法，要求在所有可能的系统模型中，都必须满足安全性。也就是说，即使所有节点发生崩溃，或者整个网络中断，算法确保不能返回错误的结果。

而对于活性，则存在一些必要条件。例如，只有在系统多数节点没有崩溃，以及网络最终可以恢复的前提下，才能保证可以收到响应。