分布式系统的时间问题
2018-04-17 本文已影响0人
小忍甜甜圈
由于在分布式系统中没有绝对的全局时钟，各个物理设备上的本地时钟也不是准确的，所以为了解决一些时序的问题，形形色色的算法和优化措施被提出来了。
晶振和时钟偏移
在计算机中主要通过晶体的震荡周期进行计时，晶体的震荡周期决定了单机的时钟分辨率。比如计算机中使用的是一个晶振12Mhz的石英，那么时钟周期就是1/12us。计算机无法分辨更细的时间间隔了，这对高精度要求的系统造成了巨大的挑战。
另外，时钟频率也可能因为温度等外部因素导致时钟偏移，普通的石英晶体的漂移率大约10e-6 s/s，也就是12天左右会有1s的偏差。这对微秒精度的系统同样造成了困扰。比如GPS等需要精确地时间戳来定位的系统，时间的精度影响了定位的准确性。
时间正确性
我们通过外部同步和内部同步的方式来实现时钟正确性。
- 外部同步: 设置同步范围D>0, UTC时间源S，只要时钟C与S在任意时间点上的欧氏距离小于D，那么就处于外部同步状态。
- 内部同步: 系统内部时钟在D范围内一致，也就是说时钟没有过大的偏移。
时钟正确性在不同场景下有不同的提法，一种提法是时钟的漂移率始终在一个设定范围内。另一种较弱的提法是要求时钟始终保证单调性。比如编译工具make会根据时间戳重新编译文件，假如在设置一个文件的时间戳以后，把时钟向后偏移了一段时间，然后修改了文件，那么make将会错误的不编译这些文件。另一个例子是密码学中使用时间戳防止重放攻击，如果时间向前偏移量超过了可接受阈值，那么就会很容易受到攻击。
ntp同步服务
ntp(Network Time Protocol)，网络时间协议定义了时间服务的体系结构以及在互联网上发布时间信息的协议。ntp的主要设计特色有:
- 提供一个服务，能够让跨互联网用户能够跟UTC时间精确同步
- 提供一个能在漫长的链接丢失中生存的服务: 提供冗余的服务器并在服务器之间提供冗余的路径
- 提供保护，防止对时间服务的干扰。
ntp使用以下三种模式相互同步,组播、过程调用和对称模式:
- 组播模式应用于高速LAN上，一台或多台服务器定期将时间广播到LAN中的其他计算节点上
- 过程调用模式，类似于Cristina过程:
进程p估算到远程进程q的延迟(比如多次使用ping获得多个T_r，取最小值)，然后请求q获得时间戳t，最后设置时间为t + T_r/2 -
对称模式是获得较高准确精度的方法:
设服务器B时钟是正确的时钟，Ta1绝对时间是指服务器A本地时钟到达Ta1是，正确的时间是多少。这也是A需要同步的时间;
a. 服务器A在本地Ta1时间向B发送时间请求包
b. 服务器B在本地Tb1时间收到B发来的包，Tb1 = Ta1绝对时间 + T请求时延
c. 服务器B在本地Tb2=Tb1 + 1时间发送时间戳包给A
d. 服务器A在本地Ta2时间收到B回复的时间戳包，Ta2绝对时间 = Tb2 + T回复时延
那么A需要同步的时间 = Tb2 + T回复时延 = Tb2 + (Tb1 - Tb2 + Ta2 - Ta1) / 2
当然这个算法也有个缺陷，就是假设了包来回的时延相等，在光纤这种半双工物理介质中，时延不一定相等，就会造成误差。
逻辑时钟与向量时钟
逻辑时钟是一种简单的相对计时方式，通常是一个单调增长的软件计数器。Lamport Timers利用逻辑时间维护不同进程间事件发生的时序:
- LC1: 在进程pi发出事件之前，L1+=1
- Li: Li+=1
- LC2: (a) 当进程pi收到消息m时，在m中附加值t=L1
(b)在接受(m, t)时，进程pj 计算Lj: =max(Lj ,t)，然后再给receive(m)打上时间戳Lj+=1
Lamport时钟可以很容易根据e->e'(同一序列中) => L(e) < L(e')，但是无法根据L(e) < L(e') 推出 e->e'，
向量时钟的提出，克服了lamport 时钟的这个缺陷:
- VC1: 初始情况下，vi[j] = 0
- VC2: 给事件pi加时间戳之前，vi[j] += 1
- VC3: pi在他发送的每个消息中包括值t=Vi
- VC4: 当pi接收到消息中的时间戳时，设置vi[j] = max(Vi[j], t[j]), j={0,1,..N}，这个过程称为merge(合并)
向量时钟就可以根据L(e) < L(e') => e->e'
