电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 分布式系统时间和全局状态 [此博文包含图片] [打印本页]

作者: yuyang911220 时间: 2015-8-14 15:55 标题: 分布式系统时间和全局状态 [此博文包含图片]

分布式系统中各个节点要实现时间的同步，才能为很多其他系统提供基础，例如：审计电子商务，维护数据一致性，竞争锁等等。

计算机中，时钟分为低精度的时钟和高精度时钟。低精度的时钟是有cmos芯片提供，高精度的时钟是由CPU向一个寄存器里面写不断发送时钟信号，再由程序去读它得到，这个时钟通常表示成“从开机到现在为止，CPU跳了多少下”。精度通常是纳秒级别。

但是由于CPU的老化，型号甚至批次的不同，温度不同，高精度时间是有误差的。

时钟偏移也不可避免。

因此如果是一个集群，集群里面每个节点的时钟肯定是有差异的，要想做到同步，有系统中的同步和依赖外部时钟服务器去同步。

系统内的同步：
条件：
已知时钟的漂移范围
存在最大的消息传输延迟
进程每一步的执行时间已知
过程：
一个进程将自己的时间发送给另外一个进程，传输时间的不确定性为u=max-min，则
接受进程直接使用时间 t = (max+min)/2,时钟的便宜至多为u/2.

Cristian算法：
这个算法是系统内的时间同步，通常是系统内有一台机器油标准时间（例如UTC时间）的接收器，而其他的服务器时间需要与它同步。

前提：
有一个时间服务器，提供标准时钟，其它系统通过询问与它同步。
消息传输的耗时比起所要求的精度，足够短。
过程
这个算法面对的两个问题：
1.（主要）服务器的时间是不能倒退的，假设服务器的时间倒退了，很多程序将面临严重的错误，例如make程序，无法判断源文件是否需要重新进行编译。
2. （次要）从时间服务器到请求的服务器之间的传输，以及时间服务器做出应答，都是要耗时的。
解决问题的办法：
1.调整时间的时候，假如时间服务器需要慢下来，需要逐渐减慢自己的时间，而不能让时间倒退。假如服务器每秒产生100次中断，每次中断将时间增加10毫秒。当时钟需要调慢时，每次中断仅仅增加9毫秒。直到时间正确。
2. 算法会做一系列的测量，试图估算消息往返的时间消耗，并在时钟校准的时候考虑这个消耗。

伯克利算法：
这个算法的主要时间不同在于各个服务器是主动的将自己的时间报告给服务器，服务器告诉它需要如何调整。
算法如下：
-主机通过周期轮训从属机时间。
-主机通过消息往返时间估算从属机时间
-主机计算容错平均值
-主机给系统内发送每个从属机的调整量

a图: 主机发送“我这里是3点钟”，给从属机
b图：从属机回应自己时间的差值，以表示自己的时间。
c图：主机计算容错平均值，并且纠正。

外部同步：
网络时间协议NTP
设计目标：

可外部同步：
使得跨互联网的用户能够精确与UTC同步
高可靠性：
可以处理连接丢失，采用冗余服务器、路径的方式。
扩展性好：
大量用户可以经常同步。
安全性强：
防止恶意或者偶然的干扰。

协议结构：

同步模式：
组播 - 适用于高速LAN，准确度较低

过程调用：
与cristin算法类似，准确的较低

对称模式：
保留时序类型，准确度最高。

逻辑时钟：
就是一种相对时间，比如“从整个系统启动到现在过了多久多久”这样的时钟。
不进行交互的两个进程之间不需要时钟同步。

a事件发生在b事件之前，记为a→b。
消息的发送肯定在接受之前，记为send(m)→recv(m)
X→Y 和 Y→X都不成立，称为X || Y

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)