cristian算法介绍和实现详细介绍

cristian算法是一种时钟同步算法, 用于通过客户端进程与时间服务器同步时间。此算法适用于低延迟网络, 其中往返时间与准确性相比, 它是短的, 而易于冗余的分布式系统/应用程序与该算法不能并存。这里的往返时间是指请求开始到相应响应结束之间的持续时间。
以下是模仿cristian算法工作的示意图:

cristian算法介绍和实现详细介绍

文章图片
算法:
1)客户端计算机上的进程在以下时间将获取时钟时间(服务器时间)的请求发送到时钟服务器
cristian算法介绍和实现详细介绍

文章图片
.
2)Clock Server侦听客户端进程发出的请求, 并以Clock server time的形式返回响应。
3)客户端进程会及时从Clock Server获取响应
cristian算法介绍和实现详细介绍

文章图片
并使用以下公式计算同步的客户端时钟时间。
cristian算法介绍和实现详细介绍

文章图片
其中
cristian算法介绍和实现详细介绍

文章图片
指同步时钟时间,
cristian算法介绍和实现详细介绍

文章图片
指服务器返回的时钟时间,
cristian算法介绍和实现详细介绍

文章图片
指的是客户端进程发送请求的时间,
cristian算法介绍和实现详细介绍

文章图片
指的是客户端进程收到响应的时间
以上公式的工作/可靠性:
cristian算法介绍和实现详细介绍

文章图片
指网络和服务器将请求传输到服务器, 处理请求并将响应返回给客户端进程所花费的总时间, 假设网络延迟
cristian算法介绍和实现详细介绍

文章图片

cristian算法介绍和实现详细介绍

文章图片
大致相等。
客户端的时间最多与实际时间不同
cristian算法介绍和实现详细介绍

文章图片
秒。使用上面的陈述, 我们可以得出结论, 同步错误最多为
cristian算法介绍和实现详细介绍

文章图片
秒。
因此,
cristian算法介绍和实现详细介绍

文章图片
以下Python代码说明了Cristian算法的工作原理:
以下代码用于在本地计算机上启动时钟服务器的原型:
# Python3 program imitating a clock serverimport socket import datetime# function used to initiate the Clock Server def initiateClockServer():s = socket.socket() print ( "Socket successfully created" )# Server port port = 8000s.bind(('', port))# Start listening to requests s.listen( 5 ) print ( "Socket is listening..." )# Clock Server Running forever while True : # Establish connection with client connection, address = s.accept() print ( 'Server connected to' , address)# Respond the client with server clock time connection.send( str ( datetime.datetime.now()).encode())# Close the connection with the client process connection.close()# Driver function if __name__ = = '__main__' :# Trigger the Clock Server initiateClockServer()

输出如下:
Socket successfully created Socket is listening...

以下代码用于在本地计算机上启动客户端进程的原型:
# Python3 program imitating a client processimport socket import datetime from dateutil import parser from timeit import default_timer as timer# function used to Synchronize client process time def synchronizeTime():s = socket.socket()# Server port port = 8000# connect to the clock server on local computer s.connect(( '127.0.0.1' , port)) request_time = timer()# receive data from the server server_time = parser.parse(s.recv( 1024 ).decode()) response_time = timer() actual_time = datetime.datetime.now()print ( "Time returned by server: " + str (server_time))process_delay_latency = response_time - request_timeprint ( "Process Delay latency: " \ + str (process_delay_latency) \ + " seconds" )print ( "Actual clock time at client side: " \ + str (actual_time))# synchronize process client clock time client_time = server_time \ + datetime.timedelta(seconds = \ (process_delay_latency) /2 )print ( "Synchronized process client time: " \ + str (client_time))# calculate synchronization error error = actual_time - client_time print ( "Synchronization error : " + str (error.total_seconds()) + " seconds" )s.close()# Driver function if __name__ = = '__main__' :# synchronize time using clock server synchronizeTime()

输出如下:
Time returned by server: 2018-11-07 17:56:43.302379 Process Delay latency: 0.0005150819997652434 seconds Actual clock time at client side: 2018-11-07 17:56:43.302756 Synchronized process client time: 2018-11-07 17:56:43.302637 Synchronization error : 0.000119 seconds

时钟同步的即兴性:
使用网络上的迭代测试, 我们可以定义一个最小传输时间, 以此可以制定一个改进的同步时钟时间(减少同步误差)。
在这里, 通过定义一个最小的传输时间(具有较高的可信度), 我们可以说服务器时间将
总是在之后产生
cristian算法介绍和实现详细介绍

文章图片

cristian算法介绍和实现详细介绍

文章图片
将始终在之前生成
cristian算法介绍和实现详细介绍

文章图片
, 在哪里
cristian算法介绍和实现详细介绍

文章图片
是最小传输时间, 它是
cristian算法介绍和实现详细介绍

文章图片

cristian算法介绍和实现详细介绍

文章图片
在几次迭代测试中。同步错误可以表述为:
cristian算法介绍和实现详细介绍

文章图片
同样, 如果
cristian算法介绍和实现详细介绍

文章图片

cristian算法介绍和实现详细介绍

文章图片
相差相当长的时间, 我们可以替代
cristian算法介绍和实现详细介绍

文章图片
by
cristian算法介绍和实现详细介绍

文章图片

cristian算法介绍和实现详细介绍

文章图片
, 在哪里
cristian算法介绍和实现详细介绍

文章图片
是观察到的最短请求时间, 并且
cristian算法介绍和实现详细介绍

文章图片
是指在网络上观察到的最小响应时间。
在这种情况下, 同步时钟时间可以计算为:
cristian算法介绍和实现详细介绍

文章图片
因此, 通过仅将响应时间和请求时间引入为单独的时间延迟, 我们可以改善时钟时间的同步性, 从而减少总体同步误差。要运行的迭代测试的数量取决于整体时钟漂移观测到的。
参考文献:
1)https://en.wikipedia.org/wiki/Cristian%27s_algorithm
2)https://en.wikipedia.org/wiki/Round-trip_delay_time
3)https://www.lsbin.org/socket-programming-python
4)https://en.wikipedia.org/wiki/Clock_drift
【cristian算法介绍和实现详细介绍】首先, 你的面试准备可通过以下方式增强你的数据结构概念:Python DS课程。

    推荐阅读