阅读笔记（十二）Lamport Clock算法原理《Time, Clocks, and the Ordering of Events in a Distributed System》

￡神魔★判官ぃ 2023-07-02 05:23 97阅读 0赞

### 一. 简介 ###

《Time, Clocks, and the Ordering of Events in a Distributed System》是大神Leslie Lamport写的一篇关于时钟序列的文章。本文影响极其深远，可以说是分布式领域开山奠基式的重要文章。而该作者Leslie Lamport，同时也是共识算法[Paxos][]的发明者，也是Latex的创作者，是一位非常可敬的牛人。  
  此文不长，主要以提出算法和数学证明为主。在这里我主要记录算法的主要思想，具体证明过程请参考原文深入了解。

### 二. 分布式的时钟同步问题 ###

在单台机器上，我们很容易的就可以对所有的进程、事务进行排序，因为我们有一个统一的标准：CPU时钟。而对于多台机器，则相对麻烦，因为难免会出现CPU时钟周期不相同、时间延迟、或者人为造成时间的修改等等。为此，在分布式系统中，不同机器通讯的先后顺序是一个比较麻烦的问题。总的来说，有几种解决方法：

1.  同步中央时钟：对多台机器进行同步处理，使其时钟保持一致，如NTP协议。但是这样带来了一些问题，首先需要保持同步则需要定期进行通信，从而增加了额外的时延和带宽消耗。另外，该方法仅针对网络拓扑稳定的环境适用。因为如果有机器不断地增加、减少，是无法保证每台机器CPU时钟周期相同，也无法保证时钟同步。
2.  局部排序：对每台机器单独进行排序，采取一些算法使其序列统一。如本文的Lamport Clock，后续的vector clock，以及version clock等。

### 三. Lamport Clock具体内容 ###

lamport逻辑时钟算法

1.  每个事件对应一个Lamport时间戳，初始值为0
2.  如果事件在节点内发生，时间戳加1
3.  如果事件属于发送事件，时间戳加1并在消息中带上该时间戳
4.  如果事件属于接收事件，时间戳 = Max(本地时间戳，消息中的时间戳) + 1

算法主要包括五条规则：

1.  进程A在T1时刻使用某资源，则发送消息T1:A给所有其他的进程，并将该消息加载自己的请求队列中
2.  其他进程收到了消息T1:A之后，将其加在自己的请求队列中，并发送ACK回复A
3.  为了释放资源，进程A移除请求队列中的T1:A，并发送释放消息给其他进程
4.  当其他进程收到了释放消息后，移除自身请求队列中的T1:A消息
5.  进程A在满足以下两条件的情况下才释放资源：（1）在请求队列中存在T1:A，并且该序列T1要先于请求队列中的其他请求消息 （2）A接受到了其他进程晚于T1的时间戳

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]

如图所示为一个由三台主机（A, B, C）构成的分布式系统。从图中可以很容易理解该算法的思想。但是有一个需要注意的点：Lamport Clock没有解决“并行发生”的关系，如B3和A1， B4和C3。在原文中，采用了物理时钟进行了补正，但是依然不能完美解决同时发生的情况。为此才有了后来的向量钟Vector Clock。

### 四. 参考文献 ###

【1】《Time, Clocks, and the Ordering of Events in a Distributed System》  
【2】https://en.wikipedia.org/wiki/Lamport\_timestamps

--------------------

欢迎关注本人公众号，公众号会更新一些不一样的内容，相信一定会有所收获。  
![在这里插入图片描述][20201219120057415.jpg_pic_center]

[Paxos]: https://blog.csdn.net/u013354486/article/details/104081997
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200130163033133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[20201219120057415.jpg_pic_center]: https://img-blog.csdnimg.cn/20201219120057415.jpg#pic_center