本系列文章主要介绍计算机系统中时钟的处理。主要内容包含NTP，Lamport逻辑时钟，向量时钟，TrueTime等。本文是第一篇，介绍NTP协议。
电脑的时钟
不知道你注意过没有，假如隔了好几天打开你的电脑，任务栏的时间依然是显示正确的，即使你的电脑没有联网，这是如何做到的？
计算机的主板上有一个石英晶体振荡器和一个纽扣电池。石英晶体振荡器的频率是32768Hz每秒。在通电的时候，石英晶体每振动32768次，电路就会传出信息，表示1秒钟到了，通过这种方式来记录时间。但是石英晶体会有误差，正常情况下，每天的计时误差在正负1秒钟。而且在极端温度下，比如零下二十度，误差会变大。
NTP协议架构
正是因为石英晶体误差比较大，所以1985年特拉华大学的David L. Mills设计了网络时间协议NTP（Network Time Protocol）来同步不同计算机系统之间的时钟。
NTP协议的目标是将所有计算机的时间同步到几毫秒误差内。实际上广域网可以达到几十毫秒的误差，局域网误差可以在1毫米内。NTP协议是一种主从式架构协议，使用分层的时钟源系统，每一层称为Stratum，阶层的上限是15，阶层16表示未同步设备。常见的阶层如下：
阶层0
参考（基准）时钟，主要由高精度计时设备，比如铯或铷原子钟、GPS时钟、无线电时钟。它们生成非常精确的脉冲信号，触发计算机上的中断和时间戳。
阶层1
主时间服务器，这些服务器与阶层0设备相连，在几微秒误差内同步系统时钟。阶层1服务器之间可以互相连接，进行完整性检查和备份。
阶层2
这些计算机通过网络和阶层1服务器同步。每个计算机可以查询多个阶层1服务器，阶层2计算机之间也可以互相连接。
阶层3
这些计算机与阶层2的服务器同步。
NTP协议流程
NTP协议的时钟同步过程如下：
- 客户端A发送NTP消息给服务器B，消息中包含发送时间戳 T1
- 服务器B收到NTP消息后，将接收时间 T2 写入消息中
- 服务器B发送该NTP消息给客户端A，发送时间 T3 写入消息中
- 客户端A收到该NTP消息的时间为 T4
从上面的流程中可以很容易地计算出：
AB之间的网络往返时间RTT(Round Trip Time)：δ = (T4 - T1) - (T3 - T2)
AB之间的时间偏移：θ = ( (T2 - T1) + (T3 - T4) ) / 2
推导过程：A从发送请求消息到收到响应的时间间隔是 T4 - T1，其中 T3 - T2 是B的处理时间，所以网络往返时间
δ = (T4 - T1) - (T3 - T2)。
假设A和B的时间偏差为θ，那么 T3 - θ = T3`。
T4和T3` 的间隔是半个RTT：T4 - T3` = δ / 2
把T3`和δ代入上面这个等式，得到：θ = ( (T2 - T1) + (T3 - T4) ) / 2。
NTP协议格式
NTP协议使用UDP协议来传输，端口为123，报文格式如下：
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Reference Timestamp (64) +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Origin Timestamp (64) +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Receive Timestamp (64) +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Transmit Timestamp (64) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Optional (96) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
各个字段的含义如下：
- LI Leap Indicator: 2比特，用来警告是否有闰秒或者未和上级同步。具体定义如下:
+-------+----------------------------------------+
| Value | Meaning |
+-------+----------------------------------------+
| 0 | no warning |
| 1 | last minute of the day has 61 seconds |
| 2 | last minute of the day has 59 seconds |
| 3 | unknown (clock unsynchronized) |
+-------+----------------------------------------+
- VN Version Number: 3比特，协议版本，目前是4。
- Mode: 3比特，工作模式，具体定义如下：
+-------+--------------------------+
| Value | Meaning |
+-------+--------------------------+
| 0 | reserved |
| 1 | symmetric active |
| 2 | symmetric passive |
| 3 | client |
| 4 | server |
| 5 | broadcast |
| 6 | NTP control message |
| 7 | reserved for private use |
+-------+--------------------------+
- Stratum: 8比特，阶层，具体定义如下：
+--------+-----------------------------------------------------+
| Value | Meaning |
+--------+-----------------------------------------------------+
| 0 | unspecified or invalid |
| 1 | primary server (e.g., equipped with a GPS receiver) |
| 2-15 | secondary server (via NTP) |
| 16 | unsynchronized |
| 17-255 | reserved |
+--------+-----------------------------------------------------+
Poll: 8比特，轮询间隔时间，两个NTP报文之间的时间间隔，用2的幂表示。
Precision: 8比特，系统的时钟精度，用2的幂表示。
Root Delay: 32比特，本地到主时钟源的往返时间RTT。
Root Dispersion: 32比特。
Reference Identifier: 32比特，上层时钟源的标识。
Reference Timestamp: 64比特，本系统时钟最后一次被设置的时间。
Originate Timestamp: 64比特，NTP报文离开发送端时发送端本地时间，也即前面图中的T1。
Receive Timestamp: 64比特，NTP报文到达接收端时接收端端本地时间，也即前面图中的T2。
Transmit Timestamp: 64比特，NTP报文离开接收端时接收端本地时间，也即前面图中的T3。
NTP的误差
NTP协议在广域网可以达到几十毫秒的误差，局域网误差可以在1毫米内。误差最大的一个原因是发送请求和接收响应这两个阶段的网络时间可能是不一样的。前面我们推导时间偏移公式的时候，假设网络往返发送和接收阶段的时间是一样的，但是实际网络中，这两个阶段走的路由可能是不一样的，所花的时间也可能不一样，计算的时间偏移也不准确，这样就造成了广域网的误差可能达到几十毫秒甚至更高。局域网中因为网络比较稳定，经过的路由器也比较少，所以误差可以到1毫米内。
