分布式系统与单台计算机有着根本的区别，有很多新的方法可以使事情出错。
1 故障与部分失效
单个计算机中，电脑崩溃会导致功能全部失效，但是在分布式系统中，系统有可能部分失效（partial failure） 。难点在于部分失效是不确定性的（nonderterministic），这种不确定性和部分失效的可能性，使得分布式系统难以工作。
1.1 云计算与超级计算机
大型计算系统有一系列构建哲学，超级计算机中有几千个CPU，而云计算有多个数据中心，不同的哲学会导致不同的故障处理方式。
如果系统能容忍部分节点发生故障，继续保持可用，就易于操作和维护。所以分布式系统需要接受部分故障的可能性，并在软件中建立容错机制（不论系统大小）。
换句话说，我们需要从不可靠的组件构建一个可靠的系统。
2 不可靠的网络
本书中关注的分布式系统是无共享的系统，即通过网络连接的一堆机器，一台机器不能直接访问另一台机器的内存和硬盘。
互联网和数据中心（通常是以太网）中的大多数内部网络都是异步分组网络（asynchronous packet networks） 。在这种网络中，不能保证节点发送数据包的到达时间和是否到达。发送者不知道数据包是否成功发送出去了，而超时检测也无法让发送者知道接收者是否收到请求。
2.1 真实世界的网络故障
网络故障是很常见的，网络的一部分会由于网络故障而被切断（这种情况也叫网络分区或网络断裂）。因此，我们需要定义网络故障的错误和处理，否则可能会发生一些严重的情况，例如死锁。
当网络遇到问题时，我们可用简单的向用户显示一条错误信息。但是我们需要知道软件如何应对网络问题，并且必须确保系统能从网络中恢复。
2.2 检测故障
许多系统需要自动检测故障节点，例如：
- 负载平衡器需要停止向已死亡的节点转发请求（即从移出轮询列表（out of rotation） ）。
- 在单主复制功能的分布式数据库中，如果主库失效，则需要将从库之一升级为新主库（处理节点宕机）
然而，网络的不确定性使得很难判断一个节点是否工作，因此不能指望关于远程节点关闭的反馈：即使TCP确认已经传送了一个数据包，但是应用在处理之前可能已经崩溃。
综上，如果想确保请求是成功的，需要应用本身的响应。因此，我们通过超时响应来检测节点状态，当响应超时，证明节点已经死亡。
2.3 超时与无穷的延迟
若超时是检测故障的唯一可靠方法，那么我们应该等待多久？
时间长了会降低用户体验，用户需要一直等着。
时间短可能会导致错误地宣布节点失效，从而导致更高的风险：如果节点实际上活着并且正在执行一个工作，而我们宣布它死了，于是让另一个节点接管其工作，那么这个动作就会被执行两遍。当节点被宣告死亡后，将它的负载转移到其他节点会带来额外的负担，可能会导致级联失效（cascading failure） ，极端情况下会导致所有节点都宣告对方死亡，所有节点都停止工作。
若网络可以保证数据包的最大延迟，那么我们就可以计算出合理的超时时间，然而异步网络具有无限的延迟（尽可能快的传送数据包，但是数据包到达可能需要的时间没有上限）。
网络拥塞与排队
网络中，数据包的延迟通常是由于排队：
- 交换机排队将数据包送入目标网络链路。若交换机队列填满，数据包会被丢弃，因此需要重新发送数据包。
- 数据包到达目标机器时，若所有CPU内核都在繁忙，则请求会被操作系统排队。
- 在虚拟化环境中，对CPU出现资源争用时，传入没在使用CPU的虚拟机的数据会被虚拟监视器排队。
- TCP的流量控制（拥塞避免） ，会导致数据进入网络之前也会排队。
在高利用率的系统中，很快就能积累很长的队列。在公共云和多租户数据中心中，资源被很多客户共享，批处理工作负载（第十章）很容易让网络连接饱和。
在这种环境下，我们可以通过实验方式选择超时：测量延长的网络往返时间和多台机器的分布，以确定延迟的预期可变性。然后，考虑到应用程序的特性，可以确定故障检测延迟与过早超时风险之间的适当折衷。
更好的一种做法是，系统不是使用配置的常量超时时间，而是连续测量响应时间及其变化（抖动），并根据观察到的响应时间分布自动调整超时时间。（这可以通过Phi Accrual故障检测器来完成）
2.5 同步网络vs异步网络
若我们可以依靠网络来传递一些最大延迟固定的数据包，而不是丢弃数据包。那么分布式系统就会简单很多。为什么不能在硬件层面上解决这个问题呢？
看一看移动电话网络：打电话时，会建立一个电路，两个呼叫者之间的整个路线上为呼叫分配一个固定且有保障的带宽量，这个电路会保持至通话结束。呼叫建立时，每个帧内（每个方向）分配16位空间。因此，在通话期间，每一方都保证能够每250微秒发送一个精确的16位音频数据。即使数据经过多个路由器，也不会受到排队的影响，因为呼叫的16位空间已经在网络的下一跳中保留了下来。而且由于没有排队，网络的最大端到端延迟是固定的。我们称之为有限延迟（bounded delay） 。
我们不能简单的使网络延迟可预测吗？
电话网络电路与TCP连接有很大不同：电路是固定的预留带宽，而TCP的数据包会使用任何可用的带宽。同时，以太网和IP是分组交换协议，这些协议可以从排队中获得，从而使网络无限延迟。
数据中心网络和互联网使用分组交换是针对突发流量（bursty traffic） 进行的优化。电话时每秒传送的比特数固定，而请求网页传输文件等没有特定的带宽要求，分组优化可以提高网络利用率。资源的动态分配可以提高资源利用率，以可变延迟为代价，这是成本和收益权衡的结果。
已经有一些尝试建立支持电路交换和分组交换的混合网络，它们在链路层实现了端到端的流量控制，从而减少了在网络中排队。
异步传输模式（Asynchronous TransferMode, ATM） 在20世纪80年代是以太网的竞争对手，但最终在电话网核心交换机之外并没有得到太多的采用。
但是，目前在多租户数据中心和公共云或通过互联网进行通信时，此类服务质量尚未启用。当前部署的技术不允许我们对网络的延迟或可靠性作出任何保证：我们必须假设网络拥塞，排队和无限的延迟总是会发生。 因此，超时时间没有“正确”的值——它需要通过实验来确定。
3 不可靠时钟
众所周知，时间和时钟是很重要的，但是在分布式系统中，由于通信的可变延迟，很难确定多台机器间发生事情的顺序。网络时间协议（NTP） 用于同步设备之间的时钟，允许根据一组服务器报告的时间来调整计算机时钟。服务器则从更精确的时间源（GPS等）获取时间。
3.1 单调钟和时钟
时钟
根据某个日历返回当前的日期和时间。例如Linux上的clock_gettime(CLOCK_REALTIME)和Java里的System.currentTimeMillis()返回自epoch（1970年1月1日 午夜 UTC，格里高利历）以来的秒数（或毫秒）。
时钟与NTP同步，然而计算机内的石英钟会自动发生漂移（drifts） 而不准，网络中提供NTP服务校准时间就会发生时钟回拨或跳跃的问题。
而与NTP同步后，机器间的时钟也会有差异，因为网络间有延迟，当网络拥塞时，误差可能超过100ms。
单调钟
单调钟保证时间是向前的，不发生时钟回拨问题，适用于测量持续时间（时间间隔），例如超时或服务的响应时间。Linux上的clock_gettime(CLOCK_MONOTONIC)，和Java中的System.nanoTime()都是单调时钟。
单调钟的绝对值没有任何意义，时钟值之差为两次检测之间的时间间隔。单调钟可以在几微妙或更短时间内测量时间间隔。
分布式系统中，单调钟测量经过时间（elapsed time） 的效果很好，因为它不假定不同节点之间的时间存在同步。
3.3 依赖同步时钟
时钟有一个巨大的缺陷：一天可能不会有精确的86400秒，时钟可能会前后跳跃，而一个节点上的时间可能与另一个节点上的时间完全不同。
然而，不正确的时钟很容易被视而不见，时间错误时应用似乎还是可以正常工作，数据会悄无声息的丢失而不是惊天动地的崩溃。
因此，要使用同步时钟的软件时，必须仔细监控所有机器之间的时钟偏移，时钟偏离其他时钟太远的节点应当被宣告死亡，并从集群中移除。这样的监控可以确保你在损失发生之前注意到破损的时钟。
有序事件的时间戳
依赖时钟的分布式系统，可能会出现写入时间早而时间戳更晚的情况
如上图，客户端B的写入比客户端A的写入要晚，但是B的写入具有较早的时间戳。这样会导致最后写入胜利（LWW） （在多领导复制和无领导数据库中被广泛使用）错误的删除掉值。
此外，LWW也无法区分高频顺序写入（有因果）和真正并发写入（无因果）。而NTP同步精度本身受到网络往返时间限制，也会出现误差。
逻辑时钟可以更安全的排序事件，逻辑时钟仅测量事件的相对顺序。时钟和单调钟也成为物理时钟。
时钟读数存在置信区间
由于时钟不是准确的，所以将时钟读数视为一个时间点没有意义，它更像是一段时间范围。
不确定性界限可以根据时间源来计算。但是大多数系统不会告诉我们时间戳的预期错误。
全局快照的同步时钟
前文中提到，快照隔离是数据库中非常有用的功能，它允许只读事务看到特定时间点的处于一致状态的数据库，且不会锁定和干扰读写事务。
快照隔离最常见的实现需要单调递增的事务ID。如果写入比快照晚（即，写入具有比快照更大的事务ID），则该写入对于快照事务是不可见的。在单节点数据库上，一个简单的计数器就足以生成事务ID。
但是在分布式系统中，大量小规模、高频率事务的情境下，全局单调递增的事务ID很难形成。
如果有足够的同步性，我们就能用同步时钟的时间戳作为事务ID。Spanner在提交读写事务时，会故意等待置信区间长度的时间，同时，Google在每个数据中心部署了一个GPS接收器或原子钟，这两个操作保证了事务时间戳能反映因果关系。
3.4 暂停进程
一个节点如何知道它仍然是领导者（它并没有被别人宣告为死亡），并且它可以安全地接受写入呢？
租约是类似带超时的锁，当一个节点获得一个租约时，它知道它在某段时间内自己是领导者，直到租约到期。为了保持领导地位，节点必须在周期性地在租约过期前续期。 如果节点发生故障，就会停止续期，所以当租约过期时，另一个节点可以接管。
然而分布式系统不能使用租约（lease）来确保节点的领导者地位：
- 它依赖于同步时钟，租约到期期间由另一台机器设置，却与本地时钟进行比较。
- 当线程在获取时间的代码行暂停时，等他好了租约可能已经过期并由另一个节点接管领导，然而它却不知道，从而继续循环。（GC机制偶尔就需要停止所有线程，类似的情况还有挂起虚拟机、停止世界、执行同步磁盘访问等待磁盘IO等）
当一台机器上编写多线程代码时，有很多工具保证线程安全，但是这些工具不能转化为分布式系统操作，因为分布式系统没有共享内存，只能通过不可靠的网络发送消息。
分布式系统中的节点，必须假定其执行可能在任意时刻暂停相当长的时间，即使是在一个函数的中间。其执行可能在任意时刻暂停相当长的时间，即使是在一个函数的中间。
响应时间保证
导致暂停的原因是可以消除的，某些软件的运行环境要求很高，例如飞机、火箭、汽车上的软件。在这些系统中，软件必须有一个特定的截止时间（deadline） ，若截止时间不满足可能会导致整个系统故障。这就是所谓的硬实时（hard real-time） 系统。
例如，当车载传感器检测到当前正在经历碰撞，GC暂停就可能导致安全气囊释放系统延迟弹出。
在嵌入式系统中，实时是指系统经过精心设计和测试，以满足所有情况下的特定时间保证。提供实时保证需要各级软件栈的支持，所有这些都需要大量额外的工作，严重限制了可以使用的编程语言，库和工具的范围，所以开发费用昂贵，通常用于安全关键的嵌入式设备。
限制垃圾收集的影响
语言运行时在计划垃圾回收时具有一定的灵活性，因为它们可以跟踪对象分配的速度和随着时间的推移剩余的空闲内存。
例如可以将GC暂停视为这个节点的计划中断，让其他节点处理来自客户端的请求：运行时可以警告应用程序一个节点很快需要GC暂停，那么应用程序可以停止向该节点发送新的请求，等待它完成处理未完成的请求，然后在没有请求正在进行时执行GC。一些对延迟敏感的金融交易系统使用这种方法。
还可以只用垃圾收集器来处理短命对象（这些对象要快速收集），并定期在积累大量长寿对象（因此需要完整GC）之前重新启动进程。一次可以重新启动一个节点，在计划重新启动之前，流量可以从节点移开，就像滚动升级一样。
这些措施不能完全阻止垃圾回收暂停，但可以有效地减少它们对应用的影响。
4 知识、真相与谎言
分布式系统与运行在单台计算机上的程序的不同之处：没有共享内存，只有通过可变延迟的不可靠网络传递的消息，系统可能遭受部分失效，不可靠的时钟和处理暂停。
节点只能通过交换消息来找出另一个节点所处的状态（存储了哪些数据，是否正确运行等等）。如果远程节点没有响应，则无法知道它处于什么状态，因为网络中的问题不能可靠地与节点上的问题区分开来。
4.1 真理由多数所定义
半断开：一个节点可以接收信息，但是发送不出去，所以其他节点宣布了它的死亡。
另一种情况：节点经过了一个长时间的GC，其他节点宣布了它的死亡，但是GC结束后该节点又恢复了正常。在这个节点的角度来看，它没有经历任何时间。
以上情况说明了，节点不一定能相信自己对于情况的判断。分布式系统不能完全依赖单个节点，因为节点可能随时失效，可能会使系统卡死，无法恢复。
所以，许多分布式算法都依赖于法定人数，即在节点之间进行投票，决策需要来自多个节点的最小投票数，以减少对于某个特定节点的依赖。这也包括关于宣告节点死亡的决定。如果法定数量的节点宣告另一个节点已经死亡，那么即使该节点仍感觉自己活着，它也必须被认为是死的。个体节点必须遵守法定决定并下台。
最常见的法定人数是超过一半的绝对多数。多数法定人数允许系统继续工作，如果单个节点发生故障，系统仍然是安全的。
领导者与锁定
通常情况下，一些东西在一个系统中只能有一个。例如：
- 数据库分区的领导者只能有一个节点，以避免脑裂（split brain） （参阅“处理节点宕机”）
- 特定资源的锁或对象只允许一个事务/客户端持有，以防同时写入和损坏。
- 一个特定的用户名只能被一个用户所注册，因为用户名必须唯一标识一个用户。
但在分布式系统中需要注意，一个节点认为它是领导者，不意味着有法定人数的节点同意，领导者节点可能在它不知道的时候被降级了（GC、网络中断等），如果不处理这种情况就会出现大问题（如图）。
这个问题就是我们先前在“进程暂停”中讨论过的一个例子：如果持有租约的客户端暂停太久，它的租约将到期。另一个客户端可以获得同一文件的租约，并开始写入文件。当暂停的客户端回来时，它不正确地认为它仍然有一个有效的租约，并继续写入文件。结果，客户的写入冲突和损坏的文件。
防护令牌
“防护”这个技术可以可以简单的解决上面这个问题。
我们假设每次锁定服务器授予锁或租约时，它还会返回一个防护令牌（fencing token） ，这个数字在每次授予锁定时都会增加（例如，由锁定服务增加）。然后，我们可以要求客户端每次向存储服务发送写入请求时，都必须包含当前的屏蔽令牌。
上图中，存储服务器记住它已经处理了一个具有更高令牌编号（34）的写入，因此它会拒绝带有令牌33的请求。
4.2 拜占庭故障
屏蔽令牌可以检测和阻止无意中发生错误的节点（例如，因为它尚未发现其租约已过期）。但是，如果节点有意破坏系统的保证，则可以通过使用假屏蔽令牌发送消息来轻松完成此操作。
如果存在节点可能“撒谎”（发送任意错误或损坏的响应）的风险，则分布式系统的问题变得更困难了——例如，如果节点可能声称其实际上没有收到特定的消息。这种行为被称为拜占庭故障（Byzantine fault） ，在不信任的环境中达成共识的问题被称为拜占庭将军问题。
当一个系统在部分节点发生故障、不遵守协议、甚至恶意攻击、扰乱网络时仍然能继续正确工作，称之为拜占庭容错（Byzantine fault-tolerant） 。
这个问题在某些场景中有意义：重要的系统（航天），多个参与组织的系统。
在大多数服务器端数据系统中，部署拜占庭容错解决方案的成本非常高。我们通常不使用拜占庭容错协议，而只是让服务器决定什么是客户端行为。在没有这种中心授权的对等网络中，拜占庭容错更为重要。
同时，拜占庭容错算法对网络安全问题没有意义，因为如果攻击者能渗透一个节点，那么它基本上就能以同样的方式渗透所有节点，因为他们的系统相同。
4.3 系统模式与现实
已经有很多算法被设计以解决分布式系统的各种故障。算法的编写方式并不过分依赖于运行的硬件和软件配置的细节。这又要求我们以某种方式将我们期望在系统中发生的错误形式化。我们通过定义一个系统模型来做到这一点，这个模型是一个抽象，描述一个算法可能承担的事情。
关于定时假设，三种系统模型是常用的：
- 同步模型（synchronous model）：假设网络延迟，进程暂停和和时钟误差都是有上限的。
- 部分同步（partial synchronous）：系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的上限。
- 异步模型：一个算法不允许对时机做任何假设——事实上它甚至没有时钟（所以它不能使用超时）。一些算法被设计为可用于异步模型，但非常受限。
考虑节点失效时，三种最常见的模型是：
- 崩溃-停止故障：假设节点只能因为崩溃而失效，即节点可能在任意时刻停止，然后就永远消失。
- 崩溃-恢复故障：假设节点可能会在任何时候崩溃，但也许会在未知的时间之后再次开始响应。在此模型中，节点具有稳定的存储（即，非易失性磁盘存储）且会在崩溃中保留，而内存中的状态会丢失。
- 拜占庭故障（任意故障）：节点可以做（绝对意义上的）任何事情，包括试图戏弄和欺骗其他节点，如上一节所述。
在真实系统的建模中，通常使用崩溃-恢复故障的部分同步模型。
算法的正确性
为了定义算法是正确的，我们可以描述它的属性。例如，排序算法的输出具有如下特性：对于输出列表中的任何两个不同的元素，左边的元素比右边的元素小。这只是定义对列表进行排序含义的一种形式方式。
同样，我们可以写下我们想要的分布式算法的属性来定义它的正确含义。例如，如果我们正在为一个锁生成屏蔽令牌，我们可能要求算法具有以下属性：唯一性、单调序列、可用性（请求防护令牌且没有崩溃的节点，都会收到响应）
安全性和活性
安全性（safety）通常被非正式地定义为，没有坏事发生，而活性（safety）通常就类似：最终好事发生。
活性属性通常在定义中通常包括“最终”一词。在刚刚给出的例子中，唯一性和单调序列是安全属性，但可用性是活性属性。
- 如果安全属性被违反，我们可以指向一个特定的时间点（例如，如果违反了唯一性属性，我们可以确定重复的防护令牌返回的特定操作） 。违反安全属性后，违规行为不能撤销——损失已经发生。
- 活性属性反过来：在某个时间点（例如，一个节点可能发送了一个请求，但还没有收到响应），它可能不成立，但总是希望在未来（即通过接受答复）。
区分安全性和活性属性的一个优点是可以帮助我们处理困难的系统模型。
将系统模型映射到现实世界
系统模型只是对现实的简化抽象， 证明算法正确并不意味着它在真实系统上的实现必然总是正确的。算法的理论描述可以简单宣称一些事在假设上是不会发生的，但实际上我们还是需要对可能发生和不可能发生的故障做出假设，真实世界的实现，仍然会包括处理“假设上不可能”情况的代码。
这并不是说理论上抽象的系统模型是毫无价值的，恰恰相反，它们对于将实际系统的复杂性降低到一个我们可以推理的可处理的错误是非常有帮助的，以便我们能够理解这个问题，并试图系统地解决这个问题。我们可以证明算法是正确的，通过显示它们的属性总是保持在某个系统模型中。理论分析可以发现算法中的问题，这种问题可能会在现实系统中长期潜伏，直到你的假设（例如，时间）因为不寻常的情况被打破。理论分析与经验测试同样重要。
