时间和事件顺序

6.1 物理时钟

  • 机械时钟
  • 石英时钟
  • 原子钟：原子共振频率标准来计算
  • GPS

6.2 时钟同步

NTP:(430条消息) NTP详解(网络时间协议)_127.127.1.0 ntp含义_思福迪小白的博客-CSDN博客

针对NTP同步导致时间回退甚至是负数的情况–单调时钟，保证返回的时间严格单调增长

Cloudflare没用单调时钟，而是在发现时间差为负数或者0时变为一个默认值（golang没暴露单调时钟）

单调时钟的局限性：以自身所在的计算机的某个时间为起点，也就是说，来自同一个节点的单调时钟才有意义。

如何发明分布式系统中的单调时钟？

6.3 逻辑时钟

Lamport Clock

Happens-Before:

​ if a->b

  • if a and b are in the same process, and a is before b, then a->b
  • if a is the event that sends a message , b is the event that receives the message, then a->b.
  • if a->b and b->c, then a->c; if a /->b or b/->a, then a and b are in concurrency(a||b).

a->b, then C(a)<C(b)

C(a)<C(b), a/->b

  • 每个进程都有自己的逻辑时钟，初始值为0
  • 如果进程i内部发生一个新的事件，那么将其逻辑时钟加一，即Ci= Ci+1
  • if process i sends a message to process j , and the logic clock in process i is C(i), then, firstly, C(i)=C(i)+1, and then, i sends Ci and the message to process j, and then, process j updates its logic clock Cj= max(Ci,Cj)+1

根据离散数学的关系而言，逻辑时钟和物理时钟的区别在于，物理时钟的先后关系是一种total ordering，是全局可见的一种关系，谁先谁后一目了然；然而逻辑时钟 is a kind of partial ordering，只有部分元素的先后关系（本质原因是，我们不能根据逻辑时间的先后去判定逻辑业务的先后）

如何使逻辑时钟也具有全序关系？给进程加上优先级，但是赋予进程不同的优先级排序会有不同的全序关系

RAFT的任期、选举算法、日志和状态机的思想等都出自这篇论文（Lamport,Leslie.”Time,clocks,and the ordering of events in a distributed system.”Concurrency: the Works of Leslie Lamport. 2019.179-196）：

  • 一个去中心化的算法，通过逻辑时钟实现分布式资源互斥来分配资源
  • 每个进程维护一个消息队列，消息的格式为Tm: Pi, 即为第i个进程在Tm的逻辑时钟下发送的消息
  • 进程维护自己的消息，也接收别人的消息，决定自己是否能够获取资源的条件
    • 消息队列中除开自己的消息之外的消息的逻辑时间，均大于自己的消息
    • 排在队头的消息是自己的消息（这里消息的插入可以是对头队尾，也可以是中间）

6.4 向量时钟

跟逻辑时钟很类似，只不过逻辑时钟只考虑了本地的逻辑时间，而向量时钟的维度为节点数，维护全局的时间。

向量时钟（Vector Clock）是一种在分布式系统中用于记录事件发生顺序的机制。它通过给每个节点分配一个独特的向量来跟踪每个节点上的事件发生次数，这个向量被称为向量时钟。

向量时钟的大小等于节点数，每个元素代表了一个节点的时间戳。当一个事件发生时，对应节点的时间戳会自增1。如果两个事件发生在不同的节点上，那么它们的时间戳是相互独立的，无法比较先后顺序；但如果它们发生在同一个节点上，就可以用向量时钟来比较它们的先后顺序。比如说，设有A,B,C三个节点，此时在A节点上发生了一个事件，那么其向量时钟会变为[1,0,0]，因为这是A节点上第一个事件。如果随后在C节点上发生了一个事件，那么其向量时钟会变为[0,0,1]，因为这是C节点上第一个事件。如果再在B节点上发生了一个事件，那么其向量时钟会变为[0,1,0]，因为这是B节点上第一个事件。这样，在整个分布式系统中，我们得到了A为[1,0,0]，B为[0,1,0]，C为[0,0,1]的向量时钟。

当一条消息从一个节点传递到另一个节点时，消息中会包含发送方的向量时钟。接收方在收到消息后，将它自己的向量时钟和接收到的消息中的向量时钟进行比较，取每个位置上较大的值作为新的时间戳。然后将接收到的消息的时间戳同步到本地，再加上1，表示接收到了这条消息。这样，接收方就可以知道这条消息是在哪个节点上发送的，以及这条消息的先后顺序。

向量时钟不仅能够帮助我们比较事件间的先后关系，还能检测出并发事件。比如说，如果两个事件A和B同时发生，那么它们对各自持有的向量时钟都会影响到相应的位置上，导致这两个节点上的向量时钟不一致。这样，我们就可以检测出这两个事件的并发性。

缺点在于，向量的维度与节点数正相关，随着节点增多，向量时钟越大，向量时钟需要大量的磁盘和内存空间，同时需要更长的时间来计算和比较。