cristian算法是一种时钟同步算法, 用于通过客户端进程与时间服务器同步时间。此算法适用于低延迟网络, 其中往返时间与准确性相比, 它是短的, 而易于冗余的分布式系统/应用程序与该算法不能并存。这里的往返时间是指请求开始到相应响应结束之间的持续时间。
以下是模仿cristian算法工作的示意图:
文章图片
算法:
1)客户端计算机上的进程在以下时间将获取时钟时间(服务器时间)的请求发送到时钟服务器
文章图片
.
2)Clock Server侦听客户端进程发出的请求, 并以Clock server time的形式返回响应。
3)客户端进程会及时从Clock Server获取响应
文章图片
并使用以下公式计算同步的客户端时钟时间。
文章图片
其中
文章图片
指同步时钟时间,
文章图片
指服务器返回的时钟时间,
文章图片
指的是客户端进程发送请求的时间,
文章图片
指的是客户端进程收到响应的时间
以上公式的工作/可靠性:
文章图片
指网络和服务器将请求传输到服务器, 处理请求并将响应返回给客户端进程所花费的总时间, 假设网络延迟
文章图片
和
文章图片
大致相等。
客户端的时间最多与实际时间不同
文章图片
秒。使用上面的陈述, 我们可以得出结论, 同步错误最多为
文章图片
秒。
因此,
文章图片
以下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
时钟同步的即兴性:
使用网络上的迭代测试, 我们可以定义一个最小传输时间, 以此可以制定一个改进的同步时钟时间(减少同步误差)。
在这里, 通过定义一个最小的传输时间(具有较高的可信度), 我们可以说服务器时间将
总是在之后产生
文章图片
和
文章图片
将始终在之前生成
文章图片
, 在哪里
文章图片
是最小传输时间, 它是
文章图片
和
文章图片
在几次迭代测试中。同步错误可以表述为:
文章图片
同样, 如果
文章图片
和
文章图片
相差相当长的时间, 我们可以替代
文章图片
by
文章图片
和
文章图片
, 在哪里
文章图片
是观察到的最短请求时间, 并且
文章图片
是指在网络上观察到的最小响应时间。
在这种情况下, 同步时钟时间可以计算为:
文章图片
因此, 通过仅将响应时间和请求时间引入为单独的时间延迟, 我们可以改善时钟时间的同步性, 从而减少总体同步误差。要运行的迭代测试的数量取决于整体时钟漂移观测到的。
参考文献:
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课程。
推荐阅读
- 瑞士信贷面试经历|实习校园(浦那)
- 使用物联网的作物监控和智能农业
- Android常用实例—Alert Dialog的使用
- Android 使用 Https问题解决(SSLHandshakeException)
- 如何使用电脑上的谷歌浏览器来调试安卓手机上的移动端页面
- Android APK瘦身大法——SVG图片瘦身
- 原生Android也能做Web开发了
- Android(架构)
- Android 应用开发-从设计到实现 3-2 前期准备