系统模型-进程

在真实的分布式系统中，可能存在服务器（节点）、处理器、进程、线程等并发执行的实体。

在分布式算法中，这些实体都被抽象为进程。

注意，这里的进程与操作系统中的进程不完全是一个概念，后者侧重于描述一组资源的集合，例如文件句柄、地址空间、数据、代码等，还可以有多个线程，而前者是一个有状态的自动机。

前面专门指出，一个进程正在处理某事件时，如果感知到另一个事件，那么该进程会先处理完前一个事件，然后基于处理后的状态处理下一个事件。这里隐藏的含义是，进程只有一个顺序执行过程，不能再分叉为多个执行序列。

进程的构成如图 3-1 所示。进程内部有一个运行时环境，它先于任何自动机实例启动，为自动机实例提供了一个托管环境，包括定时器、底层物理链路抽象等。同时，运行时环境还负责自动机实例的生命周期管理，包括创建、恢复、销毁自动机实例等。

图3-1 进程的构成示意图

在本篇中，若无特殊说明，把一个分布式系统中的进程集合记为Π，把这个进程集合的大小，即进程总数，记为N。每个进程都有一个进程标识，例如p1， p2，…， pn。进程标识有如下特性。

第一是不变，即进程标识在整个分布式系统运行的全过程中是不会改变的。

第二是两两可比，即任何两个进程的标识都是可以比较“大小”的。正因如此，集合中每个进程的标识都是独一无二的，但都执行相同的自动机算法。

第三是全局公开，即每个进程在初始化时就已经知道其他进程的标识了，并可以通过进程标识相互通信。

在描述算法时，进程自身可以用self来标识。除非另行说明，这个进程集合是静态的，也就是说，在运行过程中，既没有新的进程加入集合，也没有新的进程离开这个集合。

消息

进程之间相互收发的数据被称为消息。进程间的通信是靠消息进行的。

我们假设在分布式系统中，每个消息在全局范围内都是独一无二的。这一点并不难实现，只需要让每个消息的标识包含发送进程的标识和发送进程自身维护的一个递增序号，即可确保每个消息在全局范围内的标识都是独一无二的。

消息都是通过链路传递的。我们假设这个链路可以识别消息的接收进程，并通过消息接收进程标识，将消息传递到接收进程。如果这个链路是一个介质共享的广播网络，这一点显然是可以做到的。如果链路是一个基于IP（Internet Protocol）的网络，那么消息的接收进程标识可以是接收进程所在服务器的IP地址。

本篇主要介绍分布式算法，只关注消息和消息传递过程的特性，而不关注消息传递过程的工作细节。

当消息通过不可信的链路进行传递时，消息内容可能被窃听，也可能被篡改，消息的发送进程和接收进程标识可能会被伪造，如不采取额外的措施，分布式系统难以正常运行。

针对这些问题，密码学已经有了比较成熟的解决方案。例如，我们可以利用公钥密码术解决双方身份认证的问题，利用对称密码术解决防止信息窃取的问题，利用散列函数和数字签名技术防止消息被篡改的问题。至于密码术的工作原理和细节，本书不做介绍。但要解决这些问题，只需要让每个进程都提前获得其他进程的公钥即可，就如同让每个进程都提前知道其他进程的标识一样。这样一来，在后续的讨论中，我们就可以认为消息是不会被窃听或篡改的，且身份是不会被伪造的。

进程启动

每个进程的标识在进程启动前就已经确定了，并且对所有进程都是公开的，即每个进程不仅知道自己的进程标识，还知道其他进程的标识。

对消息进行加密和认证所需要的密钥也应该事先分配给进程。例如，每个进程都有一对公钥和私钥，其中私钥只有该进程自身可见，而公钥则是所有进程可见的。每个进程不仅知道自己的私钥和公钥，还知道其他进程的公钥。

进程标识和密钥分配应该在进程启动之前准备好。在实践中，进程标识和密钥往往由管理员事先分配好，或者通过其他程序自动进行分配。

当进程启动时，运行时环境会创建自动机实例。如果这个自动机是一个合成自动机，那么运行时环境会根据构成该合成自动机实例的部件自动机之间的调用关系，按照被调用的部件自动机优先的原则，逐个创建部件自动机实例。当且仅当所有部件自动机实例创建成功时，整个合成自动机实例才算创建成功，进程启动才算成功，否则进程启动失败。

当运行时环境创建部件自动机实例时，会调用该部件自动机实例的一个特殊的输入事件<Init＞，这个输入事件被称为初始化事件。当部件自动机实例处理初始化事件时，一般会对部件自动机实例的状态进行初始化。当部件自动机实例完成初始化事件的处理后，该自动机实例才算创建成功。

进程失败

在分布式系统中，单点故障是很常见的情况，但整个系统应该能够继续正常工作。节点故障的类型有很多，我们需要对这些故障进行建模，然后根据不同的故障模型采取不同的算法，才能较好地解决问题。

我们定义：如果一个进程不能按照预设的算法执行，那么这个进程就是失败的，否则这个进程就是正确的。例如，节点掉电或进程崩溃一般被认为是进程失败，但如果预设的算法允许进程崩溃后恢复，那么曾经崩溃过的进程就不一定是失败的进程。

不同的实例对同一个进程是否正确，可以有不同的判断，这取决于该实例是否认为该进程按照预设的算法执行。例如，实例a认为进程p是正确的，实例b认为进程p是失败的，这也是可以的，即使实例a和实例b同时运行于同一个进程内，而且是同一个抽象的两个实例。

进程失败的最小单位是进程，而不是进程内部的自动机实例。实例b可以认为“进程p失败了”，但不能说“进程p中的实例c失败了”，因为不存在“某个实例失败了”的说法。

假设一个分布式系统的进程总数（包括正确的和失败的）为N，如果允许失败的进程数量上限为f，那么f被称为该分布式系统的韧性（resilience）。这个f可能是严格小于N/2的最大整数，也可能是N-1，还可能是其他值，这取决于自动机的抽象和实现。

在本篇中，若无特殊说明，系统的韧性用f表示。

崩溃式失败

崩溃式失败（Crash Failure）是指进程不再执行任何步骤，也不接收或发送任何消息。

崩溃式失败很常见。例如，服务器断电就属于崩溃式失败，服务器网卡停止工作也属于崩溃式失败。这一点不太容易理解，但仔细分析便知，由于服务器无法与外界进行任何通信，尽管这台服务器本身或许还在执行一些本地逻辑，但在其他服务器看来，这台服务器与断电停止工作没什么区别，所以它会被其他服务器认为是崩溃了。

所以，判断一个进程是否是崩溃式失败，关键不在于该进程是否真的崩溃了，而在于在其他实例看来它是否崩溃了。

因为在一个分布式系统中，在进程间除消息传递外，没有任何其他手段知道其他进程的真实状态。如果在实例a看来，进程p不执行任何步骤或者不发送任何消息，那么实例a就会认为进程p崩溃了。

是否选择崩溃式失败模型，关键不在于进程是否会崩溃，而在于算法是否允许这个进程崩溃后重新恢复并且继续参与算法的执行过程。如果不允许，那么即使进程p在崩溃后被恢复了，例如服务器被重启了或者网卡被修复了，以前认为进程p已经崩溃的那些实例仍然会认为进程p是崩溃的。被恢复的进程p或许还能收到来自其他进程的消息，并执行对应的步骤，但这与其他进程没有关系。

即使进程p恢复之后向其他进程发送消息，其他进程也不会理会这些消息，就好像收到了一个不认识的进程发来的消息一样。在崩溃式失败模型中，一旦实例a认为进程p崩溃，那么在实例a的生命周期内，进程p永远会被实例a认为是崩溃的，不会再参与实例a的算法执行。

读者可能会感到困惑，如果崩溃式失败模型不允许恢复的进程继续参与工作，那么系统中不可用的进程会越来越多，系统迟早会停止工作。这样一来，崩溃式失败模型岂不只是纸上谈兵的纯理论，而无法用于实际生产？

其实不然。尽管进程p被实例a认为崩溃了，但是其他的实例都会独立地看待进程p。例如，与实例a不属于同一个抽象的实例b，或者与实例a属于同一个抽象的实例a'，都认为进程p按照预设的算法执行，也就是认为进程p是正确的。

因此，即使在崩溃式失败模型中，一个恢复的进程p仍然有机会继续参与系统的工作，只不过实例b或实例a'看到的是一个从未崩溃过的进程p。

遗漏式失败

遗漏式失败（Omission Failure）是指进程不能发送（或接收）它本应该按照算法发送（或接收）的消息。一般来说，遗漏是由进程的缓存溢出或者网络拥塞引起的消息丢失，导致进程不能按照算法约定执行。

遗漏式失败可以分为发送遗漏和接收遗漏。发送遗漏时，进程可以接收其他进程发送的消息并更新自己的状态，但无法把消息发送给其他进程，因此在其他进程看来，该进程已经停止执行了。接收遗漏时，进程无法接收其他进程发送的消息，但可以把消息（例如心跳请求）发送给其他进程，因此在其他进程看来，该进程并没有停止执行。

相比于崩溃式失败，遗漏式失败是可以恢复的，例如，在某个时刻t，因为网卡不稳定而导致进程接收消息失败，而又在后续的某个时刻t'（t'＞t），因为网卡恢复，进程继续正常执行算法。因此，崩溃式失败可以看作一种特殊的、即遗漏发生后不会恢复的遗漏式失败。

恢复后崩溃失败

在恢复后崩溃失败模型中，我们允许正确的进程曾经崩溃过。如果一个进程能最终恢复，那么这个进程仍然被认为是正确的。但如果一个进程经过多次崩溃、恢复后最终崩溃，或者崩溃、恢复的次数是无限的，那么该进程就是失败的。根据这个定义，如果一个进程经历了有限次崩溃后，最终恢复了，那么这个进程仍被认为是正确的。

在恢复后崩溃失败模型中，当一个进程崩溃后，它将不能收发任何消息，当该进程被恢复后，它又可以继续收发消息了，这与遗漏式失败有一些相似。

但两者的不同之处在于，在遗漏式失败模型中，进程并未崩溃，其内部状态依然是保留的，一旦进程继续收发消息，进程将会从上次与外界失联的状态开始执行；而在恢复后崩溃失败中，进程的确是崩溃了，当该进程被恢复时，它的状态被清空，好像“失忆”了一般，只能从头执行。

因此，遗漏式失败可以看作恢复后崩溃失败的特例，即一种不失忆的恢复。

对于其他进程来说，“失忆”是一个挑战：如果不再理会这个恢复过来的进程的任何消息，那么这个模型就退化为崩溃式失败模型了；如果继续接纳这个失忆的进程，则要面对进程随时还会崩溃的可能。为了简化设计，在恢复后崩溃失败模型中，每个进程都有一个持久化存储来保存状态，以便进程被重启后恢复到崩溃前的样子，这个持久化存储被称为日志（Log）。通常，日志可以用机械磁盘或固态硬盘实现。访问日志比访问易失性内存（Volatile Memory）要慢得多，因此要尽可能减少不必要的日志访问。

当进程启动时，运行时环境会检查该进程是否成功启动过。若该进程从未成功启动过，那么运行时环境将继续重新创建自动机实例，该过程在上面中介绍。

若进程成功启动过，那么运行时环境会恢复自动机实例。如果这个自动机是一个合成自动机，那么运行时环境会根据构成该合成自动机实例的部件自动机之间的调用关系，按照被调用的部件自动机优先的原则，逐个恢复部件自动机实例。当且仅当所有部件自动机实例恢复成功时，整个合成自动机实例才算恢复成功，进程恢复才算成功，否则进程恢复失败。如果进程恢复失败后再次启动，那么运行时环境会重头依次恢复各个部件自动机。

当运行时环境恢复部件自动机实例时，运行时环境会调用该部件自动机实例的一个特殊的输入事件<Recovery＞，这个输入事件被称为恢复事件。当部件自动机实例处理恢复事件时，一般会对部件自动机实例的状态进行恢复，例如从日志中将状态恢复至内存。当部件自动机实例完成恢复事件的处理后，该部件自动机实例才算恢复成功。

或许有人认为，只要在进程恢复时换一个进程标识，即可利用崩溃式失败模型解决进程恢复的问题了。实际上这种想法是不对的，一个分布式系统的进程集合在系统初始化时就已经确定了，而且是静态的。如果一个进程换一个新的标识试图加入系统，其他进程要么会拒绝该进程，例如不向它发送任何消息，或忽略它发出的任何消息；要么会认为这个“新”进程刚从失败状态恢复过来，这仍然适用于恢复后崩溃失败模型。

拜占庭失败

有时，进程还在继续执行步骤，也没有发生任何遗漏式失败，但却不按照预设的算法执行，这种失败被称为拜占庭失败（Byzantium Failure），这种进程被称为拜占庭进程。拜占庭失败也叫作随意式失败。

发生拜占庭失败，很容易被理解为遭到恶意攻击。实际上，一些非恶意的过失行为也可能导致拜占庭失败。例如，应用软件、函数库、编译器、操作系统的bug可能导致进程在偶然情况下执行错误的步骤，从而未能按照预设的算法执行。

有时，进程的确是遭到了恶意攻击。例如，当服务器被黑客入侵后，黑客可以向进程“注射”一段精心设计的代码，从而改变进程的行为。这段精心设计的代码可以获得进程所有的状态和所有收发的消息，因而构造出难以被加密、认证、校验等普通手段检测出来的消息。

应对拜占庭失败的代价是较高的。一个系统中的拜占庭进程数必须严格小于进程总数的1/3，例如，在一个进程总数为7的系统中，拜占庭进程数最多为2；如果进程总数为6，则拜占庭进程数最多为1，而不是2，因为2并非严格小于6/3。

各种失败的关系

进程失败可以被分为四种，分别是崩溃式失败、遗漏式失败、恢复后崩溃失败和拜占庭失败，它们的关系如图3-2所示。其中，崩溃式失败可以看作一种特殊的、即遗漏发生后不会恢复的遗漏式失败；遗漏式失败可以看作恢复后崩溃失败的特例，即一种不失忆的恢复；恢复后崩溃失败可以看作拜占庭失败的特例，即没有进程、不按照预设的算法执行的、特殊的拜占庭失败。

图3-2 进程失败的包含关系

时钟

本地时钟和全局时钟

如果一个进程能访问专属于自己的时钟，那么这个时钟被称为进程本地时钟，简称本地时钟。本地时钟的读数被称为本地时间。本地时间的度量单位不是秒，而是“嘀嗒”。所谓嘀嗒，就是“本地时钟的读数增加1秒”这个事件。如果本地时间经过了5秒，实际上是指本地时钟嘀嗒了5次，即“本地时钟的读数增加1秒”这个事件发生了5次，而非“真实的物理时空经过了5秒”。

本地时钟就好像手表，进程可以通过本地时钟获取本地时间。但正如手表可能不准一样，本地时间也可能“不准”。但“不准”是相对某个走得准的标准时钟而言的，这个标准时钟叫作全局时钟（Global Clock）。全局时钟的读数被称为全局时间（Global Time）。

全局时钟是一个理想时钟，它表示真实物理时空的真实时间，所以全局时间的度量单位是秒。世界上并不存在这样一台理想的全局时钟。2019 年，由美国国家标准局研制的量子时钟已达到330亿年误差不超过1秒的水平，成为世界上最准的原子钟。如果用这样一台原子钟来代表全局时钟，那么这台原子钟嘀嗒1次，基本上可以认为全局时间刚好增加1秒。

虽然全局时钟不是真实的物理存在，进程也无法直接读取其读数，但引入全局时钟这个概念有助于我们进行算法分析。例如，有两个本身并没有逻辑先后顺序的事件e1和事件e2，如果需要区分它们两者的先后顺序，就需要引入一个观察者，以这个观察者的视角来判断这两个事件的先后顺序，这个观察者就是全局时钟。

一个分布式系统只需要一个全局时钟，所有事件的全局时间都取自这个全局时钟的读数。如果把这些事件对应的全局时间画在一条直线上，那么这条直线就称为全局时间轴。显然，一个全局时钟只对应一个全局时间轴。

因果顺序不变

细心的读者也许会提出这样的质疑：既然观察者是一个虚构的概念，那么如果非要选择多个观察者，会怎样呢？首先，我们讨论一下什么是因果顺序。设“进程p发送了一个消息m1”为事件e1，“进程q接收了消息m1”为事件e2，“进程q在接收了消息m1之后发送消息m2”为事件e3，那么从逻辑上看，事件e1一定先于事件e2，事件e2一定先于事件e3。如果不是这样，那么在逻辑上说不通，因为只有进程p发出了消息m1，进程q才有可能接收到消息m1，进而发出消息m2，这与如何选择观察者无关。这里的“逻辑”就是“因果”，逻辑顺序就是因果顺序，逻辑上的先后关系就是先因后果的因果关系。

那对于没有因果关系的两个事件，应该如何比较先后呢？设“甲在月球上开灯”为事件e1，“乙在火星上开灯”为事件e2，观察者在地球上同时收到了甲和乙分别来自月球和火星的灯光，请问事件e1和事件e2谁先谁后？绝大多数人会认为事件e2先发生，因为火星离地球更远，光传过来需要花费更长的时间，而地球上的观察者还能同时接收到月球和火星的灯光，那么显然是火星上的乙先开灯。

回答者之所以如此判断，实际上是利用了很多物理学的信息和知识，例如“月球、火星、地球三者的远近关系”这一位置信息，光速这一速度信息，以及“速度×时间=位移”这一物理原理。但在分布式算法中，我们不考虑物理学的知识，例如月球、火星、地球三者的空间未知关系是未知的，光速也不清楚，仅基于常识讨论先后，那么答案又是什么呢？——取决于观察者。

如果观察者在地球上，先看到事件e1、后看到事件e2，那么就是甲先开灯、乙后开灯。如果观察者在火星的卫星上，先看到事件e2、后看到事件e1，那么就是乙先开灯、甲后开灯。这两种顺序都是合理的。这两种顺序不是基于事件e1和事件e2的因果关系得到的，而是基于观察者的顺序。因此，选择不同的观察者，就会得到不同的顺序。

但是，明明事件e1和事件e2在何时发生是“客观”的，怎么会因观察者的位置不同而不同呢？这个世界岂不乱套了？

其实并没有乱套。如果事件e1在因果上先于事件e2，其实无论观察者所在何处，一定会先看到事件e1、后看到事件e2。

图3-3 观察者与全局顺序

如图 3-3所示，设“甲在月球上开灯”为事件e1，“乙在火星上看到了甲的灯光后开灯”为事件e2。由于乙在看到了甲的灯光后才开灯，因此事件e1和事件e2是因果关系。所谓观察者看到事件 e1和事件 e2，实际上是说这两个事件以最快的速度通知观察者，这个最快的速度莫过于光速。又根据三角形两边之和大于第三边的原理可知，无论观察者所在何处，AB+BC＞AC 必然成立，所以观察者一定先看到甲开灯，后看到乙开灯，符合“事件e1先于事件e2”这一因果顺序。

因此，只要观察者与事件位于同一参照系，无论观察者的位置如何，观察者得到的事件顺序都是相同的，并不会颠倒因果顺序。只不过，对于两个完全独立（无因果关系）的事件而言，把任何一种顺序当成它们的全局顺序都是合理的。这两个完全独立的事件就被称为并行事件或者同时发生，因为本无因果，所以顺序全凭观察者定夺。

也许有读者认为：假设太阳上有一个时钟，甲、乙两人在开灯时，先从太阳上看一下时钟，然后把太阳上读到的时钟读数藏在灯光信号中，这样一来，观察者通过灯光信息中隐藏的时钟读数来区分谁先开灯，不就与观察者的位置无关了吗？实际上，在这种情况下，太阳上的那个时钟才是真正的观察者，尽管它没有拿笔记录下当前的时间，但太阳的位置决定了甲、乙两人从月球和火星上看到的时钟读数。因此，若要区分先后，还是离不开观察者。

也许还有读者认为：假如月球上有一个时钟A，然后再克隆一个完全一样（初始读数相同、走得“一样快”）的时钟B，把时钟B缓慢地（避开狭义相对论中时钟变慢的效应）运送到火星上，甲、乙两人在开灯时分别看一下月球和火星上的时钟，然后把读到的时钟读数藏在灯光信号中。这样一来，观察者通过灯光信息中隐藏的时钟读数来区分谁先开灯，不就与观察者的位置无关且没有全局时钟了吗？

实际上，在这种情况下，观察者得到的仅仅是甲、乙开灯时月球和火星的时钟读数，并不能区分甲、乙谁先开灯。读者之所以认为能区分先后，实际上是基于“两个时钟完全一样”这一物理学的假设而非因果关系得出的结论。实际上，观察者得到的只是甲、乙开灯时月球和火星的时钟读数，至于两个读数是否相同，是物理学要解决的问题。只有物理学保证了“A和B两个时钟的读数是相同的”，才能判断出甲、乙谁先开灯。因此，这个假设仍然不能推翻“区分先后离不开观察者”这一结论。

最后，我们以股票交易为例。甲、乙两人的操作顺序非常重要，例如，先买者价低、后买者价高，因此对于股票交易平台而言，需要尽可能准确地区分甲、乙两人的先后顺序。但甲、乙相隔千里，谁也不是另一方的因或果，如果不引入观察者，实际上是无法区分先后顺序的。所以股票交易平台会以平台本身作为观察者，把平台接收到请求的先后顺序作为甲、乙两人进行操作的先后顺序。

回到本节开头的问题。的确，观察者是虚构的，可以选择多个观察者，但选择多个观察者并不会改变因果关系，即不会改变事件之间的因果顺序，因此选择一个就够了。在本书中，一个分布式系统的全局时钟就只有一个，全局时间轴也只有一个。

逻辑时钟

如果没有本地时钟，那么进程也可以用收获事件的次数来表示时间，这个时间被称为逻辑时间（Logical Time），对应的时钟概念被称为逻辑时钟（Logical Clock）。通常用如下算法来度量逻辑时间。

（1）每个进程p在本地用一个整数变量lp来表示逻辑时间，初始值为0。

（2）当进程p收获一个事件时，会把逻辑时间lp的值加1。

（3）当进程p发送消息时，会对消息打一个时间戳，时间戳的值为发送瞬间进程p的逻辑时间，用t（e）表示。

（4）当进程p接收消息时，会把消息中的时间戳tm与逻辑时间的最大值加1作为最新的逻辑时间，即lp=max{tm， lp}+1。

上面描述中提到了，事件不仅包括进程的接口事件，还包括内部事件。

例如，进程的定时器触发的本地事件是一种会导致本地逻辑时钟自增的事件。

逻辑时钟可以刻画分布式系统中事件的先后关系，这个先后关系是逻辑上的因果关系。如图 3-4所示，当下列情况之一成立时，就说事件e1因果先于事件e2，表示为e1→e2。

（1）在同一个进程p中，事件e1发生在事件e2前，对应图3-4（a）。

（2）事件e1表示进程p发送了消息m，事件e2表示进程q接收了这个消息m，对应图3-4（b）。

（3）存在某个事件e'，使得e1→e'且e'→e2，对应图3-4（c）。

图3-4 事件的先后顺序

不难理解，当e1→e2时，t（e1）<t（e2）成立，反之则不成立。

时钟偏移

一般情况下，进程的本地时钟不是完美的，它与全局时钟总是有偏差的，并且需要一种方式来描述这种偏差。

进程的本地时间可以表示为C（t）=C（t0）+R（t-t0），其中，C（t）表示进程在全局时间t时刻的本地时间；C（t0）表示进程在全局时间t0时刻的本地时间；R是进程的时钟频率（Clock Change Rate），其物理含义是当全局时间前进1秒时，本地时钟嘀嗒的次数，度量单位是“嘀嗒每秒”（嘀嗒/秒）。

在理想情况下，时钟频率R=1，即本地时钟前进的速度与全局时钟完全相同，本地时间与全局时间的差值在任何时候都是恒定的。当R＞1时，本地时钟就会快于全局时钟，反之则慢于全局时钟。这种由时钟频率导致的本地时间与全局时间的偏差就称为时钟偏移（Clock Drift）。

对于某个本地时钟而言，在特定的环境下（例如特定的温度、气压、湿度等）和某个全局时间段内，使得时钟频率R∈（1/（1+ρ），1+ρ）总是成立的最小正数ρ被称为时钟偏移率，度量单位是“嘀嗒每秒”（嘀嗒/秒）。

本地时钟有很多种实现方式，常见的方式是通过石英晶体和等效的电路的震荡来驱动，其时钟偏移率ρ一般在20～1000ppm之间。ppm是parts per million的缩写，即“百万分之”的意思。由于ρ很小，1/（1+ρ） ≈1-ρ，因此时钟频率 R∈（1-ρ，1+ρ）也成立。

时钟偏移示意图如图 3-5 所示，偏移率ρ决定了两条虚线的斜率，两条虚线之间形成的夹角表示时钟频率的范围。

图3-5 时钟偏移示意图

在一个分布式系统中，进程的时钟偏移率是否存在上限，是设计分布式算法时需要考虑的一个重要问题。

时间假设

分布式系统的时间假设（Timing Assumption）是指该系统在事件处理、消息传递和时钟漂移等方面的时间特性。这些时间特性包括各个进程的事件处理耗时、各个链路的消息传递耗时，以及各个进程的时钟偏移率和超时处理耗时。

这些时间特性的组合不仅影响了一个分布式系统的性能，还决定了这个系统的时间假设，即这个系统是异步系统、同步系统，还是部分同步系统，进而影响分布式算法的设计。当我们说一个系统是异步、同步或部分同步系统时，就是假设这个系统符合异步、同步或部分同步系统的时间特性。我们把基于异步系统、同步系统和部分同步系统而设计的算法，分别称为异步算法、同步算法和部分同步算法。

消息传递耗时是指链路将消息从一个进程传递到另一个进程的耗时。事件处理耗时是指进程处理事件的耗时，也可以理解为自动机执行一步的耗时。消息传递耗时与事件处理耗时之和是消息耗时。例如，从进程p发送消息m到进程q接收消息m的耗时是消息传递耗时α，从进程q接收消息m到更新内部状态、向进程p发送新的消息m'的耗时是事件处理耗时β，消息耗时则是α+β。从进程p发送消息m到进程p接收并处理完消息m'的耗时则是2（α+β）。

超时事件是一种特殊的事件，由定时器触发，超时处理耗时特指进程处理超时事件的耗时。

由于网络丢包、延迟是比较常见的现象，因此讨论消息传递耗时是否存在上限是一件比较容易理解的事情。事件处理耗时往往被认为可以忽略，然而实际并非如此。例如，在操作系统上运行的一个进程p，在正常情况下可以在已知的耗时上限内完成对消息的处理，但是当操作系统物理内存不够时，进程p所使用的内存可能会被交换出物理内存，执行速度严重下降，导致事件处理耗时变得不可忽略。又例如，Java虚拟机在执行过程中会被迫进行完全垃圾回收（Full Garbage Collection），此时Java应用程序会暂停一段时间，导致事件处理耗时久到超乎想象。再例如，当进程p收到SIGSTOP 信号时，会暂停执行任何步骤，导致消息的处理出现不可预测的延后。以上都是可能发生但容易被忽略的因素。

异步系统

所谓异步系统（Asynchrony System），就是假设事件处理耗时不存在已知上限，或者消息传递耗时和时钟偏移率均不存在已知上限的分布式系统。

在异步系统中，我们不对进程执行速度的快慢、消息传递速度的快慢、本地时钟前进的快慢等做任何假设，因此任何系统都是异步系统。由于定时器依赖于本地时钟，因此也不能用于比较先后顺序。唯一可用的时钟只有逻辑时钟。

异步系统能够实现的抽象是有限的，有些抽象是无法在异步系统中实现的。例如，Fischer、Lynch和Paterson在1985年发表的论文中证明了“FLP不可能结论”：即便假设只有一个进程会崩溃，也不可能存在一个确定性算法可以在异步系统中实现共识抽象。这也意味着，不存在任何确定性算法可以在异步系统中实现那些依赖于共识抽象的其他抽象，例如全序广播、复制状态机、信号量、原子提交、组成员关系等抽象。

异步算法不仅适用于异步系统，还适用于同步系统和部分同步系统，因此异步算法的适用范围是最广的，可用于不可靠的环境。例如 P2P 系统，它的程序运行在消费者的终端上，这些终端没有共享内存，终端之间通过不稳定的互联网进行消息传递，终端的本地时钟也不可靠，因此这样的系统可被认为是一个异步系统。

值得注意的是，对于一个确定的物理系统，它的事件处理耗时、消息传递耗时和时钟偏移率的上限是存在且确定的。关键是我们是否知道这个上限，以及是否利用这个上限来设计分布式算法。我们如果不利用这个上限，那么仍然可以把它当成异步系统对待。

同步系统

所谓同步系统（Synchrony System），就是假设消息耗时存在已知上限的分布式系统。同步系统也可以被定义为，假设超时处理耗时和时钟偏移率均存在已知上限的分布式系统。

在 后面，我们会证明这两种定义是等价的，即基于消息耗时存在已知上限的假设可以构造出时钟偏移率存在已知上限的系统，基于超时处理耗时和时钟偏移率有上限的假设可以构造出消息耗时存在已知上限的系统。同步系统能够实现很多异步系统无法实现的功能，具体如下。

（1）失败检测。如果消息耗时存在已知上限，则可以设计基于心跳的失败检测算法。进程p每隔一段时间就会向进程q发送一个消息，这个消息被称为心跳请求。进程q接收心跳请求后，会立即向进程p发送心跳响应。假设系统的消息耗时上限为δ，如果进程p不能在发送心跳请求后2δ时间内收到进程q发送的心跳响应，就知道进程q已经失败了；否则，根据同步系统的定义，进程p必然会在发送心跳请求后2δ时间内收到进程q发送的心跳响应。

（2）进程协同。一个同步系统可以实现共识抽象，从而实现很多基于共识抽象才能实现的其他抽象。例如，基于共识实现信号量，可以使多个进程协同访问资源。

（3）最差性能分析。根据消息传递耗时上限，可以分析系统的最大延迟等性能情况。

同步系统要求更苛刻的物理环境，例如更可控的运行时环境，以确保事件处理耗时有上限，更可靠的链路以确保消息传递耗时有上限等，因此一般出现在物理条件较好的电路设计领域。而对于环境不可控的系统，尤其是跨节点通信的系统，则一般不能视为同步系统，除非系统可以不需要正确性。

实践经验

从算法复杂度的角度看，对于实现同一个抽象，由于同步系统在一些时间特性上存在已知上限，因此同步算法的性能优于异步算法。

以作者的经验来看，凡是跨节点的通信，即使是小规模的分布式系统，也很难准确地预估消息传递耗时的上限。为了让实际的消息传递耗时不超过预估的消息传递耗时上限，我们往往会将预估的消息传递耗时上限设置得非常大。当出现进程失败时，同步算法需要花很长的时间才能检测出失败的进程，从而导致系统长时间不可用。因此，只有在物理条件较好的系统中，同步算法才能发挥出高性能。而对于故障频发的系统，同步系统对故障的容忍能力是更低的。

部分同步系统

分布式系统在运行正常时，相关时间特性都低于预设的上限，此时的系统是一个同步系统。但是在某些异常出现时（例如消息传递耗时）会超过预设的上限，此时的系统不再是同步系统，而变成了异步系统。比如，当网络因负载太高而丢失消息，或者进程因运行过慢而不能及时从网络缓冲中取出消息而丢失消息时，都将突破消息传递耗时的预设上限，从而变成异步系统。

当异常现象消失后，消息传递耗时又回到预设的上限内，此时系统又变回了同步系统。这种允许在一个自动机实例的生命周期中多次变成异步系统，但最终变回同步系统的系统，被称为部分同步（Partial Synchrony）系统。

下面举例说明部分同步系统的必要性。

假设有一个异地分布的数据库系统需要实现共识，又假设异地之间正常情况下的消息传递耗时不超过0.1秒，但在极端情况下，网络中断最多需要30分钟才能修复。如果把这个系统视为同步系统，且把系统的消息传递耗时上限设置为30分钟，那么算法性能将非常低下，例如确认进程失败需要等待30分钟，从而失去实用价值。如果把系统的消息传递耗时上限设置为0.1秒，那么就很有可能把一个正确进程误判为失败进程，从而导致数据库数据损坏。

如果把这个系统视为异步系统，又因为 FLP不可能结论，即不存在任何确定性算法能够实现共识抽象，此问题变得无解。因此，无论将其视为同步系统还是异步系统，都无法很好地满足需要。

为了解决这问题，Dwork、Lynch和Stockmeyer在1988年发表的论文中提出了部分同步系统。部分同步系统有两种定义。

第一种定义是系统的相关时间特性是有上限的，但上限值一开始是未知的。这就要求所设计的算法对于任何时间特性（例如无论消息传递耗时多长）都是正确的。第二种定义是各项时间特性，例如消息传递耗时，在某个时刻 T 以后是有已知上限的，但 T的值一开始是未知的。这就要求所设计的算法对于任何T都是正确的。

其实，这两种定义是等价的。以消息传递耗时这个时间特性为例。假设第二种定义中的已知的消息传递耗时上限为L，从 T0时刻到T 时刻这段时间内，消息传递耗时会超过L。由于[T0，T]这个时间段的长度是有限的，因此在[T0，T]这个时间段内发生的消息发送和接收的次数也是有限的，那么总是可以测量出最大的那次消息传递耗时为L'。这就回到了第一种定义，即消息传递耗时是有上限的，该上限一开始是未知的，但最终被测量出来是L'。这就证明了两种定义是等价的。

下面以上述异地分布的数据库系统为例，介绍部分同步系统是如何实现

共识的。最初，该系统是一个同步系统，并能够达成共识。当某一时刻，系统变成异步系统后，进程无法达成共识，从而导致数据库服务停止，但不会因为达成错误的共识（即不一致的共识）而导致数据损坏。一旦系统变回同步系统后，进程将达成共识，使服务自动恢复正常。

实际上，很少有系统是绝对的同步系统或异步系统，它们大部分是部分同步系统。

安全性和活性

在分布式系统中，进程是并发执行的，因此一个确定的分布式算法可能对应着多种不确定的执行轨迹，但所有可能的执行轨迹都必须满足自动机抽象定义的所有特性。这些特性可以分为两类，一类叫安全性（Safety），另一类叫活性（Liveness）。

安全性可以理解为正确性，是指在任何情况下执行轨迹都必须满足的特性。精确地说，如果在某个时刻t，执行轨迹违反了该特性，那么在接下来的任何一个时刻t'（t'≥t），无论进程如何执行，对应的执行轨迹都将违反该特性，那么这个特性就属于安全性。通俗地说，安全性就是“坏事不会发生”，一旦发生，就违反特性了。例如，抽象 2-2中的BTH2合理特性，即“被拒绝的task不会被处理”，就属于安全性，因为它要求任何一种可能的执行轨迹都满足这条特性。

只有安全性是不够的，否则算法可以什么都不做，这样坏事也不会发生，但显然这样的算法并不能解决任何问题。因此，除了安全性，还需要另一种约束来确保算法最终能实现所要达到的目标，这种约束被称为活性。

精确地说，在任何一个时刻 t，如果该特性都有希望在当前或后续某个时刻 t'（t'≥t）被满足，那么该特性就属于活性。通俗地说，活性可以理解为“好事终将来临”。如果一个算法有可能导致在某个时刻t之后“好事”不可能发生，那么这个算法就不满足活性。例如，抽象 2-2中的BTH1响应保证特性，即“每个提交的task都会被确认或拒绝”，就属于活性。因为，如

果在某个时刻t，task未被提交，由于命题的前提条件为假，因此整个命题为真，即这个特性已经被满足；如果在某个时刻 t，task已被提交，则该特性希望在后续某个时刻t'（t'≥t），task会被确认或拒绝。因此，该特性属于活性。

设计分布式算法的主要挑战在于既要保证安全性（坏事不会发生），又要保证活性（好事终将来临），同时，一个分布式算法一般也兼具两种特性。如果一个自动机抽象只具有安全性或者只具有活性，那么很有可能这个自动机抽象本身的定义就有问题。

组合模型

一个系统的进程失败有4种，时间假设有3种，那么它们的组合有12种。

我们主要研究以下5种组合模型，如表3-1所示。

表3-1 组合模型的类型

停止型失败（Fail-Stop）：进程的失败为崩溃式失败，故不考虑进程恢复的情况。时间假设是同步系统，因此可以假设系统中消息耗时和时钟偏移率存在已知上限，可以使用定时器。

噪音型失败（Fail-Noisy）：进程的失败为崩溃式失败，故不考虑进程恢复的情况。时间假设是部分同步系统，因此可以假设系统中消息耗时和时钟偏移率最终存在已知上限，可以使用定时器。

静音型失败（Fail-Silent）：进程的失败为崩溃式失败，故不考虑进程恢复的情况。时间假设是异步系统，因此不能假设系统中消息耗时和时钟偏移率存在已知上限，故也无法保证定时器在何时会触发超时事件。

恢复型失败（Fail-Recovery）：进程的失败为恢复后崩溃失败，每个进程都有一个本地日志以解决进程恢复后状态恢复的问题。时间假设既可以是部分同步系统，也可以是异步系统。如果是部分同步系统，则可以假设系统中消息耗时和时钟偏移率最终存在已知上限，可以使用定时器。

任意型失败（Fail-Arbitrary）：进程的失败为拜占庭失败，时间假设是异步系统。这是一种最为复杂的、性能最低的系统。

补充说明

目前受到广泛关注的区块链技术，其本质就是基于任意型失败模型的共识技术。区块链技术是去中心化的技术，组成区块链的各个节点由不同的国家（地区）的组织（个人）拥有和运营。区块链的核心功能就是让这些节点对于“记录”达成一致，即共识。至于记录的是什么，根据业务需求决定，例如一笔交易。

由于区块链承载的业务（例如比特币等）往往与金钱相关，因此各个节点的运营者很有可能受利益驱使而修改自己所运营的节点的算法逻辑，通过作弊而实现牟利。因此，在设计区块链系统时，应该假设进程会出现拜占庭失败。又由于组成区块链的各个节点遍布全球，节点之间通过互联网通信，消息传递耗时无上限，故时间假设为异步系统。所以，区块链就是适用于任意型失败模型的高性能、大容量的共识系统。

值得注意的是，停止型失败、噪音型失败、静音型失败、恢复型失败和任意型失败指的是进程失败和时间假设所组成的组合模型，而3.4节介绍的崩溃式失败、遗漏式失败、恢复后崩溃失败和拜占庭失败仅仅指进程失败的种类，请注意区分。

上述几种模型是从进程失败和时间假设维度出发进行的组合。尽管在任意型失败模型中，拜占庭进程的执行轨迹不确定，但正确的进程仍然执行确定性的算法。然而，在随机化（Randomized）模型中，算法是被设计成随机性的，这与其他组合模型有本质的不同。

随机化是指进程仍然按照预设的算法执行，但算法本身对执行轨迹的选择具有某种不确定性，因此随机化并非拜占庭失败。例如算法定义了一个随机源，进程根据这个随机源的输出选择不同的执行轨迹。在某些时候，随机化比确定性算法要高效得多，甚至是解决问题的唯一途径，例如在异步系统中实现共识抽象。

多数派

在一个分布式系统中，多数派（Quorum）是一组进程的集合，它最重要的特点是：任何两个多数派的交集必然包含一个正确的进程。

在停止型失败、噪音型失败、静音型失败和恢复型失败模型中，多数派是由严格过半数的进程组成的任意集合，即当进程总数为N时，多数派的大小q＞N/2。例如，当N=5时，多数派的大小可以为3、4或5；当N=6时，多数派的大小可以为4、5或6，但不能为3。由于多数派的大小严格过半，因此任意两个多数派的交集必然非空；如果从进程集合中拿走任意一个多数派，那么剩下的进程将无法构成多数派。此时，系统可以容忍的最大进程失败数为f<N/2。例如，当N=5时，f等于2；当N=6时，f也等于2。

在任意型失败模型中，假设一个分布式系统的总进程数为N，其中失败的进程数为f，多数派的大小为q。若不考虑拜占庭失败模型，则显然q+f=N，且f<N/2，因此q＞N/2，即多数派的大小必须严格过半。但由于拜占庭进程的存在，它可以“混入”多数派，那么为了确保多数派内部不受拜占庭进程的影响，必须满足 f<q/2。又因为q+f=N，因此不难得到f<N/3，q＞2N/3。正因为q＞2N/3，所以从N个进程中选择任何两个多数派，共有2q个进程，显然2q-N＞4N/3-N=N/3＞f，这说明任何两个多数派的交集的大小（即重复的进程数）大于f。这也说明重复的进程不可能全部都是失败的进程，其中至少有一个正确的进程。

“任何两个多数派的交集必然包含一个正确的进程”这一特点至关重要。由于正确的进程将严格按照预设的算法执行，它不会两边投票，这意味着，只要能够获得任何一个多数派的支持，则剩下的进程无法构成多数派。在分布式算法的设计中，多数派有着十分广泛的应用。

性能度量

分析分布式算法的性能时，主要关注两个指标：一是完成操作所需要的消息的个数，二是完成操作所需要的通信次数。我们把消息在进程间单向传递1次定义为通信1次，消息在进程间来回传递1次则是通信2次。有时，完成操作所需要的消息的大小也需要被考虑，单位是“字节”。考虑恢复型失败模型时，还需要考虑访问日志的次数。

性能度量一般用符号O标记。把算法执行所需要的性能消耗用输入大小为n的函数表示，即 T（n）。在分布式算法中，n 一般是进程总数。若存在常数 c、k 和函数f（n），使得当n≥c时T（n）≤k·f（n），则称T（n）是O（f（n））阶的。

例如，T（n）=5n 2+8n+9，则存在常数c=10、k=6、f（n）=n 2，使得当n≥10时，T（n）=5n 2+8n+9≤k·f（n）=6n 2，因此T（n）是O（n 2）阶的，该算法的复杂度是O（n 2）。