Cloud Computing and Supercomputing

There is a spectrum of philosophies on how to build large-scale computing systems:

如何构建大规模计算系统有各种不同的哲学观点：

• At one end of the scale is the field of high-performance computing (HPC). Supercomputers with thousands of CPUs are typically used for computationally intensive scientific computing tasks, such as weather forecasting or molecular dynamics (simulating the movement of atoms and molecules).

  在一端的尺度上是高性能计算（HPC）领域。具有成千上万个CPU的超级计算机通常用于计算密集的科学计算任务，例如天气预报或分子动力学（模拟原子和分子的运动）。

• At the other extreme is cloud computing , which is not very well defined [ 6 ] but is often associated with multi-tenant datacenters, commodity computers connected with an IP network (often Ethernet), elastic/on-demand resource allocation, and metered billing.

  在另一个极端是云计算，它没有非常明确的定义，但通常与多租户数据中心、使用以太网连接的普通计算机、弹性/按需资源分配以及按量计费相关联。

• Traditional enterprise datacenters lie somewhere between these extremes.

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

With these philosophies come very different approaches to handling faults. In a supercomputer, a job typically checkpoints the state of its computation to durable storage from time to time. If one node fails, a common solution is to simply stop the entire cluster workload. After the faulty node is repaired, the computation is restarted from the last checkpoint [ 7 , 8 ]. Thus, a supercomputer is more like a single-node computer than a distributed system: it deals with partial failure by letting it escalate into total failure—if any part of the system fails, just let everything crash (like a kernel panic on a single machine).

这些哲学观念带来了处理故障的非常不同的方法。在超级计算机中，作业通常会定期将计算状态检查点存储到持久性存储器中。如果一个节点出现故障，一种常见的解决方案是简单地停止整个群集的工作负载。在修复有故障的节点后，计算将从上一个检查点重新启动[7，8]。因此，超级计算机更像单节点计算机，而不是分布式系统：它通过让局部故障升级为总体故障来处理部分故障——如果系统的任何部分出现故障，就让一切崩溃（就像单个机器上的内核恐慌）。

In this book we focus on systems for implementing internet services, which usually look very different from supercomputers:

在本书中，我们专注于实现互联网服务的系统，这些系统通常与超级计算机大不相同。

• Many internet-related applications are online , in the sense that they need to be able to serve users with low latency at any time. Making the service unavailable—for example, stopping the cluster for repair—is not acceptable. In contrast, offline (batch) jobs like weather simulations can be stopped and restarted with fairly low impact.

  许多与互联网相关的应用程序是在线的，这意味着它们需要能够随时以低延迟为用户提供服务。使服务不可用，例如停止集群进行维修，是不可接受的。相反，像天气模拟这样的离线（批处理）作业可以停止和重新启动，影响相对较小。

• Supercomputers are typically built from specialized hardware, where each node is quite reliable, and nodes communicate through shared memory and remote direct memory access (RDMA). On the other hand, nodes in cloud services are built from commodity machines, which can provide equivalent performance at lower cost due to economies of scale, but also have higher failure rates.

  超级计算机通常使用专门的硬件构建，每个节点非常可靠，节点通过共享内存和远程直接内存存取(RDMA)进行通信。另一方面，云服务中的节点是由商品机器构建的，这些商品机器由于经济规模而能够以更低的成本提供相当的性能，但也具有更高的故障率。

• Large datacenter networks are often based on IP and Ethernet, arranged in Clos topologies to provide high bisection bandwidth [ 9 ]. Supercomputers often use specialized network topologies, such as multi-dimensional meshes and toruses [ 10 ], which yield better performance for HPC workloads with known communication patterns.

  大型数据中心网络通常基于IP和以Clos拓扑结构排列的以太网，以提供高度双分带宽[9]。超级计算机通常使用专用的网络拓扑结构，例如多维网格和环形结构[10]，这些结构对HPC负载具有已知通信模式的性能更好。

• The bigger a system gets, the more likely it is that one of its components is broken. Over time, broken things get fixed and new things break, but in a system with thousands of nodes, it is reasonable to assume that something is always broken [ 7 ]. When the error handling strategy consists of simply giving up, a large system can end up spending a lot of its time recovering from faults rather than doing useful work [ 8 ].

  系统越大，它的每个组件出现问题的可能性也越大。随着时间的推移，坏的东西会被修复，新的东西则会出现问题，但在一个拥有成千上万个节点的系统中，可以合理地假设总会有东西是坏的[7]。当错误处理策略只是放弃时，大型系统最终可能会花费大量时间来恢复故障，而不是执行有用的工作[8]。

• If the system can tolerate failed nodes and still keep working as a whole, that is a very useful feature for operations and maintenance: for example, you can perform a rolling upgrade (see Chapter 4 ), restarting one node at a time, while the service continues serving users without interruption. In cloud environments, if one virtual machine is not performing well, you can just kill it and request a new one (hoping that the new one will be faster).

  如果系统能够容忍故障节点，且整体仍能正常运行，那么这将是运营和维护非常有用的特性。例如，你可以执行滚动升级（见第四章），一次重启一个节点，而服务仍能继续为用户提供服务而不会中断。在云环境中，如果一个虚拟机的表现不佳，你可以将其 “kill”，并请求一个新的虚拟机（希望新的虚拟机速度更快些）。

• In a geographically distributed deployment (keeping data geographically close to your users to reduce access latency), communication most likely goes over the internet, which is slow and unreliable compared to local networks. Supercomputers generally assume that all of their nodes are close together.

  在地理分布的部署中（使数据在地理上接近用户以减少访问延迟），通信最可能通过互联网进行，与本地网络相比，互联网速度慢且不可靠。超级计算机通常假定它们的所有节点都彼此靠近。

If we want to make distributed systems work, we must accept the possibility of partial failure and build fault-tolerance mechanisms into the software. In other words, we need to build a reliable system from unreliable components. (As discussed in “Reliability” , there is no such thing as perfect reliability, so we’ll need to understand the limits of what we can realistically promise.)

如果我们想要使分布式系统正常运作，我们必须接受部分失败的可能性，并将容错机制纳入软件中。换句话说，我们需要从不可靠的组件中构建可靠的系统。（正如在“可靠性”中讨论的那样，不存在完美的可靠性，因此我们需要了解我们可以现实承诺的限制。）

Even in smaller systems consisting of only a few nodes, it’s important to think about partial failure. In a small system, it’s quite likely that most of the components are working correctly most of the time. However, sooner or later, some part of the system will become faulty, and the software will have to somehow handle it. The fault handling must be part of the software design, and you (as operator of the software) need to know what behavior to expect from the software in the case of a fault.

即使是由只有几个节点组成的较小系统，考虑到部分故障也是很重要的。在小型系统中，大多数组件大部分时间运行正常是相当可能的。然而，迟早会有一些组件出现故障，软件必须以某种方式进行处理。故障处理必须是软件设计的一部分，您（作为软件的操作者）需要知道在发生故障的情况下可以从软件期望什么样的行为。

It would be unwise to assume that faults are rare and simply hope for the best. It is important to consider a wide range of possible faults—even fairly unlikely ones—and to artificially create such situations in your testing environment to see what happens. In distributed systems, suspicion, pessimism, and paranoia pay off.

认为故障很少并且只是希望一切顺利是不明智的。重要的是要考虑到各种可能的故障，即使是相对不太可能的故障，也要在测试环境中人为创建这种情况来观察发生了什么。在分布式系统中，怀疑，悲观和偏执是有回报的。

Network Faults in Practice

We have been building computer networks for decades—one might hope that by now we would have figured out how to make them reliable. However, it seems that we have not yet succeeded.

数十年来，我们一直在建立计算机网络——人们或许希望我们早已学会如何使它们可靠。然而，现在看来我们还没有成功。

There are some systematic studies, and plenty of anecdotal evidence, showing that network problems can be surprisingly common, even in controlled environments like a datacenter operated by one company [ 14 ]. One study in a medium-sized datacenter found about 12 network faults per month, of which half disconnected a single machine, and half disconnected an entire rack [ 15 ]. Another study measured the failure rates of components like top-of-rack switches, aggregation switches, and load balancers [ 16 ]. It found that adding redundant networking gear doesn’t reduce faults as much as you might hope, since it doesn’t guard against human error (e.g., misconfigured switches), which is a major cause of outages.

一些系统研究和大量的个人经验表明，即使是由一家公司操作的数据中心这样的受控环境中，网络问题也可能很常见 。一项在中型数据中心进行的研究发现，每月约有12次网络故障，其中一半将一个计算机断开连接，另一半将整个机架断开连接。另一项研究测量了顶部交换机、聚合交换机和负载均衡器等组件的故障率。它发现，添加冗余网络设备并不能像您希望的那样减少故障，因为它不能防止人为错误（例如，配置错误的交换机），这是故障的主要原因之一。

Public cloud services such as EC2 are notorious for having frequent transient network glitches [ 14 ], and well-managed private datacenter networks can be stabler environments. Nevertheless, nobody is immune from network problems: for example, a problem during a software upgrade for a switch could trigger a network topology reconfiguration, during which network packets could be delayed for more than a minute [ 17 ]. Sharks might bite undersea cables and damage them [ 18 ]. Other surprising faults include a network interface that sometimes drops all inbound packets but sends outbound packets successfully [ 19 ]: just because a network link works in one direction doesn’t guarantee it’s also working in the opposite direction.

公共云服务，比如EC2，以频繁的短暂网络故障著称[14]，而良好管理的私有数据中心网络可能会更加稳定。然而，无论如何，任何人都不能免于网络问题：例如，交换机软件升级期间出现问题可能会触发网络拓扑重构，在此期间，网络数据包可能会延迟超过一分钟[17]。鲨鱼可能会咬断海底电缆并损坏它们[18]。其他令人惊讶的故障包括某些时候会丢失所有入站数据包但能成功发送出站数据包的网络接口[19]：仅因为一个网络连接在一个方向工作并不能保证它在相反方向也能正常工作。

Even if network faults are rare in your environment, the fact that faults can occur means that your software needs to be able to handle them. Whenever any communication happens over a network, it may fail—there is no way around it.

即使在您的环境中网络故障很少见，但故障可能发生的事实意味着您的软件需要能够处理它们。无论何时在网络上进行任何通信，都可能会失败-这是无法避免的。

If the error handling of network faults is not defined and tested, arbitrarily bad things could happen: for example, the cluster could become deadlocked and permanently unable to serve requests, even when the network recovers [ 20 ], or it could even delete all of your data [ 21 ]. If software is put in an unanticipated situation, it may do arbitrary unexpected things.

如果网络故障的错误处理未定义和测试，可能会发生任意糟糕的事情：例如，集群可能会陷入死锁状态，永久无法提供请求服务，即使网络恢复[20]，或者甚至可能删除所有数据[21]。如果软件遇到未预料的情况，它可能会做出任意意想不到的事情。

Handling network faults doesn’t necessarily mean tolerating them: if your network is normally fairly reliable, a valid approach may be to simply show an error message to users while your network is experiencing problems. However, you do need to know how your software reacts to network problems and ensure that the system can recover from them. It may make sense to deliberately trigger network problems and test the system’s response (this is the idea behind Chaos Monkey; see “Reliability” ).

处理网络故障并不一定意味着容忍它们：如果您的网络通常相当可靠，一种有效的方法可能是在网络遇到问题时向用户显示错误消息。然而，您需要了解您的软件如何应对网络问题，并确保系统可以从中恢复。 有意诱发网络问题并测试系统的响应可能是有意义的（这是混沌猴子背后的想法；请参见“可靠性”）。

Detecting Faults

Many systems need to automatically detect faulty nodes. For example:

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

• A load balancer needs to stop sending requests to a node that is dead (i.e., take it out of rotation ).

  负载均衡器需要停止向已经挂掉的节点发送请求（即将其从轮循列表中移除）。

• In a distributed database with single-leader replication, if the leader fails, one of the followers needs to be promoted to be the new leader (see “Handling Node Outages” ).

  在具有单领导复制的分布式数据库中，如果领导者失败，则需要将其中一个跟随者提升为新领导者（请参见“处理节点故障”）。

Unfortunately, the uncertainty about the network makes it difficult to tell whether a node is working or not. In some specific circumstances you might get some feedback to explicitly tell you that something is not working:

不幸的是，由于网络的不确定性，很难确定节点是否正常工作。在某些特定情况下，您可能会得到一些反馈来明确告诉您某些东西没有正常工作。

• If you can reach the machine on which the node should be running, but no process is listening on the destination port (e.g., because the process crashed), the operating system will helpfully close or refuse TCP connections by sending a RST or FIN packet in reply. However, if the node crashed while it was handling your request, you have no way of knowing how much data was actually processed by the remote node [ 22 ].

  如果您可以连接到节点应该运行的机器，但目的端口上没有进程正在监听（例如，因为进程崩溃了），操作系统会发送RST或FIN数据包来关闭或拒绝TCP连接。然而，如果节点在处理您的请求时崩溃了，您就无法知道远程节点实际处理了多少数据。

• If a node process crashed (or was killed by an administrator) but the node’s operating system is still running, a script can notify other nodes about the crash so that another node can take over quickly without having to wait for a timeout to expire. For example, HBase does this [ 23 ].

  如果节点进程崩溃（或被管理员终止），但节点的操作系统仍在运行，脚本可以通知其他节点关于崩溃的情况，以便另一个节点可以快速接管而不必等待超时过期。例如，HBase就是这样做的。

• If you have access to the management interface of the network switches in your datacenter, you can query them to detect link failures at a hardware level (e.g., if the remote machine is powered down). This option is ruled out if you’re connecting via the internet, or if you’re in a shared datacenter with no access to the switches themselves, or if you can’t reach the management interface due to a network problem.

  如果您可以访问数据中心网络交换机的管理界面，您可以查询它们以检测硬件级别的链路故障（例如，如果远程计算机关闭电源）。如果您通过互联网连接，或者在一个共享数据中心中，无法访问交换机自身，或者由于网络问题无法到达管理界面，则此选项被排除。

• If a router is sure that the IP address you’re trying to connect to is unreachable, it may reply to you with an ICMP Destination Unreachable packet. However, the router doesn’t have a magic failure detection capability either—it is subject to the same limitations as other participants of the network.

  如果路由器确定你要连接的IP地址无法到达，它可能会向你发送一个ICMP目的地不可达的数据包。但是，路由器也没有奇迹般的故障检测能力，它受到网络其他参与者同样的限制。

Rapid feedback about a remote node being down is useful, but you can’t count on it. Even if TCP acknowledges that a packet was delivered, the application may have crashed before handling it. If you want to be sure that a request was successful, you need a positive response from the application itself [ 24 ].

远程节点故障的快速反馈很有用，但不能依赖它。即使TCP确认消息已传递，应用程序在处理消息之前可能已经崩溃。如果您想确保请求成功，您需要从应用程序本身获得积极的响应[24]。

Conversely, if something has gone wrong, you may get an error response at some level of the stack, but in general you have to assume that you will get no response at all. You can retry a few times (TCP retries transparently, but you may also retry at the application level), wait for a timeout to elapse, and eventually declare the node dead if you don’t hear back within the timeout.

相反地，如果出现了问题，可能会在堆栈的某个层次上收到错误响应，但通常你必须假设你将根本不会收到任何响应。你可以尝试几次（TCP 会透明地重试，但您也可以在应用层重试），等待超时时间到期，如果在超时时间内没有收到回复，最终将节点设置为离线。

Timeouts and Unbounded Delays

If a timeout is the only sure way of detecting a fault, then how long should the timeout be? There is unfortunately no simple answer.

如果一个超时是唯一能够确定故障的方法，那么超时时间应该是多少呢？不幸的是，没有简单的答案。

A long timeout means a long wait until a node is declared dead (and during this time, users may have to wait or see error messages). A short timeout detects faults faster, but carries a higher risk of incorrectly declaring a node dead when in fact it has only suffered a temporary slowdown (e.g., due to a load spike on the node or the network).

长时间超时意味着节点被宣告为死亡需要等待很长时间（在此期间，用户可能需要等待或看到错误消息）。短时间超时可以更快地检测故障，但可能会错误地宣告节点死亡，而实际上它只是暂时减速（例如，由于节点或网络的负载峰值）的风险更高。

Prematurely declaring a node dead is problematic: if the node is actually alive and in the middle of performing some action (for example, sending an email), and another node takes over, the action may end up being performed twice. We will discuss this issue in more detail in “Knowledge, Truth, and Lies” , and in Chapters 9 and 11 .

过早宣布节点死亡是有问题的：如果节点实际上仍然存活并正在执行某些操作（例如发送电子邮件），而另一个节点接管了，那么该操作可能会被执行两次。我们将在“知识，真相和谎言”以及第9章和第11章中更详细地讨论这个问题。

When a node is declared dead, its responsibilities need to be transferred to other nodes, which places additional load on other nodes and the network. If the system is already struggling with high load, declaring nodes dead prematurely can make the problem worse. In particular, it could happen that the node actually wasn’t dead but only slow to respond due to overload; transferring its load to other nodes can cause a cascading failure (in the extreme case, all nodes declare each other dead, and everything stops working).

当一个节点被宣布死亡时，它的责任需要转移到其他节点，这会给其他节点和网络增加额外的负载。如果系统已经处于高负载状态，过早地宣布节点死亡可能会使问题恶化。特别的，可能会发生节点实际上并没有死亡，只是因为负载过重而反应较慢的情况；将它的负载转移到其他节点可能会导致级联故障（在极端情况下，所有节点互相宣布死亡，一切都停止工作）。

Imagine a fictitious system with a network that guaranteed a maximum delay for packets—every packet is either delivered within some time d , or it is lost, but delivery never takes longer than d . Furthermore, assume that you can guarantee that a non-failed node always handles a request within some time r . In this case, you could guarantee that every successful request receives a response within time 2 d + r —and if you don’t receive a response within that time, you know that either the network or the remote node is not working. If this was true, 2 d + r would be a reasonable timeout to use.

想象一个虚构的系统，其中网络保证了分组的最大延迟——每个分组都在某个时间d内被传送，否则就会丢失，但传送时间永远不会超过d。 此外，请假设您可以保证非故障节点始终在某个时间r内处理请求。在这种情况下，您可以保证每个成功的请求都会在2d + r时间内接收到响应——如果您没有在该时间内收到响应，那么您就知道网络或远程节点不起作用了。如果这是真的，2d + r将是一个合理的超时时间。

Unfortunately, most systems we work with have neither of those guarantees: asynchronous networks have unbounded delays (that is, they try to deliver packets as quickly as possible, but there is no upper limit on the time it may take for a packet to arrive), and most server implementations cannot guarantee that they can handle requests within some maximum time (see “Response time guarantees” ). For failure detection, it’s not sufficient for the system to be fast most of the time: if your timeout is low, it only takes a transient spike in round-trip times to throw the system off-balance.

很不幸，我们所涉及的大多数系统都没有这些保证：异步网络有无限延迟（也就是说，它们会尽可能快地传输数据包，但数据包到达所需的时间没有上限），并且大多数服务器实现不能保证在某个最大时间内处理请求（请参阅“响应时间保证”）。对于故障检测来说，系统大部分时间表现良好是不够的：如果您的超时时间很短，只需一次往返延迟的瞬时波动就足以使系统失衡。

Network congestion and queueing

When driving a car, travel times on road networks often vary most due to traffic congestion. Similarly, the variability of packet delays on computer networks is most often due to queueing [ 25 ]:

在驾驶汽车时，路网上的行驶时间往往最受交通拥堵的影响变化最大。同样，计算机网络中数据包延迟的变化也往往是由于队列延迟引起的。

• If several different nodes simultaneously try to send packets to the same destination, the network switch must queue them up and feed them into the destination network link one by one (as illustrated in Figure 8-2 ). On a busy network link, a packet may have to wait a while until it can get a slot (this is called network congestion ). If there is so much incoming data that the switch queue fills up, the packet is dropped, so it needs to be resent—even though the network is functioning fine.

  如果有多个不同的节点同时尝试发送数据包到相同的目的地，网络交换机必须将它们排队并逐一输入目的地网络链接（如图8-2所示）。在繁忙的网络链接上，数据包可能需要等待一段时间才能获得槽位（这被称为网络拥塞）。如果有太多的传入数据，交换机队列就会填满，数据包就会被丢弃，因此需要重新发送，即使网络正常运行。

• When a packet reaches the destination machine, if all CPU cores are currently busy, the incoming request from the network is queued by the operating system until the application is ready to handle it. Depending on the load on the machine, this may take an arbitrary length of time.

  当数据包到达目标机器时，如果所有CPU核心都在忙，那么操作系统会将来自网络的请求排队，直到应用程序准备好处理它。根据机器的负载情况，这可能需要任意长度的时间。

• In virtualized environments, a running operating system is often paused for tens of milliseconds while another virtual machine uses a CPU core. During this time, the VM cannot consume any data from the network, so the incoming data is queued (buffered) by the virtual machine monitor [ 26 ], further increasing the variability of network delays.

  在虚拟化环境中，运行中的操作系统常常会因为另一个虚拟机在使用CPU核心而暂停数十毫秒。在此期间，虚拟机无法从网络中消耗任何数据，因此进入的数据将被虚拟机监视器排队缓冲，进一步增加了网络延迟的不确定性。

• TCP performs flow control (also known as congestion avoidance or backpressure ), in which a node limits its own rate of sending in order to avoid overloading a network link or the receiving node [ 27 ]. This means additional queueing at the sender before the data even enters the network.

  TCP执行流量控制（也称拥塞避免或反压），其中节点限制自己的发送速率，以避免超载网络链接或接收节点[27]。这意味着在数据甚至进入网络之前，在发送方进行额外的排队。

Figure 8-2. If several machines send network traffic to the same destination, its switch queue can fill up. Here, ports 1, 2, and 4 are all trying to send packets to port 3.

Moreover, TCP considers a packet to be lost if it is not acknowledged within some timeout (which is calculated from observed round-trip times), and lost packets are automatically retransmitted. Although the application does not see the packet loss and retransmission, it does see the resulting delay (waiting for the timeout to expire, and then waiting for the retransmitted packet to be acknowledged).

此外，TCP 认为如果一份数据包在规定的超时时间内（这个超时时间是从已观察到的往返时间计算出来的）没有得到确认，那么这份数据包就被视为丢失了。并且，已经丢失的数据包会自动地被重新发送。虽然应用程序并没有意识到数据包的丢失和重新发送，但是它会感知到由此带来的延迟（因为需要等待超时时间的到来，然后再等待重新发送的数据包被确认）。

All of these factors contribute to the variability of network delays. Queueing delays have an especially wide range when a system is close to its maximum capacity: a system with plenty of spare capacity can easily drain queues, whereas in a highly utilized system, long queues can build up very quickly.

所有这些因素都会导致网络延迟的变化。排队延迟在系统接近最大容量时具有特别广泛的范围：有足够多备用容量的系统可以轻松地排空队列，而在高度利用的系统中，队列很快就会积累起来。

In public clouds and multi-tenant datacenters, resources are shared among many customers: the network links and switches, and even each machine’s network interface and CPUs (when running on virtual machines), are shared. Batch workloads such as MapReduce (see Chapter 10 ) can easily saturate network links. As you have no control over or insight into other customers’ usage of the shared resources, network delays can be highly variable if someone near you (a noisy neighbor ) is using a lot of resources [ 28 , 29 ].

在公共云和多租户数据中心中，资源被许多客户共享：网络链接和交换机，甚至每台机器的网络接口和 CPU（在虚拟机上运行时）都是共享的。 批处理工作负载，例如MapReduce（见第十章），可以轻松饱和网络链接。 由于您无法控制或了解其他客户对共享资源的使用，如果某个邻近的用户（嘈杂的邻居）正在使用大量资源，则网络延迟可能会变化很大 [28，29]。

In such environments, you can only choose timeouts experimentally: measure the distribution of network round-trip times over an extended period, and over many machines, to determine the expected variability of delays. Then, taking into account your application’s characteristics, you can determine an appropriate trade-off between failure detection delay and risk of premature timeouts.

在这种环境下，您只能通过实验选择适当的超时时间：长时间内测量网络往返延迟时间分布，并在多台设备上测量，从而确定延迟期望的可变性。然后，考虑您的应用特点，您可以确定适当的故障检测延迟和过早超时的风险之间的权衡。

Even better, rather than using configured constant timeouts, systems can continually measure response times and their variability ( jitter ), and automatically adjust timeouts according to the observed response time distribution. This can be done with a Phi Accrual failure detector [ 30 ], which is used for example in Akka and Cassandra [ 31 ]. TCP retransmission timeouts also work similarly [ 27 ].

更好的做法是，系统可以不使用配置的恒定超时时间，而是不断测量响应时间及其变异性（抖动），并根据观察到的响应时间分布自动调整超时时间。这可以通过Phi Accrual失效探测器来实现，例如Akka和Cassandra中使用的方法。TCP重传超时时间也类似地工作。

Synchronous Versus Asynchronous Networks

Distributed systems would be a lot simpler if we could rely on the network to deliver packets with some fixed maximum delay, and not to drop packets. Why can’t we solve this at the hardware level and make the network reliable so that the software doesn’t need to worry about it?

如果我们可以依赖网络以一定的最长延迟传递数据包，而不是丢弃数据包，分布式系统将会更简单。为什么我们不能在硬件层面解决这个问题，使网络变得可靠，从而软件不需要担心这些问题呢？

To answer this question, it’s interesting to compare datacenter networks to the traditional fixed-line telephone network (non-cellular, non-VoIP), which is extremely reliable: delayed audio frames and dropped calls are very rare. A phone call requires a constantly low end-to-end latency and enough bandwidth to transfer the audio samples of your voice. Wouldn’t it be nice to have similar reliability and predictability in computer networks?

回答这个问题，有趣的是将数据中心网络与传统的固定电话网络（非蜂窝、非VoIP）进行比较，后者非常可靠：延迟的音频帧和掉话非常少。电话呼叫需要始终保持低的端到端延迟和足够的带宽来传输您的语音样本。难道在计算机网络中拥有类似的可靠性和可预测性不好吗？

When you make a call over the telephone network, it establishes a circuit : a fixed, guaranteed amount of bandwidth is allocated for the call, along the entire route between the two callers. This circuit remains in place until the call ends [ 32 ]. For example, an ISDN network runs at a fixed rate of 4,000 frames per second. When a call is established, it is allocated 16 bits of space within each frame (in each direction). Thus, for the duration of the call, each side is guaranteed to be able to send exactly 16 bits of audio data every 250 microseconds [ 33 , 34 ].

当你通过电话网络打电话时，它建立了一个电路：在两个通话者之间的整个路线上，分配了一个固定的，保证的带宽量用于通话。这个电路一直保持到通话结束为止。例如，ISDN网络以固定速率运行为每秒4,000帧。当通话建立时，在每个帧（每个方向）内分配了16个位的空间。因此，在通话期间，每个部分都保证可以每250微秒传送确切的16位音频数据。

This kind of network is synchronous : even as data passes through several routers, it does not suffer from queueing, because the 16 bits of space for the call have already been reserved in the next hop of the network. And because there is no queueing, the maximum end-to-end latency of the network is fixed. We call this a bounded delay .

这种网络是同步的：即使数据经过多个路由器，由于调用的16位空间已在网络的下一个跳中预留，因此它不会受到排队的影响。由于没有排队，网络的最大端到端延迟是固定的。我们称之为有界时延。

Monotonic Versus Time-of-Day Clocks

Modern computers have at least two different kinds of clocks: a time-of-day clock and a monotonic clock . Although they both measure time, it is important to distinguish the two, since they serve different purposes.

现代计算机至少有两种不同类型的时钟：一个是时间钟，另一个是单调钟。虽然它们都可以测量时间，但是将它们区分开来非常重要，因为它们有不同的用途。

Clock Synchronization and Accuracy

Monotonic clocks don’t need synchronization, but time-of-day clocks need to be set according to an NTP server or other external time source in order to be useful. Unfortunately, our methods for getting a clock to tell the correct time aren’t nearly as reliable or accurate as you might hope—hardware clocks and NTP can be fickle beasts. To give just a few examples:

单调时钟不需要同步，但是时钟需要按照NTP服务器或其他外部时间源设置，以便有用。不幸的是，我们校准时钟的方法并不像您希望的那样可靠或准确 - 硬件时钟和NTP可能会出现问题。举几个例子：

• The quartz clock in a computer is not very accurate: it drifts (runs faster or slower than it should). Clock drift varies depending on the temperature of the machine. Google assumes a clock drift of 200 ppm (parts per million) for its servers [ 41 ], which is equivalent to 6 ms drift for a clock that is resynchronized with a server every 30 seconds, or 17 seconds drift for a clock that is resynchronized once a day. This drift limits the best possible accuracy you can achieve, even if everything is working correctly.

  电脑中的石英钟不太准确：它会漂移（比应该的快或慢）。时钟漂移取决于设备的温度。谷歌的服务器假定钟漂移为200个百万分之一（ppm）[41]，相当于每30秒重新与服务器同步一次的时钟漂移为6毫秒，或每天重新同步一次的时钟漂移为17秒。即使一切正常，此漂移也限制了您能够实现的最佳精度。

• If a computer’s clock differs too much from an NTP server, it may refuse to synchronize, or the local clock will be forcibly reset [ 37 ]. Any applications observing the time before and after this reset may see time go backward or suddenly jump forward.

  如果电脑时钟与NTP服务器差距太大，它可能会拒绝同步，或者本地时钟会被强制重置[37]。在此重置之前和之后观察时间的任何应用程序可能会看到时间倒流或突然向前跳跃。

• If a node is accidentally firewalled off from NTP servers, the misconfiguration may go unnoticed for some time. Anecdotal evidence suggests that this does happen in practice.

  如果某个节点意外地被防火墙隔离在NTP服务器之外，这种配置错误可能会被忽视一段时间。个人经验表明，实际上确实会发生这种情况。

• NTP synchronization can only be as good as the network delay, so there is a limit to its accuracy when you’re on a congested network with variable packet delays. One experiment showed that a minimum error of 35 ms is achievable when synchronizing over the internet [ 42 ], though occasional spikes in network delay lead to errors of around a second. Depending on the configuration, large network delays can cause the NTP client to give up entirely.

  NTP同步的准确度受网络延迟的影响，当网络拥塞且包传输时间变化时，其准确度将受到限制。一项实验表明，通过互联网同步可以达到最小误差为35毫秒的精度[42]，但是偶尔遇到的网络延迟峰值会导致误差大约为一秒。根据配置，大的网络延迟可能会导致NTP客户端完全放弃。

• Some NTP servers are wrong or misconfigured, reporting time that is off by hours [ 43 , 44 ]. NTP clients are quite robust, because they query several servers and ignore outliers. Nevertheless, it’s somewhat worrying to bet the correctness of your systems on the time that you were told by a stranger on the internet.

  有一些NTP服务器的时间是错误的或者配置不当，与实际时间相差数小时[43, 44]。 NTP客户端非常强大，因为它们会查询多个服务器并忽略异常值。 尽管如此，但是将系统的正确性放在来自互联网上的陌生人的时间上还是令人担忧的。

• Leap seconds result in a minute that is 59 seconds or 61 seconds long, which messes up timing assumptions in systems that are not designed with leap seconds in mind [ 45 ]. The fact that leap seconds have crashed many large systems [ 38 , 46 ] shows how easy it is for incorrect assumptions about clocks to sneak into a system. The best way of handling leap seconds may be to make NTP servers “lie,” by performing the leap second adjustment gradually over the course of a day (this is known as smearing ) [ 47 , 48 ], although actual NTP server behavior varies in practice [ 49 ].

  闰秒会导致一分钟长为59秒或61秒，这会影响那些没有考虑闰秒的系统的时间假设。事实上，闰秒已经让许多大型系统崩溃，显示了时钟方面的错误假设多么容易潜入系统中。最好的处理闰秒的方法可能是让NTP服务器“撒谎”，在一天的时间内逐渐进行闰秒调整（这被称为扩散），尽管实际的NTP服务器行为因实践而异。

• In virtual machines, the hardware clock is virtualized, which raises additional challenges for applications that need accurate timekeeping [ 50 ]. When a CPU core is shared between virtual machines, each VM is paused for tens of milliseconds while another VM is running. From an application’s point of view, this pause manifests itself as the clock suddenly jumping forward [ 26 ].

  在虚拟机中，硬件时钟被虚拟化，这给需要准确计时的应用程序带来了额外的挑战[50]。 当一个CPU核心在虚拟机之间共享时，每个虚拟机都会暂停数十毫秒，而另一个虚拟机正在运行。从应用程序的角度来看，这种暂停表现为时钟突然向前跳动[26]。

• If you run software on devices that you don’t fully control (e.g., mobile or embedded devices), you probably cannot trust the device’s hardware clock at all. Some users deliberately set their hardware clock to an incorrect date and time, for example to circumvent timing limitations in games. As a result, the clock might be set to a time wildly in the past or the future.

  如果您在未完全控制的设备上运行软件（例如移动设备或嵌入式设备），您可能无法完全信任设备的硬件时钟。一些用户会故意将其硬件时钟设置为不正确的日期和时间，例如为了规避游戏中的时间限制。因此，时钟可能被设置为过去或未来的时间。

It is possible to achieve very good clock accuracy if you care about it sufficiently to invest significant resources. For example, the MiFID II draft European regulation for financial institutions requires all high-frequency trading funds to synchronize their clocks to within 100 microseconds of UTC, in order to help debug market anomalies such as “flash crashes” and to help detect market manipulation [ 51 ].

如果你足够重视，愿意投入更多的资源，就有可能实现非常好的时钟精度。例如，欧洲金融机构的《MiFID II》草案要求所有高频交易基金将时钟同步到离协调世界时（UTC）100微秒以内，以帮助调试市场异常，例如“闪崩”，并帮助检测市场操纵[51]。

Such accuracy can be achieved using GPS receivers, the Precision Time Protocol (PTP) [ 52 ], and careful deployment and monitoring. However, it requires significant effort and expertise, and there are plenty of ways clock synchronization can go wrong. If your NTP daemon is misconfigured, or a firewall is blocking NTP traffic, the clock error due to drift can quickly become large.

通过使用GPS接收器、精确时间协议（PTP）[52]和仔细的部署和监测可以达到这种准确度。然而，这需要大量的努力和专业技能，并且时钟同步有很多出错的可能。如果您的NTP守护程序配置不正确，或防火墙阻止NTP流量，时钟漂移引起的时钟误差可能会迅速变大。

Relying on Synchronized Clocks

The problem with clocks is that while they seem simple and easy to use, they have a surprising number of pitfalls: a day may not have exactly 86,400 seconds, time-of-day clocks may move backward in time, and the time on one node may be quite different from the time on another node.

时钟的问题在于它们看起来简单易用，但实际上却有很多难以预料的缺陷：一天可能并非恰好有86,400秒，时钟可能会倒退时间，而且一个节点上的时间可能与另一个节点上的时间相差很大。

Earlier in this chapter we discussed networks dropping and arbitrarily delaying packets. Even though networks are well behaved most of the time, software must be designed on the assumption that the network will occasionally be faulty, and the software must handle such faults gracefully. The same is true with clocks: although they work quite well most of the time, robust software needs to be prepared to deal with incorrect clocks.

在本章早些时候，我们讨论了网络丢包和任意延迟数据包的问题。尽管网络大多数时候都表现良好，但软件必须在假设网络偶尔出现故障的基础上进行设计，并且软件必须能够优雅地处理这些故障。同样的情况也适用于时钟：尽管大多数时候时钟工作正常，但强健的软件需要准备好处理不正确的时钟。

Part of the problem is that incorrect clocks easily go unnoticed. If a machine’s CPU is defective or its network is misconfigured, it most likely won’t work at all, so it will quickly be noticed and fixed. On the other hand, if its quartz clock is defective or its NTP client is misconfigured, most things will seem to work fine, even though its clock gradually drifts further and further away from reality. If some piece of software is relying on an accurately synchronized clock, the result is more likely to be silent and subtle data loss than a dramatic crash [ 53 , 54 ].

问题的一部分在于不正确的时钟很容易被忽略。如果机器的 CPU 有缺陷或其网络配置不正确，它很可能根本就不能工作，因此很快就会被发现并进行修复。另一方面，如果它的石英钟有缺陷或其 NTP 客户端配置不正确，大多数东西看起来似乎运行良好，尽管其时钟逐渐偏离现实。如果某些软件依靠准确同步的时钟，结果更可能是静默和微妙的数据丢失，而不是显着的崩溃[53、54]。

Thus, if you use software that requires synchronized clocks, it is essential that you also carefully monitor the clock offsets between all the machines. Any node whose clock drifts too far from the others should be declared dead and removed from the cluster. Such monitoring ensures that you notice the broken clocks before they can cause too much damage.

因此，如果您使用需要同步时钟的软件，必须仔细监控所有机器之间的时钟偏移量。任何时钟偏离其他机器太远的节点都应被声明为失效并从集群中删除。这种监控确保您在时钟出现问题之前就能注意到，避免造成过度损伤。

Timestamps for ordering events

Let’s consider one particular situation in which it is tempting, but dangerous, to rely on clocks: ordering of events across multiple nodes. For example, if two clients write to a distributed database, who got there first? Which write is the more recent one?

考虑一种情况，依赖于时钟会很诱人，但也很危险：多个节点之间事件的排序。例如，如果两个客户端写入一个分布式数据库，谁先到达那里？哪个写入是最新的？

Figure 8-3 illustrates a dangerous use of time-of-day clocks in a database with multi-leader replication (the example is similar to Figure 5-9 ). Client A writes x = 1 on node 1; the write is replicated to node 3; client B increments x on node 3 (we now have x = 2); and finally, both writes are replicated to node 2.

图 8-3 展示了在具有多主复制的数据库中使用时间戳时可能出现的危险情况（这个例子与图 5-9 类似）。客户端 A 在节点 1 上写入 x = 1；写入操作被复制到节点 3；客户端 B 在节点 3 上增加 x，使得 x = 2；最后，两个写入操作都被复制到节点 2。 图 8-3 展示了在具有多主复制的数据库中使用时间戳时可能出现的危险情况（这个例子与图 5-9 类似）。客户端 A 在节点 1 上写入 x = 1；写入操作被复制到节点 3；客户端 B 在节点 3 上增加 x，使得 x = 2；最后，两个写入操作都被复制到节点 2。

Figure 8-3. The write by client B is causally later than the write by client A, but B’s write has an earlier timestamp.

In Figure 8-3 , when a write is replicated to other nodes, it is tagged with a timestamp according to the time-of-day clock on the node where the write originated. The clock synchronization is very good in this example: the skew between node 1 and node 3 is less than 3 ms, which is probably better than you can expect in practice.

在图8-3中，当写操作被复制到其他节点时，它会被标记上时间戳，该时间戳基于写操作源节点的当日时间。在此示例中，时钟同步非常好：节点1和节点3之间的偏差少于3毫秒，这可能比实际情况要好。

Nevertheless, the timestamps in Figure 8-3 fail to order the events correctly: the write x = 1 has a timestamp of 42.004 seconds, but the write x = 2 has a timestamp of 42.003 seconds, even though x = 2 occurred unambiguously later. When node 2 receives these two events, it will incorrectly conclude that x = 1 is the more recent value and drop the write x = 2. In effect, client B’s increment operation will be lost.

然而，图8-3中的时间戳未能正确排序事件：写入x = 1的时间戳为42.004秒，但写入x = 2的时间戳为42.003秒，尽管x = 2显然后发生。当节点2接收到这两个事件时，它将错误地得出x = 1是更近的值并删除写入x = 2。实际上，客户端B的增量操作将丢失。

This conflict resolution strategy is called last write wins (LWW), and it is widely used in both multi-leader replication and leaderless databases such as Cassandra [ 53 ] and Riak [ 54 ] (see “Last write wins (discarding concurrent writes)” ). Some implementations generate timestamps on the client rather than the server, but this doesn’t change the fundamental problems with LWW:

这种冲突解决策略被称为最后一次写入获胜(LWW)，它被广泛用于多领导者复制和无领导者数据库，比如Cassandra[53]和Riak[54](详见“最后一次写入获胜(丢弃并发写入)”）。一些实现会在客户端而非服务器上生成时间戳，但这不会改变LWW的根本问题：

• Database writes can mysteriously disappear: a node with a lagging clock is unable to overwrite values previously written by a node with a fast clock until the clock skew between the nodes has elapsed [ 54 , 55 ]. This scenario can cause arbitrary amounts of data to be silently dropped without any error being reported to the application.

  数据库写入可能会神秘消失：当一个节点的时钟落后时，它无法覆盖先前由具有快速时钟的节点写入的值，直到节点间的时钟偏差已经过去。此情况可能导致任意数量的数据被无声丢弃，而应用程序不会报告任何错误。

• LWW cannot distinguish between writes that occurred sequentially in quick succession (in Figure 8-3 , client B’s increment definitely occurs after client A’s write) and writes that were truly concurrent (neither writer was aware of the other). Additional causality tracking mechanisms, such as version vectors, are needed in order to prevent violations of causality (see “Detecting Concurrent Writes” ).

  LWW不能区分在快速连续发生的顺序写（在图8-3中，客户端B的递增明显是在客户端A的写之后发生的） 和真正并发的写（两个写者都不知道对方的写）。需要额外的因果跟踪机制，如版本向量，才能防止因果关系的违规（请参阅“检测并发写入”）。

• It is possible for two nodes to independently generate writes with the same timestamp, especially when the clock only has millisecond resolution. An additional tiebreaker value (which can simply be a large random number) is required to resolve such conflicts, but this approach can also lead to violations of causality [ 53 ].

  两个节点独立生成相同时间戳的写入是有可能的，特别是当时钟仅具有毫秒分辨率时。需要一个额外的决定胜负的值（可以简单地是一个大的随机数）来解决这种冲突，但这种方法也可能导致因果关系的违反。[53]。

Thus, even though it is tempting to resolve conflicts by keeping the most “recent” value and discarding others, it’s important to be aware that the definition of “recent” depends on a local time-of-day clock, which may well be incorrect. Even with tightly NTP-synchronized clocks, you could send a packet at timestamp 100 ms (according to the sender’s clock) and have it arrive at timestamp 99 ms (according to the recipient’s clock)—so it appears as though the packet arrived before it was sent, which is impossible.

因此，尽管通过保留最“近期”的数值并丢弃其他数值来解决冲突是很诱人的，但重要的是要意识到“近期”定义取决于本地的时间时钟，可能是不正确的。即使使用紧密NTP同步的时钟，您可能会在时间戳100毫秒（根据发件人的时钟）发送数据包，并在时间戳99毫秒（根据收件人的时钟）到达，因此似乎该数据包在发送之前就已到达，这是不可能的。

Could NTP synchronization be made accurate enough that such incorrect orderings cannot occur? Probably not, because NTP’s synchronization accuracy is itself limited by the network round-trip time, in addition to other sources of error such as quartz drift. For correct ordering, you would need the clock source to be significantly more accurate than the thing you are measuring (namely network delay).

NTP同步能否精确到无法发生错误排列的程度？可能不行，因为NTP的同步精度本身受到网络往返时间的限制，除了石英漂移等其他误差来源。为了正确排序，您需要的时钟源比您要测量的东西（即网络延迟）更准确。

So-called logical clocks [ 56 , 57 ], which are based on incrementing counters rather than an oscillating quartz crystal, are a safer alternative for ordering events (see “Detecting Concurrent Writes” ). Logical clocks do not measure the time of day or the number of seconds elapsed, only the relative ordering of events (whether one event happened before or after another). In contrast, time-of-day and monotonic clocks, which measure actual elapsed time, are also known as physical clocks . We’ll look at ordering a bit more in “Ordering Guarantees” .

所谓的逻辑时钟[56, 57]，它们基于递增计数器而不是振荡的石英晶体，是对于事件排序的一种安全替代方法（见“检测并发写入”）。逻辑时钟不测量日期或经过的秒数，只测量事件的相对顺序（一个事件在另一个事件之前或之后发生）。相反，测量实际经过时间的时钟，如当天时间和单调时钟，也被称为物理时钟。我们将在“排序保证”中更详细地讨论排序。

Process Pauses

Let’s consider another example of dangerous clock use in a distributed system. Say you have a database with a single leader per partition. Only the leader is allowed to accept writes. How does a node know that it is still leader (that it hasn’t been declared dead by the others), and that it may safely accept writes?

让我们考虑分布式系统中另一个危险的时钟使用例子。假设你有一个数据库，每个分区只有一个领导者。只有领导者可以接受写入。一个节点如何知道它仍然是领导者(它没有被其他节点宣布死亡)，并且它可以安全地接受写入呢？

One option is for the leader to obtain a lease from the other nodes, which is similar to a lock with a timeout [ 63 ]. Only one node can hold the lease at any one time—thus, when a node obtains a lease, it knows that it is the leader for some amount of time, until the lease expires. In order to remain leader, the node must periodically renew the lease before it expires. If the node fails, it stops renewing the lease, so another node can take over when it expires.

一种选择是领导者从其他节点获得租赁，类似于带有超时的锁[63]。每次只能有一个节点持有租赁 - 因此，当一个节点获得租赁时，它知道自己在一段时间内是领导者，直到租赁到期。为了保持领导地位，节点必须在其到期之前定期更新租赁。如果节点失败，则停止更新租赁，因此在其到期时另一个节点可以接管。

You can imagine the request-handling loop looking something like this:

你可以想象请求处理循环大概长这样：

while (true) {
    request = getIncomingRequest();

    // Ensure that the lease always has at least 10 seconds remaining
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000) {
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

What’s wrong with this code? Firstly, it’s relying on synchronized clocks: the expiry time on the lease is set by a different machine (where the expiry may be calculated as the current time plus 30 seconds, for example), and it’s being compared to the local system clock. If the clocks are out of sync by more than a few seconds, this code will start doing strange things.

这段代码有什么问题？首先，它依赖于同步的时钟：租约的到期时间是由另一台机器设置的（到期时间可能被计算为当前时间加30秒），并且与本地系统时钟进行比较。如果时钟相差超过几秒钟，这段代码就会开始出现奇怪的问题。

Secondly, even if we change the protocol to only use the local monotonic clock, there is another problem: the code assumes that very little time passes between the point that it checks the time ( System.currentTimeMillis() ) and the time when the request is processed ( process(request) ). Normally this code runs very quickly, so the 10 second buffer is more than enough to ensure that the lease doesn’t expire in the middle of processing a request.

其次，即使我们将协议更改为仅使用本地单调时钟，还有另一个问题：代码假定在检查时间（System.currentTimeMillis()）和处理请求（process(request)）之间经过了很少的时间。通常，此代码运行速度非常快，因此10秒缓冲区足以确保租约不会在处理请求的过程中过期。

However, what if there is an unexpected pause in the execution of the program? For example, imagine the thread stops for 15 seconds around the line lease.isValid() before finally continuing. In that case, it’s likely that the lease will have expired by the time the request is processed, and another node has already taken over as leader. However, there is nothing to tell this thread that it was paused for so long, so this code won’t notice that the lease has expired until the next iteration of the loop—by which time it may have already done something unsafe by processing the request.

然而，如果程序执行中出现了意外的暂停怎么办？例如，在线路lease.isValid()附近的线程停止了15秒，最终才继续执行。在这种情况下，租约很可能在请求被处理时已经过期，并且另一个节点已经成为了领导者。然而，对于该线程来说，没有任何东西能告诉它它被暂停了这么久，因此这段代码在下一次循环之前不会意识到租约已经过期，到那时它可能已经通过处理请求做了一些不安全的事情。

Is it crazy to assume that a thread might be paused for so long? Unfortunately not. There are various reasons why this could happen:

这么假定一个线程可能会暂停这么长时间是疯狂的吗？不幸的是不是。有各种原因会导致这种情况发生：

• Many programming language runtimes (such as the Java Virtual Machine) have a garbage collector (GC) that occasionally needs to stop all running threads. These “stop-the-world” GC pauses have sometimes been known to last for several minutes [ 64 ]! Even so-called “concurrent” garbage collectors like the HotSpot JVM’s CMS cannot fully run in parallel with the application code—even they need to stop the world from time to time [ 65 ]. Although the pauses can often be reduced by changing allocation patterns or tuning GC settings [ 66 ], we must assume the worst if we want to offer robust guarantees.

  许多编程语言的运行时环境（比如Java虚拟机）都有垃圾回收器（GC），需要偶尔停止所有正在运行的线程。这些“停止世界”GC暂停有时知道持续几分钟！即使是所谓的“并发”垃圾回收器，如HotSpot JVM的CMS，也不能完全与应用程序代码并行运行，即它们也需要定期停止工作。虽然通过改变分配模式或调整GC设置经常可以减少暂停，但如果我们想要提供强大的保证，我们必须假设最坏情况。

• In virtualized environments, a virtual machine can be suspended (pausing the execution of all processes and saving the contents of memory to disk) and resumed (restoring the contents of memory and continuing execution). This pause can occur at any time in a process’s execution and can last for an arbitrary length of time. This feature is sometimes used for live migration of virtual machines from one host to another without a reboot, in which case the length of the pause depends on the rate at which processes are writing to memory [ 67 ].

  在虚拟化环境中，虚拟机可以被暂停（暂停所有进程执行并将内存内容保存到磁盘）和恢复（恢复存储在内存中的内容并继续执行）。此暂停可以发生在进程执行的任何时间，并且可以持续任意长的时间。该功能有时用于虚拟机的实时迁移，无需重新启动，此时暂停的长度取决于进程写入内存的速率[67]。

• On end-user devices such as laptops, execution may also be suspended and resumed arbitrarily, e.g., when the user closes the lid of their laptop.

  在终端用户设备上，例如笔记本电脑，执行也可以任意暂停和恢复，例如当用户关闭笔记本电脑盖子时。

• When the operating system context-switches to another thread, or when the hypervisor switches to a different virtual machine (when running in a virtual machine), the currently running thread can be paused at any arbitrary point in the code. In the case of a virtual machine, the CPU time spent in other virtual machines is known as steal time . If the machine is under heavy load—i.e., if there is a long queue of threads waiting to run—it may take some time before the paused thread gets to run again.

  当操作系统切换到另一个线程时，或者当虚拟机中的运行时hypervisor切换到另一个虚拟机时，当前正在运行的线程可以在代码的任意点暂停。在虚拟机中，CPU在其他虚拟机中所花费的时间称为被窃取时间。如果机器负载很重，即有很长的线程等待运行的队列，那么在暂停的线程再次运行之前可能需要一些时间。

• If the application performs synchronous disk access, a thread may be paused waiting for a slow disk I/O operation to complete [ 68 ]. In many languages, disk access can happen surprisingly, even if the code doesn’t explicitly mention file access—for example, the Java classloader lazily loads class files when they are first used, which could happen at any time in the program execution. I/O pauses and GC pauses may even conspire to combine their delays [ 69 ]. If the disk is actually a network filesystem or network block device (such as Amazon’s EBS), the I/O latency is further subject to the variability of network delays [ 29 ].

  如果应用程序执行同步磁盘访问，则线程可能会因等待缓慢的磁盘I/O操作而暂停[68]。在许多语言中，即使代码没有明确提到文件访问，磁盘访问也可能会突然发生 - 例如，Java类装入器会在第一次使用类文件时惰性地加载它们，这可能会在程序执行期间的任何时候发生。I/O暂停和GC暂停甚至可能合并它们的延迟[69]。如果磁盘实际上是网络文件系统或网络块设备（例如Amazon的EBS），则I/O延迟还受网络延迟变化的影响[29]。

• If the operating system is configured to allow swapping to disk ( paging ), a simple memory access may result in a page fault that requires a page from disk to be loaded into memory. The thread is paused while this slow I/O operation takes place. If memory pressure is high, this may in turn require a different page to be swapped out to disk. In extreme circumstances, the operating system may spend most of its time swapping pages in and out of memory and getting little actual work done (this is known as thrashing ). To avoid this problem, paging is often disabled on server machines (if you would rather kill a process to free up memory than risk thrashing).

  如果操作系统配置为允许交换到磁盘（分页），一个简单的内存访问可能导致一个页面错误，需要将一个页面从磁盘加载到内存。在这个缓慢的I / O操作发生时，线程会暂停。如果内存压力很大，这可能需要将不同的页面交换到磁盘。在极端情况下，操作系统可能会花费大部分时间将页面从内存中换入和换出，并且实际上完成很少的工作（这称为抖动）。为了避免这个问题，服务器机器上通常禁用分页（如果您宁愿杀死一个进程来释放内存而不是冒险抖动）。

• A Unix process can be paused by sending it the SIGSTOP signal, for example by pressing Ctrl-Z in a shell. This signal immediately stops the process from getting any more CPU cycles until it is resumed with SIGCONT , at which point it continues running where it left off. Even if your environment does not normally use SIGSTOP , it might be sent accidentally by an operations engineer.

  Unix进程可以通过发送SIGSTOP信号暂停，例如在shell中按下Ctrl-Z。此信号立即停止进程从获取更多的CPU周期，直到使用SIGCONT恢复为止，此时它将在离开的地方继续运行。即使您的环境通常不使用SIGSTOP，操作工程师可能会意外发送它。

All of these occurrences can preempt the running thread at any point and resume it at some later time, without the thread even noticing. The problem is similar to making multi-threaded code on a single machine thread-safe: you can’t assume anything about timing, because arbitrary context switches and parallelism may occur.

所有这些情况都可能在任何时候抢占正在运行的线程，并在稍后的时间恢复它，而线程甚至都不会注意到。这个问题类似于在单个机器上编写多线程代码的线程安全性：您不能假设任何有关计时的事情，因为任意的上下文切换和并行性可能会发生。

When writing multi-threaded code on a single machine, we have fairly good tools for making it thread-safe: mutexes, semaphores, atomic counters, lock-free data structures, blocking queues, and so on. Unfortunately, these tools don’t directly translate to distributed systems, because a distributed system has no shared memory—only messages sent over an unreliable network.

在单机上编写多线程代码时，我们有相当不错的工具可以使其线程安全：互斥锁、信号量、原子计数器、无锁数据结构、阻塞队列等。不幸的是，这些工具无法直接转换为分布式系统，因为分布式系统没有共享内存，只有通过不可靠网络发送的消息。

A node in a distributed system must assume that its execution can be paused for a significant length of time at any point, even in the middle of a function. During the pause, the rest of the world keeps moving and may even declare the paused node dead because it’s not responding. Eventually, the paused node may continue running, without even noticing that it was asleep until it checks its clock sometime later.

分布式系统中的一个节点必须假定其执行可以在任何时候暂停很长一段时间，甚至在函数中间。在暂停期间，其余世界会继续前进，甚至可能宣布暂停的节点已经死亡，因为它没有响应。最终，暂停的节点可能会继续运行，并且甚至在稍后检查其时钟时也没有注意到它睡着了。

The Truth Is Defined by the Majority

Imagine a network with an asymmetric fault: a node is able to receive all messages sent to it, but any outgoing messages from that node are dropped or delayed [ 19 ]. Even though that node is working perfectly well, and is receiving requests from other nodes, the other nodes cannot hear its responses. After some timeout, the other nodes declare it dead, because they haven’t heard from the node. The situation unfolds like a nightmare: the semi-disconnected node is dragged to the graveyard, kicking and screaming “I’m not dead!”—but since nobody can hear its screaming, the funeral procession continues with stoic determination.

想像一下一个有不对称故障的网络：一个节点能够接收到对它发送的所有消息，但是从该节点发送的任何消息都被丢弃或延迟[19]。即使该节点运行得非常好，而且正在接收其他节点的请求，但其他节点无法听到其响应。经过一段时间后，其他节点会宣布它死亡，因为他们没有从该节点那里听到消息。这种情况就像一场噩梦一样展开：这个半断开的节点被拖入坟墓，大喊着“我还没死！”——但由于没有人能听到它的尖叫声，葬礼队伍会义无反顾地继续前行。

In a slightly less nightmarish scenario, the semi-disconnected node may notice that the messages it is sending are not being acknowledged by other nodes, and so realize that there must be a fault in the network. Nevertheless, the node is wrongly declared dead by the other nodes, and the semi-disconnected node cannot do anything about it.

在一个稍微不那么可怕的情况下，半断开的节点可能会注意到它发送的消息未被其他节点确认，因此意识到网络中一定存在故障。然而，其他节点错误地宣布该节点死亡，而半断开的节点无法对此做出任何反应。

As a third scenario, imagine a node that experiences a long stop-the-world garbage collection pause. All of the node’s threads are preempted by the GC and paused for one minute, and consequently, no requests are processed and no responses are sent. The other nodes wait, retry, grow impatient, and eventually declare the node dead and load it onto the hearse. Finally, the GC finishes and the node’s threads continue as if nothing had happened. The other nodes are surprised as the supposedly dead node suddenly raises its head out of the coffin, in full health, and starts cheerfully chatting with bystanders. At first, the GCing node doesn’t even realize that an entire minute has passed and that it was declared dead—from its perspective, hardly any time has passed since it was last talking to the other nodes.

作为第三种情景，想象一下一个节点经历了一次长时间的停机垃圾收集暂停。所有该节点的线程都被垃圾收集器抢占并暂停了一分钟，因此，没有任何请求被处理和响应被发送。其他节点等待、重试、变得不耐烦，并最终宣布该节点已经死亡并将其装入灵车。最后，垃圾收集完成，该节点的线程继续执行，就好像什么都没有发生过一样。其他节点会感到惊讶，因为这个本来被认为已经死亡的节点突然从棺材里探出头来，身体健康，并开始和旁观者愉快地聊天。一开始，正在进行垃圾收集的节点甚至没有意识到已经过去了整整一分钟，而它被宣布死亡-从它的角度来看，自上次与其他节点交流以来几乎没有经过任何时间。

The moral of these stories is that a node cannot necessarily trust its own judgment of a situation. A distributed system cannot exclusively rely on a single node, because a node may fail at any time, potentially leaving the system stuck and unable to recover. Instead, many distributed algorithms rely on a quorum , that is, voting among the nodes (see “Quorums for reading and writing” ): decisions require some minimum number of votes from several nodes in order to reduce the dependence on any one particular node.

这些故事的寓意是，一个节点不能仅依靠自己对情况的判断。分布式系统不能只依赖于单个节点，因为节点可能随时出现故障，导致系统出现故障并且无法恢复。相反，许多分布式算法依赖于法定人数，即节点之间的投票（见“用于读写的法定人数”）：决策需要来自多个节点的最小投票数，以减少对任何特定节点的依赖。

That includes decisions about declaring nodes dead. If a quorum of nodes declares another node dead, then it must be considered dead, even if that node still very much feels alive. The individual node must abide by the quorum decision and step down.

这包括关于宣布节点死亡的决定。如果一组节点宣布另一个节点已经死亡，那么即使该节点仍然非常有生气，也必须被视为已死亡。个体节点必须遵守法定人数的决定并下台。

Most commonly, the quorum is an absolute majority of more than half the nodes (although other kinds of quorums are possible). A majority quorum allows the system to continue working if individual nodes have failed (with three nodes, one failure can be tolerated; with five nodes, two failures can be tolerated). However, it is still safe, because there can only be only one majority in the system—there cannot be two majorities with conflicting decisions at the same time. We will discuss the use of quorums in more detail when we get to consensus algorithms in Chapter 9 .

通常情况下，法定人数是超过一半以上节点的绝对多数（虽然其他种类的法定人数也是可能的）。多数派法定人数可以使系统在个别节点失败时继续工作（对于三个节点，可以容忍一个故障；对于五个节点，可以容忍两个故障）。但是，它仍然是安全的，因为系统只能有一个多数派—同时不能有两个有冲突决定的多数派。当我们在第9章讨论共识算法时，我们将更详细地讨论法定人数的使用。

The leader and the lock

Frequently, a system requires there to be only one of some thing. For example:

经常，系统要求有一些东西只能有一个。例如：

• Only one node is allowed to be the leader for a database partition, to avoid split brain (see “Handling Node Outages” ).

  一个数据库分区只允许存在一个领导者节点，以避免出现分裂脑的情况（参见“处理节点故障”）。

• Only one transaction or client is allowed to hold the lock for a particular resource or object, to prevent concurrently writing to it and corrupting it.

  只允许一个事务或客户端持有锁定特定资源或对象的锁，以防止同时写入并损坏它。

• Only one user is allowed to register a particular username, because a username must uniquely identify a user.

  一个用户名只能注册给一位用户，因为用户名必须唯一标识一个用户。

Implementing this in a distributed system requires care: even if a node believes that it is “the chosen one” (the leader of the partition, the holder of the lock, the request handler of the user who successfully grabbed the username), that doesn’t necessarily mean a quorum of nodes agrees! A node may have formerly been the leader, but if the other nodes declared it dead in the meantime (e.g., due to a network interruption or GC pause), it may have been demoted and another leader may have already been elected.

在分布式系统中实施这个需要小心：即使一个节点认为自己是“被选择的”（分区的领导者、锁定的持有者、成功抓取用户名称的请求处理器），这并不意味着节点的多数同意！一个节点可能曾经是领导者，但如果其他节点在此期间声明它已死（例如，由于网络中断或GC暂停），它可能已经被降级，另一个领导者可能已经被选举。

If a node continues acting as the chosen one, even though the majority of nodes have declared it dead, it could cause problems in a system that is not carefully designed. Such a node could send messages to other nodes in its self-appointed capacity, and if other nodes believe it, the system as a whole may do something incorrect.

如果一个节点即使大多数节点已经宣布它死亡，仍然继续担任被选择的节点，会在系统不小心设计的情况下造成问题。这样的节点可能会在自我任命的能力下向其他节点发送消息，如果其他节点相信它，整个系统可能会做出错误的操作。

For example, Figure 8-4 shows a data corruption bug due to an incorrect implementation of locking. (The bug is not theoretical: HBase used to have this problem [ 74 , 75 ].) Say you want to ensure that a file in a storage service can only be accessed by one client at a time, because if multiple clients tried to write to it, the file would become corrupted. You try to implement this by requiring a client to obtain a lease from a lock service before accessing the file.

例如，图8-4展示了由于锁定实现不正确而导致的数据损坏错误。（这个错误不是理论上的：HBase曾经有过这个问题[74, 75]。）假设你想确保存储服务中的文件一次只能被一个客户端访问，因为如果多个客户端尝试写入它，文件会变得损坏。你尝试通过要求客户端在访问文件之前从锁定服务中获取租约来实现这一点。

Figure 8-4. Incorrect implementation of a distributed lock: client 1 believes that it still has a valid lease, even though it has expired, and thus corrupts a file in storage.

The problem is an example of what we discussed in “Process Pauses” : if the client holding the lease is paused for too long, its lease expires. Another client can obtain a lease for the same file, and start writing to the file. When the paused client comes back, it believes (incorrectly) that it still has a valid lease and proceeds to also write to the file. As a result, the clients’ writes clash and corrupt the file.

问题是我们在“流程暂停”中讨论的一个例子：如果持有租约的客户端暂停时间过长，租约将会过期。另一个客户端可以获取相同文件的租约，并开始写入文件。当暂停的客户端回来时，它会错误地认为自己仍然拥有有效的租约，然后继续写入文件。结果，客户端的写入冲突并破坏了文件。

Fencing tokens

When using a lock or lease to protect access to some resource, such as the file storage in Figure 8-4 , we need to ensure that a node that is under a false belief of being “the chosen one” cannot disrupt the rest of the system. A fairly simple technique that achieves this goal is called fencing , and is illustrated in Figure 8-5 .

当使用锁定或租赁来保护某些资源的访问权限（例如图8-4中的文件存储）时，我们需要确保一个错误地认为自己是“被选中者”的节点不能破坏整个系统。一个相当简单的技术可以实现这个目标，它叫做栅栏，如图8-5所示。

Figure 8-5. Making access to storage safe by allowing writes only in the order of increasing fencing tokens.

Let’s assume that every time the lock server grants a lock or lease, it also returns a fencing token , which is a number that increases every time a lock is granted (e.g., incremented by the lock service). We can then require that every time a client sends a write request to the storage service, it must include its current fencing token.

假设每次锁服务授予锁或租约时，它也返回一个围栏令牌，这是一个数字，每次授予锁时都会增加（例如，由锁服务增加）。然后，我们可以要求每次客户端向存储服务发送写入请求时，必须包含其当前的围栏令牌。

In Figure 8-5 , client 1 acquires the lease with a token of 33, but then it goes into a long pause and the lease expires. Client 2 acquires the lease with a token of 34 (the number always increases) and then sends its write request to the storage service, including the token of 34. Later, client 1 comes back to life and sends its write to the storage service, including its token value 33. However, the storage server remembers that it has already processed a write with a higher token number (34), and so it rejects the request with token 33.

在图8-5中，客户端1使用33个令牌获得租约，但之后进入长时间暂停并且租约到期了。客户端2使用34个令牌（数字一直增加）获得租约，然后将其写请求发送给存储服务，包括34个令牌。稍后，客户端1重新活跃并将其写请求发送到存储服务，包括其33个令牌值。但是，存储服务器记得它已经处理了一个更高令牌号（34）的写请求，因此拒绝了使用33个令牌的请求。

If ZooKeeper is used as lock service, the transaction ID zxid or the node version cversion can be used as fencing token. Since they are guaranteed to be monotonically increasing, they have the required properties [ 74 ].

如果ZooKeeper作为锁定服务使用，则事务ID zxid或节点版本cversion可用作分隔令牌。由于它们保证单调递增，因此具有所需的属性[74]。

Note that this mechanism requires the resource itself to take an active role in checking tokens by rejecting any writes with an older token than one that has already been processed—it is not sufficient to rely on clients checking their lock status themselves. For resources that do not explicitly support fencing tokens, you might still be able work around the limitation (for example, in the case of a file storage service you could include the fencing token in the filename). However, some kind of check is necessary to avoid processing requests outside of the lock’s protection.

请注意，此机制要求资源自身在检查令牌时扮演积极角色，拒绝任何具有较旧令牌的写入，该令牌已经被处理，它并不能仅仅依赖客户端自己检查其锁定状态。对于不明确支持栅栏令牌的资源，您可能仍能绕过此限制（例如，在文件存储服务的情况下，您可以在文件名中包含栅栏令牌）。但必须进行某种检查，以避免处理锁定保护范围外的请求。

Checking a token on the server side may seem like a downside, but it is arguably a good thing: it is unwise for a service to assume that its clients will always be well behaved, because the clients are often run by people whose priorities are very different from the priorities of the people running the service [ 76 ]. Thus, it is a good idea for any service to protect itself from accidentally abusive clients.

在服务器端检查令牌可能似乎有缺点，但这也是一件好事：服务不应该假设其客户始终表现良好，因为客户的优先级通常与运行服务的人的优先级非常不同。因此，任何服务都应该保护自己免受意外虐待的客户。

Byzantine Faults

Fencing tokens can detect and block a node that is inadvertently acting in error (e.g., because it hasn’t yet found out that its lease has expired). However, if the node deliberately wanted to subvert the system’s guarantees, it could easily do so by sending messages with a fake fencing token.

栅栏令牌可以检测和阻止错误地操作节点（例如，因为它尚未发现其租期已过期）的节点。然而，如果节点有意想要破坏系统的保证，它可以轻松地通过发送带有伪造栅栏令牌的消息来实现。

In this book we assume that nodes are unreliable but honest: they may be slow or never respond (due to a fault), and their state may be outdated (due to a GC pause or network delays), but we assume that if a node does respond, it is telling the “truth”: to the best of its knowledge, it is playing by the rules of the protocol.

在这本书中，我们假设节点是不可靠但诚实的：它们可能很慢或从不响应（由于故障），它们的状态可能过时（由于GC暂停或网络延迟），但我们假设如果节点确实响应，它正在“真实”地讲述事实：据它所知，它正在按照协议的规则进行操作。

Distributed systems problems become much harder if there is a risk that nodes may “lie” (send arbitrary faulty or corrupted responses)—for example, if a node may claim to have received a particular message when in fact it didn’t. Such behavior is known as a Byzantine fault , and the problem of reaching consensus in this untrusting environment is known as the Byzantine Generals Problem [ 77 ].

如果存在节点可能“说谎”（发送任意错误或损坏的响应）的风险，分布式系统问题会变得更加困难 - 例如，如果一个节点可能声称已收到某个消息，而实际上没有。这种行为被称为拜占庭故障，而在这种不信任环境中达成共识的问题被称为拜占庭将军问题[77]。

A system is Byzantine fault-tolerant if it continues to operate correctly even if some of the nodes are malfunctioning and not obeying the protocol, or if malicious attackers are interfering with the network. This concern is relevant in certain specific circumstances. For example:

如果某些节点出现故障并且违反协议，或者有恶意攻击者干扰网络，一个系统是拜占庭容错的，可以继续正确运行。这个问题在某些具体情况下非常重要。例如：

• In aerospace environments, the data in a computer’s memory or CPU register could become corrupted by radiation, leading it to respond to other nodes in arbitrarily unpredictable ways. Since a system failure would be very expensive (e.g., an aircraft crashing and killing everyone on board, or a rocket colliding with the International Space Station), flight control systems must tolerate Byzantine faults [ 81 , 82 ].

  在航空航天环境中，计算机的内存或CPU寄存器中的数据可能会因为辐射而损坏，导致其对其他节点以任意不可预测的方式做出响应。由于系统故障会非常昂贵（例如，飞机坠毁并导致所有人死亡，或火箭与国际空间站相撞），所以飞行控制系统必须容忍拜占庭故障[81, 82]。

• In a system with multiple participating organizations, some participants may attempt to cheat or defraud others. In such circumstances, it is not safe for a node to simply trust another node’s messages, since they may be sent with malicious intent. For example, peer-to-peer networks like Bitcoin and other blockchains can be considered to be a way of getting mutually untrusting parties to agree whether a transaction happened or not, without relying on a central authority [ 83 ].

  在多个参与组织的系统中，某些参与方可能尝试欺骗或欺诈其他人。在这种情况下，节点不能简单地相信另一个节点的信息，因为它们可能具有恶意意图。例如，像比特币和其他区块链一样的对等网络可以被视为一种让相互不信任的各方同意某个交易是否发生，而不依赖于中央机构的方式。

However, in the kinds of systems we discuss in this book, we can usually safely assume that there are no Byzantine faults. In your datacenter, all the nodes are controlled by your organization (so they can hopefully be trusted) and radiation levels are low enough that memory corruption is not a major problem. Protocols for making systems Byzantine fault-tolerant are quite complicated [ 84 ], and fault-tolerant embedded systems rely on support from the hardware level [ 81 ]. In most server-side data systems, the cost of deploying Byzantine fault-tolerant solutions makes them impractical.

然而，在本书讨论的系统中，我们通常可以安全地假设没有拜占庭故障。在您的数据中心中，所有节点都受到您组织的控制（因此希望它们是可信的），并且辐射水平低到足以使内存损坏不成为主要问题。使系统具有拜占庭容错性的协议非常复杂[84]，并且容错嵌入式系统依赖于硬件级别的支持[81]。在大多数服务器端数据系统中，部署拜占庭容错解决方案的成本使它们变得不切实际。

Web applications do need to expect arbitrary and malicious behavior of clients that are under end-user control, such as web browsers. This is why input validation, sanitization, and output escaping are so important: to prevent SQL injection and cross-site scripting, for example. However, we typically don’t use Byzantine fault-tolerant protocols here, but simply make the server the authority on deciding what client behavior is and isn’t allowed. In peer-to-peer networks, where there is no such central authority, Byzantine fault tolerance is more relevant.

网络应用需要预料到受最终用户控制的客户端（如Web浏览器）的任意和恶意行为。这就是为什么输入验证、净化和输出转义非常重要的原因：例如，防止SQL注入和跨站点脚本。然而，在这里我们通常不使用拜占庭容错协议，只需将服务器作为决定允许哪些客户端行为的权威。在点对点网络中，没有这样的中央权威，因此拜占庭容错更加相关。

A bug in the software could be regarded as a Byzantine fault, but if you deploy the same software to all nodes, then a Byzantine fault-tolerant algorithm cannot save you. Most Byzantine fault-tolerant algorithms require a supermajority of more than two-thirds of the nodes to be functioning correctly (i.e., if you have four nodes, at most one may malfunction). To use this approach against bugs, you would have to have four independent implementations of the same software and hope that a bug only appears in one of the four implementations.

软件中的漏洞可能被视为拜占庭故障，但如果你将同一软件部署到所有节点上，那么拜占庭容错算法将无法拯救你。大多数拜占庭容错算法需要超过三分之二的节点正常运行（例如，如果你有四个节点，则最多只能有一个节点出现故障）。如果想要使用这种方法来解决漏洞，你需要有四个独立的软件实现，并希望漏洞只出现在其中一个实现中。

Similarly, it would be appealing if a protocol could protect us from vulnerabilities, security compromises, and malicious attacks. Unfortunately, this is not realistic either: in most systems, if an attacker can compromise one node, they can probably compromise all of them, because they are probably running the same software. Thus, traditional mechanisms (authentication, access control, encryption, firewalls, and so on) continue to be the main protection against attackers.

同样，如果协议可以保护我们免受漏洞、安全妥协和恶意攻击的侵害，那将会很吸引人。不幸的是，这也是不现实的：在大多数系统中，如果攻击者可以入侵一个节点，他们可能可以入侵所有节点，因为它们可能运行相同的软件。因此，传统机制（身份验证、访问控制、加密、防火墙等）继续成为对抗攻击者的主要保护。

System Model and Reality

Many algorithms have been designed to solve distributed systems problems—for example, we will examine solutions for the consensus problem in Chapter 9 . In order to be useful, these algorithms need to tolerate the various faults of distributed systems that we discussed in this chapter.

很多算法都被设计用来解决分布式系统问题——例如，在第9章中，我们将讨论共识问题的解决方案。为了有用，这些算法需要容忍我们在本章中讨论过的分布式系统的各种故障。

Algorithms need to be written in a way that does not depend too heavily on the details of the hardware and software configuration on which they are run. This in turn requires that we somehow formalize the kinds of faults that we expect to happen in a system. We do this by defining a system model , which is an abstraction that describes what things an algorithm may assume.

算法需要编写成不太依赖于硬件和软件配置的方式运行。因此，我们需要以某种方式将我们所预期发生的系统故障形式化。我们通过定义系统模型来实现此目的，这是描述算法可能假设的抽象概念。

With regard to timing assumptions, three system models are in common use:

关于时间假设，常用的有三种系统模型：

Synchronous model

The synchronous model assumes bounded network delay, bounded process pauses, and bounded clock error. This does not imply exactly synchronized clocks or zero network delay; it just means you know that network delay, pauses, and clock drift will never exceed some fixed upper bound [ 88 ]. The synchronous model is not a realistic model of most practical systems, because (as discussed in this chapter) unbounded delays and pauses do occur.

同步模型假设有工作网络延迟、进程暂停和时钟误差的限制。这并不意味着完全同步的时钟或网络延迟为零；它只是意味着你知道网络延迟、暂停和时钟漂移永远不会超过某个固定的上限。同步模型不是大多数实际系统的现实模型，因为（正如本章所讨论的）无限的延迟和暂停确实会发生。

Partially synchronous model

Partial synchrony means that a system behaves like a synchronous system most of the time , but it sometimes exceeds the bounds for network delay, process pauses, and clock drift [ 88 ]. This is a realistic model of many systems: most of the time, networks and processes are quite well behaved—otherwise we would never be able to get anything done—but we have to reckon with the fact that any timing assumptions may be shattered occasionally. When this happens, network delay, pauses, and clock error may become arbitrarily large.

部分同步意味着系统大部分时间表现为同步系统，但有时会超出网络延迟、进程暂停和时钟漂移的限制。[88]这是许多系统的现实模型：大多数时间，网络和进程表现良好 -否则我们就无法完成任何事情- 但我们必须考虑到任何时间假设可能会偶尔破裂。当这种情况发生时，网络延迟、暂停和时钟误差可能变得任意大。

Asynchronous model

In this model, an algorithm is not allowed to make any timing assumptions—in fact, it does not even have a clock (so it cannot use timeouts). Some algorithms can be designed for the asynchronous model, but it is very restrictive.

在这个模型中，算法不允许做出任何时间假设——事实上，它甚至没有时钟（因此无法使用超时）。一些算法可以为异步模型设计，但它是非常严格的。

Moreover, besides timing issues, we have to consider node failures. The three most common system models for nodes are:

此外，除了时间问题外，我们还必须考虑节点故障。节点的三种最常见的系统模型是：

Crash-stop faults

In the crash-stop model, an algorithm may assume that a node can fail in only one way, namely by crashing. This means that the node may suddenly stop responding at any moment, and thereafter that node is gone forever—it never comes back.

在崩溃停止模型中，算法可能假设节点只能以一种方式失败，即崩溃。这意味着节点可能随时突然停止响应，然后该节点就永远离开了——它永远不会回来。

Crash-recovery faults

We assume that nodes may crash at any moment, and perhaps start responding again after some unknown time. In the crash-recovery model, nodes are assumed to have stable storage (i.e., nonvolatile disk storage) that is preserved across crashes, while the in-memory state is assumed to be lost.

我们假设节点随时可能崩溃，并可能在一段未知的时间后重新开始响应。在崩溃恢复模型中，假定节点具有稳定的存储（即，不揮发的磁盘存储），该存储在崩溃期间保持不变，而内存状态被认为是丢失的。

Byzantine (arbitrary) faults

Nodes may do absolutely anything, including trying to trick and deceive other nodes, as described in the last section.

节点可以做任何事情，包括尝试欺骗其他节点，正如最后一节所描述的那样。

For modeling real systems, the partially synchronous model with crash-recovery faults is generally the most useful model. But how do distributed algorithms cope with that model?

对于建模实际系统来说，具有崩溃恢复错误的部分同步模型通常是最有用的模型。但是分布式算法如何应对这个模型呢？