阿里妹导读
本文从生活中的时间观、事件的因果顺序、逻辑时钟等方面系统的介绍了分布式系统中的时空观是如何构建的。（文末有活动～）
一、生活里的时间观
时间，无疑是我们观察、描述这个世界的主要手段。时间，很重要，与我们每个人的生活息息相关，不过它的本质却很难描述清楚。古代的先贤们对时间有着非常深刻的认识，《论语·子罕》一篇里有云：子在川上曰，逝者如斯夫，不舍昼夜。看来，当我们把时间和事件联系起来，便会对时间产生非常直观且具体的感受。或者说，这个让我们认识到时间其实就是事件的流逝。进一步地，如果我们不断去了解、总结各类事件发生的先后，那么就越来越接近了解这个世界的本质规律，这个也就是《大学》里提到的：物有本末，事有终始，知所先后，则近道矣。翻译成现代语言就是说，时间是用来表达、描述事件因果顺序的手段，这里的事件才是推动世界上万物演化的根本。
图1. 生活中的时间，无处不在
时间对于认知这个世界如此的重要，于是人们便有了时钟（当然，古人也称之为圭表，日晷等）这种表征时间的物化工具。有了时钟，我们可以看着自家的时钟指向了09:00，然后电话联系好友10:00在商场准时碰面，我们知道在10:00的时候一定会在商场见到好友。生活中还有很多根据时间指导人们行动的例子，譬如火车/地铁/公交车的时刻表，学生上课的课程表，银行/商场/店铺的营业时间等等。我们每个人独立地参考着自家的时钟，或者自己的手机去理解这些个时刻表、课程表以及营业时间等，没有任何违和感，也不会因为理解的不一致产生困惑，这种默契仿佛我们每个人都在基于同一个时钟在生活，这个当然也极大了便利了人们的生产生活。
图2. 现实中的时钟是存在误差的
实际上，现实生活中的每个时钟之间是存在微小误差的，只是这个误差足够可控的前提下，并不影响时钟指导我们的生活安排。不过，再微小的误差，随着日积月累也会逐渐扩大，此时我们再基于不同的时钟描述事件，就有可能产生差错。如图2所示，在某个会议室，我们看到这样的景象，墙上的时钟的显示当前时间是11:42，而电视显示屏显示的此刻时间却是11:40，所以，究竟哪个是正确的？会议结束时间究竟以哪个为准？如果按照墙上时钟显示会议已经到期，那么我们的会议室该不该让出？显然，这里会产生困惑，让人无所适从。所以，实际现实生活中的时钟是需要定时校准的，它们对齐的对象是国家授时中心。以我们国家为例，国家授时中心使用了40多台连续运行的不同类型的守时型原子钟，综合产生稳定的原子时，产生的北京时间即为我们国家的时间基准，经由授时系统发播到全国，无形地影响着人们的生产生活。
以上生活中的时钟给予我们两方面的启示：一方面，误差可控的时钟一定是有意义的，可以指导生产生活中对时间误差有一定容忍度的许许多多的事件；另一方面，一个统一的、以恒定速率跳跃的授时中心的存在对于精确指导全局层面描述事件因果也有着重大意义。
二、事件的因果顺序
这个大千世界本身就像一个巨大的分布式系统无时无刻不在运行着，有参与的诸多个体（人类，动物，植物，机器，山川，河流，...），这些个体之间也存在各种形式的交互。当然以所谓分布式系统来分析整个世界的运作机理实在太过于复杂，不过无论如何，生活中对时间的运用是可以极大地启示、指导我们去理解、去设计分布式系统的时空观。生活中的时间最主要的功能是描述一系列事件发生的先后。因此，我们完全相信，如果分布式系统中引入时间概念，一定也是为了解释系统中各类事件的发生先后，并且事件的先后顺序可以解释分布式系统的状态是否正确。
在分布式系统中，信息的交互产生了各类事件，这些存在因果顺序关系的事件持续推进着分布式系统的演化。这里，我们用a->b来表示事件a实际发生在事件b之前，或者称为两个事件的因果序。按照狭义相对论定义的物理时空观，存在因果关系的事件顺序不依赖任何个体的物理时钟，是超脱了时间参考系的绝对存在，因此事件之间的因果序对于描述分布式系统的行为是必要的。实际上，我们可以把个体的事件来源分为两类：
  • 内部事件：此类事件由个体内部独自产生，与其他个体不产生关联；
  • 外部事件：此类事件由其他个体与本个体交互产生，表现形式是消息传递；
图3. 分布式系统中的内部与外部事件
图3是来自参考文献[1]中的例子，展示了一个由三节点组成的分布式系统，横轴方向代表空间，纵轴方向代表时间，越往上表示越晚发生。每个点表示一个具体的事件，波浪线表示信息传递。在图4中我们可以观察到，节点P触发了一个信息传递至节点Q，即事件p1导致了事件q2，这个是所谓的外部事件。而p2之后是p3，这个是节点P内部独自产生的，没有与其他节点交互，这个是所谓的内部事件。
通过引入内部事件/外部事件的概念之后，我们可以描述出图3中的分布式系统发生事件的因果先后顺序，譬如p1->q2->q3->q4->q5->p4。但是我们也发现了因果顺序事件之外的“并发”事件的存在，譬如p3与q3就是并发发生的事件。虽然我们在图上把事件q3标记的比p3发生的更早，但是节点P在事件p4发生之前是没有机会知晓节点Q上事件q3的存在。因此，事件p3与q3是独立并发发生的，无法给定先后顺序。我们把分布式系统中，根据因果关系推导出来的事件顺序定义为偏序（partial ordering），一个合理的分布式系统的设计原则是，根据偏序足以理解该分布式系统是否状态正确，并发独立的事件顺序不应该影响对分布式系统状态正确的理解。
另一方面，一个实现了所有事件全排列的全序（total ordering）也是有意义的，能够指导我们准确实现分布式系统。可以认为，全序是一种特殊的偏序，即包括了原先的因果约束的时间顺序，也给并发独立的事件顺序提供了一个唯一、明确仲裁机制。简单来说，一个分布式系统能够接受并发独立的事件的任意排序，但是“任意”序列无法指导我们具体的系统实现，因此需要从“任意”序列中明确一个出来，这样有利于简化系统的生产实现。
好了，现在我们对时间在分布式系统中的使命有了清晰的认识：利用时间来描述分布式系统中的因果顺序，当然，为了简化分布式系统的实现，很多时间，我们还需要利用时间给分布式系统中的并发顺序给予唯一、确定的先后顺序。
我们首先想到的很可能是利用分布式系统中每个节点机器上的物理时钟，但是正如前文所言，物理时钟是有误差的，这个误差对于指导高并发的分布式系统确定正确的因果序是致命的。举个栗子，事务1要修改机器A，B上的数据，事务2要修改机器B，C上的数据，实际上事务1与事务2是存在严格的因果序的，即事务2在事务1明确提交之后才发起的。但是机器A的物理时间相较于机器B跑的比较快，机器C的物理时间相较于机器B跑的比较慢，那么我们依旧什么判断出来事务1是先于事务2发生的呢？别急，物理时钟不靠谱，我们有逻辑时钟。
三、单调的逻辑时钟
Leslie Lamport应该是首位正式探讨分布式系统中时空构建的科学家，他首先提出了逻辑时钟（Logical Clock）的概念。如图5所展示的，在他的理论假设中，每个节点Pi内都有一个独立的逻辑时钟Ci(e) ，为每个事件e赋予一个代表时间的逻辑值，这里的Ci的逻辑值作用于全局，节点Pi中发生的事件e，有C(e)=Ci(e)。如果两个事件存在因果顺序a->b，那么对应到逻辑时钟C(a)<C(b)。逻辑时钟的增长完全由事件驱动，在Lamport原始的设计中，一个正确且完备的逻辑时钟系统需要满足以下两个原则：
  1. 对于节点Pi，逻辑时间戳Ci在两个连续的事件之间自增，即更新Ci=Ci+1；
  2. 如果节点Pi向节点Pj发送消息m，需要把当前的逻辑时间戳Ci作为消息时间戳带上一并发送，当节点Pj收到了消息<Ci,m>时，更新本地逻辑时间Cj=max(Ci,Cj)+1；
图4. Lamport的逻辑时钟
图4展示了两个节点的分布式系统下，节点P1与P2的本地独立的逻辑时钟如何更新的一个范例。在这个简单的例子，我们也发现了两个节点上存在逻辑时间戳相同的事件，这些在整个系统中看来是并发的事件，先后顺序不影响系统的正确性。但是如前文所言，一个确定的、可比的全局序对于简化分布式系统实现是有意义的。大神在经典论文[1]中也给出了一个从偏序到全序的转换方法：给所有节点编号，当不同节点上逻辑时间相同时，根据节点号的大小进行排序，以此即可得到一个全序。
事实上，一个全序时间戳一定能够包含所有存在因果序事件的大小关系，但是反过来，在一个全序时间戳中存在大小关系的两个事件未必有因果关系。Mattern等人针对这个问题提出了向量时钟（参考文献[2]），相当于是对以上偏序时钟的扩展，从点对点的两个节点扩展到了系统内的所有节点，时间戳以向量形式表征。当一个节点发送消息时，需要带上本节点已知的所有节点的逻辑时钟值，接收方收到后，会对向量内的所有时钟值按照偏序规则更新，得到一个新的向量时钟。显然，向量时钟的扩展性是存在问题的，随着参与节点的增加，通信开销会随之线性增长，并且无法指导全序的产生，这块我们就不延伸讨论了。
Lamport的逻辑时钟概念是分布式系统时空观构建的开山之作，极大地启发了人们思考一个合理的分布式系统如何构建它的时空，如果描述因果序，如果给定全局序。但是，从理论到落地，还存在一个很大的差距：如果每个节点都单独维护一个独立的逻辑时钟，这个开销显然太大了，随着分布式系统中节点数的增加，相应的逻辑时间参考系数量会爆炸。此外，节点之间的所有通信都要带上节点的逻辑时间戳，不允许有back channels的存在，这个约束也会比较限制工业落地。怎么办呢？这个当然不用大神亲自出马，人家都已经指明方向了，你还要自行车？！（类似的，当年Lamport大神提出了Paxos共识协议，业界普遍觉得晦涩难懂，大神又写了一篇白话文版本，大家还是嚷嚷着看不懂，最后Google的工程师解围，表明虽然坑比较多，但是的确能落地，也好用。一直等到2014年Raft的横空出世，终于让Paxos从阳春白雪演变成了下里巴人，业界也开始逐步推广开来）
事实上，第一节里面介绍的生活里的时钟给予我们的启示恰恰就是解决逻辑时钟落地的两大思路：一者，摒弃每个节点独立维护逻辑时钟的概念，全局选取一个中心化的逻辑时钟作为唯一参考系，各个节点与该中心化逻辑时钟交互取号。这个思路演进出来的是TSO（Timestamp Service Oracle）流派；二者，每个节点上天然已经有了物理时钟的依赖，我们不直接依赖物理时钟来给与事件分配时间戳，但是我们可以把物理时钟想象成每台机器上的逻辑时钟，进而提取出一个“已知的最大物理时间”这个逻辑概念，这个逻辑概念是可以为事件分配时间戳的。这个思路演进出来的是HLC（Hybrid Logical Clock）流派。
这里要额外说明一下，除了Lamport开启的逻辑时钟的概念，基于的假设是物理时钟不靠谱，存在较大误差。跟这个思路并行的还有一个Google推出的TrueTime思路，方向是怎么把机器上的物理时钟做精确，误差绝对可控，我们把这个TrueTime流派视为在追求绝对时间参考系。下面，我们就逐个介绍TSO，HLC以及TrueTime这三大流派。
四、全局唯一参考系
TSO是独立部署的中心化服务，这类时间戳解决方案通过一个中心授时的服务器提供时间戳服务。TSO的优势很明显，架构简单并且能够提供严格线性一致性的保障。TSO的问题是会引入额外的一跳取号的网络开销，不过，当前数据中心内部的一跳网络开销已经非常小，通常在零点几个毫秒。此外，经过预取号机制优化的TSO的吞吐可以轻松达到百万TPS，性能不会是瓶颈。因此当前业界中，Google的Percolator，TiDB，Oceanbase 2.0，PolarDB-X，Postgres-XL等等，均采用了TSO的时间戳解决方案。
TSO最主要挑战还是单点故障问题，即中心授时的服务器本身一旦不可用，时间戳服务随机中断。业界通常做法是引入多副本复制状态机（Replicated State Machine）机制。譬如基于Paxos/Raft等共识协议构建TSO服务（你看，还是绕不开Lamport大神），所有取时间戳的请求经由leader处理，一旦leader宕掉会自动触发一轮重新选主，新当选的leader会在旧leader已经分配过的时间戳基础上，继续递增地分配时间戳。重新选举过程是个不可服务窗口，即这个期间的时间戳服务是不可用的。
图5. 全局唯一的基准时钟：TSO
需要说明的是，为了实现时间戳发号能力能力不成为性能瓶颈，譬如要达到上百万TPS，业界通常做法是预取序号机制。做法也比较常规，leader会定期申请一组连续递增的时间戳，并将其中最大的时间戳持久化，面对客户端取号的请求，leader以内存态高效地分配序号。在本轮申请的时间戳耗尽之前，leader会提前、异步地申请出新一组连续递增的时间戳，并继续持久化其中最大值，这样确保leader始终可以以内存态高效地分配序号。一旦发生了failover，重新选举产生的新leader需要先获取旧leader预存的时间戳上限值，基于这个上限值，新leader会申请出新一组连续递增的时间戳并持久化其中最大值，然后再重新对外提供内存态的高效发号服务。整个这个机制能够保障TSO高效发号并且整体上时间戳单调递增、不回退。
我们知道共识协议能够保证任何时候只有一个写请求能达成多数派，但是引入上述预取号优化的TSO，对外提供的发号服务事实上变成了“强一致性读”，此时TSO就会陷入共识协议经典的“双主”陷阱，即新旧leader同时对外提供内存态的取号服务，这样就会事实上打破时间戳单调递增性的基本性质。解决方案是进一步引入租约机制 ，通过租约机制来将不同阶段（generation, term, etc,.）的leadership进行真实时钟维度上的隔离，确保同一时刻，实际只有一个leader提供内存态的发号服务。
总结起来，TSO这个时间戳流派的特点是真的简单好用，将原本散落在每台机器上的逻辑时钟归一到全局唯一参考系。TSO增加的一跳延迟是个潜在问题，当业务拓展到跨数据中心甚至是跨域场景，多出的这一跳延迟会逐步成为主要矛盾。此外，引入共识协议的TSO，在工程实现上，还是要小心谨慎，细致维护。或者说，用共识协议来解决发号器的容错问题，总是感觉有高射炮打蚊子的味道。
五、可控的多参考系
HLC是逻辑时钟的进阶版（参考文献[3]），实现了去中心化，同时考虑了物理时钟和经典的逻辑时钟，来确保事件因果保序的正确性。HLC包含wall time和logic time两部分。注意，这里的wall time是该节点视角已知的当前系统中的最大物理时间，而非节点此刻的物理时间（即没有直接依赖物理时钟作为时间戳参考系）；logic time则用于比较wall time相同的事件之间的先后顺序。在具体设计上，HLC给分布式系统中每个事件分配一个混合的时间戳，比如事件e的HLC记作 l.e，HLC保证能够满足以下三个性质：
  1. 如果事件 e 发生在事件 f 之前，那么 l.e 一定小于 l.f，也就是满足因果关系；
  2. l.e 占用的bit数不变，通常一个整数即可存储，不会随着分布式系统中节点数的增加而增加；
  3. l.e 的值不会无限增长，和事件 e 发生的物理时钟值接近，即| l.e - pt.e |的值会小于一定范围；
HLC依赖的物理时间是以NTP等时钟同步协议为基础的，NTP会协调同步各节点之间的UTC时间，保证各节点的clock skew有上届，不会无限增长。为了保证上述四个性质，HLC实现中实际为每个事件准备了三个维度的计量：事件 j 发生时的物理时钟值 pt.j，事件 j 发生时节点所感知到的系统最大物理时钟值 l.j，事件 j 的逻辑时钟部分 c.j，这里 c.j 是用于几个事件在同一个物理时钟值内发生时比较之间的因果关系。
本质上，HLC要维护的是<l.j, c.j>这个二维的向量递增不回退。因此，发生本地或者发送事件的时候，获取节点上当前的物理时钟值pt.j，如果这个时钟值相较于之前的l.j并没有变高，那么我们只能更新c.j的值确保此种情况下时间的因果顺序能够得到保证；否则更新已知的系统中的最大物理时钟值l.j，并且重置c.j：
if pt.j <= l.j thenc.j = c.j + 1elsec.j = 0; l.j = pt.j
在考虑接收事件的时候，假设从事件 m 发送至时间 j，如果事件 j, 消息 m 和本地物理时钟三个值均相同，那么更新逻辑时钟部分；如果本地物理时钟没赶上HLC的物理时钟，并且事件 j 的逻辑时钟更大，那么增加逻辑时钟的值。如果本地物理时钟没赶上HLC的物理时钟，并且m消息的逻辑时钟更大，那么更新HLC的逻辑时钟部分以及物理时钟部分；其余情况，更新更新HLC的物理时钟部分，而逻辑时钟部分置零：
if l.j == l.m == pt.j then c.j = max(c.j, c.m) + 1elseif pt.j <= l.j and l.m <= l.j then c.j = c.j + 1elseif pt.j <= l.m and l.j <= l.m then c.j = c.m + 1; l.j = l.melsec.j = 0; l.j = pt.j
总结起来，HLC依赖本地物理时钟作为参考提取目前已知的最大物理时间，在遇到本地时钟回跳或者跨机器的时钟误差这个场景，引入逻辑时间来比较相同物理时间下的顺序。图6给出了一个HLC的例子，我们可以发现，即使节点0与节点1的物理时钟有较大差距，但是在两者之间发生了一次通信事件之后，节点1的已知最大物理时间即被推高至10，逻辑时间推高至1，随后在该节点上的两个事件，已知最大物理时间不更新，仅更新逻辑时间值，等待本地物理时钟追上。所以，HLC本质上来说还是一个逻辑时钟，它只能提供partial ordering，而不能提供total ordering。如果2个节点中发生独立事件a和b，他们的时间戳在误差上界范围内，也是无法全局定序的。
图6. 同时依赖物理时钟与逻辑时钟的HLC机制
我们认为，HLC本质上还是为了解决传统的Logical Clock参考系爆炸的问题，引入了有误差的物理时钟作为参考系，巧妙地选取“已知系统最大物理时间”作为时间戳，并且通过引入逻辑时间值作为校准辅助。HLC的问题是，如果某个节点的NTP物理时钟值出现了异常，比如变成一个极大的值，其他节点收到这个故障节点的消息，会导致其他节点的HLC值出现问题，并发请求定序会变得越发的困难。为了阻止故障的扩散，实践中，可以设置HLC物理部分偏差的上限，如果收到的消息物理部分值的偏差超过上限，忽略这条消息，同时系统发送告警等待人工介入处理。
总结起来，HLC机制看着很美，完全分布式的架构，没有额外的网络延迟的开销，解决了参考系爆炸的问题，还能够准确呈现因果序。HLC面临的最大问题还是引入了物理时钟的依赖，并且围绕着控制clock skew要做很多工作，工业落地还是存在较大挑战的。不过，这些年时钟同步协议也持续在演进，除了 NTP, 还有 PTP, DTP 以及 Huygens等各种高精度的时钟同步协议在演进，有理由相信 HLC 的未来也会很不错。
六、绝对时间参考系
接下来聊一聊TrueTime。可以说，TrueTime在解决分布式系统中事件定序的思路上十分的新奇，大胆。他们是以追求绝对物理时间参考系为目标在做这个事情！Google在2012年的Spanner论文（参考文献[5]）中首次提出了TrueTime，它是由硬件和算法组成的高精度物理时钟。时钟硬件由GPS时钟和原子钟组成，使用这两种硬件的原因是因为这两种硬件的故障原因不一样（GPS时钟故障的原因有天线和接收器故障，无线信号干扰等。原子钟可能由于频率问题造成时钟漂移），这样可以更好地提高时钟的可靠性。
图7. Google的土豪玩法，TrueTime
大体的架构如图7，Spanner在全球每个数据中心有若干个TimeMaster机器。大部分TimeMaster机器安装了GPS天线和接收器。剩下的TimeMaster机器安装了原子钟。TimeMaster之间会相互校验时间，如果某个TimeMaster发现自己的本地时间和其他TimeMaster相比差异很大，会把自己设置为离线，停止工作。客户端向多个TimeMaster查询，防止某个TimeMaster出现故障影响结果。当然，即使使用了GPS时钟和原子钟，TrueTime也不能保证绝对的时钟零误差。2012年论文发表时，TrueTime的时钟的误差范围是1ms到7ms，平均4ms。作为一款定位全球数据强一致分布式数据库，这样的时钟误差的控制的确非常出色。
图8. TrueTime应用于分布式事务保序的例子
具体调用语义上，TrueTime返回的是一个时间区间[t-ε,t]（称为[earliest,latest]），真实的物理时间一定会落入这个区间内（这个接口也很新奇，是不是）。换句话说，TrueTime保证任意两台机器的时钟误差不会超过ε（即clock skew的最大值为ε）。我们来看下Spanner是怎么使用TrueTime保序的。以分布式事务为例，Spanner在TrueTime基础之上，利用commit wait来实现了分布式事务的全序。图8展示了T1，T2两个事务，其中T2在T1提交后开启，那么我们期望T2的时间戳一定会大于T1的时间戳。T1在获取了当前的时间，返回[3, 15]，然后在ε个单位的时间之后，再通知各个参与者以15这个时间戳做真正的commit收尾动作。这个等待的操作是保持数据一致性的关键，最极端的情况下，T1的真实时间是区间右边界，T2的真实时间是区间左边界，通过这个等待ε个单位的时间，能够把时钟误差消除掉，维持好因果先后顺序（这里的巧妙之处要品一下，你细品）。
有关TrueTime，以分布式事务为例，基于commit wait提供的全局有序的事务引擎的瓶颈就在原子钟的授时精度上：精度越高，clock skew越小，commit wait的时间越短，整个系统的吞吐量也就越高；反之亦然。当然，依靠TrueTime高精度的时钟误差控制，Spanner提供了出色的性能表现。但是TrueTime这套机制它贵呀，维护起来也很复杂，很适合土豪，这个也导致了TrueTime这只王谢堂前燕，难以飞入寻常百姓家。
七、多样的落地场景
数据库
图9. 分布式数据库提供了很好scalability
数据库领域可以认为是时间戳服务的最大的拥趸。很大程度上，数据库领域的时间戳跟快照隔离是紧密相连的。快照隔离（SI，Snapshot Isolation），对于数据库领域的同学来说是入门级的知识，业界主流的数据库，单机如MySQL、MongoDB，分布式如TiDB、OceanBase，几乎都实现了Snapshot Isolation这一级别的隔离。领域里面的经典之作Clock-SI（参考文献[4]）指出，Snapshot Isolation的正确性包含三点：
  • Consistent Snapshot：快照由SnapshotTS标识，事务可见的快照具备一致性的含义是快照包含且仅包含Commit先于SnapshotTS的所有事务；
  • Commit Total Order：所有事务提交构成一个全序关系，每次提交都会生成一个新的快照，由CommitTS标识；
  • Write-Write Conflict: 事务Ti和Tj有冲突，即它们writeset有交集，且[SnapshotTS, CommitTS]有交集；两个并行事务不允许writeset存在交集，且[SnapshotTS, CommitTS]也不允许有重叠；
相应地，Clock-SI给出了一个精巧的保证SI的Read和Commit两部分协议，厉害之处在于仅依赖物理时钟，并且在特定条件下触发delay来保证快照一致，时钟误差不影响正确性。Clock-SI的算法如下：
  • StartTS：直接从本地时钟获取；
  • Read：当目标节点的时钟小于StartTS时，进行等待；当事务处于Prepared或者Committing状态时，也进行等待；等待结束之后，即可读小于StartTS的最新数据；这里的Read Delay是为了保证Consistent Snapshot；
  • CommitTS：区分出单Partition事务和分布式事务，单Partition事务可以使用本地时钟作为CommitTS直接提交；而分布式事务则选择max{PrepareTS}作为CommitTS进行2PC提交；为了保证CommitTS的全序，会在时间戳上加上节点的id，和Lamport Clock的方法一致；
  • Commit：不论是单partition还是多partition事务，都由单机引擎进行WW冲突检测；
看了Clock-SI的算法，大体上，我们能够领会到，类似HLC的做法，Clock-SI也是利用了物理时钟一直向前走的这个假设，区别是HLC引入了“系统已知最大物理时间”来确保物理时钟一直向前，Clock-SI的方法则比较保守，一个字，等，一直等到看到的物理时间的确是向前走了位置。等的这个策略跟TrueTime也比较类似，区别是TrueTime等的是设计最大clock skew，而Clock-SI等的是两台机器之间的clock skew。总结起来，原生的ClockSI有以下几点创新：
  • 使用普通的物理时钟，同样也是个去中心化的设计；
  • 对单机事务引擎的侵入较小，能够基于一个单机的Snapshot Isolation数据库实现分布式的SI；
  • 区分单机事务和分布式事务，几乎不会降低单机事务的性能；分布式使用2PC进行原子性提交；
在实际的工程实现中，还需考虑时钟漂移，虽然Clock-SI算法的正确性不受时钟漂移的影响，但时钟漂移会增加事务的延迟，包括增加abort rate。根据资料来看，PostgreSQL是实现了Clock-SI的，不过，更多的分布式数据库依赖中心化的TSO来实现快照隔离性，即TSO-SI，譬如Google的Percolator，TiDB，Oceanbase2.0，PolarDB-X，Postgres-XL均是如此。
这里要特别讨论一下跨地域的场景，我们介绍一下PolarDB-X在其IEEE ICDE'22论文中呈现的最佳实践，以2AZ为例，每个AZ内都有单独TSO，各自负责AZ内事务的逻辑时间戳分配。如果有个跨域的事务，以2PC操作为例，事务在发起端AZ访问本地的TSO取号，跨域事务操作会带上本端TSO分配的序号，如果对端TSO当前的逻辑序号低于本端AZ的序号，那么在对端再TICK一下TSO，直接提升最新逻辑时间戳。通过这样的设计，在跨地域场景下并没有引入额外的跨域取号的网络开销，因此也取得了较好的跨域事务的性能表现。
存储产品
图10. 块/文件/对象等分布式存储系统
在各类的分布式存储产品中，如图10展示的，譬如块存储，文件存储，对象存储等，同样存在依赖单调递增的时间戳来解决数据一致性的难题。这里以块存储为例，包括快照、一致性磁盘组均寻求快速建立单个云盘或多个云盘在某一致性时间点下的数据镜像，但是由于分布式系统中缺少全局时钟，往往会给一致性同步点的建立带来了困难。以云盘快照为例，用户写请求潜在的因果关系影响着快照到底应该包含哪些数据：如果用户写请求R1先于写请求R2完成，当R2中的数据被记录在快照中时，那么R1的数据也应记录在快照中；同理，如果用户写请求R3的完成先于发起快照创建之前，那么R3的数据也应记录在快照中。
为了实现数据镜像一致性这个强需求，分布式发号器服务的需求也就应运而生，对外高效提供严格递增的数字序列，给块存储的每个写I/O带上逻辑时钟以便建立时间上因果关系，更方便地确定某个时间点前所有I/O请求。
总的来说，在分布式存储系统中，独立取号这个思路对于业务的改造成本最小，并且存储系统本身已经提供了持久化能力，因此，依赖TSO是个非常合理的实现。当然，这里要考虑好我们前面提到的预取号的优化，双主问题的影响等等。我们的观点是，基于共识来实现一个可容错的发号器，实在有些高射炮打蚊子，因此，我们认为最优的TSO应该是去共识的。
业务系统
图11. 各式各样的业务系统
有别于上述强调因果顺序的时间戳服务，实际上许多业务系统也存在另一类的时间戳服务需求，这些系统对时间戳的最核心诉求是序号的唯一性，例如订单号，活动号以及消息号等。这些业务系统对序号有序并非严格要求。事实上，这类时间戳需求并非本文讨论的强调因果的时间戳范围。为了让读者朋友们更容易理解这里的区别，本文也简单介绍这类时间戳服务。
图12. snowflake的结构
强调全局唯一性的时间戳服务，单点的实现方法有数据库的auto_increment来生成全局唯一递增ID、基于redis incr自增。分布式的实现方法有UUID、snowflake（雪花算法）等。这其中，snowflake应该算是目前应用最为广泛的。我们这里介绍一下snowflake算法，它是twitter开源的分布式ID生成算法，如图12所示，结构上总共 64 个 bit 位，其核心思想是：
  • 1 位符号位，正数是 0，负数是 1，id 一般是正数，因此最高位是 0；
  • 41 位时间戳（毫秒级），41 位时间戳不是存储当前时间的时间戳，而是存储时间戳差值。开始时间戳一般是 Id 生成器开始投入使用的时间，可在程序中指定。41 位时间戳，可以使用 69 年；
  • 10 位机器位，可以部署 1024 个节点，包括 5 位 datacenterId 和 5 位 workerId；
  • 12 位序列号，毫秒内计数，支持每个节点每毫秒产生 4096 个不重复 ID 序号；
snowflake算法单机每秒理论上最多可以生成1000*(2^12)，也就是400万个序号，完全能满足业务需求。该算法的确很好用，分布式的、去中心化、无第三方依赖。但是也是存在软肋的，其强依赖于时钟的特性很容易在时钟回拨的情况下产生重复的序号。
八、时钟的技术选型
图13. 完美的时间戳-六边形战士
说到时钟的技术选型，当然这里提到了是依赖因果顺序的分布式系统，我们尝试罗列了业务希望各种性质，如图13，我们发现这些性质叠加起来就是一个完美的六边形战士！显然这个并不存在，所以，我们说一下技术选型中的一点点建议吧：
如果业务系统能够接受增加的额外一跳取号延迟（特别AZ内延迟已经压的很低，零点几个毫秒），那么可以试一试TSO，这个业界已经有很多成熟的做法，包括成熟的开源软件。此外，如果我们尝试一种全新的去共识的无主发号器，这个进一步在稳定性，工程实现难度上给现有的TSO带来质的提升；
如果业务本身对于引入逻辑时间戳的改造成本能够接受，并且业务的实际使用场景上对于物理时间的误差有较好的控制力，那么不妨试试HLC。事实上，特别在跨机房跨地域场景下，HLC或者TrueTime可以认为是目前已知的实际可行的唯二的方案选举；

参考文章：

[1] Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System"
[2] Friedemann Mattern, "Virtual Time and Global States of Distributed Systems"
[3] Sandeep S. Kulkarni, etc., "Logical Physical Clocks"
[4] Jiaqing Du, etc., "Clock-SI: Snapshot Isolation for Partitioned Data Stores Using Loosely Synchronized Clocks"
[5] James C. Corbett, etc., "Spanner: Google's Globally-Distributed Database"
[6] Dongxu Huang, etc., "TiDB: A Raft-Based HTAP Database"
[7] Wei Cao, etc., "PolarDB-X: An Elastic Distributed Relational Database for Cloud-Native Applications"
[8]  https://www.cs.princeton.edu/courses/archive/fall22/cos418/docs/L18-spanner_pt2.pdf
[9] “时钟与事件：从混乱到有序”：https://zhuanlan.zhihu.com/p/355289092
[10] “Snapshot Isolation综述”：https://zhuanlan.zhihu.com/p/54979396
[11] “深度解析：分布式存储系统实现快照隔离的常见时钟方案”：https://www.infoq.cn/article/0x7mi6f75zxldyubjefz
[12] “分布式唯一ID生成算法——UUID&Snowflake”：https://www.cnblogs.com/-beyond/p/12452632.html
[13] “计算机的时钟（五）：混合逻辑时钟”：http://yang.observer/2020/12/16/hlc/
[14] “计算机的时钟（四）：TrueTime”：https://yang.observer/2020/11/02/true-time/
[15] “PolarDB-X 全局时间戳服务的设计”：https://zhuanlan.zhihu.com/p/360160666
[16] “PolarDB-X 分布式事务的实现（四）：跨地域事务”：https://zhuanlan.zhihu.com/p/415744064
有奖讨论
引入时间概念的分布式系统，让业务更好实现了吗？对于分布式系统构建时空观，你有哪些想要聊的，点击阅读原文来阿里云开发者社区分享你的观点吧，参与讨论即有机会获得双肩背包哦～
继续阅读
阅读原文
关键词
数据
数据库
问题
时间
时间戳