时间戳（Timestamp）与分布式系统的排序（Ordering）

时间戳

和人类一样，计算机系统也需要时间的概念；通常我们需要一个时间戳来标记事件发生的时间。例如，当我们使用 Mac 的 TimeMachine 来为系统进行备份的时候，我们需要知道当前备份的时间；这样我们可以在恢复时明确我们恢复的什么时候的备份。

分布式时间戳

分布式系统和单机系统一样，也需要时间戳来标记事件（如数据更新）的时间。如何生成系统的时间戳？我们可否直接使用系统的时间，比如 linux 的系统调用，中time()? 如果系统中只有一台机器，那么我们当然可以使用这个方法来确定时间戳。然而，如果系统中有许多台机器，那么使用每台机器自己的时间戳通常是不够的；因为他们之间的时钟往往是不同步的。例如，我们手机上的时间可能会和电脑的时间不一样。

不同步时钟带来的问题：我们用一个简单的例子来看不能同步的时间戳会在分布式系统中带来何种问题。我们以一个简单数据库为例子，假设我们有两个服务器，server0 和 server1，如下图所示。他们存储同一个数据库。数据库接受客户端（client）的 update function 来更新：add x将 x 添加到数据库；delete x将 x 删除。假设 client 需要在数据库中添加 x，则他会同时往两台服务器同时发送add x的请求。我们假设服务器顺序的执行所有的 update function。

由于数据存在备份，那么就会有一致性（consistency）的问题。例如下图所示：一个 client 给发送add x1而另一个 client 发送add x2。由于网络消息的到达可能会乱序，这么两台服务器执行 update function 的顺序会不同，造成不一致。

备份系统通常需要提供一定程度的一致性来方便开发人员使用存储的数据。我们这边考虑最简单（也最弱）的一致性：eventual consistency，即最终 server0 和 server1 的状态最终会是一样的。我们之后会看到，由于不一致的时钟，即使是这种最弱的一致性条件下也会出现问题。

实现 eventual consistency 最简单的方法就是采用有序日志（ordered log）；即我们将 client 发送来的 update function 记入一个日志（log），然后按照他们的发送时间戳排序；最后按照排序依次执行。一种简单的时间戳分配方法就是使用 client 的本地时钟来标记 update function 的时间。如下图所示，ordered log 完美的解决了问题：虽然不同服务器收到的 update function 的顺序不一样，但我们可以利用已知的时间戳来为他们进行排序；再进行执行。这样，最终 server0 和 server1 的状态总会是一样的。

读者可能好奇，在这个简单支持 eventual consistency 的例子中，似乎我们对时间戳几乎没有要求：因为这里的时间戳仅仅是作为排序日志的一种方式。然而，如果真的对时间戳没有要求的话，实际上并不能保证用户需要的一致性！我们来看下面一个例子：client2 先发送了add x而 client1 随后发送了del x；然而由于 client 的时钟在分布式下可能会不一致，del x的时间戳（0）可能于add x。这样，服务器可能会先于add x执行del x。

不同步时间戳带来的问题：我们可以看到，在 server0 或者 server1 执行的时候，del x会先于add x执行，这其实违反了用户需要的一致性！通常，在客户端看来，他是先确定添加了x之后才会将其删除。这主要是由于这些请求可能来自于不同的 client；而他们的时间未必会和事件发生的真实事件一致。

Lamport Timestamp

其实我们看到，不同步的时间戳的最关键问题就是有序的事件需要给他们分配有序的时间戳。在上文的例子中，由于del x逻辑上是依赖于add x的，因此del x在客户端发送的时候，理想情况下他发送的时间戳需要更大。如果直接简单的用客户端的机器时间戳来作为 ordered log 的依据，则没有办法保证这一特性，因为分布式系统中不同机器之间的时钟是不一致的。

为了解决这一问题，大名鼎鼎的Leslie Lamport 提出了 lamport timestamp[1]，如下图[2]所示:

Logical Timestamp 的思想非常简单，如果事件之间有依赖关系，则更新时间戳来体现这种依赖关系。具体的方法，就是将时间戳更新为比依赖事件的时间戳更大。

我们来从之前的例子来看，lamport timestamp 怎么解决之前例子的问题。假设add x先执行了，则我们以 lamport timestamp 的方式记下add x的时间。在发送del x的时候我们以 lamport timestamp 的方式来给其分配时间戳；这样del x的时间戳永远会比add x大。这样，在以他们的时间戳排序 ordered log 的时候，就会避免之前执行顺序的问题。

全局有序的时钟

Lamport Timestamp 只能保证一个偏序：如果一个事件依赖于另一个事件，则他的时间戳会更大；反之则不成立。通常，人们还是希望时间戳能够提供更强的顺序， 而不单单提供逻辑事件之间的关系。这种顺序通常刻画为外部一致性（extern consistency），即如果一个事件在真实时间中发生在另一件事件之后，那么他就会有一个更大的时间戳，无论他们是否具有依赖关系。

通常，最简单的在分布式下提供 external 一致性的时间戳的方法有以下两种：

全局时钟服务器：我们采用一台机器来单独的作为时间戳服务器，分布式系统中所有的机器以这台机器产生时间戳为准。通常，如果一个客户端需要一个时间戳，他需要与这台时间戳服务器进行通信来获得当前的时间。

Vector timestamp：是全局时钟服务器的一个变种，即每台机器维护一个时间戳。vector timestamp 的实现方式有多种且比较复杂，因此本文不详细讨论这个情况。

全局的时间戳服务器显然是最直观提供符合事件发生先后顺序的方法；然而他也有明显的弊端，即所有的请求都会发送一个额外的请求到时间戳服务器，这样会造成一次额外的通信开销；同时时间戳服务器会成为性能的瓶颈。这在 geo-replicated，即服务器分布在地球各地的情况下更加糟糕，因为跨地域的网络延迟通常会非常大。

TrueTime

Google 在 2012 年的 Spanner[3] 数据库中提出了一个 TrueTime API，来避免使用一个全局时间戳服务器，同时提供的时间能够保证外部一致性。

简单来说，TrueTime 提供了一个 delta；并且保证不同机器之间的时钟最多不会超过 delta。这样，当一个事件发生时 ,最多只需要等待 delta 的事件，便可保证他的时间戳一定大于先于他之前发生的事件的时间戳。Spanner 用 TrueTime 在 geo-eplicated 的情况下支持 strict serializability 的数据库事务。

Delta 的大小对使用 TrueTime 应用的性能非常相关：通常使用 TrueTime 的应用需要等待 delta 来确保时间戳的准确。TrueTime 提供的 delta 通常是毫秒级。Delta 的大小取决于许多因素，如网络延迟。最近有研究在单数据中心的情况下，利用快速的网络（如 RDMA）可以将 delta 降低到微秒级[4]。

参考资料：

[1]Time, clocks and the ordering of events in a distributed system,lamport.azurewebsites.net

[2]ipads.se.sjtu.edu.cn/co

[3]usenix.org/conference/o

[4]microsoft.com/en-us/res