分布式系统时序

在分布式系统中事务的正确顺序保证了正确性。
在现实生活中事件总是有顺序的，不可能存在现在肚子饱了是由于10分钟后吃的饭导致的这类事情。现实生活的正确性建立在物理时间是线性的，事件是按先后顺序发生。
但是在分布式系统当中，执行事务的各个节点的本地时间是不同的。甚至由于某些原因会导致某些节点的时间是错误的。这导致了在分布式系统中依靠本地时间决定事务的顺序肯定是不可行的。

偏序和全序

偏序：在一台节点上发生的事件肯定是有序的，这个称之为偏序。
全序：所有事件按时间排序，称为全序。
如果有全局时钟来保证每个节点上的时间是一致的，那么就能得到全序。

逻辑时钟

逻辑时钟依赖计数器和通信确定分布式系统当中的事件的顺序。

兰伯特时钟

lamport clock

  1. 如果事件是发送消息，则该事件的时间戳与消息一起发送。
  2. 如果事件是接收消息，则进程的时间戳记计数器的当前值（在此事件之前刚刚增加）与接收到的消息中的时间戳记进行比较。
  3. 如果接收到的消息的时间戳大于或等于当前事件的时间戳，则事件和进程的时间戳计数器都将用接收到的消息中的时间戳值加1进行更新。这确保了接收到的事件的时间戳以及该进程上的所有其他时间戳将大于发送消息以及该进程上的所有先前消息的事件的时间戳。

向量时钟

矢量时钟是 Lamport 时钟的扩展，它维护一个[ t1, t2, … ]由 N 个逻辑时钟组成的数组 - 每个节点一个。每个节点不是递增公共计数器，而是在每个内部事件时将向量中自己的逻辑时钟递增 1。因此更新规则为：

  1. 每当进程工作时，就增加向量中节点的逻辑时钟值
  2. 每当进程发送消息时，都包含逻辑时钟的完整向量
  3. 当收到消息时：
    将向量中的每个元素更新为max(local, received)
    增加表示向量中当前节点的逻辑时钟值 vector clock
  4. 如果时间戳记V的每个元素小于或等于时间戳记W的相应元素，则V因果顺序在W之前，并且事件不是并发的。
  5. 如果时间戳记V的每个元素都大于或等于时间戳记W的相应元素，则W因果顺序在V之前，并且事件不是并发的。
  6. 如果这些条件都不适用，并且V中的某些元素大于W而其他元素小于W中的对应元素，则事件是并发的。

总结

Lamport时钟建立的是分布式系统中事件的部分顺序。部分顺序意味着并不是所有事件都可以相互比较来确定它们的确切顺序。相反，Lamport时钟提供了一个部分顺序，满足以下两个条件：

  1. 如果事件A在事件B之前发生，那么事件A的Lamport时间戳将小于事件B的Lamport时间戳：ts(A) < ts(B)。
  2. 如果事件A和事件B是并发的（在不同进程/节点中同时发生），则它们的Lamport时间戳之间没有严格的顺序关系：ts(A)和ts(B)可能相等，而无法确定它们的确切顺序。

Lamport时钟可以捕获事件之间的因果关系，当存在直接因果关系（即一个事件导致另一个事件）时，但可能无法准确反映并发事件的顺序。这是因为Lamport时钟依赖于进程之间的消息交换来建立顺序，而来自不同进程的并发事件可能没有任何直接的通信或因果关系。
相比之下，向量时钟通过维护关于不同进程/节点上事件的相对顺序的附加信息，扩展了Lamport时钟。通过向量时钟，可以建立更完整和准确的事件顺序，即使在并发事件的情况下也能做到。向量时钟可以提供事件的全序，捕获因果关系和并发关系，这是相对于Lamport时钟的重要改进。