分布式系统中逻辑时钟和向量时钟
为什么在分布式系统中时钟是个问题？
软件应用依赖计算机的时钟 (Clocks) 来解决多种问题，如判断多个请求到来的先后顺序等等，这在单体系统中这不是问题，而在分布式系统中，由于多个节点自身时间的不一致性，就没法准确的判断事件先后顺序，而判断事件的先后顺序对于一个分布式系统来说其实是非常重要的。
逻辑时钟
在一个分布式系统中，既然不能依靠物理时钟来判断事件的先后顺序，那么我们就放弃物理时钟，不通过物理时钟来判断事件的先后顺序，另外发明一种时钟来计算分布式系统中的事件的先后顺序。这就是 lamport 在1978 年论文中提出的逻辑时钟概念。
生活经验告诉我们：事件通常不是孤立存在的，两个事件之间往往存在某种因果关系。而分布式系统是一个组件分布在不同，联网的计算机上，组件之间通过消息进行通信和协调，共同完成一个分布式任务。消息传递就可以看成分布式系统中事件之间构成因果关系的桥梁。
比如我们可以将发送消息的事件称为因，而接收消息的事件看作果，将此扩展到每个节点，那么我们不需要任何物理时钟，则依然得出了事件的顺序。
lamport 在论文中将上面的关系定义为一种 "发生于......之前" 关系。并给出了其形式化的表述，将 事件a发生于事件b 之前的关系定义为
逻辑时钟的定义，如果，则事件 a 和 事件 b 满足以下3个条件：
- 如果事件 a b 发生在在同一个进程中，事件a 发生事件之前，则
- 如果a 是发送一条消息的事件，而b是收到这条消息的事件，那么
- 假如
成立，且
成立，那么
成立
- 如果事件 a b 不满足
，那么认为 这两个事件 a b 是并发的。
基于时钟条件，逻辑时钟的计算方法如下：
- 每个进程都记录自己的逻辑时钟，初始值为0
- 如果进程i 内部发生一个新的事件，那么将其逻辑时钟加一，即 $$
- 如果进程i 向进程j 发送消息，进程 先将其逻辑时钟加一，即 然后将 和消息以前发送给进程，进程更新自己的逻辑时钟为 $$
image.png
现在，让我们看看另一个场景问题：
由此可见，在一个分布式系统中，我们并不能依靠逻辑时钟能得到所有的事件发生的时间顺序。物理时钟得到的是一种全序关系，即集合中任意两个元素可以互相比较并比较大小；而逻辑时钟得到的是一种偏序关系，即集合中任意两个元素可以互相比较并比较大小
那么人如何将偏序关系扩展成全序关系呢？
Lamport 的方式是在逻辑时钟上附加进程编号，同时定义进程的全序关系，默认情况下，使用逻辑时钟排序，逻辑时钟相同的情况下按照进程的全序关系进行排序。
利用逻辑时钟解决分布式锁的问题
TODO
向量时钟
向量时钟是在逻辑时钟的基础上改进而来，我们发现逻辑时钟的每个节点只有自己的本地时钟，没有其他进程的时钟，从而导致仅仅通过逻辑时钟依然无法计算出某些事件，必须指定一个进程的优先级。向量时钟的思想是，让每个进程都知道系统中其他进程的时钟，这样就无需额外指定进程的优先级。向量时钟依旧只能得出分布式系统中的事件偏序关系，不过向量时钟包含了其他节点的信息，通常用于数据冲突检测。
向量时钟和逻辑时钟的原理几乎一样，只不过对于每个阶段或者进程而言，它维护的不只是自己的时间戳，而是一个由所有节点的时间戳构成的向量，向量维度等于分布式系统中的节点数量，向量时钟因此得名。
- 版本向量
TODO
