分布式系统-理解翻译

引言

我想写一篇能够说明目前一些分布式系统，例如亚马逊的Dynamo，谷歌的Big Table和Map Reduce，Apache的Hadoop背后的一些原理的文章

在这篇文章中我会尽力更简单易懂的介绍分布式系统，不关注概念背后的具体细节

在我看来，多数的分布式程序都是为了解决分布式导致的两个问题：

• 信息光速传播
• 独立事务独立失败

换句话而言，分布式程序的核心就是处理距离带来的问题和处理多个问题。这两方面的约束定义了一系列设计规则。希望通过这篇文章，你能更好的理解距离、时间和一致性模型是怎样相互影响的

文章会介绍一些主要的协议和算法，包括一些新的怎么去保证最终一致性的方法，比如CRDTs和CALM理论

1、 基本概念

第一节会介绍分布式系统的一些重要术语和概念。包括可扩展性、实用性、性能、延迟和容错性，及这些实施起来的难度，并引入抽象和模型比如分区和复制的设计规则

2、 一系列的抽象来描述系统的特征

第二节会关注抽象和不可能的结果。首先会介绍尼采的引言，然后会从各种典型的系统模型的假设来介绍分布式系统模型，接着会讨论CAP原理以及FLP不可能结果。最后会介绍CAP原理怎样实施。还会讨论许多一致性的模型

3、 时间和顺序

理解分布式系统的很重要的一点，需要了解时间和顺序。错误理解模型的时间，系统也不能很好的理解。第三节将讨论时间、顺序和时钟及他们的应用

4、 复制：强一致性

第四节将讨论分布式系统中的复制问题，以及介绍两种主要的复制方式。将从最小容错到Paxos来论述保持单拷贝一致性的复制方法

5、 复制：弱一致性

第五节将讨论保持弱一致性的复制。首先介绍分散复制集如何达到最终一致，然后以亚马逊的Dynamo系统作为一个例子，来讨论怎样设计一个保证弱一致性的分布式系统。最后，介绍了CRDTs和CALM理论

1、 分布式系统基本概念

分布式程序就是使用多台计算机像单台计算机一样解决一个问题

分布式系统主要是为了提高两个方面的能力

• 存储能力
• 计算能力

如果有足够的钱和无穷的等待回复时间，那分布式系统就没有存在的必要。所有的计算和存储都能在一个单机上实现

但实际上不会存在无尽的资源。因此，我们必须了解真实存在的花费-收益曲线。在小尺度下，升级硬件资源能够带来更多的收益。但是随着问题尺度的加大，光靠升级一个单节点上的硬件来解决问题的成本花费是及其高的。基于此，分布式系统的存在就很有必要性

在现实情况中，最好的结果是拥有中等程度的硬件，同时维护成本能够通过具有容错性的软件来降低

高端硬件带来计算的主要好处在于，从内存直接访问数据速度会比网络获取快得多，能够降低访问速度。但是当节点之间需要进行大量的通信时，高端硬件的优点会受到限制

image.png

图：不同粒度的集群下，高端硬件（128-core SMP）和低端硬件（4-core SMP）构建童谣的处理核的性能对比

从图中可以发现，随着集群数目的增加高端硬件性能优势越来越不明显

理想情况下，增加一个新的机器会使得系统的性能线性增长。但是这通常是不现实的，因为由于计算机的分离会带来一些难以克服的问题：数据需要被复制到各个节点上，需要协作节点上的计算任务等。为了找到一个高效解决这些问题的办法，同时了解到什么是可能的，正确实施需要的最小代价是什么，什么是不可能的，分布式算法的学习非常重要

本文关注系统的设计，不进行细节优化的探讨

分布式系统目标：

任何问题，当任何维度的尺度变大，这个问题将变得难以解决。

扩展性：

一个系统、网络或进程能够解决随着任务量增长的能力，增大后性能不会受很大的影响

增长关注的三个维度：

• 尺寸可扩展：增加节点使系统线性增长，数据增大不会加大延迟
• 地理可扩展：多数据中心能够被用来减少反馈用户查询命任务的响应时间，同时能够处理因多中心带来的延迟
• 管理可扩展：增加节点的同时，不应该增加系统在管理节点上的开销

在真实的系统中，增长往往同时发生在多个不同的维度上；每个度量标准仅仅表述的是某个方面的增长

一个可扩展性的系统随着尺度的增长，仍然能够满足用户的需求。性能和可用性通常用来衡量系统是否能够满足用户需求。

性能（和延迟）

性能：任务所花费的时间和资源，好性能的系统通常需要满足以下三点：

• 低响应时间
• 高吞吐量（生产力，即工作进程速率）
• 低计算资源利用率

想要优化这些结果，系统需要进行权衡和折中处理。比如：一个系统通过处理大批次的工作可能拥有很高的吞吐量，但是由于个体间的独立工作会导致响应时间变长。

同时，低延迟（短的响应时间）是性能表现指标中最有意思的，它很大程度上是受物理分布的限制，而与经济条件限制无关。你很难通过利用更好的硬件资源来减少分布式系统的延迟

延迟性：事务从发生开始到产生具象的时长

假设一个分布式系统在处理一个高级别的任务：给定一个查询，需要读取系统的各个节点的数据最终计算返回一个值

结果=查询（系统的所有数据）

影响系统延迟性的并不在于数据的多少，而在于系统处理数据到返回结果的速度。具体而言，延迟性应该是系统能够返回一个直观结果所需要花费的时长

在分布式系统中，有一个最小延迟无法避免：信息传播速度限制，硬件操作的时间
最小延迟时长的大小取决于查询语句本身，以及这些信息之间传输的物理距离

可用性（和容错性）

可用性：系统所能处于可用状态的时间比例
Availability=uptime/（uptime+downtime）

分布式系统建立冗余（组件、服务、数据等方面）来允许部分失败的发生，从而提升它的可用性。

可用性从技术角度而言，与系统的容错性相关。例如：当系统的组件数量增多时，系统发生错误的可能性会上升，但一个高可用性的系统应该保证系统的可靠性不会随着组件数量的增多而下降。

举例说明：

image.png

可用性的概念比正常运行时间概念更广。例如一个系统如果遭遇断电、或者服务发生中断，这个时候与系统的容错性无关，但是这些情况仍然会影响系统的可用性。

但通常而言，系统的容错性越强，可用性越高。提高系统的容错性是我们最需要关注的

容错性：系统在错误发生后有明确的处理方式

系统定义发生的错误，并定义相应的处理方法。系统的容错性设计是考虑已想到的故障，没有考虑到的故障，系统是没法容错的

分布式系统受两个物理因素的限制：

• 节点数量（当需要更大的存储、计算能力时，节点数会增多）
• 节点间的距离（信息传播）

限制：

• 节点增加，系统发生失败的可能性增加（降低可用性，增加管理的花费）
• 节点增加，独立节点之间的通信增多（随着尺度增大降低性能）
• 地理距离增加，最小延迟时长增加（降低特定的操作的性能）

性能和可用性都由系统的保证确定的。例如：在SLA中，系统保证如果写数据，那么多长时间能从其它地方访问它？如果让系统进行一个运算，多长时间能返回结果？当组件发生失败时，系统会遭受什么样的影响？

这里有一个不明确但是需要实施的标准：可理解性。也就是这些保证需要能够被理解和明白的。

分布式系统中的抽象和模型

• 抽象：将现实层面的事务抽象出来，便于更好的管理和处理
• 模型：精确描述分布式系统中的关键属性

本文主要讨论下面三种类型的模型：

• 系统模型（异步/同步）
• 故障模型（crash-fail，分区，Byzantine）
• 一致性模型（强一致性、最终一致性）

好的抽象能使系统的运行更方便理解，同时能捕获与特定目标相关的因素

我们希望多节点上运行的分布式系统能像单系统一样运作。但是通常最熟悉的模型需要花费的代价是很大的，比如在一个分布式系统上实施内存共享

一个实施若保证的分布式系统通常能获得更自由以及更好的操作性能，但同时它会难以推理验证。相比于多节点，我们往往能够很好的理解单系统的工作原理

当对系统内部的了解更深时，系统的性能将会越高。举个例子，在列存储技术中，典型的查询语句，用户能够推断键值对所在的位置从而做出影响性能的决定。系统隐藏更多的技术细节，用户更容易理解，但性能会更低。

分布式系统中可能出现的各种问题，使得它像单系统一样运行变得困难。当发生网络延迟和网络分区时，系统将要面临是保证可用性还是保证系统的安全性的取舍

CAP****理论会讨论分布式系统中这些问题的取舍关系

一个理想的分布式系统需要满足编程人员的需求（明确的语义）和业务需求（可用性/一致性/延迟性）

分布式系统的技术：分区和复制

数据集在多节点中的分配方式非常重要。对于系统的任何计算，我们需要定位数据然后再对其进行操作

对数据集的操作设计到两个基本的技术：

• 分区：为了进行并行处理，数据将被分割到多个节点中
• 复制：为了减少客户端和服务器之间的距离，同时为了提高容错性，数据会被备份或缓存到不同的节点中

下图阐述了两者之间的差异：分区数据（A和B）被划分成两个独立的数据集，于此同时复制数据（C）被拷贝到不同的节点上

image.png

许多分布式的算法都用到了分区和复制。不同的限制条件取决于你设计的目的

分区

将数据集分割成相互独立的小数据集，减少因数据集增长而带来对单个节点的压力

• 提高性能：限制分区中数据量的大小，降低数据压力
• 提高可用性：数据之间相互独立，不同分区之间失败互不影响，允许失败节点的存在

分区需要考虑：

• 基于将要进行的主要访问模式如何定义分区
• 怎样处理独立分区带来的局限性（跨分区低效率访问）

复制

将同样的数据备份到多个机器当中，这样能够使得更多的服务器参与到计算当中

复制是解决latency的主要方法之一

• 提高性能：生成适合新备份数据的二外计算能力和带宽，提高系统性能
• 提高可用性：备份数据，允许更多的节点出错，提高容错性

复制能够让我们实现系统的可扩展性和容错性。

• 避免单节点故障和瓶颈
• 多系统上复制计算能够加快计算速度
• 复制数据到本地缓存中能够减少在多个机器上进行运算的延迟时长，同时提高吞吐量

同时，由于复制集分布在各个相互独立的节点上，系统需要对多个机器上的数据进行同步更新处理，复制也会导致一系列问题的产生。我们需要使用一致性模型来保证复制的一致性

选择一致性模型的关键点在于：一个好的一致性模型能够提供清楚的语义信息给程序员，同时能够满足业务目标，比如高的可用性和强一致性

2、 分布式系统的抽象

这一节将关注一些不可能的结果（CAP和FLP），并且会继续讨论性能

通常编程会在一些抽象层次上工作，比如API接口，7个层的计算机网络的OSI模型（开放系统互连模型，将通信系统分为7层：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层）

分布式编程在很大程度上都在解决由于分布带来的一系列问题。怎样让分布式系统工作起来像单机一样有一定的困难。我们希望找到一个能够平衡“可理解性”和“高效性”的好的抽象

通常我们说X是一个比Y更好的抽象，代表我们认为X在Y的基础上不会给人带来额外的信息，X只是比Y更好理解而已

正如尼采所言：
我们将不同事物的共性抽象成为一个概念。例如每个叶子都有。。。。

事实上，在分布式系统中，每一个节点、每一种情况都是不一样的，抽象其实在根本上是不存在的。但是一个抽象能够让一些问题能够被陈述出来，更利于理解和处理，并且由于关注的是问题的本质，所以解决方案往往应用会更广泛

例如不可能的结果就是一种好的抽象：由于对于问题采用最简单的公式来描述，并且证明不可能存在一组约束或假设能解决这个问题。

系统模型

分布式系统最重要的一个属性就是：分布，程序在分布式系统上需要满足：

• 在独立的节点上同时运行
• 网络连接可能会带来不确定性和丢失信息
• 不共享内存和时钟

具体而言：

• 每个节点会同时执行程序
• 信息局部存在：局部节点之间相互访问快，但是关于全局的信息可能会过期
• 节点之间的失败和恢复能够相互独立
• 信息可能会出现延迟或丢失（网络失败与节点失败难以辨别）
• 节点之间的时钟不同步（局部时间戳和全局时间顺序不吻合，并且难以被观察到）

系统模型

分布式系统实施过程中的一系列关于环境与设置的假设
这些假设包括：

• 节点容量及怎样算失败
• 通信交互操作如何进行及怎样算失败
• 总体系统的属性，如：时间和顺序
  弱假设会使得系统具有更高的鲁棒性，强假设会使系统具有更高的理解性和可推理性

分布式系统中的节点

节点用来计算和存储，它拥有：

• 执行程序的能力
• 存储大量数据的能力（数据可能会丢失，但也可以恢复）
• 时钟（可能不是很精确）

节点执行时满足：当消息被接收到时，本地状态与消息决定了本地运算、本地运算后的状态以及消息发送的唯一性

有许多故障模型会描述能够容许节点发生什么样类型的失败。实际上，大部分系统都是一个
-崩溃恢复失效模型：节点只能由于崩溃而失败，并且在接下来的时间节点能够被恢复
另一种故障模型：

• 拜占庭容错：节点可以能以任意方式发生故障，其容错过于复杂昂贵，现实中很少处理。

系统模型中的通信链路

通信链路使得各个分布的节点之间能相互连接，并传输信息。

当节点仍在操作时，网络发生失败会导致网络分区，信息将会丢失或者发生延迟，直到网络修复。但此时用户仍然能够访问节点。所以网络失败必须要和节点失败区分开来。下同阐明了两种情况：

image.png

时间/顺序假设

分布式中，节点之间存在距离，信息传递一定存在通信时间，并且每个节点接收到信息的时刻不一致

两种关于时间假设选择的模型：

• 同步系统模型
  程序锁步执行，消息传播延迟有明确的上限，每一步都有精确的时钟

• 异步系统模型
  没有时间假设，每个进程执行在相互独立的比率下，消息传播没有延迟上限，时钟不存在

同步系统有许多时间与顺序的限制，默认节点有相同的体验，消息传播延迟在一定的范围内，程序执行严格按照锁步。但在异步系统中，时间的依赖不存在

因此对于同步系统来说，解决问题更容易一些，因为你能通过对于时间和顺序的假设，来推测和排除失败场景发生在哪些地方。

但通常而言，同步系统模型能更好解释和理解，但不现实

一致性问题

接下来讨论两个系统中的属性差异：

• 失败模型中是否包含网络分区
• 同步异步时间假设
  会对系统设计造成什么样的影响，以及会带来的两种结果（FLP与CAP）

首先解释什么是一致性问题：

• 一致性（Agreement]）：每个正确的进程对某个值达成共识
• 完整性（Integrity）：每个正确的进程最多决定一个值，一旦决定了某个值，那么这个值一定被其它进程接受
• 终止性（Termination）：所有进程最终达成一致同意某个值
• 合法性（Validity）：如果所有正确的节点进程提出相同的值V，那么所有正确的节点进程达成一致，承认值V

共识问题是许多商业分布式系统的核心，解决共识问题可以解决几个相关的、更高级的问题，如原子广播和原子提交（？）

两个不可能结果

• FLP定理
  分布式算法需要关注
• CAP定理
  实践者需要关注（不关心算法，关心选择什么样的系统设计）

FLP

FLP定理：在异步通信场景，即使只有一个进程失败了，没有任何算法能保证非失败进程能够达到一致性（在假设网络可靠、节点只会因崩溃而失效的最小化异步模型系统中，仍然不存在一个可以解决一致性问题的确定性算法。FLP只是证明了异步通信的最坏情况，实际上根据FLP定理，异步网络中是无法完全同时保证 safety 和 liveness 的一致性算法，但如果我们 safety 或 liveness 要求，这个算法进入无法表决通过的无限死循环的概率是非常低的。）

因为异步系统中的消息传播具有延迟性，那么如果存在这样一个算法，这个算法会在任何的时间内保持着不确定信，无法保证达成一致性，与假设矛盾。因此通常异步系统模型需要进行折中处理：放弃一定的安全性当消息传播延迟上限不能确定时

CAP

CAP定理：一个分布式系统不可能同时满足consistency、availability、partition tolerance这三个基本需求，最多同时满足两个

• consistency一致性：所有节点同一时刻看到相同数据
• availability可用性：节点失败不阻止其他正在运行的节点的工作
• partition tolerance分区容错：即使出现信息丢失或网络、节点失败，系统也能继续运行（通过复制）
  
  image.png

这三种性质进行俩俩组合，得到下面三种情况

image.png

• CA：完全严格的仲裁协议，例如2PC（两阶段提交协议，第一阶段投票，第二阶段事物提交）
• CP：不完全（多数）仲裁协议，例如Paxos、Raft
• AP：使用冲突解决的协议，例如Dynamo、Gossip

CA和CP系统设计遵循的都是强一致性理论。不同的是CA系统不能容忍节点发生故障。CP系统能够容忍2f+1个节点中有f个节点发生失败。原因如下：

• CA系统无法辨别是网络故障还是节点故障，因此一旦发生失败，系统为了避免带来数据分歧，会立马阻止写操作（不能判别，所以安全的办法就是stop）
• CP系统通过强制性分开两侧分区的不对称行为来阻止发生分歧。仅仅保证主要的分区工作，并且要求最少的分区是不可用的。最终能够使得主要的分区能够运行工作，保证一定程度上的可用性，确保单拷贝一致性

在复制一节会进行更详细的介绍。

重要的一点是，CP系统中将网络分区考虑到了它的故障模型中，并且用算法识别主要分区和小分区。CA系统不关注分区

当我们假设分区一定发生时，那么在可用性和一致性中怎样进行一个选择呢

image.png

早期的分布式系统没有考虑分区容错（CA设计）。但是分区容错是一个很重要的性质，因为一旦系统规模很大，网络分区是不可避免的

CAP理论阐述了强一致性和高可用性之间的关系

强一致性会导致当存在分区时系统不可用。因为当两个复制集之间不能相互通信时，无法将写操作告诉对方，因此会带来分歧

那么该怎样避免这种情况发生呢。一致性和可用性之间应该怎样进行折中处理？这个时候就需要将强一致性进行弱化，转成弱一致性，来使得我们再保证弱一致性的情况下，也能保证系统的可用性

如果不想降低可用性（在网络分区的情况下），就应该找到另一个一致性模型而不是继续锁定强一致性

例如：当数据复制到不同的机器上，并且节点间的联系发生故障时，需要协调两方的数据。这个存在一定的技术挑战和商业风险，当两者都能解决时，此时系统还是高可用性的

CAP中的一致性指的是强一致性，但一致性并不代表强一致性，一致性没有单一、明确的属性

image.png

一致性模型（强一致性和其它一致性）

一致性模型能被分为两类：强一致性模型和弱一致性模型

• 强一致性模型（数据维持一份）
  -- 线性一致
  -- 顺序一致
• 弱一致性模型
  -- 客户为中心的一致性模型
  -- 因果一致性：可用最强模型
  -- 最终一致性模型

强一致性模型保证数据更新的表现和顺序像无复制系统一样，弱一致性模型则不保证

强一致性模型

两种有轻微差别的形式：

• 线性一致性：所有操作都是有序进行的，按照全局真实时间操作顺序
• 顺序一致性：所有操作也是有序进行的，任一单独节点操作顺序与其它节点一致

不同的是，线性一致性模型要求操作按照全局真实时间顺序来，而顺序一致性模型只要节点操作被观察到的顺序是一致的就行

强一致性模型能够允许你的单服务程序一直到分布式节点集群上并且不会发生任何错误

相比于强一致性模型，其它的一致性模型都会存在一些异常，但是它们允许异常发生，或者写了处理异常的代码

客户为中心的一致性模型

客户为中心的一致性模型是一种以某种方式涉及客户或会话概念的模型。举例来说，一个以客户为中心的一致性模型可以保证单个用户看到的数据版本永远是最新的版本。通常通过建立缓存到客户端库，使得如果一个用户移动到一个包含了老版本数据的复制的节点时，通过客户端库能够返回数据的缓存值而不是复制集的老版本。

如果复制节点没有包含最新的数据版本，客户仍然会看到数据的老版本，但是客户永远不会看到旧版本的值重现的异常情况。（？？？？？不是可以保证最新版本？）

最终一致性

最终一致性模型中，当停止改变数值的一段不确定的时间后，所有的复制集将会最终保持一致。这表明，在这段时间之前，复制集在某种情形下是不一致的。由于这个条件非常容易满足（只用保证liveness），因此没有补充信息它是没有用的。经过一定的时间，各个复制集最终保持一致

说一个事情最终能够保证一致就像是说“人总有一死”。这是一个很弱的约束条件。这里至少需要加一些比较明确的特征来形容它：

• have a strict lower bound
  首先，“最终保持一致”的最终到底是多久？这个需要有一个明确严格的上限，或者至少要知道通常系统达到一致结果时所需要的时间
• replicas agree on a value
  其次，复制集最终是如何到达一致的？一个总是返回固定值“42”的系统能保证最终一致性：所有的复制集都为同一值。但这个系统仅仅是范围一个固定的数值，并非收敛于同一个有用值。这不是我们想要的。我们希望能有一个使得复制集最终保持一致的好方法，例如，使用最大时间限的值作为最终值。这里系统需要达到一致的目标，而不是固定的返回某一个值

所以，当提到”最终一致“时，它实际上想表达的是更精确的术语，类似于想表达”最后的写操作为最终值，与此同时，读操作读取最新的数据“这样的一致性。这里我们最需要关注的是”如何到达最终一致“中的”如何“，因为一个坏的方法可能会使得写操作的数据丢失，例如：如果某个节点上的时钟是不正确的，但是它的时间戳却仍然被使用，这个时候可能会造成写失误。

关于这两点，在复制方法章节会进行更加详细地介绍。

3、 时间和顺序

分布式系统的目标是能够让多台机器像单机一样处理问题。在这里面需要关注的核心是顺序。任何系统在同一时刻都只能做一件事情，这样就会产生一系列有顺序的操作。

传统的模型是：单一程序利用一个CPU运行在一个进程和一个内存空间中。而分布式模型通常处理多个CPU和多个程序以及程序之间的内存通常需要共享。这个时候即使程序运行在多台机器之间，我们希望它也能像单机一样，同样顺序执行程序

分布式系统的好处在于一个定义好的顺序是通用的。你不需要担心它是如何操作的，无论你进行什么样的操作，你都可以使用这个系统。

分布式系统程序运行在多个节点之间。你需要分配一个全局顺序，需要精确的时钟与一些通信方式。你可以对每一个操作贴上一个时间戳，来保证它们全局有序，或者也可以采用某种通信方式（例如计数器），来确保它们全局有序

操作顺序包括：全局有序、偏序

全局有序和偏序

• 全局有序：数据集中每一个元素顺序的一种二进制关系
• 偏序：分布式系统中最自然的状态就是偏序。独立节点与网络不能保证相关顺序，但在每个节点中，自身有本地顺序

两个明确的元素之间能够进行相互大小比较，但是在一个分区有序数据集中，不同区的元素之间是没发进行比较的，因为它们只在自己的分区中有序

无论是全局有序还是偏序，都遵从传递性（transitive）和反对称性（antisymmetric）。下面的描述表达了顺序具有的性质：

image.png

偏序（分区有序？可以这样理解吗）的性质比全局顺序的性质要弱，因为有些元素他们是没法进行比较的

Git分支就是偏序的一个实例。我们都知道git的版本控制能够让你从一个单一的基本分支中创造出多个分支。例如，从主分支中进行后续创建。每一个分支代表原始代码从最初到后面的变化历程：

image.png

在一个有单一节点构成的系统中，全局有序是必要的，这使得程序的执行结果具有可预测性。这样的顺序也能在分布式系统中维持，但昂贵的通信成本以及时间同步的困难和脆弱性使得其代价十分昂贵。

时间

没有时间就没有顺序。时间能让我们确定操作的顺序，同时也能被更好的理解

从某种角度而言，时间像计数器一样，能够让大多数的运算有自己专用的时间传感器。对于同步系统而言，我们能有一个不用互相通信就存在的精确的计数器

时间戳是表达事物所处状态的一个简单的速记值。如果一件事发生在某一时刻，那么它受到发生在它之前的事件的影响。这个想法可以概括为一个因果时钟，它明确地跟踪原因（依赖性），而不是简单地假设时间戳之前的所有内容都是相关的。当然，通常的假设是，我们只应该担心特定系统的状态，而不是整个世界。

假设时间在任何地方都以相同的速度进行——这是一个很大的假设，我稍后将回到这个假设——时间和时间戳在程序中使用时有几个有用的解释。这三种解释是：

• 顺序
• 持续时间
• 表现形式

顺序：一系列事件发生的顺序

• 我们能通过事件发生的时间戳来确定事件发生的顺序
• 我们能够利用时间戳来定义一系列操作的顺序，或者传递信息（例如，如果一个操作发生故障，则延迟它）
• 通过时间戳能够确定一件事是否发生在另一件事前

表现形式：时间是一个可以进行全局比较的值。时间的表现形式可以有多种，比如日期、星期几等等

持续时间：通过时间段长短可以来判断系统是发生分区还是发生了高延迟

就其性质而言，分布式系统的组件的行为不可预测。它们不保证任何特定的顺序、速率或没有延迟。每个节点都有一些本地顺序——因为执行是（大致）连续的——但是这些本地顺序彼此独立。（节点内的order和节点之间的order相互独立）

强制（或假定）顺序是减少可能执行和发生的空间的一种方法。当事情可以以任何顺序发生时，有太多的排列需要考虑，因而很难对事情进行推理。

各个分布式节点中时间相同吗？

依据个人经验，我们都有一个直观的时间概念。但直观的时间概念使我们更容易描绘出总顺序而不是部分顺序。更容易想象事情发生的顺序，一个接一个，而不是同时发生。对一个消息顺序进行推理要比对以不同顺序和不同延迟到达的消息进行推理容易得多。（通常一串连续发生的事件比同时发生要更容易理解）

然而，在实施分布式系统时，我们希望避免对时间和顺序做出强有力的假设，因为假设越强，系统就越容易受到“时间传感器”或时钟的问题的影响。此外，执行命令也会带来成本。我们越能容忍时间上的不确定性，就越能利用分布式计算。（分布式系统中关于“时间传感器”的定义和假设相较而言没那么刻板。对时间的不确定性容忍度约稿，对于系统的分布式计算更有利）

对于分布式节点中的时间是否同步，使用不同的时钟假设是不同的：

• 全局时钟：相同 （同步系统模型）
• 本地时钟：不同，但是本地有序 （部分同步系统模型）
• 不使用时钟：不同 （异步系统模型，用逻辑时钟来确定顺序）

全局时钟

全局时钟：有一个全局精确的时钟，并且每个节点都能接触到

image.png

全局时钟的存在使在任何节点上的操作都按照一定的顺序执行，即便这些节点之间不发生通信交互

但在现实世界中，时钟同步只能存在于能容忍一定程度上的不精确的系统中。因为由于空间分布的原因而存在的延迟。

假设时钟在分布式节点中完美同步的话，说明时间都是从同一个值开始计时，并且永远不会不一样。这样一来的话使用时间戳的话就能完美的保证全局顺序。但是通常会有异常现象存在，但针对这些异常，也会有相应的处理方案

然而，现实中有一些系统使用的是全局时钟假设。比如Facebook的Cassandra系统。它使用时间戳来解决写的冲突，最新的版本胜出。另一个例子Google的Spanner，它的时钟也是同步的，但同时考虑了最坏情况下的时钟漂移

本地时钟

更合理的情况是，每一个机器上有自己的时钟，但是不存在全局时钟。即你能通过本地时间戳来确定本地事件发生顺序，但是不能对不同机器间的时间戳进行比较

image.png

be
本地时钟的假设最符合真实世界的情况。它表明时间在每一个独立的分区上能够有序，但是在所有的系统中仅仅靠时钟来并不能保证事件的顺序

无时钟

这里存在一个逻辑时间的概念。不在使用时钟来追寻时间发生的因果顺序，而是通过另一种其它的方式-计数器和通信

通过这种方式，我们能对不同机器上发生的事件的顺序进行比较，但是没法使用关于时间间隔以及超时设置的变量了（即不存在时间传感器了）。这从某种角度而言也是一种局部有序的情况：时间在单系统中能够使用计数器并且不用进行通信来保证事件顺序，但是在多系统之间就需要进行信息交换

矢量钟就是一种不利用真正的时间来进行时间顺序因果追寻的方式。后面会进行详细介绍

分布式系统中时间的作用

时间的作用：

• 能够定义系统中事件的顺序（不需要通信）
• 能够定义算法的边界条件（故障检测器）

在分布式系统中，确定事件发生的顺序是很重要的，因为许多操作是需要顺序进行的

• 系统的正确性取决于正确的时间顺序
• 当资源发生竞争时，顺序能够作为评判标准

一个全局时钟能够允许两个机器上的操作有序进行并且不需要通信。但一旦没有全局时钟，我们就需要进行通信来确定不同机器上操作的顺序

时间也可以用来定义算法的边界条件，比如，判定系统到底是发生了“高延迟”还是出现了“服务或者网络的宕机”。用来做这个判断的算法被称为是故障检测器，后面会进行讨论

矢量时钟

前面我们讨论了分布式系统中不同的时间假设。如果我们没法获得精确的时钟同步的话，那么如何保证分布式系统中事件有序呢？

Lamport clocks和矢量时钟能够代替物理时钟来进行保证系统有序。通过计数器+通信来决定事件顺序

Lamport clock

Lamport clock很简单，每一个进程都有一个计数器，服从下面的规则：

• 一旦一个进程开始工作，计数器递增
• 任何进程发送的消息中，包含计数器的值
• 当一个消息被接收时，更新计数器的值为max（本地，接收）+1

用代码表示的话：

image.png

Lamport clock允许使用计数器来比较事件发生的顺序，比如如果 timestamp(a) < timestamp(b)：

• a可能在b之前发生
• a可能和b同时发生

这和时钟的一致性一样，如果一件事发生在另一件事之前，那么它的逻辑时钟也发生在这件事之前。如果事件a和事件b都是从同一个历史中演化而来的，那么如果a<b，a一定发生在b之前

使用Lamport时钟也有一个缺点，因为它只包含了一个时间线的计数信息，那么同步发生的事情在这个时钟下仍然可比，即表现出有序性，但本质上，他们是同步的，不应该表现出有序性

vector clock矢量时钟

矢量时钟是Lamport clock的一个衍生，它包含了一个含有N个节点计数器值的计数器列表 [t1,t2,...]，每一个节点递增他们自己的逻辑时钟（计数器的值），规则如下：

• 一旦一个进程开始工作，矢量钟中的关于该进程节点上的计数器值递增
• 任何进程发送的消息中，包含矢量计数器列表
• 当一个消息被接收时：
  -- 更新矢量
  -- 递增矢量中代表当前节点的逻辑时钟的计数器的值

代码表示如下：

image.png

下图也能表示矢量钟：

image.png

总结：

• Lamport clock每个节点上维护一个计数器值，每次通信对这个值进行更新
• vector clock每个节点上维护一个计数器列表，每次通信对这个列表进行更新

故障检测器

前面说过，等待花费的时长能够用来作为一个判断系统到底是发生了分区故障，还是高延迟的一种线索。在这里，我们不需要假设有一个精确的全局时钟，仅仅有一个可信赖的本地时钟就足够了

一个节点上运行一个程序，如果运行的信息延迟的时间到达一定的时长的话，我们就认为这个节点发生了故障。但是这个时长改如何定义呢？

故障检测器是一种抽象的方法：心跳信息+定时器

进程间交换心跳信息，如果一个进程在超时前没有收到响应信息，那么这个进程会怀疑其它进程

一个基于超时而言的故障检测器通常要么会过度检测（轻易断言一个节点发生故障），要么检测会过于保守（花费很长的等待时间来判断故障）。那么一个如何使用故障检测器使得它发挥出好的作用呢？

有人用两个属性（完整性、精确性）将故障检测器进行了描述：

强完整性：每个故障的进程都会被任何正确的进程怀疑
弱完整性：每个故障的进程会被一部分正确的进程怀疑
强精确性：没有正确的进程会被怀疑
弱精确性：一些正确的进程也会被怀疑

完整性比精确性更容易实现。并且一个弱完整性的故障检测器能够转换成强完整性的故障检测器（通过广播被怀疑的进程的消息？？？）

通常对一个没有发生故障的进程进行错误的怀疑是无法避免的，因为你不知道消息延迟的上限是多少。但是在同步系统中，这个消息延迟的上限是固定的，因此在同步系统中使用故障检测器是非常精确的。

研究表明即使是一个弱故障检测器（最终故障检测器），也能用来解决一致性问题。下图阐述了系统模型和问题可解性之间的关系：

image.png

（同步系统中靠同步时钟来解决问题√，异步系统中什么是可信赖广播？什么是一致性原子广播？什么是无阻塞原子广播？）

从上图可以看到，异步系统中，不使用故障检测器是无法对明确的问题进行解决的。因为，如果没有故障检测器，你无法得知一个远方的节点是否发生故障，或是因为高延迟的存在。这个判断对于单拷贝一致性的系统来说非常重要：故障节点会被忽略，因为它们不会带来分歧，但是分区节点不能被忽略，因为可能会造成数据分歧

怎样实施一个故障检测器呢？事实上，不存在一个很简单的故障检测器，因为判断一个节点是否发生故障时很难的

依赖超时设置的值来判断是否发生故障。Cassandra它使用的是一个精确的故障检测器，它给出的故障判断是一个猜测值（0-1间，概率值）而不是一个二进制的数（0、1），这样一来，系统应用能够根据自己的定义来判断节点是否发生故障，进行一个无误检测和超前检测的权衡

时间、顺序和性能

如果你在设计一个分布式系统，你肯定拥有不止一台的计算机。那么从直观的角度来看，顺序是分区有序的而并非全局有序。你能够通过通信的方式，使得分区有序转变成全局有序，但是这通常还需要等待以及受到任意同一时刻能够有多少节点进行同时工作的限制

就最简单的保持一个简单的整数计数器在分布节点上同步都很有挑战性

事实上，算法通常不在乎时间，而是在乎顺序：

• 事件发生的原因顺序
• 故障检测器
• 一致快照

全局一致是可以实现的，但是很昂贵，它要求所有的处理在相同的速度条件下。一个最简单的方法是：投票，选出一个经过了所有操作的节点出来

时间/顺序/同步真的有必要吗？这取决于你的案例。比如在一些用户案例中，我们想要每一次的操作都能让系统从一个一致性的转态转到另一个一致性的状态。举个例子：在数据库中，我们想要从数据库中找到能代表所有可用的信息，同时我们想避免处理系统返回不一致的结果所带来的问题。

但是在其他的一些例子中，我们可能不需要时间/顺序/同步。比如，我们想进行一个很长的计算操作，只要能保证最后的结果是正确的，我们并不关心这些运算是否同步发生

同步性通常是用来做为操作的限制工具的，仅仅当我们的结果只是收到一部分数据集的影响的时候才需要。顺序什么时候保证系统的可用性-这涉及到我们之后讨论的CALM理论

还有另一些例子中，我们能够接受那些尽力而为的答案作为我们系统的最后结果。这会涉及到一致性问题

• 强一致性：保证准确性但付出可用性低的代价
• 弱一致性：保证系统可用性，但要接收“best effort”答案