分布式系统的硬核：时间时钟问题和算法

分布式系统中时间是核心概念，依靠时间多个机器才能协同交互。分布式数据库 微服务交互都逃不过这个硬核。本文概括了物理时钟和逻辑时钟等概念。
作为软件工程师，我们都依赖于时间概念：确保我们程序中的事件遵循时间顺序的关键概念。然而，调用“获取当前时间”的简单调用可能会产生意外结果，如果使用不当会导致无法预料的后果。此外，我们在本地开发机器上观察到的关于时间的不变性可能并不一定存在于云中或任何分布式系统中。先上结论：

• 使用System.nanoTime()用于测量时间间隔
• 使用System.currentTimeMillis()获得的挂钟时间
• 使用Clock.systemUTC().instant()用于获取挂钟时间与NS 精度
• 即使它的精度很高，也不是每个时钟都能为您提供所需的分辨率
• 挂钟时间可以关闭几十毫秒（或更多，或更少）
• 如果时间同步很重要，请使用云提供商提供的NTP
• 逻辑时钟可能比实际时钟更合适，但它们具有相关的成本

2. 分辨率Resolution
分辨率是第二个属性。它是两个时钟周期之间最小的可观察差异。带有秒针的简单机械表的分辨率为1秒。当你盯着手表时，手表位置可以是12秒或13秒，但不会是12点半秒。

3.延迟Latency
当我们谈论时钟时，通常会忽略延迟，但是当我们考虑其他属性（如分辨率）时，它非常重要。例如，如果你手上有最精确的原子手表，皮秒picosecond分辨率也没关系 - 如果我问你现在是什么时间，你需要大约一秒，有时更少，有时甚至更多，看看回应，所有这些精度都消失了。

那么，Java时钟有哪些属性，它们如何应用于我们在开始时看到的问题？

挂钟
让我们从System.currentTimeMillis()开始吧，通常，开始探索的最佳位置是用Javadoc编写的文档，并且有很多内容可供参考。下面是对我们现在最重要的内容的摘录。

/**
 * Returns the current time in milliseconds. Note that
 * while the unit of time of the return value is a millisecond,
 * the granularity of the value depends on the underlying
 * operating system and may be larger.  For example, many
 * operating systems measure time in units of tens of
 * milliseconds.
 *
 * ...
 *
 * @return  the difference, measured in milliseconds, between
 *          the current time and midnight, January 1, 1970 UTC.
 */
public static native long currentTimeMillis();

我们可以看到，时钟为我们提供了毫秒级的精度值，但实际的分辨率取决于操作系统。此外，如果我们通过测量执行时间来测量延迟，它将会低于1毫秒。
但java的时钟是可以倒退吗？Javadoc没有提到任何关于单调性的东西，所以我们需要深入挖掘，并看一下实现。
本文仅探讨Linux和MacOS的本机实现。但是，类似的技术也可以应用于其他操作系统。

该方法是原生的，因此实现取决于底层操作系统。Linux和MacOS的本机实现看起来几乎完全相同。
Linux：

jlong os::javaTimeMillis() {
  timeval time;
  int status = gettimeofday(&time, NULL);
  assert(status != -1, "linux error");
  return jlong(time.tv_sec) * 1000  +  jlong(time.tv_usec / 1000);
}

jlong os::javaTimeMillis() {
  timeval time;
  int status = gettimeofday(&time, NULL);
  assert(status != -1, "bsd error");
  return jlong(time.tv_sec) * 1000  +  jlong(time.tv_usec / 1000);
}

这些函数调用完全相同的gettimeofday系统调用。手册页可以为我们提供更多信息，但更重要的是提供一些有价值的说明：手册页。

NAME
       gettimeofday, settimeofday - get / set time

NOTES
       The time returned by gettimeofday() is affected by discontinuous
       jumps in the system time (e.g., if the system administrator manually
       changes the system time).  If you need a monotonically increasing
       clock, see clock_gettime(2).

如上所述，时间受到系统时间的不连续跳跃的影响，这可能是向后的，因此时钟不是单调的。第三个问题的答案是肯定的，这是有道理的：如果我们将当前时间改为一小时，我们仍然希望currentTimeMillis返回当前时间，即使当前时间的定义已经改变。这就是为什么它通常被称为挂钟时间，如果我们调整它，挂钟也可以及时跳回来。

当前时间的纳秒nanos 
可以采用相同的路径探索研究System.nanoTime()。让我们从Javadoc开始，它比前一个更具有吸引力的细节; 这是一段摘录。
显然，这个时钟返回的时间与任何现实世界的时间无关; 它只能用于比较同一个JVM实例中的时间戳，它相对于将来可能存在的任意“原点”，因此它可能是负数。类似地currentTimeMillis，该方法提供纳秒级精度，但不一定是纳秒级分辨率。
System.nanoTime()纳秒时间只能用于测量时间间隔，所以它应该是单调的，对吧？不幸的是，Javadoc没有说出单调性，所以下一步就是具体实现。
Linux：

jlong os::javaTimeNanos() {
  if (os::supports_monotonic_clock()) {
    struct timespec tp;
    int status = Linux::clock_gettime(CLOCK_MONOTONIC, &tp);
    assert(status == 0, "gettime error");
    jlong result = jlong(tp.tv_sec) * (1000 * 1000 * 1000) + jlong(tp.tv_nsec);
    return result;
  } else {
    timeval time;
    int status = gettimeofday(&time, NULL);
    assert(status != -1, "linux error");
    jlong usecs = jlong(time.tv_sec) * (1000 * 1000) + jlong(time.tv_usec);
    return 1000 * usecs;
  }
}

这是第一个惊喜：纳米时间确实是单调的，但只有底层操作系统支持它。公平地说，任何现代Linux服务器都支持CLOCK_MONOTONIC; 
苹果系统：

jlong os::javaTimeNanos() {
  const uint64_t tm = mach_absolute_time();
  const uint64_t now = (tm * Bsd::_timebase_info.numer) / Bsd::_timebase_info.denom;
  const uint64_t prev = Bsd::_max_abstime;
  if (now <= prev) {
    return prev;   // same or retrograde time;
  }
  const uint64_t obsv = Atomic::cmpxchg(now, &Bsd::_max_abstime, prev);
  assert(obsv >= prev, "invariant");   // Monotonicity
  // If the CAS succeeded then we're done and return "now".
  // If the CAS failed and the observed value "obsv" is >= now then
  // we should return "obsv".  If the CAS failed and now > obsv > prv then
  // some other thread raced this thread and installed a new value, in which case
  // we could either (a) retry the entire operation, (b) retry trying to install now
  // or (c) just return obsv.  We use (c).   No loop is required although in some cases
  // we might discard a higher "now" value in deference to a slightly lower but freshly
  // installed obsv value.   That's entirely benign -- it admits no new orderings compared
  // to (a) or (b) -- and greatly reduces coherence traffic.
  // We might also condition (c) on the magnitude of the delta between obsv and now.
  // Avoiding excessive CAS operations to hot RW locations is critical.
  // See https://blogs.oracle.com/dave/entry/cas_and_cache_trivia_invalidate
  return (prev == obsv) ? now : obsv;
}

突出的第一件事是巨大的注解说明块。作为软件工程师，我们知道如果有很长的评论，那么必须要进行一些狡猾的事情。
实际上，评论非常有趣。调用mach_absolute_time使用下面的RDTSC指令可能会导致在具有多个CPU插槽的机器上出现非单调行为，类似机械同情邮件列表上另一个发人深省的讨论。

所以，至少，我们可以确信在MacOS上纳米时间总是单调的，对吧？实际上，它取决于JVM版本。

上面列出的代码是在JDK-8040140的 JDK9中引入的，并且后向兼容到JDK8。

当毫秒不够时
在微秒精度的情况下gettimeofday远远超过System.currentTimeMillis()，但在转换过程中精度丢失。

jlong os::javaTimeMillis() {
  timeval time;
  int status = gettimeofday(&time, NULL);
  assert(status != -1, "linux error");
  return jlong(time.tv_sec) * 1000  +  jlong(time.tv_usec / 1000);
                                                      // ^^ precision loss
}

操作系统可以为我们提供额外的信息，我们会将其暴力丢弃，以便将其整合到一个jlong内。

如果我们真的想知道这些微观怎么办？在JDK 8中，新的JSR 310到达，这使得有可能获得一个Instant类的实例，其中包含自纪元以来的秒数和自上一秒开始以来的纳秒数。

JSR 310：日期和时间API

Instant instant = Clock.systemUTC().instant();
long epochSecond = instant.getEpochSecond();
int nanoSinceSecond = instant.getNano();

最后，所有Java开发人员都可以高精度地访问挂钟时间，对吧？不是那么快，如果我们看看JDK8中的实现，我们会发现它只是直接代表System.currentTimeMillis()。

JDK8时钟

@Override
public long millis() {
    return System.currentTimeMillis();
}
@Override
public Instant instant() {
    return Instant.ofEpochMilli(millis());
}

显然，这不是最优的，并且相应的问题JDK-8068730已经解决，因此精度提高了。它需要对JDK9 +进行更新，其中该方法在Linux上使用以下实现委托给本机调用。假设您的操作系统可以提供微秒分辨率，这个时钟就是具有纳秒精度的时钟的一个很好的例子，但只有微秒的分辨率。

JDK9 +时钟

void os::javaTimeSystemUTC(jlong &seconds, jlong &nanos) {
  timeval time;
  int status = gettimeofday(&time, NULL);
  assert(status != -1, "linux error");
  seconds = jlong(time.tv_sec);
  nanos = jlong(time.tv_usec) * 1000;
}

时间交换
以微秒分辨率获得当前挂钟时间的可能性很大，但经常需要吗？使用挂钟时间的原因之一是能够将在一台机器上发生的事件与在不同机器上发生的另一事件相关联，或者更准确地说，决定这些事件的顺序。

这些事件的性质可能非常不同。其中一些可能不是非常关键，例如日志行上的时间戳，但其中一些必须是正确的，例如由于同时写入两个值而数据库中存在冲突，并且时间戳用于确定哪个事件是持续。这种策略称为Last Write Wins，或简称为LWW。

两个客户端Alice和Bob正在尝试同时写入有两个节点的最终一致的webscale数据库。当Alice写的第一个值成功同步时，Alice的第二次写入恰好与Bob的同时发生。在这种情况下，数据库必须解决冲突，以便所有节点之间的数据保持一致。在LWW的情况下，将通过比较每次写入的时间戳来选择最新的写入。如果时钟完全同步，LWW可以完美地工作，但是，如果时钟同步性差并且第一个节点的时钟漂移到第二个节点之前，则LWW变为Lucky Write Wins - 连接到幸运节点的客户端总是赢得冲突。

NTP
确保群集中不同节点上的时钟同步的标准方法是使用网络时间协议（NTP）。NTP不仅有助于同步时钟，还有助于传播闰秒标志。
处理闰秒的传统方法是“飞跃涂抹”。负责飞跃模糊的NTP服务器可以在引入第二个之前的12小时之前和之后的12小时内分配额外的秒。在这24小时内的挂钟时间越来越慢，每秒钟的时间延长了1/86400，这可能会令人惊讶，但不会比跳回时间更令人惊讶。问题是没有多少NTP服务器支持跳跃模糊，公共NTP服务器绝对不会。
主要的云提供商Google和AWS都为NTP服务提供了飞跃涂抹支持。如果您的应用程序托管在提供NTP服务的平台上并且您关心时钟同步，那么检查NTP同步是否与提供商的NTP服务一起设置是值得的。它不仅可以帮助避免应用闰秒的恶劣后果，而且还可以显着降低同步错误，因为在单个数据中心内网络延迟通常要低得多。

在最好的情况下，使用本地NTP服务器可以将时钟漂移降低到毫秒甚至微秒，但最坏的情况是什么？关于这个主题的研究不多，但Google Spanner论文中提到了一些值得注意的结果。

在同步之间，守护进程宣告缓慢增加的时间不确定性。ε来自保守应用的最坏情况本地时钟漂移。ε还取决于时间主站的不确定性和时间主站的通信延迟。在我们的生产环境中，ε通常是时间的锯齿函数，在每个轮询间隔内从大约1到7毫秒变化。ε？因此大部分时间都是4毫秒。守护程序的轮询间隔当前为30秒，当前应用的漂移率设置为200微秒/秒，它们共同占据了0到6毫秒的锯齿边界。

- Spanner：Google的全球分布式数据库

逻辑时钟
即使我们集群中的监控显示时钟与微秒精度同步，我们也需要谨慎，如果这种假设的失败是不可接受的，我们的软件就不应该依赖它。因此，如果失败是不可接受的，我们需要知道分布式系统中事件的顺序，那么我们能做些什么呢？与往常一样，学术界提出了许多解决方案。

1.Lamport时钟
我们需要的是对系统时钟的可靠替代，因此对于每两个事件A和B，我们可以说A发生在B之前，或B发生在A之前。事件之间的这种顺序称为总顺序。
在“时间，时钟和分布式系统中事件的排序”一文中，Leslie Lamport描述了“之前发生”关系和逻辑时钟，可用于使用以下算法定义一组事件的总顺序。

发送消息：

time = time + 1;
send(message, time);

收到消息：

(message, ts) = receive();
time = max(ts, time) + 1;

在这种情况下，每个参与者Alice和Bob每次发送消息时将通过维护增加的time计数器来维持当前时间的共享视图，并且当接收到消息时，time总是大于上次接受消息时最后观察到的计数器。这样，如果Alice更新数据库的值为2，并告诉Bob关于最后一个已知状态，Bob的最终写入是先查看Alice计数器，因此它被选为数据库的最终状态。

只要我们需要定义系统中捕获因果关系的事件的总顺序，这就完美地工作。重要的是要注意，具有总顺序意味着并发事件将以某种方式排序，而不一定是最合乎现实逻辑的方式。向量时钟解决这个问题。

矢量时钟/向量时钟
为了处理真正的并发事件，我们需要一个新的定义或命令，它能够表达事件可以同时发生的情况。这种顺序称为部分顺序。这意味着对于任何两个事件A和B，可以说A是否发生在B之前，B发生在A或A和B同时发生之前。
为了确定部分顺序，可以使用以下算法，其中每个actor都有一个单独的时间计数器，并跟踪系统中任何其他actor的最新时间戳。

发送消息：

V[myId] = V[myId] + 1
send(message, V);

收到消息：

(message, Vr) = receive();
for (i, v) in Vr {
    V[i] = max(V[i], v);
}
V[myId] = V[myId] + 1;[/i][/i]

该算法在1988年描述，后来在Dynamo论文中描述了使用矢量时钟在数据库中进行冲突解决。

(与前面逻辑时钟计数器不同的是，向量时钟是逻辑时钟的列表，比如Alice[0,0]，前面一个0是Alice的时间，后面的是Bob时间)，Alice通过这种列表跟踪她自己的时间计数器以及Bob的最后已知时间计数器。这样，当Alice向Bob发送消息时，他更新了他的计数器Alice[1,0]，并且在冲突解决期间选择发送到数据库的下一个消息，而Bob的时间向量的每个分量都大于前一个向量的相应分量。

当存在真正的冲突时，矢量时钟可以帮助确定事件是否真正并发。
比如两个节点都收到[0, 1] 和[0, 1]，这两个事件不能排序，在这种情况下，数据库可以保留这两个值，并在下次读取时返回它们，让Alice或Bob决定保留哪个值，以便数据不会丢失。
但是，这些属性并非免费提供。需要与每条消息交换元数据，并且需要存储多个版本。毕竟，像Cassandra这样的一些数据库不会出于某种原因使用矢量时钟。