ddia-第八章-分布式系统的麻烦

Posted on Edited on In

尽管我们已经谈了很多错误，但之前几章仍然过于乐观。现实更加黑暗。我们现在将悲观主义最大化，假设任何可能出错的东西都会出错

阅读地址

故障与部分失效

在分布式系统中，尽管系统的其他部分工作正常，但系统的某些部分可能会以某种不可预知的方式被破坏。这被称为部分失效（partial failure）。难点在于部分失效是不确定性的（nonderterministic）：如果你试图做任何涉及多个节点和网络的事情，它有时可能会工作，有时会出现不可预知的失败。

云计算与超级计算机

两个极端：

  • 高性能计算（HPC）领域。具有数千个CPU的超级计算机通常用于计算密集型科学计算任务，如天气预报或分子动力学（模拟原子和分子的运动）。
  • 云计算。通常与多租户数据中心，连接IP网络的商品计算机（通常是以太网），弹性/按需资源分配以及计量计费等相关联。

传统企业数据中心位于这两个极端之间。

不可靠的网络

互联网和数据中心（通常是以太网）中的大多数内部网络都是异步分组网络（asynchronous packet networks）。在这种网络中，一个节点可以向另一个节点发送一个消息（一个数据包），但是网络不能保证它什么时候到达，或者是否到达。如果您发送请求并期待响应，则很多事情可能会出错。

  1. 请求可能已经丢失（可能有人拔掉了网线）。
  2. 请求可能正在排队，稍后将交付（也许网络或收件人超载）。
  3. 远程节点可能已经失效（可能是崩溃或关机）。
  4. 远程节点可能暂时停止了响应（可能会遇到长时间的垃圾回收暂停），但稍后会再次响应。
  5. 远程节点可能已经处理了请求，但是网络上的响应已经丢失（可能是网络交换机配置错误）。
  6. 远程节点可能已经处理了请求，但是响应已经被延迟，并且稍后将被传递（可能是网络或者你自己的机器过载）。

处理这个问题的通常方法是超时（Timeout）：在一段时间之后放弃等待，并且认为响应不会到达。但是，当发生超时时，你仍然不知道远程节点是否收到了请求（如果请求仍然在某个地方排队，那么即使发件人已经放弃了该请求，仍然可能会将其发送给收件人）。

检测故障

许多系统需要自动检测故障节点。例如：

  • 负载平衡器需要停止向已死亡的节点转发请求（即从移出轮询列表（out of rotation））。
  • 在单主复制功能的分布式数据库中，如果主库失效，则需要将从库之一升级为新主库。

不幸的是，网络的不确定性使得很难判断一个节点是否工作。在某些特定的情况下，会收到一些结果。

  • 如果你可以到达运行节点的机器，但没有进程正在侦听目标端口（例如，因为进程崩溃），操作系统将通过发送FIN或RST来关闭并重用TCP连接。但是，如果节点在处理请求时发生崩溃，则无法知道远程节点实际处理了多少数据。
  • 如果节点进程崩溃（或被管理员杀死），但节点的操作系统仍在运行，则脚本可以通知其他节点有关该崩溃的信息，以便另一个节点可以快速接管，而无需等待超时到期。
  • 如果您有权访问数据中心网络交换机的管理界面，则可以查询它们以检测硬件级别的链路故障（例如，远程机器是否关闭电源）。如果您通过互联网连接，或者如果您处于共享数据中心而无法访问交换机，或者由于网络问题而无法访问管理界面，则排除此选项。
  • 如果路由器确认您尝试连接的IP地址不可用，则可能会使用ICMP目标不可达数据包回复您。但是，路由器不具备神奇的故障检测能力——它受到与网络其他参与者相同的限制。

超时与无穷的延迟

那么超时应该等待多久？不幸的是没有答案。

长时间的超时意味着长时间等待，直到一个节点被宣告死亡（在这段时间内，用户可能不得不等待，或者看到错误信息）。

短暂的超时可以更快地检测到故障，但是实际上它只是经历了暂时的减速（例如，由于节点或网络上的负载峰值）而导致错误地宣布节点失效的风险更高。例如邮件重新发送两次。

TCP执行流量控制（flow control）（也称为拥塞避免（congestion avoidance）或背压（backpressure）），其中节点限制自己的发送速率以避免网络链路或接收节点过载。这意味着在数据甚至进入网络之前，在发送者处需要进行额外的排队。

也因此，一些对延迟敏感的应用程序（如视频会议和IP语音（VoIP））使用UDP而不是TCP。这是在可靠性和和延迟可变性之间的折衷：由于UDP不执行流量控制并且不重传丢失的分组。

同步网络 vs 异步网络

有限延迟（bounded delay）：数据经过多个路由器，也不会受到排队的影响，因为呼叫的16位空间已经在网络的下一跳中保留了下来。而且由于没有排队，网络的最大端到端延迟是固定的。

电话网络中的电路与TCP连接有很大不同：电路是固定数量的预留带宽，在电路建立时没有其他人可以使用，而TCP连接的数据包机会性地使用任何可用的网络带宽。您可以给TCP一个可变大小的数据块（例如，一个电子邮件或一个网页），它会尽可能在最短的时间内传输它。 TCP连接空闲时，不使用任何带宽。

如果资源是静态分区的（例如，专用硬件和专用带宽分配），则在某些环境中可以实现延迟保证。但是，这是以降低利用率为代价的——换句话说，它是更昂贵的。另一方面，动态资源分配的多租户提供了更好的利用率，所以它更便宜，但它具有可变延迟的缺点。

电话交换机是静态分区，互联网动态分享网络带宽。

网络中的可变延迟不是一种自然规律，而只是成本/收益权衡的结果。

不可靠的时钟

网络上的每台机器都有自己的时钟，这是一个实际的硬件设备：通常是石英晶体振荡器。这些设备不是完全准确的，所以每台机器都有自己的时间概念，可能比其他机器稍快或更慢。可以在一定程度上同步时钟：最常用的机制是网络时间协议（NTP），它允许根据一组服务器报告的时间来调整计算机时钟。服务器则从更精确的时间源（如GPS接收机）获取时间。

单调钟与时钟

时钟，也叫挂钟时间（wall-clock time）。通常与NTP同步，Linux上的clock_gettime(CLOCK_REALTIME)和Java中的System.currentTimeMillis()

单调钟适用于测量持续时间（时间间隔），例如超时或服务的响应时间：Linux上的clock_gettime(CLOCK_MONOTONIC)，和Java中的System.nanoTime()都是单调时钟。这个名字来源于他们保证总是前进的事实（而时钟可以及时跳回）。

单调钟的绝对值是毫无意义的：它可能是计算机启动以来的纳秒数。特别是比较来自两台不同计算机的单调钟的值是没有意义的，因为它们并不是一回事。

在分布式系统中，使用单调钟测量经过时间（elapsed time）（比如超时）通常很好，因为它不假定不同节点的时钟之间存在任何同步，并且对测量的轻微不准确性不敏感。

时钟同步与准确性

计算机中的石英钟不够精确：它会漂移（drifts）（运行速度快于或慢于预期）。时钟漂移取决于机器的温度。 Google假设其服务器时钟漂移为200 ppm（百万分之一），相当于每30秒与服务器重新同步一次的时钟漂移为6毫秒，或者每天重新同步的时钟漂移为17秒。即使一切工作正常，此漂移也会限制可以达到的最佳准确度。

  • 如果计算机的时钟与NTP服务器的时钟差别太大，可能会拒绝同步，或者本地时钟将被强制重置。
  • 如果某个节点被NTP服务器意外阻塞，可能会在一段时间内忽略错误配置。
  • TP同步只能和网络延迟一样好，所以当您在拥有可变数据包延迟的拥塞网络上时，NTP同步的准确性会受到限制。较大的网络延迟会导致NTP客户端完全放弃。
  • 一些NTP服务器错误或配置错误，报告时间已经过去了几个小时。 NTP客户端非常强大，因为他们查询多个服务器并忽略异常值。
  • 处理闰秒的最佳方法可能是通过在一天中逐渐执行闰秒调整（这被称为拖尾（smearing））
  • 在虚拟机中，硬件时钟被虚拟化，这对于需要精确计时的应用程序提出了额外的挑战。当一个CPU核心在虚拟机之间共享时，每个虚拟机都会暂停几十毫秒，与此同时另一个虚拟机正在运行。从应用程序的角度来看，这种停顿表现为时钟突然向前跳跃。
  • 如果您在未完全控制的设备上运行软件（例如，移动设备或嵌入式设备），则不能信任该设备的硬件时钟。

有序事件的时间戳

最后写入胜利（LWW），它在多领导者复制和无领导者数据库中被广泛使用。客户端通过时间戳而不是先后来判定写入哪一个值。

逻辑时钟（logic clock）是基于递增计数器而不是振荡石英晶体，对于排序事件来说是更安全的选择。逻辑时钟不测量一天中的时间或经过的秒数，而仅测量事件的相对顺序。

用来测量实际经过时间的时钟和单调钟也被称为物理时钟（physical clock）。

时钟读数存在置信区间

机器的时钟大概率是不准确的——使用公共互联网上的NTP服务器，最好的准确度可能达到几十毫秒，而且当网络拥塞时，误差可能会超过100毫秒。

置信区间就是【最早的时间，最晚的时间】，因为机器会有误差导致的时间偏差。大多数系统不公开这种不确定性。

全局快照的同步时钟

只有当区间重叠时，我们才不确定A和B发生的顺序。

为了确保事务时间戳反映因果关系，在提交读写事务之前，Spanner在提交读写事务时，会故意等待置信区间长度的时间。通过这样，它可以确保任何可能读取数据的事务处于足够晚的时间，因此它们的置信区间不会重叠。为了保持尽可能短的等待时间，Spanner需要保持尽可能小的时钟不确定性，为此，Google在每个数据中心都部署了一个GPS接收器或原子钟，这允许时钟在大约7毫秒内同步。

暂停进程

假设你有一个数据库，每个分区只有一个领导者。只有领导被允许接受写入。一个节点如何知道它是领导者（它并没有被别人宣告为死亡），并且它可以安全地接受写入？

领导者从其他节点获得一个租约（lease），类似一个带超时的锁。任一时刻只有一个节点可以持有租约——因此，当一个节点获得一个租约时，它知道它在某段时间内自己是领导者，直到租约到期。为了保持领导地位，节点必须周期性地在租约过期前续期。

如果节点发生故障，就会停止续期，所以当租约过期时，另一个节点可以接管。

这种做法有几种隐患：

  • 租约到期时间是由另一台机器设置，与本地时钟比较，时钟可能会出现不同步的问题。
  • 实际的任务执行了很久，租约早已经过期。

线程可能会暂停很长时间的原因都有：

  • 编程语言的垃圾收集器，偶尔要停止所有线程，这个会持续几分钟。
  • 虚拟化环境里，挂起虚拟机（暂停执行所有进程并将内存内容保存到磁盘）并恢复（恢复内容并继续执行）。暂停的时间长度取决于写入内存的速率。
  • 笔记本电脑上，执行可能会被暂停并随意恢复。如合上笔记本电脑。
  • 当操作系统上下文切换到另一个线程时，或者当管理程序切换到另一个虚拟机时（在虚拟机中运行时），当前正在运行的线程可以在代码中的任意点处暂停。
  • 如果应用程序执行同步磁盘访问，则线程可能暂停，等待缓慢的磁盘I/O操作完成。
  • 如果操作系统配置为允许交换到磁盘（分页），则简单的内存访问可能导致页面错误（page fault），要求将磁盘中的页面装入内存。当这个缓慢的I/O操作发生时，线程暂停。
  • 发送SIGSTOP信号来暂停Unix进程，例如通过在shell中按下Ctrl-Z。 这个信号立即阻止进程继续执行更多的CPU周期，直到SIGCONT恢复为止，此时它将继续运行。 即使你的环境通常不使用SIGSTOP，也可能由运维工程师意外发送。

响应时间保证

硬实时（hard real-time）系统：某些软件的运行环境要求很高，不能在特定时间内响应可能会导致严重的损失。

真理由多数所定义

如果法定数量的节点宣告另一个节点已经死亡，那么即使该节点仍感觉自己活着，它也必须被认为是死的。个体节点必须遵守法定决定并下台。

领导者和锁

通常情况下，一些东西在一个系统中只能有一个。例如：

  • 数据库分区的领导者只能有一个节点，以避免脑裂（split brain）。
  • 特定资源的锁或对象只允许一个事务/客户端持有，以防同时写入和损坏。
  • 一个特定的用户名只能被一个用户所注册，因为用户名必须唯一标识一个用户。

如果持有租约的客户端暂停太久，它的租约将到期。另一个客户端可以获得同一文件的租约，并开始写入文件。当暂停的客户端回来时，它认为它仍然有一个有效的租约，并继续写入文件。结果，客户的写入冲突和损坏的文件。

处理的方法是：我们假设每次锁定服务器授予锁或租约时，它还会返回一个防护令牌（fencing token），这个数字在每次授予锁定时都会增加（例如，由锁定服务增加）。然后，我们可以要求客户端每次向存储服务发送写入请求时，都必须包含当前的防护令牌。

客户端1以33的令牌获得租约，但随后进入一个长时间的停顿并且租约到期。客户端2以34的令牌（该数字总是增加）获取租约，然后将其写入请求发送到存储服务，包括34的令牌。稍后，客户端1恢复生机并将其写入存储服务，包括其令牌值33.但是，存储服务器会记住它已经处理了一个具有更高令牌编号（34）的写入，因此它会拒绝带有令牌33的请求。

拜占庭故障

如果存在节点可能“撒谎”（发送任意错误或损坏的响应）的风险，则分布式系统的问题变得更困难了——例如，如果节点可能声称其实际上没有收到特定的消息。这种行为被称为拜占庭故障（Byzantine fault），在不信任的环境中达成共识的问题被称为拜占庭将军问题。

当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作，称之为拜占庭容错（Byzantine fault-tolerant）的，在特定场景下，这种担忧在是有意义的，比如航天系统。

系统模型与现实

同步模型

假设网络延迟，进程暂停和和时钟误差都是有界限的。这并不意味着完全同步的时钟或零网络延迟；这只意味着你知道网络延迟，暂停和时钟漂移将永远不会超过某个固定的上限。同步模型并不是大多数实际系统的现实模型，因为无限延迟和暂停确实会发生。

部分同步模型

意味着一个系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的界限。这是很多系统的现实模型：大多数情况下，网络和进程表现良好，否则我们永远无法完成任何事情，但是我们必须承认，在任何时刻假设都存在偶然被破坏的事实。发生这种情况时，网络延迟，暂停和时钟错误可能会变得相当大。

异步模型

在这个模型中，一个算法不允许对时机做任何假设—事实上它甚至没有时钟（所以它不能使用超时）。一些算法被设计为可用于异步模型，但非常受限。

节点失效三种最常见的节点系统模型是：

  • 崩溃-停止故障 算法可能会假设一个节点只能以一种方式失效，即通过崩溃。这意味着节点可能在任意时刻突然停止响应，此后该节点永远消失——它永远不会回来。
  • 崩溃-恢复故障 节点可能会在任何时候崩溃，但也许会在未知的时间之后再次开始响应。在崩溃-恢复（crash-recovery）模型中，假设节点具有稳定的存储（即，非易失性磁盘存储）且会在崩溃中保留，而内存中的状态会丢失。
  • 拜占庭（任意）故障 节点可以做（绝对意义上的）任何事情，包括试图戏弄和欺骗其他节点。

如果我们正在为一个锁生成防护令牌，我们要求算法具有以下属性：

  • 唯一性 没有两个防护令牌请求返回相同的值。
  • 单调序列 如果请求 $x$ 返回了令牌 $t_x$，并且请求$y$返回了令牌$t_y$，并且 $x$ 在 $y$ 开始之前已经完成，那么$t_x <t_y$。
  • 可用性 请求防护令牌并且不会崩溃的节点，最终会收到响应。

安全性（safety）和活性（liveness）。在刚刚给出的例子中，唯一性（uniqueness）和单调序列（monotonic sequence）是安全属性，但可用性是活性（liveness）属性。

安全性通常被非正式地定义为，没有坏事发生，而活性通常就类似：最终好事发生。