分布式系统中的时间
分布式系统中不同于单机系统不能使用NTP来获取时间，所以我们需要一个特别的方式来获取分布式系统中的时间，mvcc也是使用time保证读写相互不影响
Logical Time
本质是通过事件发生的顺序，通过相互通信更新自己的时间，即通过a->b 根据通信得到C(a) > C(b)；
每个进程Pi维护一个本地计数器Ci，相当于logical clocks，按照以下的规则更新Ci
1 每次执行一个事件(例如通过网络发送消息，或者将消息交给应用层，或者其它的一些内部事件)之前，将Ci加1
2 当Pi发送消息m给Pj的时候，在消息m上附着上Ci
3 当接收进程Pj接收到Pi的发送的消息时，更新自己的Cj = max{Cj,Ci}
未解决问题：我们不能通过C(a) > C(b) 得出a->b，不能使用真实时间进行事务查询
Vector Clock
VectorClock是一种用向量来表示偏序关系的逻辑时钟，从数据结构上可以理解为一个集合内包含所有节点的“时间戳”，当然这个时间戳并不是物理意义上的时间（也有些实践会同时加入timestamps以解决冲突问题），而是由程序赋予的逻辑计数（count），{Node1:0,Node2:2,Node3:3.......}，如果我们已经统一了向量内的位置对应的node，那么时钟可以直接用一个{0,2,3}来表示。
对于每一个分布式存储的对象副本都有这样一个时间戳，那么存在一下几种关系：
a：本机：{0，0，1} 消息：{0，1，2}。消息的每个节点的count都大于等于本机的，那么舍弃本机，同步消息
b:本机：{0，1，2} 消息：{0，1，1}。消息的每个节点的count都小于等于本机的，那么舍弃消息，保留本机
c:本机：{0，3，1} 消息：{0，1，2}。出现冲突，有的大，有的小，无法判断出来到底谁是最新版本。就要进行冲突仲裁。
ps:vector clock类似于quorum协议，更新的时候将本机vector clock与事务vector clock进行对比，根据规则进行更新
未解决问题：不能使用真实时间进行事务查询
True Time
前面我们说了，NTP是有误差的，而且NTP还可能出现时间回退的情况，所以我们不能直接依赖NTP来确定一个事件发生的时间。在Google Spanner里面，通过引入True Time来解决了分布式时间问题。Spanner通过使用GPS + Atomic Clock来对集群的机器进行校时，精度误差范围能控制在ms级别，通过提供一套TrueTime API给外面使用。
TrueTime API很简单，只有三个函数:
MethodReturn
TT.now()TTinterval: [earliest, latest]
TT.after(t)true if t has definitely passed
TT.before(t)true if t has definitely not arrived
首先now得到当前的一个时间区间，spanner不能得到精确的一个时间点，只能得到一段区间，但这个区间误差范围很小，也就是ms级别，我们用ε来表示，也就是[t - ε, t + ε]这个范围，
假设事件a发生绝对时间为tt.a，那么我们只能知道tt.a.earliest <= tt.a <= tt.a.latest, 所以对于另一个事件b，只要tt.b.earliest > tt.a.latest，我们就能确定b一定是在a之后发生的，也就是说，我们需要等待大概2ε的事件才能去提交b，这个就是spanner里面说的commit wait time，保证误差时间消除掉。
未解决问题：需要专用硬件支持
Hybrid Logic Clock
混合逻辑时钟HLC存储两部分信息，一部分取值来源于本地时钟(物理部分)l，另一部分取值来自于计数器(逻辑部分)c。来源于物理的部分，里面保存的其实是当前所有参与节点的本地时钟的最大值(每次进行事务通信时更新这部分信息)，另一部分则是每次事件或者消息通信时加加，类似逻辑时钟里每次事件都加加。将这两部分称为l和c。用一个混合逻辑时钟跟本地时钟比较大小时，先用比较l部分，如果相等再看c是否为零。每一台机器上都有一个HLC，每次接受消息时都会收到消息的HLC，将消息HLC与本地HLC，本地时钟对比更新本地HLC，基本思想就是更新本地HLC保证是最大的时钟
混合逻辑时钟的算法描述如下：
本地事件或者发送消息时，如果本地时钟pt大于当前的混合逻辑时钟的l，则将l更新成本地时钟，将c清零。否则，l保持不变，将c加1。
l'.j = l.j;
l.j = max(l'.j, pt.j);
if l.j = l'.j then c.j := c.j + 1 else c.j = 0
return l.j c.j
收到消息时，l在 当前的逻辑时钟的l、机器的本地时钟pt、收到消息里面带的l，三者中取最大的。如果l部分是更新为本地时钟了，则将c清零。否则，c取较大的那个l对应到的c加1。保证HLC最大，如果本地时钟最大则重置HLC.c=0
l'.j = l.j;
l.j = max(l'.j, l.m, pt.j);
if l.j = l'.j = m.j then c.j = max(c.j, c.m) + 1
else if l.j = l'.j then c.j = c.j + 1
else if l.j = l.m then c.j = c.m + 1
else c.j = 0
return l.j c.j
通俗理解就是，每个节点都维护了一个自己混合逻辑时钟的当前值。每当发生事件或者消息通信时，这个值都会更新。发出去的消息都会带上自己的时钟。如果收到了消息里面包含更大的本地时钟，则将当前物理部分拉到更大的值。如果消息的物理时间并不比自己大，则根据本地时钟更新。如果物理部分相等，则更新逻辑部分。各节点相互通信的最终结果是，来源于本地时钟的物理部分，最终记录的是所有参与者中最大的本地时钟。这里有一个问题是由于HLC是一个 相对的时间所以当集群中有一台机器时间快了的话，所有时间都提前了，另外这个时间不是一个True Time，这样 导致snapshot读的时间和整体系统运行时间不一致
那么HLC怎么实现snapshot 读呢？我们将HLC作为数据的version，假设e和f事件发生成同一节点上，l.e < l.f ，我们引入一个虚拟事件g，l.e+1 <= l.g <= l.f ，并且 c.g = 0，这样的虚拟事件肯定是能找到的，并且引入一个虚构事件并不影响真实事件发生的先后关系。注意了！这个虚拟事件的时钟其实是可以跟全局的节点比较时序的(l.g, 0) ! 也就意味着，我们可以拿一个本地时钟去确定一个快照了！我们读取HLC<=HLC.g的数据即可
快照是只要happens before我的，我一定能够看到。混合逻辑时钟通过保留了物理时钟部分，使得拿到'全局'的时间戳成为可能，而逻辑时钟里面happens before的因果关系仍然可以保留。
Timestamp Oracle(与Tidb 使用raft来实现时间一致，保证性能呢最够好，保证能读到数据即可，使用raft同步一写多读的话性能上会更好点)
无论上面的Ture Time还是Hybrid Logic Time，都是为了在分布式情况下获取全局唯一时间，如果我们整个系统不复杂，而且没有spanner那种跨全球的需求，有时候一台中心授时服务没准就可以了。
在GooglePercolator系统这，他们就提到使用了一个timestamp oracle（TSO）的服务来提供统一的授时服务，为啥叫oracle，我猜想可能底层用的就是oracle数据库。。。
使用TSO的好处在于因为只有一个中心授时，所以我们一定能确定所有时间的时间，但TSO需要关注几个问题：
网络延时，因为所有的事件都需要从TSO获取时间，所以TSO的场景通常都是小集群，不能是那种全球级别的数据库。
性能，TSO是一个非常高频的操作，但鉴于它只干一件事情，就是授时，通常一个TSO每秒都能支持1m+ 以上的QPS，而这个对很多应用来说是绰绰有余的。
容错，TSO是一个单点，所以不得不考虑容错，而这个现在基于zookeeper，etcd也不是特别困难的事情。
所以，如果我们没法实现TrueTime，同时又觉得HLC太复杂，但又想获取全局时间，TSO没准是一个很好的选择，因为它足够简单高效。
TSO方案
