Need for time synchronization
Why Global Timing?
- 假设有一个全球一致的时间标准
- 会很方便
- 谁最后坐在飞机上？
- 谁在最后期限之前提交了最终拍卖出价？
- 防守动作在动作之前动了吗
时钟同步的影响
当每台机器有自己的时钟时，在另一个事件之后发生的事件可能会被分配一个较早的时间。
复制数据库更新
更新复制的数据库并使其处于不一致的状态
Time Standards
- UT1 Universal Time
- 基于天文观测
- “格林威治标准时间”
- TAI (Temps Atomique International)
- Started Jan 1, 1958
- Each second is 9,192,631,770 cycles of radiation emitted by Cesium atom
- Has diverged from UT1 due to slowing of earth’s rotation
Clocks in a Distributed System
- 电脑时钟一般不完全一致
- Skew：两个时钟之间的差异（在任何时刻）
- 计算机时钟受时钟漂移影响（它们以不同的速率计算时间）
- Clock drift rate：从一些理想的参考时钟，每单位时间的差异
- 普通的石英钟在11-12天内漂移约1秒。 （10-6秒/秒）。
- 高精度石英钟的漂移速率约为10-7或10-8秒/秒
专有名词解释
- 物理时钟
几乎所有的计算机都有一个计时电路。尽管一般用“时钟”来表达这些设备，但它们实际上不是通常意义的时钟，称为计时器(timer)更为恰当。计算机的计时器一般是一个精密加工的石英晶体，这个晶体在其张力限度以内以一定的频率震荡。
有两个寄存器与每个石英晶体相关联，一个是计数器，一个是保存寄存器。石英晶体的每次震荡使计数器减1，当减为0时，则产生一个中断，计数器从保存保持计数器重新装入初始值。每秒60次中断，每次中断称为一个时钟滴答（clock tick），时钟每滴答一次，中断服务程序就使存储器里的时间值加一。用这种方法进行（软）时钟计时。 - 时间漂移（clock skew）
多计算机系统时，尽管石英晶体震荡的频率通常是相当稳定的，但仍不能保证所有的计算机中的石英晶体以完全相同的频率在振荡。实际上，当一个系统有n个计算机时，所有n个晶体都以略微不同的速度振荡，导致时钟逐渐不同步。
时钟同步算法
假设每台机器每秒产生H次中断，软件时钟记录着过去某一时间的时间滴答数，将这个时钟值称为C。当UTC的时间为t时，机器p的时钟值Cp(t)，最理想的情况下，对于所有的p和t，都有Cp(t) = t，
dC/dt 的理想值为1。
理论上，当H=60时，计时器应每小时产生21600个滴答。实际上，计时器芯片所能达到最大的错误率大约10-5，意味着一台机器计时器每小时可以产生的滴答次数在215998到216002之间。
1-ρ ≤dC/dt≤1+ρ，这个常量ρ由厂商规定，称为最大偏移率
时间同步技术
完美的网络
-
消息总是到达，传播延迟正好是d
image.png - 发送者在消息中发送时间T.
- 接收器将时钟设置为T + d
- 同步是确切的
同步网络
-
消息总是到达，传播延迟至多为D.
image.png - 发送者在消息中发送时间T.
- 接收器将时钟设置为T + D / 2
- 同步错误最多是D / 2
在现实世界中同步
- 真正的网络是异步的
- 消息延迟是任意的
- 真实的网络是不可靠的
- 消息并不总是到达
Cristian’s Time Sync
- 时间服务器S接收来自UTC源的信号
- 进程p请求时间mr，接受时间mt来自s
- P设置时钟t + RTT/2
-
Accuracy ± (RTT/2 - min) :
image.png
Network Time Protocol
- 原理：服务器和客户端之间通过二次报文交换，确定主从时间误差，客户端校准本地计算机时间，完成时间同步，有条件的话进一步校准本地时钟频率。
-
时间同步过程
服务器在UDP的132端口提供授时服务，客户端发送附带T1时间戳（Timestamp）的查询报文给服务器，服务器在该报文上添加到达时刻T2和响应报文发送时刻T3，客户端记录响应报到达时刻T4。
image.png
这个图中用蓝色标注了主从直接来回链路的时延Sigma：
Sigma = (t4-t1)-(t3-t2)
因此，假设来回网络链路是对称的，即传输时延相等，那么可以计算客户端与服务器之间的时间误差Delta为：
Delta = t2-t1-Sigma/2=((t2-t1)+(t3-t4))/2
客户端调整自身的时间Delta，即可完成一次时间同步。
Berkeley algorithm
- Cristian’s algorithm
- 单个时间服务器可能会失败，所以他们建议使用一组同步服务器
- 它不处理错误的服务器
将AB之间的延时和误差缓存起来，NTP将服务器分成多个层，含有参考时钟的服务器（如WWV接收器）称为1层服务器（时钟本身0层），当A和B联系时，如果它的层比A高，那么它只调整自己的时间。
-
Berkeley algorithm (also 1989)
- 一组计算机的内部同步算法
- 一个master轮询从其他人（slave）收集时钟值，
- master使用往返时间来估计slave的时钟值
- 它需要一个平均值（消除任何高于平均往返时间或错误的时钟）
- 测量
- 15台电脑，时钟同步20-25毫秒，漂移率<2x10-5
- 如果master失败，可以选择一个新的master来接管（不是在有限的时间内）
-
图示过程
1.png
时间守护进程询问所有其他机器的时钟值。
The machines answer.
时间守护进程告诉大家如何调整自己的时钟。
Network Time Protocol (NTP)（续）
- Internet的时间服务 - 将客户端同步到UTC
来自冗余路径的可靠性，可扩展性，验证时间源
1 主服务器连接到UTC来源
2 辅助服务器与主服务器同步
3 同步子网 - 用户计算机中的最低级别服务器
- 使用时间服务器的层次结构
- 1类服务器具有高度精确的时钟
- 直接连接到原子钟等
- 第2类服务器只能从第1类和第2类服务器获得时间
- 3类服务器从任何服务器获取时间
- 1类服务器具有高度精确的时钟
- 同步类似Cristian的alg。
- 修改为使用多个单向消息，而不是立即往返
- 准确度：本地〜1ms，全球〜10ms
NTP Protocol
所有模式都使用UDP
-
每封邮件都带有最近事件的时间戳
- 发送的当地时间，接受的以前信息的时间
- 当前消息发送当前时间
-
收件人记录到收货时间T3（我们有T0，T1，T2，T3）
image.png
时间戳:
- t0是请求分组传输的客户端时间戳
- t1是请求分组接收的服务器时间戳
- t2是响应数据包传输的服务器时间戳
- t3是客户端响应数据包接收的时间戳
RTT:
RTT = wait_time_client – server_proc_time = (t3-t0) – (t2-t1)
Offset :
Offset = ((t1-t0) + (t2-t3))/2 = ((offset + delay) + (offset – delay))/2
- NTP服务器过滤<rtti，offseti>对，从变异中估计可靠性，允许他们选择同伴
- 互联网路径精确度为10毫秒（1个LAN）
NTP如何改变时间？
- 不能只是改变时间
- 改变时钟的更新频率
- 以更渐进的方式改变时间
- 防止不一致的本地时间戳
假设client时钟快了 ，offset<0，表示原则上A应该把它的时钟后调。这是不允许的。例如某个目标文件在调整后编译的，则比修改后的源文件时间要早。
这种修改方式必须是逐步的。假设把计时器设置为每秒产生100个中断。正常情况下，每个中断添加10ms。当减慢时，每个中断历程只添加9ms，知道校正完成。同样，通过每个中断添加11ms，时钟可以逐步往前调
