时钟同步 (2020)

欢迎来到 Signals And Threads，深入讨论来自 Jane Street 的技术堆栈的每一层。我是罗恩·明斯基。今天我们要讨论一个看似简单的话题：时钟同步。我认为没有什么比尝试编写计算机程序来操纵时间来让你相信时间是一件非常复杂的事情，它以 16 种不同的方式复杂，从时区到闰秒再到各种其他疯狂的事情，但其中之一这个世界真正有趣的角落是如何让大型计算机网络上的所有时钟大致一致？换句话说，时钟同步。所以我们将与 Chris Perl 讨论这个问题，他是一名系统管理员，自 2012 年以来一直在 Jane Street 工作。Chris 比我曾经合作过的任何人都要好，在深入研究复杂系统的可怕细节并了解它们如何工作方面以及如何使它们更好地工作，他在这里做了很多工作，特别是在时钟同步方面，并且在此过程中，重做了我们的整个系统来进行时钟同步，所以他有机会真正学习很多关于这个话题。克里斯，首先，您能否简要介绍一下计算机时钟的工作原理？所以，我想粗略的要点是你有一些振荡器，一个小晶体有效地在计算机内部以某个频率振荡，这驱动了操作系统将在某种程度上处理的中断 - 可能有很多我只是略过这里的一些细节——但这会导致操作系统中发生的中断。操作系统正在使用它来推导它的时间概念，所以如果你有一个真正高质量的振荡器，并且这些定时器中断以正确的速率发生，这样你就可以实时跟踪可能刚刚发生的情况，并且如果您的振荡器非常好且非常稳定，那么您实际上可以非常接近正确的时间。但事实是，大多数计算机都带有相当糟糕的振荡器，它们会因各种原因（例如发热）改变它们的频率，所以如果您使用计算机编译 Linux 内核或类似的东西，那可能会改变热量分布，改变频率振荡器，实际上会改变你保持实时的效果。当我们天真地将时钟同步视为人时，我们会将其视为“我要去设置我的时钟”。我将查看现在的时间并调整我的时钟以匹配任何实时时间，但您实际上在这里谈论的是另一回事。你说的不仅仅是设置现在的正确时间，而是保持那个时间正确，本质上保持同步前进的速度。正确的。如果您能在所有计算机中以超便宜的价格获得真正、真正高质量的振荡器，那么您会喜欢它，然后您就不需要进行大量调整来让它们保持正确的时间，但这确实是昂贵的。你可以买这样的东西，它们只是要花很多钱。因此，您说计算机中发生的热量和其他各种事情会导致计算机内部出现这种向前移动的速度。这些有多准确？能不能给我一种数字感，这些东西飘了多远？我们运行的东西，我们捕获其中的一些统计数据，我们看到对它们应用了频率校正的机器，比如说，百万分之 50，这就像每秒微秒，所以大约每秒钟几秒一天，这就是你如何结束漂流。但我敢肯定，如果你的桌子底下有一个超级旧的桌面，你从你父母那里偷来的东西，然后你试图重建成一个 Linux 机器，那么你的数字可能比这更糟糕。就像来自知名供应商的一种相对较新的一代服务器，您正在谈论大约每秒 50 到 100 微秒，它们可能会偏离校准。好的，因此时钟同步是尝试使您在整个数据中心和多个数据中心中拥有的所有时钟彼此同步的过程。这是正确的思考方式吗？

我认同。 “同步”，是一种有趣的说法，对吧？如果您能够立即询问网络上的两个随机服务器，在同一确切时间点是什么时间，如果您能以某种方式神奇地做到这一点，他们会同意一些相对较小的边际错误，我认为这就是我们所说的时钟同步的意思。如果你能以某种方式神奇地冻结时间并去询问网络上的每一台计算机，“嘿。你觉得现在几点了？”他们都会在您可以定义的某个错误范围内大致同意。对。这个基本模型实际上假设有一个明确定义的概念，即瞬间同时存在的含义，由于相对论和类似的东西，这并不完全正确，但我们将主要忽略这一点。所以，我想你在这里强调的一个属性是让时钟彼此一致，这是其中的一部分，但还有另一部分，对，就是让时钟与某些外部参考一致。有一些类似的概念，世界认为时间是多少？那么，外部参考来自哪里？我不是这方面的专家，但我会给你一种 10,000 英尺的视野。您在世界各地都有各种物理实验室，例如英国的 NPL 和世界其他地方。他们都可以测量他们认为的时间，使用诸如氢脉泽之类的东西和某种非常准确的原子方法。他们将所有这些东西提供给一个单一的来源，该来源对其进行平均或进行某种加权，以得出正确的时间，然后您将这种魔法传递给空军，然后由空军发送直到 GPS 星座。 GPS 有一种机制可以从 GPS 卫星获取时间到 GPS 接收器，所以如果你是一个运行计算机网络的人，并且你有兴趣将你的时钟与 UTC 之类的东西同步到相对较高的精度，实际上是格林威治标准时间，它只是一种没有应用时区的当前时间。如果你有兴趣这样做，你可以做的是你可以去一个供应商那里买一个叫做 GPS 设备的东西，它可以连接到屋顶上的小天线。它可以从 GPS 星座接收这个信号，基本上给你时间，准确度大概在 100 纳秒左右。因此，您已经获得了一种被馈送到 GPS 星座的原子测量，直到您作为计算机网络的运营商可以购买的 GPS 接收器。出于本次对话的目的，我们将这些 GPS 接收器视为接收到的关于时间的智慧，我们的工作是弄清楚如何在计算机网络内部制造所有不同的设备彼此同意并同意该外部参考。如果你将自己置于金融监管机构的地位，并且所有这些不同的参与者都在那里用计算机系统做事，然后发生了一些奇怪的事情，并且你想对导致的事件进行总体排序这件疯狂的事情——或者是什么导致了这件好事，谁知道呢——但你想要对事件进行全面排序。如果人们没有良好的时钟同步，对于某些外部来源，您无法将参与者 A 的时间戳与参与者 B 的时间戳进行比较，因此如果您要规定每个人都必须有在某个误差范围内的时间，您知道这些时间戳是否在该错误范围内，那么我无法确定排序，但如果它们比这更远，那么我可以确定排序。我可以知道哪个先来，哪个第二，这非常有用。所以这就是我们行业特有的动机，但其他行业的人不是也很关心时钟同步吗？我原以为还有其他原因会促使您想要同步网络上的机器。哦没问题。有很多不同的东西。我的意思是，就像一般的系统管理员主题一样，很多时候您想从计算机网络上的所有系统收集日志，并且出于各种原因想要分析它们。也许是因为您担心入侵者。或者可能是因为您只是想了解事物的运作方式，如果您的时钟不同步，则很难理解系统 B 上可能发生的事情以及它们与系统 A 的关系，因为两者时间戳不是 - 如果它们不同步，您就无法比较它们。

我想也有一些分布式系统，需要时钟的算法原因。当然，某些类型的分布式算法最终会使用时钟作为打破系统之间联系的方式，因此这至少需要一定程度的合理同步。当然。还有其他广泛使用的网络协议需要时钟同步，但时钟同步的精确度要低得多。 Kerberos 是一种广泛使用的身份验证协议，它要求时钟在五分钟内同步，其想法是阻止重放攻击之类的东西，确保有人在几天内无法获取您的凭据之前再使用它们，那种东西。所以在那里，误差线很宽，但仍然需要某种同步。对。我想这是考虑同步时的一个普遍主题：不同的应用程序需要不同级别的同步，但更紧密的同步永远不会受到伤害。当你开始进入下限时肯定会有权衡，但是是的。如果它们都是免费的，当然，我希望它们完全一样。人们通常如何解决时钟同步这个问题？什么是标准工具？大多数人，您只是将您的发行版作为 NTP 守护进程运行。 NTP 代表网络时间协议，直到不久前，我还认为它使用了某种魔法，它知道如何与 Internet 上的某些服务器或某些本地服务器通信。可能然后与互联网上的服务器交谈，它会将您的时钟与这些服务器同步。它交换一些数据包，也许需要一点时间，也许几分钟，也许更长。你可能不明白为什么，但最终，你的时钟相对同步到几十毫秒左右。就像我说的，有很长一段时间，我只是假设它是魔术，并没有想太多，然后在某个时候，我接到任务，在简街，实际看看其中的一些东西并尝试满足一些比标准的几十毫秒同步更难的要求。所以我实际上去了，就像，“好吧。好。 NTP 如何从第一原则做到这一点？”对？就像，让我们去读一些大卫米尔斯的论文。让我们去看看我们是否真的可以自己推理出来。归根结底，只有四个时间戳。它周围有很多更复杂的东西，但它的核心是这四个时间戳。假设我是客户端，而你是服务器。首先，我会向您发送一个数据包，但在此之前我会写下时间戳。当您收到该数据包时，您会记下时间戳。然后，您向我发送回复，然后在此之前写下时间戳。最后，当我收到那个回复时，我会写下一个时间戳。这似乎不是开创性的，但仅凭这四个时间戳我就可以计算出两个重要的数字，偏移量和延迟。偏移量是我的时钟与你的时钟相差多远，所以如果你认为现在是下午 12 点，而我认为是下午 12:05，那么偏移量就是五分钟。延迟是这些数据包穿越网络所用的时间。为了计算这些数字，你基本上需要一个方程组，对我来说，一个重要的方面实际上是用一张纸和一支铅笔写下来，自己解决这些方程，是理解这里面有一种巨大的假设协议，第一个数据包的延迟，我打上时间戳然后你做的，以及第二个数据包的延迟，你打上时间戳然后我做，假设这些时间是相同的，如果它们不相同他们引入了所谓的错误，这是一个非常重要的方面。这是一个假设，以便您可以实际求解这些方程以获得偏移和延迟。

您能否解释一下取决于发送时间和接收时间之间的对称性的计算是什么？这些延迟是将它们联系在一起的原因，对吗？您知道如果时钟同步，您就知道您使用的时间戳减去我使用的时间戳应该等于数据包到达您的延迟，对吗？反之亦然。我的时间戳，从我收到的第二个开始，减去你的时间戳应该等于数据包从你到我的延迟。你就像，“好吧。我用这些信息做什么？”然后你说，“如果我假设这两个延迟是相等的呢？”如果我假设这两个延迟相等，那么我可以开始重新排列等式的各个部分。然后这就是您如何实际解决延迟和偏移的方法。这两个时间戳在服务端的作用是什么？所以，如果你问我现在几点了，我会在收到的时候写下来，然后写下我寄回的时间。你可以想象一个只有三个时间戳的更简单的协议。然后你就假设我记下的时间发生在那个时间间隔的中间，也就是你发送第一个方法和接收第二个消息之间的时间间隔。你怎么知道中间是什么时候，对吧？操作系统会发生很多变幻莫测的事情，比如如果你在两端打上时间戳，一旦你收到数据包就给它打上时间戳，然后也许你必须做一些工作，然后就在你发回之前给它打上时间戳，这就是你如何最接近我提到的那些代表从一个到另一个的实际网络延迟的差异。我猜你在这里做的一个额外假设是，在第一个时间戳和第二个时间戳之间的那段时间里，你最好假设时钟前进的速度是正确的。我认为这会给等式带来另一个错误项。我认为，它通常非常小，对吗？如果你只是，它肯定看起来是你可以在实践中忽略的东西。因为如果你只看百万分之几，或者不管你在说什么，就真正的计算机时钟有多少漂移而言，我认为这实际上非常小。是的，您已经得到了计算机上运行的时间守护程序应用的更正，它使时钟保持同步。据推测，这种通信的服务器端也从某个参考时钟或 NTP 中某种更高上游层的某个地方花费时间，例如比它更好的时钟，例如 GPS 接收器，并且它已经应用了某种校正对操作系统说：“嘿，我目前认为频率下降了这么多。当你把时间还给我时，请纠正这一点。”所以，我觉得你最大的——我猜你在实践中可以忽略——你最大的担忧是在这两个时间戳之间是否发生了巨大的变化，比如温度上升或下降了很多很多度或类似的东西那个频率校正现在完全不正确。好的，现在我们有了一个网络协议。放置一个时间戳，发送一条消息，另一个时间戳，另一个时间戳，你会得到它。现在启动这一切的计算机已经估计了它的时钟关闭了多少。那它有什么作用呢？

在简单的世界中，您可以设置时间。你可以只是，你可以说，“时间应该是 X”，但这通常不是大多数网络时间协议守护进程的工作方式。他们会做的是，他们会从单个服务器中获取大量样本，但是很多时候您配置了多个服务器，因此您将从多个服务器中获取许多样本，并且您将对这些事情应用不同的标准决定你是否应该考虑它们。我认为 NTPD 的参考实现有一个“爆米花尖峰”的概念，如果你的偏移量，你知道，如果你已经取回 30 个样本，而且它们看起来都差不多，但是你会得到一个非常疯狂的关闭，你只是说，“我会忽略那个，因为这可能只是由于网络中某处的疯狂排队或类似的事情。”你可以把这看作是一种投票算法：你有一堆不同的预言机告诉你时间是什么，你把它们放在一起，并有某种方法来计算关于什么的聚合假设目前的时间是试图对错误和删除异常值等保持鲁棒性。是的，我认为这是对的。你试图找出对你撒谎的人，对吗？您可能正在与上游交谈的一些服务器可能只是告诉您不正确的事情。它们通常以 NTP 的说法被称为 falsetickers，而那些不是 falseticker 的就是真正的嵌合体。我不确定为什么会出现这些名称，但如果您在 Internet 上浏览，您可能会看到这些名称。所以你试着挑出那些告诉你真相的人。您对它们应用了一些其他各种启发式方法，以尝试找出您认为最好的方法，对吗？哪些可能具有最小的误差线——尽管您可能认为这些是使用它们的不错来源，但其中一些可能具有比其他更宽的误差线，对，就像您的样本可能比其他样本代表的范围更广——所以你试着找出哪些是最好的，然后你用它来告诉你的操作系统有效地加快或减慢它的频率校正，以了解它的偏差，并随着时间的推移尝试消除该错误。您不会只是突然调整系统认为的时间。大多数时间守护进程不会主动地计时。这样做的原因是大多数应用程序不会在时间急剧变化时享受，尤其是当它在负方向上急剧变化时。这突出了您希望时钟具有的另一个特性，我们还没有触及，即：我们说过我们希望我们的时钟准确。你判断他们正确的标准是你去找他们问他们现在几点了，他们给出的数字非常接近。但是还有一个你想要的特性，那就是你想让时钟，在微观意义上，每秒前进大约一秒，并且你特别希望它永远不会倒退，因为计算机上有很多算法，这使得隐含地假设，你知道，天真地合理，时钟只会向前，当你允许时钟向后跳时，很多事情都会搞砸。对。那么，一种方式......