逻辑时钟与物理时钟

逻辑时钟通过因果关系对事件进行排序，而不参考真实时间；而物理时钟同步则在漂移的情况下，使不同机器的实时时钟保持接近。

Definition

逻辑时钟为每个事件分配一个整数时间戳，该时间戳在每个进程中单调递增，并在通信中增加，从而捕获因果顺序；物理时钟同步是调整机器硬件时钟的过程，使其读取近似相同的真实时间。

Scope

本主题涵盖了Lamport的逻辑（标量）时钟及其所遵循的“先发生”关系，如何从逻辑时间戳构建全序，以及物理时钟同步——包括限制漂移、通过交换时间戳估计偏移量，以及实践中使用的算法（Cristian方法、Berkeley算法、NTP）。它对比了何时因果逻辑时间足够，以及何时真正需要实时。

Core questions

• 如何分配时间戳以使其遵循因果“先发生”关系？
• 如何从逻辑时钟构建事件的一致全序？
• 在网络延迟和漂移可变的情况下，物理时钟能同步到何种程度？

Key theories

Lamport逻辑时钟

每个进程维护一个计数器，在每个事件发生时递增并在消息中携带；由此产生的时间戳遵循“先发生”关系，并通过进程标识符打破平局，从而产生与因果关系一致的全序。

概率和往返同步

Cristian方法通过测量往返时间并假设对称延迟来估计远程时钟，从而提供网络上可实现的同步误差的概率界限。

网络时间协议

NTP将时间服务器组织成一个分层结构，并使用重复偏移测量值的统计过滤来将互联网上的时钟校准到毫秒以内。

Clinical relevance

逻辑时钟在不信任挂钟时间的情况下，对复制存储和消息队列中的操作进行排序；而物理同步是时间戳排序数据库、分布式跟踪和依赖于有界时钟误差的安全协议的基础。

History

Lamport于1978年发表的逻辑时钟论文将分布式系统中的时间重新定义为因果而非物理概念；与此同时，Cristian等人开发了概率同步，而Mills的NTP成为保持互联网时钟对齐的标准机制。

Debates

操作排序中的逻辑时间与物理时间

逻辑时钟在不信任硬件时钟的情况下保证因果正确性，但无法将事件与真实时间关联；物理时钟允许实时推理，但当漂移超过消息延迟时，存在排序不正确的风险，这促使了混合方法的出现。

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

如果a的Lamport时间戳小于b，那么a是否发生在b之前？

不一定——较小的时间戳与“先发生”一致，但并不意味着它，因为并发事件可以接收有序的时间戳。要精确判断因果关系，您需要向量时钟，而不是标量逻辑时钟。