PDF时间，但更快
一场关于时间的计算冒险，带您穿梭镜中世界
Theo Schlossnagle，Circonus
偶尔，你会发现自己身处兔子洞中，不确定自己身在何处，也不知道现在几点。本文将呈现一场关于时间的计算冒险，带您穿梭镜中世界。
第一个前提由已故的道格拉斯·亚当斯在《银河系漫游指南》中完美地概括出来：“时间是一种幻觉。午餐时间尤其如此。” 当时间的概念与以每秒数十亿次运算速度运行的解耦计算机网络碰撞时，结果是……嗯，事实是，你永远无法真正知道现在几点。这就是为什么莱斯利·兰波特的关于兰波特时间戳的开创性论文对行业如此重要的原因，但本文实际上是关于挂钟时间，或者对其进行合理有用的估计。
即使在今天的计算机上，也可能在不到一纳秒的时间内执行一条指令。当白兔在《爱丽丝梦游仙境》中看他的怀表时，他看到的是一纳秒前的时间，因为光从表盘上的指针传播到他的眼睛——假设路易斯·卡罗尔的永恒故事发生在真空中，并且兔子将怀表放在离眼睛三分之一米的地方。
当您想到一个分布式系统，其中快速计算机集群彼此之间的距离通常超过一个光纳秒时，可以理解，要精确到纳秒级地对一个在一个地方开始并在另一个地方结束的事情进行计时是困难的；这是物理学家的领域，而不是像我们这样的、使用在自己都无法管理的环境中运行的商用计算硬件的普通人。更让新手感到不安的是，今天的每台计算机实际上都是一个分布式系统本身，每个 CPU 核心都有自己的时钟在滴答作响，具有略有不同的频率和通用的起始感。
尽管如此，计算机需要给用户提供时钟的错觉。没有它，我们就不会知道现在几点。随着计算机变得越来越快，我们能够提高系统的性能，但性能工程的一个基本原则是，我们无法改进我们无法衡量的东西；所以我们必须衡量。基本的悖论是，随着我们衡量的东西变得越来越小，衡量的成本仍然是固定的，因此变得相对巨大。
坠落的开始...
在 Circonus，我们编写一个快速且不断变得更快、更高效的数据库。我们将精力投入到这个看似无止境的旅程中，因为我们以大规模运营，我们榨取的每一分效率都会降低我们的 COGS（销货成本），并为我们的客户提供更好的服务，并且从根本上提高了遥测收集和分析的成本效益，使其接近合理的“监控一切事物”的经济性。在这种背景下...
假设我们希望操作的平均延迟达到一微秒。现在让我们围绕这个数字做一些说明。我将对硬件的某些方面做一些说明，但我将真正只关注过去几年的硬件。当您和我喜欢用秒来思考时，计算机并不关心时间这个概念。它们只关心时钟滴答。
TSC
在线 CPU 始终以某个频率向前推进，这个频率的周期称为滴答。为了节省功耗，许多计算机可以在不同的省电状态之间切换，这会导致 CPU 的频率发生变化。如果使用 CPU 的频率进行计时，这可能会使准确地判断高精度时间变得非常困难。现代 CPU 上的每个核心都有一个 TSC（时间戳计数器），用于计数已经过去的滴答次数。您可以使用巧妙命名的 rdtsc 汇编指令读取此计数器。此外，现代 CPU 具有称为不变 TSC 的功能，该功能保证滴答发生的频率不会因任何原因而改变（但主要是为了省电模式的更改）。我的开发机器具有一个不变 TSC，其滴答频率约为每纳秒 2.5999503 次。其他机器具有不同的频率。
在 Unix 机器上确定操作花费多长时间的标准工具是 clock_gettime(CLOCK_MONOTONIC,...) 或 gethrtime()。这些调用返回自过去某个任意固定点以来的纳秒数。此处显示的示例使用 gethrtime()，因为它编写起来更短。
hrtime_t start = gethrtime();
some_operation_worthy_of_measurement();
hrtime_t elapsed = gethrtime() - start;
当测量这些东西时，gethrtime() 调用本身会花费一些时间。要问的问题是：它返回的时间相对于 gethrtime() 调用本身的开始和结束位置在哪里？这可以通过基准测试来回答。测量开始和结束引入的偏差与其对总体运行时间的贡献有关。换句话说，如果使要测量的“操作”在多次迭代中花费很长时间，则可以将测量偏差降低到接近于零。使用 gethrtime() 对 gethrtime() 进行计时将如下所示
#define LOTS 10000000
hrtime_t start = gethrtime();
for(int i=0;i<LOTS;i++) (void)gethrtime();
hrtime_t elapsed = gethrtime() - start;
double avg_ns_per_op = (double) elapsed / (double)LOTS;
瞧，一个基准测试诞生了。此外，您实际上可以通过在汇编中用对 rdtsc 的调用括起测试来测量测试中经过的滴答数。请注意，您必须将自己绑定到盒子上的特定 CPU 才能使其有效，因为不同核心上的 TSC 时钟没有相同的“开始”概念。
如果在我们的两个主要平台（Linux 和 Illumos/OmniOS 在 24 核 2.6-GHz Intel 机器上）上运行此程序，则结果如下
| 操作系统 | 调用 | 调用时间 |
|---|---|---|
| Linux 3.10.0 | gettimeofday |
35.7 纳秒/操作 |
| Linux 3.10.0 | gethrtime |
119.8 纳秒/操作 |
| OmniOS r151014 | gettimeofday |
gettimeofday |
| OmniOS r151014 | gethrtime |
304.6 纳秒/操作 |
gethrtime
297.0 纳秒/操作
(119.8*2)/(1000 + 119.8*2) -> 19.33%
第一个观察结果是，Linux 对这两个调用的优化明显优于 OmniOS。这实际上已作为 Joyent 的 SmartOS 中的 LX 品牌工作的一部分得到解决，并将很快上游到 Illumos，供 OmniOS 一般使用。唉，那还不是最糟糕的事情：客观地确定现在几点，对于微秒级的计时来说太慢了，即使是上面较低的 119.8 纳秒/操作（纳秒每操作）的数字也是如此。请注意，gettimeofday() 仅支持微秒级精度，因此不适用于对更快的操作进行计时。
在仅 119.8 纳秒/操作的情况下，用它来括起一个一微秒的调用将导致
因此，19.33% 的执行时间用于计算计时，这甚至不包括记录结果所花费的时间。这里要实现的一个好目标是 10% 或更少。那么，我们如何才能达到这个目标呢？
查看我们的工具
这些具有不变 TSC 的现代 CPU 具有 rdtsc 指令，该指令读取 TSC，但没有提供关于您正在哪个 CPU 上执行的洞察力。这将需要要么在调用前加上 cpuid 指令，要么将执行线程绑定到特定的核心。前者增加了滴答计数；后者完全不方便，并且真的会破坏内核可能提供的任何高级 NUMA（非统一内存访问）感知调度。基本上，绑定 CPU 提供了一个超快但限制过多的解决方案。我们只是希望 gethrtime() 调用能够工作并且速度很快。
我们不是唯一有这种需求的人。出于普遍公认的需求，引入了 rdtscp 指令。它提供 TSC 中的值和一个可编程的 32 位值。操作系统可以将此值编程为 CPU 的 ID，并在单个指令中发出足够多的信息。不要被欺骗；这条指令并不便宜，在这台机器上测量为 34 个滴答。如果您将该指令调用编码为 uint64_t mtev_rdtscp(int *cpuid)，它返回 TSC 并可选地将 cpuid 设置为编程值。
这里的第一个挑战是了解频率。这是一个简单的计时练习
mtev_thread_bind_to_cpu(0);
hrtime_t start_ns = gethrtime();
uint64_t start_ticks = mtev_rdtscp(NULL);
sleep(10);
hrtime_t end_ns = gethrtime();
uint64_t end_ticks = mtev_rdtscp(NULL);
double ticks_per_nano = (double)(end_ticks-start_ticks) / (double)(end_ns-start_ns);
当测试此解决方案以计时作业的执行时，即使是最简单的作业，下一个挑战也变得非常清楚
uint64_t start = mtev_rdtscp(NULL);
*some_memory = 0;
uint64_t elapsed = mtev_rdtscp(NULL) - start;
这通常需要大约 10 纳秒，假设在赋值期间没有发生主要的页面错误——设置一块内存需要 10 纳秒！请记住，这包括调用 mtev_rdtscp() 的平均时间，该时间略高于 9 纳秒。那实际上不是问题。问题是，有时我们会得到巨大的答案。为什么？我们切换了 CPU，并且两个 TSC 调用的输出都在报告完全不相关的计数器。因此，为了重述问题：我们必须关联这些计数器。
用于偏差评估的代码有点多，无法在此处包含。基本思想是，我们应该在每个 CPU 上运行一个校准循环，该循环测量 TSC*ticks_per_nano 并评估与 gethrtime() 的偏差，同时考虑 gethrtime() 的运行时间。与大多数校准循环一样，偏差最大的被丢弃，其余的取平均值。这基本上可以追溯到中学数学，以找到线性截距方程：y = mx + b，或
gethrtime() = ticks_per_nano * mtev_rdtscp() + skew
由于 TSC 是每个 CPU 的，因此您需要在每个 CPU 的基础上跟踪 m 和 b（ticks_per_nano 和 skew）。
另一个细微之处在于，这两个值共同描述了 CPU 的 TSC 和系统的 gethrtime() 之间的转换，并且它们是估计值。这意味着两件重要的事情：（1）它们需要定期更新以纠正校准和估计中的误差；（2）它们需要原子地设置和读取。这就是 cmpxchg16b 指令的用武之地。
此外，此校准工作每五秒在一个单独的线程中执行，并且我们尝试使该线程在实时调度程序上具有高优先级。事实证明，即使没有更改优先级或调度类的能力，这一切也运行良好。
额外好处
由于我们显然必须校正偏差以与系统 gethrtime() 对齐，并且 gethrtime() 相对于过去的哪个点是任意的（根据文档），因此我们选择将该“任意”点设为 Unix 纪元。无需额外的指令，现在可以使用替换的 gethrtime() 来支持 gettimeofday()。因此，y = mx + b 实际上实现为
nano_second_since_epoch = ticks_per_nano * mtev_rdtscp() + skew
显然，只有当我们重新校准时，我们才会获得对挂钟的更改（通过 adjtime() 等）。
安全
显然，事情可能会而且确实会出错。各种故障安全机制已到位，以确保在优化变得不安全时行为正确。默认情况下，如果检测到缺少不变 TSC，则系统将被禁用。如果校准循环失败时间过长（15 秒），则 CPU 将被标记为坏并禁用。在初步性能测试期间，如果系统的 gethrtime() 可以击败仿真，那么我们将禁用。如果所有这些测试都通过，我们仍然会检查底层系统是否可以比我们模拟的 gettimeofday() 更快地执行 gettimeofday()；如果是，我们将禁用 gettimeofday() 仿真。目标是使 mtev_gethrtime() 与 gethrtime() 一样快或更快，并使 mtev_gettimeofday() 与 gettimeofday() 一样快或更快。
结果
总体结果比预期的要好。最初的目标只是为我们在 Illumos 上的实现提供一种方法，以满足 Linux 的性能。ZFS 的价值非常深刻，虽然 Linux 在特定领域具有一些性能优势，但如果您存储的数据发生无法检测到的损坏，那也没什么大不了的。
| 操作系统 | 调用 | 在实现中可以进行进一步的优化，但我们现在已经停止了，因为已经实现了最初的目标。此外，为了本次测试的目的，我们已经可移植地构建了代码。如果我们在使用 AVX（高级向量扩展）指令集的机器上编译 -march=native，我们可以找到几个纳秒。 | 相对于微秒级的努力，大约 40 纳秒的 gethrtime() 可以被认为足够慢，确实如此，因此仍然需要非常谨慎的选择。同样真实的是，40 纳秒的 gethrtime() 可以为用户空间检测开辟一个全新的可能性世界。它肯定让我们对一些惊人的事情大开眼界。 |
系统调用时间 |
|---|---|---|---|---|
| Linux 3.10.0 | gettimeofday |
35.7 纳秒/操作 | 35.7 纳秒/操作 | Mtev 变体调用 |
| Linux 3.10.0 | gethrtime |
119.8 纳秒/操作 | 加速 | gettimeofday |
| OmniOS r151014 | gettimeofday |
gettimeofday | 119.8 纳秒/操作 | mtev_gettimeofday |
| OmniOS r151014 | gethrtime |
304.6 纳秒/操作 | 40.4 纳秒/操作 | gethrtime |
297.0 纳秒/操作
mtev_gethrtime
47.6 纳秒/操作
gettimeofday
304.6 纳秒/操作
mtev_gettimeofday
39.9 纳秒/操作
gethrtime
297.0 纳秒/操作
mtev_gethrtime
40.4 纳秒/操作
加速比
所有这些都来自免费的 https://github.com/circonus-labs/libmtev/blob/master/src/utils/mtev_time.c。截至撰写本文时，Linux 和 Illumos 是受支持的平台，而 Darwin 和 FreeBSD 没有“更快的时间”支持。libmtev 中更快的时间支持是 Riley Berton 和 Theo Schlossnagle 共同努力的成果。
Theo Schlossnagle 是 Circonus 的创始人兼首席执行官，他在那里倾注了他的心血、灵魂和智慧，通过大规模数值数据分析来改善监控世界。Schlossnagle 是一位广受尊敬的行业思想领袖，他是 可扩展的互联网架构 （Sams Publishing，2006 年）的作者，并且是全球技术会议的常客。他创立了 OmniTI，一家互联网咨询公司，该公司已帮助全球超过 10% 的大型网站。从 OmniTI 开始，他孵化了 Message Systems，该公司为全球最大的互联网公司提供消息传递基础设施软件。他获得了约翰·霍普金斯大学的计算机科学学士和硕士学位；此外，他还曾在 JHU 的网络和分布式系统中心花费了大量时间研究分布式系统。他喜欢与妻子和三个女儿在他们在马里兰州的家中共度时光。
图片由 John Tenniel 提供，来自爱丽丝梦游仙境 (1865) 和爱丽丝镜中奇遇记 (1871)
相关文章
被动测量 TCP 往返时间
- Stephen D. Strowes
仔细观察 TCP 的 RTT 测量
https://queue.org.cn/detail.cfm?id=2539132
一秒钟的战争（你会在什么时间死去？）
- Poul-Henning Kamp
随着越来越多的系统关心秒级和亚秒级的时间，找到解决闰秒问题的持久解决方案变得越来越紧迫。
https://queue.org.cn/detail.cfm?id=1967009
互联网上稳健计时的原则