分布式系统时钟同步设计与实现.docx

2006 年 1 月January 2006第 32 卷第 2 期计算机工程Computer Engineering 2Vol.32开发研究与设计技术文章编号：10003428(2006)02027903文献标识码：A中图分类号：TP391分布式系统时钟同步设计与实现刘立月，王更生，魏永丰(华东交通大学信息学院，南昌 330013)摘 要：时钟同步是分布式系统的核心技术之一，考虑到分布式系统的可扩展性及同步精度要求，提出了基于 GPS 与 NTP 的混合同步方案解决系统时间同步问题，并对其原理与实现进行了阐述。 关键词：时钟同步；GPS；NTP；分布式系统Design and Implementation of Clock Synchronizationin Distributed SystemLIU Liyue, WANG Gengsheng, WEI Yongfeng(School of Information Engineering, East China Jiaotong University, Nanchang 330013)【Abstract】Clock synchronization is key technology in distributed system. This paper studies time synchronization technology, considering systemexpansibility and high precise time synchronization, and suggests that a design thinking of a mixed time synchronization solution based on GPS andNTP solves time synchronization in distributed system, discusses and analyses its theory and implementation.【Key words】Time synchronization; Globle positioning system; Network time protocol; Distributed system时间同步是计算机应用系统的一个最基本的要求，集中式系统的时间无二义性，而作为计算机应用系统的分布式系 统没有标准的时间统一系统或共同的时间基准，同时该系统 对时间有更高的要求，如分布式系统的任务调度，多任务(进程)间的同步以及基于优先级调度算法等对时间的分辨率都有较高的要求。 为了减少时间的不一致性对分布式系统所造成的影响，必须对系统进行时钟同步。其目的就是在一个分布式的网络 系统中维护一个全局一致的物理或逻辑时钟，以使得系统各 节点对系统中与时间有关的事件有相同的观测参考点，确保 各节点发送和接收消息在时间逻辑上具有正确的因果关系。1 系统时钟同步方案设计时钟同步可以由硬件实现、软件实现或分层混合实现。硬件同步：主要是通过分布系统在每个节点设置 GPS 接 收器，以由外部提供标准时钟同步信号，并以此为标准时间同步整个分布系统。硬件同步精度很高，同步算法简单，只需要传递标准的时间值即可，但成本较高。硬件同步适合范 围广泛，在一个大规模分布系统中完全采用硬件同步是不现 实的。软件同步：通过使用适应具体分布系统特点的合理分布 时间同步算法，完全利用软件来提供全系统统一的时间。软 件同步一般涉及时间信息包在网络中的传输，因此同步精度与网络延迟有关，不确定性大，误差容易积累。对于广域网上的大型分布系统不能保证同步精度。优点是易于操作、成 本低廉。混合同步：将硬件同步和软件同步相结合，在其中一个 节点处使用硬件同步 UTC 时钟，其它节点使用软件同步。从分布式系统可扩展性、较高同步精度要求及实现成本 相对较低出发，采用混合同步算法解决系统时间同步问题。将大型分布式系统按位置距离远近或内部局域网分成若干个工作组，每组设置一台时间服务器，工作组内工作站通过 NTP 协议与组内时间服务器同步,也称内同步；组间服务器通过 GPS 接收器保持与 UTC(Universal Time Coordinated)同步,也称外同步，从而确保整个系统时间同步。其具体的设计原理如图 1 所示。GPS 接收 器接收器 图 1 系统时间同步方案2 系统时钟同步方案实现2.1 外同步实现系统外同步主要问题是如何通过 GPS 接收器获取 UTC时间信息，关键是将 GPS 接收器的数据格式解码为用户所需 求的信息。基金项目：华东交通大学科研基金资助项目作者简介：刘立月(1970)，男，讲师、硕士，主研方向：测控，网 络与数据库；王更生，教授；魏永丰，助教收稿日期：2004-12-30E-mail：lly_GP S时间 服务器 工作站 1工作站 2 工作站 n工作 组 nGPS 接收器 时间服务 器工作 站 1工作站 2 工作站 n工作组 1时 间服务器 工作站 1工作 站 2 工作站 n工作组 2分布 式系统时钟 同步方案 Motorola Oncore 接收器是一种智能型 GPS 传感器，作为精确定位、导航系统、授时系统的部件，该接收器能通过一 个反相 TTL 串行接口提供自身位置、速度及时间信息。最低 限度可用系统包括 Oncore 接收器、天线和一个智能系统控制 器装置。2.1.1 GPS 接收器获取数据的结构Motorola Oncore 接收器在工作时，不断周期性地将 GPS接收的数据信息发送出去，用户通过串口编程可获取具体的 数据，每帧数据均由 5 部分组成，其数据结构为：(1)信息开始标志(40H，40H)； (2)信息类型标识符； (3)二进制数据序列；(4)校验和；(5)信息终止符CRLF 回车和换行(0DH，0AH)。2.1.2 GPS 获取数据分析在实现中，我们采用 12 颗卫星 GPS 接收器，通过串口编程，获取的 1 帧(154B)数据。数据起始两位为开始符，提 示 1 帧数据开始，接下来信息分别依次为年、月、日信息，时间信息，平滑定位数据，未平滑定位数据，速度，几何学参数，卫星数据，未用信息，12 颗卫星的跟踪状态，未用数 据，校验位；结束符。具体数据结果与分析图略。2.1.3 GPS 获取数据解码与实现在 VC+开发环境下，采取 MSComm 控件串口通信编程， 进行正确的编程配置，当事件被触发调用后，调用事件处理 函数，MSCOM 事件处理过程如图 2 所示。无误地到达对方。但时间传输延迟大。面向无连接的 Socket编程模型可同时服务多个客户的连接请求，时间传输延迟小。这种方案适用于通信频繁、可靠性和稳定性要求不高的场合。考虑到系统内同步中时间精度要求高且多客户的连接请求，客户与时间服务器之间采用基于 Socket 的 UDP 网络编 程实现数据传输。 基于 Socket 的网络 UDP 网络应用程序工 作原理模型如图 3 所示。客户端服务器端请求发送阻塞，等待客户请求请求响应图 3 面向无连接的 Socket 编程模型2.2.2 基于 NTP 的时间同步算法 目前采用的软件同步算法主要有确定性同步算法、概率性同步算法和网络时间协议 NTP。确定性同步算法的精度由 预先设定的传输延迟的上下界决定，而网络延迟的不确定性 很大，其同步精度很低。概率性同步算法以足够多的读取次 数达 到满足远地时 钟估值误差在 给定精度范围 内的概率要 求。为减少网络延迟不确定性影响，系统采用网络时间协议NTP。NTP 是一个基于 TCP/IP 的、跨越广域网或局域网的复 杂的同步时间协议，它通常可获得毫秒级的精度。NTP 有两 种工作方式：NTP 广播方式与 NTP 客户/服务器方式。在 NTP 广播方式中，时间服务器周期向各节点广播时间消息，各节 点利用接收到的时间消息和预先设定的服务器节点的传输延MSCOM 事件开始Flag=STARTYNNrDatai= =rDatai= =0AYYNNi1rDatai-1= =0D迟来计算本机时间。由于预先设定的传输延迟有一定的误差，YY因此它的同步精度很低。采用客户/服务器方式，时间服务器和需同步的节点以客户/服务器方式交换 NTP 数据包，从而NrDatai-1= =Y计算时间服务器时钟与网络节点时钟的偏差。具体算法如下：NrDatai-2= =帧数据校验和(1)客户端首先向时间服务器发送一个 NTP 数据包，同时在数据包上打上客户端本机的发送时间戳 Ta；(2)服务器接收到客户 NTP 数据包后，同时在数据包上打上服务 器本机的接收时间戳 Tb；(3)服务器向客户返回 NTP 数据包后，同时在数据包上打上服务器本机的发送时间戳 Tc；(4)客户端接收到服务器返回的 NTP 数据包，同时在数据包上打 上客户端接收时间戳 Td。YMSCOM 事件结束图 2 MSCOM 事件处理过程2.2 内同步实现系统内同步实现主要解决两方面的问题：一是客户与时间服务器之间采用何种技术进行数据传输，二是客户与时间 服务器之间的时间同步采用哪种算法来实现。2.2.1 基于 Socket 的 UDP 网络编程基于 Socket 的网络编程主要有两种类型。面向连接的Socket 编程模型应用最为广泛，因为面向连接协议提供了一 系列的数据纠错功能，可以保证在网络上传输的数据及时、图 4 NTP 数据包标记时间戳过程时间 服务 器时间戳 Tb 时间 戳 Tc客户 端时间 戳 Ta 时间 戳 TdFlag=0，i=0对数组 rData中数据根据帧定义的格式进行处理，提取用户所需数据Flag=STARTFlag=ENDrDatai=读入的字符close()close()recvfrom()sendto()sendto()recvfrom()bind()bind()Socket()Socket()上述 NTP 数据包标记时间戳过程如图 4 所示，利用这 4个时间戳，就可以算出时间服务器客户端的传输延迟与 时间偏差。传输延迟： Delay = (TbTa) + ( Td Tc)/2= (Tb + Td TcTa)/2时间偏差：Offset = (Tb + Tc)/2 (Td + Ta)/2= (Tb + TcTd - Ta)/2 同步结束后，客户节点的本地时钟可调整为 T 同步 = (Tb + Tc)/2 + (Td - Ta)/2= (Tb + Tc + Td - Ta)/2网络时间协议 NTP 算法程序实现流程如图 5 所示。客户端(6)Tracde_Satrllites 跟踪卫星数为：09。在基于 UDP 网络编程与 NTP 算法的基础上，我们实现了同一局域网内其它客户机与 GPS 时间服务器的同步。时间服务器端收到客户端的NTP 数据 包否？图 6 GPS 接收数据系统混合同步算法的过程由两部分组成：组内的 NTP 协 议软件同步(内同步)与组间的 GPS 硬件同步(外同步)。一般 GPS 接收器可以获得精确度达到 100ns；而在 NTP 协议软 件同步中，同步后客户节点时钟与时间服务器的标准时间误 差为(Td - Ta)/2，即同步数据包往返延迟的一半，一般可达到10ms。因此，混合同步算法时间的确度主要由 NTP 协议软 件决定，即一般可达到 10ms。如何提高组间的确度，关键 在于合理选择分组及同时避免组间网络的拥塞。4 结束语在大规模的分布式系统中，网络上节点机的时间同步显得尤为重要。本文对时钟同步技术进行研究，考虑系统的可 扩展性及保证系统较高同步精度，提出了基于 GPS 与 NTP 的混合同步方案解决系统时间同步问题，并对其工作原理与实现进行了深入的阐述与分析。该方案能保证很高的时间精度和可靠性，具有很重要的应用价值。 参考文献1 张红亮, 吴秋云. 网络时间协议实现分布式系统内时钟同步的原 理分析J. 小型微型计算机系统, 2003, 24(5): 831-8352 冯博琴, 徐景明. 计算机时间同步技术研究J. 西安交通大学学报, 1999, 33(5): 103-1053 孙 娜, 熊 伟. 分布式网络系统中时钟同步的实现J. 计算机 工程, 2003, 29(14): 136-138No返回的 NTP 数据包否？YesNoYes图 5 时间服务器端/客户端程序流程3 系统时间同步结果及分析在南昌 GPS 实验室中，通过串口编程，获得外同步时间服务器上的 GPS 时间，GPS 接收器接收数据运行结果，如图6 所示。图 6 窗体的左边为原始接收的 Motorola 二进制数据， 右边是通过算法解码出的数据，通过对其中一组数据的解析， 可以看到：(1)DATA 日期信息为：05/08/2004；(2)TIME 时间信息为：23：49：18；(3)Latitude_N 纬度为：2 844.332 031(即 28 度，44.332 031 毫 度)；(4)Longitude_E 经度为：11 551.976 563(即 115 度，51.976 5