在分布式系统中，时钟非常重要，物理时钟（Physical Time，也称PT），逻辑时钟（Logical Clock，也称LC），向量时钟（Vector Clock，也称VC），真实时钟（True Time，也称TT）、混合逻辑时钟（Hybrid Logical Clock，也称HLC），等概念需要深入了解。
-
物理时钟-Physical Time, PT
物理时钟即机器本地的时钟，而由于设备硬件不同，本身存在偏差，一天的误差可能有毫秒甚至秒级，所以需要对不同的机器时钟进行同步使得机器的时间进行相对统一。NTP是目前比较常用的同步时间的方式，其机制为CS架构，每台机器上存在一个NTP的客户端，与NTP的服务端进行同步，校准本地的时间。关于NTP具体的设计细节本文不做详细介绍，需要知道的是，由于NTP走网络传输，势必会导致同步后的物理时钟与远程NTP服务器的时钟存在一定的偏差。 -
逻辑时钟-Logical Clock, LC
由于在分布式场景下，不同机器的时间可能存在不一致，那么就没办法对跨节点的事件确定的先后关系。所以Lamport推出了逻辑时钟的概念，通过happened-before关系确定事件的逻辑时钟，从而确定事件的偏序关系。
那什么是happened-before关系？
-
如果a, b事件都是位于一个进程内（假设顺序发生，不考虑并发），且a位于b之前发生，那么a happened-before b, 记作：a hb b或者a->b，C(a)<C(b)，C表示逻辑时钟。
-
如果a，b事件是位于2个进程内，a为消息的发送事件，b为同一个消息的接收事件。那么同样 a hb b。
Lamport的算法就是根据happened-before关系来确定逻辑时钟序的。
lamport_timestamps -
每个事件都有1个逻辑时间戳，初始为0。
-
如果事件发生在节点内部，则时间戳+1.
-
如果事件属于发送事件，则时间戳+1，并在发送的消息中携带时间戳。
-
如果事件属于接收事件，则时间戳=max{本地时间戳，消息中的时间戳}+1。
这样，通过该算法就确定了一个消息的偏序关系，比如上图中C1->B1, B1->B2, B2->A1。那么如何确定全序关系？通过给每个进程指定初始的优先级来确定，比如上图的A, B, C三个进程，我们分别指定A=1, B=2, C=3表示3个不同的序号，那么假设有2个相同的逻辑时钟C(B4)=C(C3)，因为C=3>B=2，所以C(B4)<C(C3)。通过这种实现定序的方式，可以对所有事件排序，得到全序关系。
- 向量时钟-Vector Clock, VC
LC能够保证a->b=>C(a)<C(b)（=>表示推导），但是不能通过C(a)和C(b)的大小推出a, b事件发生的先后顺序。
向量时钟是1988年，基于逻辑时钟提出的一个向量化的逻辑时钟，可以保证由C(a)<C(b)=>a->b。其由一个向量构成，向量的每个元素即是一个逻辑时钟，也叫做版本号，向量的维度等于节点个数，每个结点通过不同维度的版本号握有全局信息。向量属性如下：
- VCi[i]表示进程i上面事件发生的个数。
- VCi[j]表示进程i知道的j进程上面发生的事件发生数，即进程i对进程j的认知。
向量更新算法：
进程i每次发生1个事件，对VCi[i]+1
当进程i发送消息给进程j时，携带进程i的信息VCi整个向量时钟（进程i对全局的认知）。
当进程j收到进程i时，更新自己的VCj[k]=max{VCi[k], VCj[k]}, k从1-n，即向量内部所有维度都需要更新。
3.1 VC举例
比如同样上面的例子，有a, b, c三个机器，那么就有三个向量维度。
初始状态下每个维度状态都是0：
-
VCa: [0, 0, 0]
-
VCb: [0, 0, 0]
-
VCc: [0, 0, 0]
a发生了1个事件，向量时钟更新： -
VCa: [1, 0, 0]
-
VCb: [0, 0, 0]
-
VCc: [0, 0, 0]
过段时间b和c收到来自a的更新，更新本地向量时钟： -
VCa: [1, 0, 0]
-
VCb: [1, 0, 0]
-
VCc: [1, 0, 0]
同一段时间内，b发生2次事件，更新本地向量时钟： -
VCa: [1, 0, 0]
-
VCb: [1, 2, 0]
-
VCc: [1, 0, 0]
同样，过段时间a和c收到来自b的更新，更新本地向量时钟： -
VCa: [1, 2, 0]
-
VCb: [1, 2, 0]
-
VCc: [1, 2, 0]
向量时钟更新存在一个问题，加入两端同时更新，那么最后应该采用哪个结果，比如b更新为[1, 3, 0], c更新为[1, 2, 1]，那么b和c该如何合并？VC只发现冲突，并不处理，具体的处理方式可以有多种，比如交由客户端进行处理合并、最后一个更新生效（last write win）等。
-
真实时钟-True Time, TT
TT包括一个时间戳t，还有一个误差e（e通常稳定在4ms以内，误差为[-e, +e]）。其实现的基础是基于GPS和原子钟。之所以采用2种技术是为了保证精确度。GPS有一个天线，电波干扰会导致失灵。而原子钟比较稳定，当GPS失灵的时候，原子钟仍然能够保证在一段相当长的时间内，不会出现偏差。
每个数据中心需要部署一些主时钟服务器（Master），其他机器上部署一个从时钟进程（Slave）来从Master进行时钟同步。Master可以采用GPS或者原子钟的方式。Slave定期30s从若干个Master同步时钟信息。
Google Spanner使用了一种延迟提交（Commit Wait）的手段，即如果事务T1的提交版本为时间戳t那么事务T1会在t+e之后才能提交。借用这种方式消除误差e带来的影响，从而保证线性一致性。这种方式的缺点是，事务的提交需要延迟等待，这为系统的性能带来了影响，比如e, g事务有happened-before关系，那么e的延迟提交将导致f被delay；另外，原子钟的实现代价非常高昂。 -
混合逻辑时钟-Hybrid Logical Clock, HLC
刚才我在介绍向量时钟时讲过逻辑时钟的缺点：不能通过C(a)和C(b)的大小推出a, b事件发生的先后顺序。这个会在使用时导致很多困扰，比如一个外部系统在一个逻辑时钟的分布式系统下的2个进程内部先后提交了互不相关的2个事务：e和f，f在e之后再提交。那么理论上应该e先完成，然后再f，但在逻辑时钟视角下，可能f在e之前先完成了。这个问题有几种解决方式，1种是将这个外部系统划入当前分布式系统内，但你不可能杜绝外部系统的调用；另外就是让逻辑时钟和物理时钟达成一致，这个比较困难，混合逻辑时钟HLC就是一种“尽可能”的方式。
混合逻辑时钟是2014年提出的，混合了物理时钟PT和逻辑时钟LC。其推出的目标是为了实现以下4个目标：
- 满足LC的因果一致性happened-before。
- 单个时钟O(1)的存储空间（VC是O(n)，n为分布式系统下的节点个数）。
- 单个时钟的大小有确定的边界（不会无穷大）。
- 尽可能接近物理时钟PT，也就是说，HLC和PT的差值有个确定的边界。这条规则的好处是，只要两次操作间隔大于这个确定的边界，就可以保证因果一致性，无论是否是当前分布式系统内的。
混合逻辑时钟一共64位，高32位是秒级时间戳，低32位是计数。
