分布式系统：与时间有关的故事

世界就是一个分布式系统。

时序问题在分布式系统里面是个大问题。一直以来，时序问题在很多场合有点过于理论化，所以，大部分工程领域对这个问题关心得并不多（或者说被基础组件默默地解决了），鲜有文章给出框架性的指引，我想尝试用一篇文章整理分布式系统关于时间、时钟、时序相关的经典问题和解决方法（理论、设计等），最后简单谈一谈与时序相关的一致性问题。

时序问题：从生活到分布式系统

时间是生活中一个很重要的概念，我们用时间确定事件的先后关系，进一步使得许多事情得以确定。举个例子，某天，我想请我的朋友帮忙代取快件，首先要告诉朋友，朋友同意后，才有取快件这一件事发生。例子中，“告诉朋友”是一个事件，“取快件”又是另一个事件。上面事件必有严格的先后顺序。为了确定先后顺序，除了根据逻辑推理，有时候我们还会通过比较事件发生的时间。不可能出现朋友先帮我取了快件，我再向朋友发出请求这种诡异的顺序，同时事件之间也是有因果关系的。

分布式系统也是类似的。很多时候，我们希望根据事件的先后关系确定系统表现出来的行为，使得设计的分布式系统是符合预期的。在日常生活潜移默化的影响下，我们也希望用时间解决这一问题。遗憾的是，利用时钟确定分布式系统中的事件顺序并不容易。

经典问题：提交一笔电商交易

为了方便水平扩容，以支撑持续增长的业务量，一个大型、成熟的的电商系统很多时候会采用微服务系统架构。微服务设计下，原本为单体的系统，会根据功能、开发人员等，被拆分为一个个独立的微服务（Microservices），微服务之间使用 RPC（远程过程调用，Remote Procedure Call）通信，各司其职为用户提供完整的电商交易平台。假设我们的电商平台包括了以下几个服务：

• 业务服务：面向用户，提供操作接口（如：订单提交、购物车、商品搜索等）。
• 支付服务：接收其他服务发起的支付请求，为用户订单完成一整套支付过程（三方支付、完成银行支付等）。
• 订单服务：接收、跟踪、管理用户订单。
• 库存服务：商品的库存管理。

你看这不，一个用户来下单了，向我们的系统发起了一笔交易。此时电商系统发生的事情可能是这样的：

• 业务服务的 API 被用户终端调用（$A$ 事件）。
• 业务服务发起订单创建（$B $事件）。订单服务收到业务服务发起订单创建请求（$C$ 事件）。
• 订单服务向库存服务发起调用，要求扣减商品库存。
• 库存服务收到扣减库存请求，扣减了商品库存。
• 订单服务创建一笔订单（$ D $事件）。
• …

对于每一笔订单，用日志追踪提交过程是重要的，可以便于了解系统的工作状况。我们希望日志顺序能够和事件发生的顺序一致，忠实反映系统的状态变更。进一步，如果我们期望在某些错误发生时，利用操作日志回滚整个系统的状态，确定事件的顺序就更加重要了。

问题抽象

上面的电商系统本质是分布式系统。每个系统都可以看作一个独立的进程（Process）。进程间相互通信，一定会通过网络相互传递消息（Message）。一个进程可以发送消息、接收消息和完成自己的工作职责。由此，上面系统的事件可以归为三类：发送、接收、自发。RPC调用方发生消息发送事件（如事件B），被调用方会发生接收事件（如事件C）。还有另外一类事件是自发事件，由进程自身运行产生（如事件 D）。我们需要一种方法，准确刻画事件之间先后顺序，从而得到事件的全局排列。抽象出这样的模型后，某个分布式系统时序图可能是这样的：

happened-before 关系

对于两个不同的事件 $A$、$B$ ，如果 $A$ 发生在 $B$ 之前，引入一个记号”$\rightarrow$”去描述这样的先后关系，记作为 $A \rightarrow B$，意为 $A \text{ happened before } B$ 。对于这种关系，以下事实是显然的：

• 进程内：如果事件 $A$ 和事件 $B$ 都发生在同一个进程内，而且事件 $A$ 先于事件 $B$ 发生，则有 $A \rightarrow B$。
• 进程间：显然任何一条消息都应是应该是“先发送，后接收”的，如果事件 $A$ 是一个进程引起的消息发送事件，事件 $B$ 是对应进程对该消息的接收事件，有 $A \rightarrow B$。
• 传递性：如果 $A \rightarrow B$ 且 $B \rightarrow C$，显然 $A \rightarrow C$。

如果不同事件 $A$、$B$ 无法比较先后关系，我们表示为 $A \nrightarrow B$ 且 $B \nrightarrow A$，我们说事件是并发的（Concurrent）。

特殊的，讨论任意事件与它本身的顺序关系是没有任何意义的。对于任意事件$A$，我们规定 $A \nrightarrow A$。

根据上面的图，举几个例子：

• $B_3 \rightarrow B_5$ （进程内）
• $A_1 \rightarrow B_2$ （进程间）
• $A_1 \rightarrow C_3$ （因为$A_1 \rightarrow B_2$ ，$B_2 \rightarrow B_3$，$B_3 \rightarrow B_4$，$B_4 \rightarrow C_3$，根据传递性）

happened-before 关系定义了分布式系统关于事件的，最小粒度时序关系。

偏序和全序

一个分布式系统一段时间内发生的所有事件，可以组成一个事件集合 $S$。可以根据事件的 happened-before 关系对集合内事件进行排序，得出类似 $A \rightarrow B \rightarrow C \rightarrow D$ 的次序关系，这种一般称作事件的序（Ordering）。

上面我们提到：并不是随意两个事件都能比较先后关系。我们假设事件集合 $S$ 中有事件$A$、$B$、$C$和$D$，且：

• $A \rightarrow B$
• $B \rightarrow C$
• $B \rightarrow D$

我们可以得到事件的两个序：

• $A \rightarrow B \rightarrow C$
• $A \rightarrow B \rightarrow D$

集合中存在两个事件 $C$ 和 $D$ 无法确定先后顺序，于是只能定出事件的部分顺序，定出的这种顺序称作偏序（Partial Ordering）。

如果我们上面的情况下，确定了$C \rightarrow D$，就可以得到 $A \rightarrow B \rightarrow C \rightarrow D$ ，集合中所有事件的顺序都确定了，这种情况给出了事件的全序（Totally Ordering）。

我们来看上面的时序图，很显然我们只能确定偏序关系：

• $A_1 \rightarrow B_2 \rightarrow B_3 \rightarrow B_4 \rightarrow C_3 \rightarrow C_4$
• $B_1 \rightarrow B_2 \rightarrow B_3 \rightarrow B_4 \rightarrow C_3 \rightarrow C_4$
• $C_1 \rightarrow C_2 \rightarrow B_7$
• …

显然我们没法确定：

• $A_1$、$B_1$、$C_1$
• $C_1$、$B_3$
• …

因果关系

事件的 happened-before 并不仅仅是为了追踪事件的序，里面还隐含着因果性。比如上面提交电商交易订单的例子中，终端调用引起业务服务发起订单创建，订单创建请求引发了库存扣减，进而又引发分布式系统中一系列的状态改变。一个事件引起了另一个事件的发生，事件间存在因果关系（Causal relationship），捕捉这种因果关系对于维持分布式系统的一致性相当重要（毕竟我们不希望发生“订单创建了，但库存没扣减”或者“库存扣减了，订单没创建”等等奇奇怪怪的情况）。至于这个系统的容错问题或者怎么保证业务一致性，那就是另一个故事了。这里我们仅仅关注如何捕捉事件间的因果关系。

如果事件 $B$ 是事件 $A$ 的结果，换句话说事件 $A$ 导致了事件 $B$ 的发生，我们可以知道 $B$ 一定发生在 $A$ 之后：

$$(A \text{ affects } B) \Rightarrow (A \rightarrow B)$$

注意这里只用了 $\Rightarrow$，而不是 $\Leftrightarrow$ ，有些事件并不受前面发生的事件的影响，但它们却是存在先后顺序，所以反推是不一定成立的。从这个关系我们可以知道：事件间的因果关系包含在 happened-before 关系里。

物理时钟（Physics clock）

水可载舟，亦可赛艇 —- 生活常识

至此，我们都是以上帝视角观察整个系统。回到最初的问题：我们想设计一个机制，让系统自己忠实记录事件顺序。我们是怎么比较两个事件的先后顺序的？生活的经验告诉我们，比较两个事件发生的时间就可以了。所以我们也想在分布式系统上这样干，我们使用物理时钟（Physics clock）把所有事件打上一个时间戳（Timestamp）。这种做法看似合理，其实不然。

时钟漂移问题（Clock Drift）

一个理想的分布式系统，各节点时间都是一致的。然而现实是复杂的，分布式系统各节点的时钟走时存在着飘移问题（上帝：“躺平？想的美。”）。一般计算机把时间存储在BIOS配置里，靠晶振输出频率稳定的振荡信号完成计时。晶振材料一般是石英，石英有温漂，换句话说就是工作温度影响到石英的震荡频率，除此之外石英还受到老化、电压的影响，种种因素使得振荡频率变高或变低了。这种效应间接导致的就是本地时钟走时变快或变慢了，而且这种走时误差会逐渐积累，达到分钟级，小时级，甚至天级。

我们最初想用节点的本地时钟为事件打上事件戳，这种做法下，一旦分布式系统节点间的时钟有了误差，我们就可能错判事件顺序关系，可能导致灾难性的后果。

时钟同步：NTP协议

既然走时会有偏差，我们就尝试把误差消掉吧。NTP协议能取得一些效果。NTP 协议是一个 Server/Client 协议。为了和授时服务器同步时间，NTP Client 会定时轮询一个或多个 NTP Server。算法是这样的：

客户端假设比服务端时间快$\Delta t$，客户端发送NTP请求的事件戳为 $T_1$，服务端接收NTP请求的时间戳为 $T_2$，服务端回复 NTP 请求的事件戳为 $T_3$，客户端接收到 NTP 回复的事件戳为 $T_4$。$d_1$、$d_2$ 是请求和回复的网络时延，$d$ 是 RTT（round-trip time）。整个关系如下图：

我们再假设 $d_1 = d_2$，就可以得到一个四元一次方程组：

$$\left\{\begin{matrix} T_2 = T_1 + \Delta t + d_1 \\ T_4 = T_3 - \Delta t + d_2 \\ d = d_1 + d_2 \\ d_1 = d_2 \end{matrix}\right.$$

解出关键两个参数：

$$\left \{ \begin{align} \Delta t = \frac{(T_2-T_1) - (T_4 - T_3)}{2} \\ d = (T_2-T_1) + (T_4 - T_3) \end{align}\right.$$

客户端根据结果进行时钟校正即可。因为前提假设是$d_1 = d_2$，NTP结果受到时延对称性和其他因素的影响，实际上应用中常有毫秒级的时延，跨数据中心的 NTP 同步误差可达上百毫秒，网络状况不好的情况下，可能会达到秒级。NTP 协议也并不对误差范围做任何保证（只是保证时间漂得不那么狠）。种种限制下，在时钟精度要求高的场合，NTP 时钟同步的效果并不理想。

当时钟开了挂：GPS、原子钟与 TrueTime API

时钟漂移问题的本质其实是硬件不给力。Google 说：那我们从硬件下手吧。Google Spanner 是个全球性的分布式数据库，作为 Google F1 的存储层，在全球范围内跨数据中心部署，能提供强一致性事务。为了提供外部一致（Externally consistent）的分布式事务、无锁的只读事务，还有原子化的数据 Schema 更新，Spanner 用 TrueTime API 授时，用事件定序，解决分布式的事务顺序问题。

Google 在全球的每个数据中心都部署了授时服务，它们由多台叫做 Time Master 的机器组成。大多数 Time Master 从 GPS 同步时间，并且分布部署在不同地方防止天线信号问题。剩余的 Master 内部使用原子钟保证走时准确，Google 说原子钟并不贵（^_^，手动狗头）。所有 Time Master 会相互校时，也会比较走时速率，一旦发现自身偏差过大，就把自己从集群里“踢掉”。数据中心的每一台服务器都会运行 Timeslave Daemon。Daemon 不断轮询 Master 进行时钟同步，并提供了 TrueTime API 给应用使用。关于 TrueTime 的更多细节，可以去读一下相关论文。

通过这样一种方法，TrueTime 保证了本地获取的时钟戳的误差 $\epsilon$ （Uncertainty）总在可估计的确定范围内，当然这个误差非常小，在微秒到数毫秒。TrueTime API 提供了这样的一组接口：

方法	返回值
$ TT.now() $	$TTinterval: [earliest, latest]$
$TT.after(t)$	True if $t$ has definitely passed
$TT.before(t)$	True if $t$ has definitely not arrived

因为有误差 $\epsilon$ ，$TT.now()$ 返回的是一个时间的区间 $TTinterval$，绝对时刻一定会在 $[earliest, latest]$ 内。如果有一个事件 $A$ ，$tt = TT.now()$，那么 $tt.earlist \le t_{abs}(E_{now}) \le tt.latest$。此处的 $t_{abs}(e)$ 指的是理论上的绝对时刻，$E_{now}$ 是 $TT.now()$​ 的发起（invocation）事件。

对于另外两个API。使用 $TT.after(t)$ 能保证时刻 $t$ 一定已经过去，使用 $TT.after(t)$ 能保证时刻 $t$ 一定还没有到来。它们分别等价于 $t_{abs}(E_{now}) \gt TT.now().latest$ 和 $t_{abs}(E_{now}) \lt TT.now().earliest$。

对于两个事件 $A$、$B$，一定有：

$$(tt_A.latest \le tt_B.earliest) \Rightarrow (A \rightarrow B)$$

看起来似乎有可能定出事件的全序，然而实际上并不。因为不是所有事件都能满足条件，我们考虑到两个 $TTinterval$ 区间存在重叠的情况，这种情况下就无法定序了。TrueTime 看似还是不完美，但又不是不能用。

实话说，因为保证了时间的 Uncertainty（而且很小），所以 TrueTime API 其实是个相当大的改进（相比 NTP 等）。到这里如果仍然对 TrueTime 的存在意义有疑问，不妨先了解一下文后的讨论一致性问题，再回到这里思考一下。

我们粗略看一下 Spanner 是如何使用 TrueTime 来为写事务（Transaction）定序的（不感兴趣直接跳到 TSO 中心授时吧）。（实际上要更复杂，只是举个例子）

Spanner 为每一个写事务都分配了一个单调递增的时间戳 $s$，并保证，若事务 $T_2$ 比事务 $T_1$ 先开始，那么 $s_1 < s_2$ ，其通过事件定序解决：

• Commit Wait 保证：第一个事务的真正 commit 时间 $t_{abs}(E_1^{commit})$ 一定比 $s_1$ 要晚。

• Assumption：第二个事务的绝对开始时间 $t_{abs}(E_2^{start})$，不能小于前一个事务的 commit 绝对提交时间 $t_{abs}(E_1^{commit})$

• Start Guarantee：事务的事件戳不能小于其 Commit 请求到达服务器的绝对时间 $t_{abs}(E_2^{server})$

于是呼：

$$\begin{align} s_1 &< t_{abs}(E_1^{commit}) && (\text{Commit Wait}) \\ t_{abs}(E_1^{commit}) &\le t_{abs}( E_2^{start}) && (\text{Assumption}) \\ t_{abs}(E_2^{start}) &\le t_{abs}( E_2^{server} ) && (E_2^{start} \rightarrow E_2^{server} )\\ t_{abs}(E_2^{server}) &\le s_2 && (\text{Start Guarantee})\\ s_1 &< s_2 && (\text{传递性}) \\ \end{align}$$

事务能定序，时钟 Uncertainty 导致的 Commit Wait 又很小，意味着用 TrueTime 能够：避免跨机房长距离调用的延迟，又能严格保持预期的外部一致性模型。效率+++++有木有！所以 TrueTime，可以说开了硬件的挂，这个挂叫 “GPS和原子钟”，用事件定序的方式把分布式数据库头疼了很久的一致性问题给解决了，更多细节参考 Spanner 相关论文吧。

中心授时：Timestamp Oracle（TSO）

Lamport 在其主页介绍自己的论文《Time, Clocks, and the Ordering of Events in a Distributed System》时与狭义相对论联系在了一起，表示自己从狭义相对论得到了灵感，似乎道出了分布式系统事件难以确定全序的本质原因：

Special relativity teaches us that there is no invariant total ordering of events in space-time; different observers can disagree about which of two events happened first. —- Leslie Lamport

狭义相对论里面有个概念：相对同时。指的是：在一个参考系中同时发生的两个事件，在另一个参考系看来是不同时的。举个例子，如果都基于本地时间，地面上观测事件 $A$ 先于事件 $B$ 发生，但由于相对论效应，飞船上观测结论却可能截然相反。所以 Lamport 说相对论指出了：世界上根本无绝对唯一的事件全序关系，至于谁先发生，取决于观测者。虽然现实参考系下，大部分分布式系统的相对论效应可以忽略不计，但问题是同源的。这样看来，基于物理时钟来讨论事件的序根本毫无意义，这导致了 Lamport 决定脱离物理时钟，从另一个角度去看待事件的序，这个方法就是逻辑时钟（我们下面再讨论）。然而在分布式系统设计上，即使我们有一堆观测者（节点），很多时候也必须全局定序，使得所有观测者对于事件顺序必须达成一致，否则我们就很难设计系统，也很难去定义和解决一致性问题。解决工程问题，很多时候在于妥协和取舍。既然多观测者下，难以全局定序，那么我们工程上折中一点，只用某个观测者看到的事件序作为全局的序，这样事情不就变得简单了吗？这种方法就是中心授时法。

Timestamp Oracle（TSO）是 Google 的 Percolator 分布式事务系统里依赖的授时服务的名称，因为 Percolator 事务模型过于知名，TSO 在很多情况下已经成为了中心授时的代称。关于 Percolator，有兴趣可以去读一读论文，非常有意思。

中心授时比较简单，当需要确定事件时刻，进而定序的时候，就向授时中心索要一个时间戳。因为我们舍弃了别的观测者看到事件序，授时中心看到的顺序才是权威，对于网络中消息延迟、乱序所造成的事件顺序错乱，就要小心解决。这样事件最终也能规定出全序。

中心授时带来的是单点问题，不太利于扩展，不过也不是没有 workaround。

TiKV 的实践：混合时钟，TSO+LC

对于 TSO 中心授时，TiKV 作了改进。TiKV 通过 PD（Placement Driver） 进行授时，使用64位事件戳，物理时钟和逻辑时钟分别占 46 位和 18 位，本质是中心式的混合逻辑时钟。

PD 首先使用 raft 选举出 leader，进而进行校时。校时过程确定系统的时间到底被推进到了哪里，从 etcd 里先获取上一个 Leader 分配的最大时间 $t_{last}$，然后与本地时间进行比较，两者取大值。如果取的是$t_{last}$，那么将时间戳物理部分向前推进1，保证即将分配时间戳一定在已经分配的时间戳之后，完成校时。

PD 每次都会分配一个时间窗口的所有时间戳，以保证分配性能。对于客户端的请求，PD 允许请求多个事件戳，以减少网络负载，提高性能。

PD 每一段时间都会使用 raft，推进物理时钟。当前物理事件戳下逻辑时钟即将耗尽或已经耗尽时，也会推进物理时钟。

PD Leader 不可用时，会选举出新的 Leader，选举期间系统会有一小段时间不可用，这也是 TSO 中心授时带来的小问题。不过 PingCAP 表示，实际使用上这样的设计并没有造成过什么不可忽视的影响。

逻辑时钟（Logical Clock）

前面提到了 Lamport 联系到了狭义相对论，认为在物理时钟下讨论事件的序是有很大问题的，直接给了 Lamport 一个如何追踪分布式系统中时间序的启发，另一个角度出发，于是就有了最早的逻辑时钟算法，Lamport 时钟。

Lamport 时钟

There is only a partial order in which an event e1 precedes an event e2 iff e1 can causally affect e2. —- Leslie Lamport

Lamport 认为，时空中没有不变的事件全序关系，只有因为事件间相互影响造成因果关系，从而有事件的偏序。在上面的系统时序图中，我们从抽象视角上，引入一个时钟，仅仅通过赋予发生的事件一个简单的数字去追踪事件关系。可以认为这个简单的数字，其实就是事件发生的一个时刻值。为了更精确描述这个算法，我们为每一个进程定义： $C_i$是进程 $i$ 的时钟，$C_i\langle E \rangle$ 指事件 $E$ 在进程 $i$ 的发生时刻值。注意到，这个时刻值与物理时间是没有任何联系的，所以我们定义的时钟是个逻辑时钟（Logical Clock），我们可以抛开一切物理计时的方法，通过计数器（Counter）去实现它。

进一步，我们想一想怎么实现这个时钟才是正确的，或者说这个时钟应该满足什么性质或条件。我们想用这个时钟去追踪事件间的 happened-before 关系，很明显我们需要这样一个条件：

• Clock Condition：$\forall\text{ Event }A,B: (A \rightarrow B) \Rightarrow (C \langle A \rangle \lt C\langle B \rangle)$

注意，这里仍然是 $\Rightarrow$，不是 $\Leftrightarrow$。这样的条件可以进一步推出满足的两个条件：

• Clock Condition C1：$\forall\text{ Event }A,B \text{ in Process } P_i : (A \rightarrow B) \Rightarrow (C_i \langle A \rangle \lt C_i\langle B \rangle) $
• Clock Condition C2：对于消息 $M$， $A$ 是其在进程 $P_i$ 的发送事件， $B$ 是其在进程 $P_j$ 的发送事件，那么 $C_i \langle A \rangle \lt C_j\langle B \rangle$。

为了让时钟满足上面的条件，我们用例子来说明。我们在保留 happened-before 关系，且满足 Clock Condition 前提下画上等时线，越过等时线，时钟则必须向前跳变（Tick）：

然后我们把等时线拉平，重新观察时序图：

我们很容易可以得到算法：

• Implementation Rule 1：同一进程，在顺序两个事件发生的期间，时钟会向前跳变。
• Implementation Rule 2(a)：任意发送事件 $A$ 包含了一个时间戳 $T_m = C_i\langle A \rangle$。
• Implementation Rule 2(b)：接收到任意事件 $B$ ，进程 $j$ 会将自身时钟设定为不小于消息事件戳 $T_m$ 的值。

Implementation Rule 1 保证了 Clock Condition C1，Implementation Rule 2(a) 和 Implementation Rule 2(b) 保证了 Clock Condition C2。它们共同保证了逻辑时钟满足 Clock Condition。

按照 $ C \langle A \rangle \lt C\langle B \rangle $ 这种关系给出的偏序，有可能把并发事件的 happened-before 关系搞错（比如时序图中的 $C_2$ 和 $B_3$），但因为并发事件没有数据交互，某些情况下并无大碍。整个分布式系统一定会达成事件因果上的一致，比如按照时间戳顺序去执行一组写操作事件，有因果关系的写操作一定是按顺序执行的。

人为定义的全序

任意一个进程，通过比较时间戳给出的是偏序关系，因为我们遇到 $ C \langle A \rangle = C\langle B \rangle $ 的时候，就没法比较了。当然有时候为了在全局范围内取得全序，达成一致，我们可以罔顾外部观察的事实，人为定义全序：

$$A \rightsquigarrow B \equiv (C_i \langle A \rangle \lt C_j\langle B \rangle ) \lor (C_i \langle A \rangle = C_j\langle B \rangle \land P_i \prec P_j)$$

在时间戳相等时，我们认为进程序号比较大的事件发生在进程序号小的事件之后，这个是人为定义的全序，并不为了反映外部观察的客观事实，而仅仅是一种约定。我们也可以用其他约定来定义全序。但在这里的定义下，明显有：

$$A \rightarrow B \Rightarrow A \rightsquigarrow B$$

信息更弱了。实际上，因果关系并没有被破坏。人为定义全序有助于分布式系统操作上取得全局一致，虽然这一结果有时候并不符合我们的预期。

Lamport 时钟算法并不是一种分布式系统下，实现数据一致性的算法，只是一种用来确定因果一致的事件序的想法。类似对同一资源操作造成冲突的并发事件，Lamport 时间戳无法作出区分，也就无法进一步解决冲突。

向量时钟（Vector Clock）

对于两个事件 $A$、$B$，Lamport 时钟下观测到的结果 $C \langle A \rangle \lt C\langle B \rangle$，给出的信息非常有限。有时候希望有更强的Clock Condition：

$$\forall\text{ Event }A,B: (A \rightarrow B) \Leftrightarrow (C \langle A \rangle \lt C\langle B \rangle)$$

这样我们能够准确的确定 happened-before 关系，并且准确确定出哪些事件之间是并发的。我们想知道为什么时间戳不能用来反推事件的 happened-before 关系，辗转反侧终于找到了原因。本质是我们没有区分不同进程的时钟，从而导致了信息的丢失。比如进程 $i$ ，$j$ 在某一个时间段内时钟达成了一致（$C_i = C_j$），此时 $i$ 发生了事件，推进了时钟，导致了 $(C \langle A \rangle \lt C\langle B \rangle) \Rightarrow (A \rightarrow B) $ 的反例的出现，关系便不再成立了。我们的可以做一个改进，将各个进程的时钟分开，这个便是向量时钟（Vector Clock）。

为了实现更强的 Clock Condition，单独维护每个进程的时钟，使得 $C_i$ 从一个值变成了一个向量：

$$C_i = [c_1,c_2,c_3,...,c_n]$$

跟逻辑时钟一样，我们可以定义算法规则：

• Rule 1：同一进程，在顺序两个事件发生的期间，时钟向量中自身时钟会向前跳变，其他维持原状。
• Rule 2a：任意发送事件 $A$ 包含了向量时间戳 $T_m = C_i\langle A \rangle$。
• Rule 2b：接收到任意事件 $B$ ，进程 $j$ 根据消息的向量事件戳 $T_m$，更新本地时间向量，使得本地向量所有时钟分量不小于事件戳向量对应的时钟分量。

我们定义时间戳比较的规则：

$$C(A) < C(B) \equiv (\exists i \in \mathbb{N}:C(A)[i] < C(B)[i]) \land ( \forall i \in \mathbb{N}:C(A)[i] \le C(B)[i])$$

即对于 $C(A) < C(B)$，要求 $A$ 事件所有时钟分量都小于或等于 $B$ 事件对应分量，且至少有一个分量小于 $B$ 事件的对应分量。

不满足 $C(A) < C(B)$ 的事件相互都是并发事件。

通过比较时间戳，向量时钟可以准确观测事件的 happened-before 关系，准确给出因果关系确定的事件偏序。这个性质使得使用向量时间戳可以严格区分出并发事件。

上面的时序图中有两个冲突的并发事件 $Set(A,2)$ 和 $Del(A)$。紫色是 Lamport 时间戳，绿色的是向量时间戳。

如采用 Lamport 时钟，那么 $C(E_{Del(A)}) = 5$， $C(E_{Set(A,2)}) = 3$，如果不改进算法，则无法分辨出两个操作是并发冲突的。

在向量时钟下，$C(E_{Del(A)}) = [1,5,2]$， $C(E_{Set(A,2)}) = [2,2,3]$，可以判断两个操作是并发事件。

向量时钟不足的地方是 Timestamp 的 Overhead：在节点很多的时候，向量维度会非常的高，占用很多空间。（想象一下，我们仅仅想传递一个 8 位的 integer，在512台机器的集群里，假设时间戳32位，我们要带上 2kB 的时间戳）

混合逻辑时钟（HLC，Hybird Logical Clock）

Time is an illusion. —- Albert Einstein

物理时钟不好记录 happened-before 关系，逻辑时钟又有点太理论化了。年复一年，人们端详着 Lamport 时钟，面对着现实不太给力的 NTP 协议，想找到一种折中一点的工程办法。终于在 2014 年，提出了一种将理论和现实结合在一起的时钟，混合逻辑时钟（HLC，Hybird Logical Clock）。HLC 既可以跟逻辑时钟一样追踪 happened-before 关系，又能逼近物理时钟。

对于任意一个事件 $E$ ，HLC 使用两段时间戳：物理时间戳 $E.l$、逻辑时间戳 $E.c$。它们共同组成时间戳 $E.hlc = \langle E.l, E.c \rangle$。对于时间戳的比较：

$$A.hlc < B.hlc \equiv (A.l < B.l) \lor (A.l = B.l \land A.c < B.c)$$

以下是 HLC 想达到的效果：

• $A \rightarrow B \Rightarrow A.hlc < B.hlc$，其中 $l$ 是事件的时间戳（Timestamp）。
• 时间戳仅仅占用 $O(1)$ 空间。
• 物理时间戳部分与事件实际发生时间的误差是有界的，即 $|E.l - E.pt| < \epsilon $，$E.pt$ 是事件 $E$ 发生时本地的物理时间。

HLC 算法与 Lamport 时钟算法有点相似。规则是这样的：

• 每一个进程（记为$j$）在本地维护一个混合逻辑时间戳，初值 $j.hlc = \langle 0, 0 \rangle$

• 对于发生新事件，总是保证本地时间戳比已知的时间戳要新，这里根据消息类型采用不同的算法：

  • 对于自发事件或发送事件：

    $$\begin{align} &j.l' = j.l;\\ &j.l = max(j.l', j.pt);\\ & \text{If } (j.l == j.l') \text{ then } j.c = j.c + 1\\ &\text{ else } j.c = 0; \end{align}$$

  • 对于接收事件 $M$ ：

  $$\begin{align} &j.l' = j.l;\\ &j.l = max(j.l', j.pt, M.l);\\ &\text{If }(j.l==j.l' \land j.l'==M.l) \text{ then } j.c = max(j.c, M.c)\\ &\text{ Else If }(j.l==j.l') \text{ then } j.c = j.c + 1 \\ &\text{ Else If }(j.l == M.l) \text{ then } j.c = M.c + 1\\ &\text{ Else } j.c = 0; \end{align}$$

• 发生的新事件打上更新后的本地时间戳。

• 在同一节点的满足 $E.l < F.l$ 的两个事件 $E$、$F$ 中间，引入自发的 Virtual Dummy 事件 $L$，满足 $L.l \in [E.l + 1, F.l] \land L.c = 0$。

HLC 满足以下的几个定理：

• 两个事件 $E$、$F$，满足 $E \rightarrow F \Rightarrow E.hlc < F.hlc$。

• 对于任意一个事件 $F$：

  • $F.l \ge F.pt$

  • $F.l > F.pt \Rightarrow (\exists \text{ Event } G:G \rightarrow F \land G.pt = F.l)$

  • 物理时钟误差有界：$|F.l - F.pt| \le \epsilon $，$\epsilon$ 是时钟同步的 Uncertainty。

  • 逻辑时间的跳变一定是由因果事件引起的，在全局一定存在着一系列事件：

  $$\begin{align} F.c = k \land k > 0 \Rightarrow (\exists &\text{ Event } G_1,G_2,...,G_k: \\ &(\forall i \in [1,k) : G_i \rightarrow G_{i+1}) \\ \land & (\forall j \in [1,k] : G_j.l = F.l) \\ \land & G_k \rightarrow F) \end{align}$$
  • 除去 Virtual Dummy 事件，$F.c \le |{\text{Event } G: G \rightarrow F \land G.l = F.l}|$
  • 逻辑时间戳不会无限增长：$F.c \le N*(\epsilon + 1)$
    • 若本地物理时钟在消息传递期间，一定会增长 $d$，那么逻辑时间戳最大不超过 $\frac{\epsilon}{d} + 1$。

一堆公式看起来比较头大。笔者对 HLC 了解不深，证明就不放这里了，所以感兴趣的话可以参考论文《Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases》。

自稳定问题

采用 HLC 的系统里，如果有时间不正常的节点，可能会把整个系统所有节点的本地物理时间戳都推进到一个非常大的值。在 HLC 下，逻辑时间的重置，要求物理时间向前推进，若物理时钟长期赶不上本地的物理时间戳，带来的就是逻辑时间戳的无限增长，从而某种意义上打破了 HLC 的几个有界性定理。论文给出的可能的做法是：

• 一旦发现某个 Message 的物理时间戳大大超越了本地时间，则把这样的 Message 丢弃，因为节点两方，有一方的时钟可能已经出问题了，同时也记录下相关日志，触发告警。
• 限制逻辑时间戳 $c$ ，让其不能无限增长。

全局一致性快照（Globally Consistent Snapshots）

假设我们需要读 $t = 10$ 时刻的快照。因为时钟同步全局时间误差在 $\epsilon$ ，在 $\epsilon$ 时间内，全局每一个节点都将产生一个 $\langle 10, 0 \rangle$ 的 Dummy 事件作为分隔。分隔使得一切事件将会发生在这个 Dummy 事件之后，不可能再产生时间戳在 $\langle 10, 0 \rangle$ 之前的事件，也就是系统在 $t = 10$ 一定会有一个全局的快照。除此我们也可以给所有节点广播一个消息，使得分隔事件提前产生。

HLC 的优势

NTP 同步下的物理时钟，可能会被其更新到一个更早的时间，以此生成的时间戳并不满足严格单调增长。HLC 时钟虽然使用 NTP 同步下的物理时钟作为时钟源，但其物理时间部分一定是保证严格单调增长的，且 HLC 的理论上的某些性质，使得 HLC 的时钟漂移量比 NTP 的时钟漂移量要小。由此，HLC 可以说继承了物理时钟的优点，且克服了 NTP 下同步时钟的某些缺陷，是一种很不错改良的方案。HLC 足以成为物理时钟的一种替代方案。

除此之外，HLC 作为逻辑时钟的一种改进，能够捕捉事件的因果关系，继承了逻辑时钟的优点，所以也足以替代一般的逻辑时钟。

可以说 HLC 是一种目前来说相对有效的，生成时间戳的方法。因此应用上，CockroachDB、MongoDB 都在使用 HLC 作为时间戳方案。

时序和一致性

一致？共识？

本不想在这篇文章总结一致性问题。最后想了想一致性模型和时序联系紧密，还是写一下。明确了时序的概念后，我们就可以很容易理解一致性问题了。但在讨论之前，我想先抛出一个问题：我们讨论分布式系统一致性问题、共识问题的时候，到底在说些什么？它们是等价的吗？“一致性”对应的单词为“Consistency”，”共识”对应的单词则是“Consensus”。可能是由于翻译问题，不少文章会将两者混淆起来，统称“一致性”，然后文章下面就开始谈论 Paxos、Raft 算法了。然而如果翻阅 Paxos 或者 Raft 原论文，会发现作者都会将描述的算法称作共识算法，而不是一致性算法。比如非常著名的 Raft 短篇 Paper，题目是“In Search of an Understandable Consensus Algorithm (Extended Version)”，而不是 “Consistency Algorithm”，《Paxos Made Simple》更是整篇文章都没用过“Consistency”这个词。所以问题出在哪？

分布式系统中，如何在节点之间就某个提议或者某个数据的值达成一致，称作共识（Consensus）。比如说“某个分布式事务是否应该提交”、“哪个节点是 Leader”等等。而一致性（Consistency）针对的则是，在一定时序的一系列操作下，系统表现出来的行为模型。主要用于评判系统行为正确与否。这个系统可能是单机系统，比如加了Cache的内存、数据库等等，当然也可能是分布式系统。最常见的操作则是对系统里面数据进行增删改查。在分布式系统下，最常针对的是数据副本的变更问题：对于某个副本的变更，在任意节点读取副本，是否能看到这个变更；进一步的，什么时候变更不可见，什么时候开始变更对外部可见，从什么时候开始数据一致；对于并发操作，所有节点对于并发操作执行顺序是一样的吗？数据都最终一致吗？外部观察者从任意一个节点看数据的变化情况是否是一样？这是典型的一致性问题，并且和时序息息相关。

一致性有强弱，共识无强弱。

时序到共识

文章前面在讨论分布式系统时序的时候，我们发现不同节点看到的事件顺序不一。对于同一资源的并发操作，除非我们统一所有节点对事件观测的全序，按照全序地执行操作，否则节点间数据很难一致。顺理成章，我们希望基于时间戳事先确定一套对并发事件的定序规则，解决共识问题。但实践过后我们会发现这种方法能实现的一致性模型非常有限。于是我们就只能使用别的方法确定变更事件的全序了，这变成了分布式系统下的共识问题（Consenus Problem）。 可以通过在节点间对变更时序达成共识去实现符合某个一致性模型的分布式系统。共识算法中，Paxos 和 Raft 最为知名。

我们说一个分布式系统遵循某个一致性模型，实质上是在说：我们仅仅请求系统中某个一个节点，进行各种操作的情况下，所有节点的状态变化，或者说任意节点对系统观察者的表现，都符合模型的预期，系统所有节点对等，对外可以看作一个整体。比如 Raft 算法中，我们只是在实现 Raft 复制状态机区分 Follower 和 Leader，外部进程看到的节点是对等的，它们可以任意选择节点对系统进行操作。

常见的一致性模型

严格意义下，对任何系统的请求不可能一瞬间完成。外部进程向系统发起请求到接收到返回，有一定的时间间隔。其中有两个事件：发起（Invocation）和返回（Response）。返回的时刻一般就是操作顺利完成的时刻。一个完整 Write 操作，时序图是这样的：

为了描述方便，我们换一个绘图方式。

我们考虑多个进程并发地对系统进行读写，系统状态的变更要满足一定的条件，这衍生出一系列一致性模型。

严格一致性（Strict consistency）

严格一致性是最强的一致性模型。其要求是，系统一旦在 $t$ 时刻状态变更了，从此 $t’ > t$ 新状态必须对外能被看到。对于分布式系统来说，就是在 $t$ 时刻所有节点状态都瞬间改变，$t’ > t$ 在 $t’$ 时刻随便找一个节点都能读到最新的状态，不能存在一个节点状态变更了，另一个节点状态没有变更的情况。严格一致性可保证分布式系统在外部看来就是一个单机系统。但因为要求非常苛刻，除了单机可满足严格一致性，分布式系统基本没法满足。毕竟节点间消息传递需要时间，同步变更需要时间，实时同步是不可能的。

线性一致性（Linearizability）

线性一致性介于严格一致性和顺序一致性之间，比前者弱，比后者强。线性一致性要求对系统的一次变更在发起（Inv）和返回（Res）之间的某个时间点原子般生效，对外部可见。一般语境下的强一致性（Strong consistency）就是指它。比如 CAP 定理中的 C，就是线性一致性。线性一致性又被称作原子一致性（Atomic consistency）和外部一致性（External consistency）。后者似乎源于 Google Spanner 的论文。举个例子：

例子中带有大量并发读写，但依然满足线性一致性。System 线上标明了 Write 操作在系统中的时序，对于分布式系统，要求所有节点的时序都与之相同。Process 线上的小红点标出了系统收到请求并原子地完成的时刻，由于消息传递需要时间，它们总是在 Inv 事件和 Res 事件中间。线性一致性要求对正确性的要求是有余量的，比如说例子中 Process c 的第一次读，例子中读出的是 2，但读出 0 也是符合线性一致性的，因为这次读操作可以在其 Inv 和 Res 之间任何一个时刻完成。

分布式系统下，要实现线性一致性，需要在变更事件的全序达成共识的基础上，牺牲系统的可用性和性能，用一定机制给生效时间加上约束（更严格的时序）。比如 Basic Raft 算法，多数节点提交日志后，操作就算成功了，Client 将得到返回消息。消息返回后一段时间内，仍然可能存在少数节点的日志是落后的，若向这类节点请求数据，返回的就是旧的值，违反线性一致性。另外，网络分区也会导致这种情况发生。这是实现上必然会遇到的 Stale Read 问题。要解决，只能引入新的机制，比如读请求也走一次 Raft 提交，或者引入 Raft 大论文提到的 ReadIndex ，牺牲的是性能和系统可用性。反之，允许 Stale Read，一致性将减弱为顺序一致性，不满足线性一致性。

顺序一致性（Sequential consistency）

顺序一致性更弱一些。相比线性一致性，顺序一致允许操作在发起和返回之间外的某个时间点生效，但变更操作的顺序必须被保留，任意一个进程操作的顺序是一致的，变更的状态序列必须一致的。实现顺序一致性只需要对变更事件的全序达成共识，这是一般共识算法所完成的。

例子中可以看到，Write(x,2) 操作完成后，一段时间内都没有看到 Read(x) = 2 这个结果，反而是过了一段时间才看到。Write(x,1)、Write(x,5) 等操作也是没有立即生效。写入使得x的变化是：0,2,1,5,3。读出的顺序也是0,2,1,5,3，顺序得以保留。

因果一致性（Causal consistency）

因果一致性，不要求所有变更操作的顺序一致，仅仅要求具有因果关系的一组变更操作是按顺序执行的。它属于弱一致性的范畴。只要能追踪事件的因果关系，就可以实现因果一致性。比如用逻辑时钟给操作打上时间戳，按时间戳顺序执行操作，就可以实现这种一致性模型。

FIFO 一致性（FIFO consistency）

FIFO 一致性也称作 PRAM 一致性（PRAM consistency），是比因果一致性更弱的一致性。若对于同一资源，只存在一个进程对其进行变更，那么其他进程必须能看到相同的变更顺序，如果多个进程并发对同一个资源变更，其他进程看到变更顺序允许不一致。

总结

我用这篇长文梳理了分布式系统中，关于时间、时钟、时序的相关问题。主要探讨了事件因果、顺序，还有分布式系统常见的时钟解决方案。时钟解决方案包括物理时钟和逻辑时钟两类，包含了目前工程上的主要实现方案。最后简要讨论了与时序联系紧密的一致性问题。至于如何让一个分布式系统符合一定的一致性模型是一个很复杂的问题，就是另一个很长的故事了。共识问题也超出了文章的讨论范围，而且以作者拙劣的计算机科学理论水平，也很难写得出很深入的文章，就留给学术界的各位作者吧。

文章总结可能会有一些欠严谨的地方，等以后再慢慢修改。

参考文献 References

• PD的时钟服务——TSO
• 《Time, Clocks, and the Ordering of Events in a Distributed System》
• 《Spanner: Google’s Globally-Distributed Database》
• 《Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases》
• 《Paxos Made Simple》
• 《Consensus: Bridging Theory and Practice》
• Wikipedia:Consensus (computer_science)
• Consistency model
• 《Strong consistency models》
• 《Linearizability: A Correctness Condition for Concurrent Objects》