order有些技术点看似无处不在，却很少有人有时间和精力把它们串起来组成一个系统，然后系统地去理解。难得有多人合着的对缓存技术的多角度理解。“身在深渊，不如退而结网”。1什么是时间？2物理时间：挂钟3逻辑时钟：排序事件4真实时间：物理时钟的回归5区块链：重新定义时间6其他影响6.1NTP时间同步6.2限时不可能性6.3延迟6.4租约7总结8参考1什么是时间？时间是一个非常抽象的概念，困扰了无数哲学家。伟人牛顿的绝对时空原理或许代表了大多数人的观点——时间在整个宇宙中是一个不变的常数：在牛顿的时空观中，时间和空间是相互独立、互不相关的两个事物。绝对空间就像一个空房子，它区分了物理事件发生的地方，并用三维坐标来描述它们。绝对时间就像一个滴答作响的秒表，区分物理事件的顺序，并用不可逆的一维坐标来描述它们。“牛顿认为他知道时间是什么”——有人开玩笑说。在牛顿的绝对时空中，时间的概念在整个宇宙中是恒定不变的，时间是衡量事件先后顺序的基础。这很像我们的单机或者紧耦合的计算机集群，时间一目了然，先后顺序也一目了然。在计算机科学的最初几十年里，我们从未考虑过计算机之间的时间。另一位科学大师爱因斯坦在他的狭义相对论中有两个要点：?物理定律，包括时间，对所有观察者都是相同的。?光速是恒定的。广义相对论说，整个时空都是一个引力场，时间和空间都不是连续的。狭义相对论的主要意思是没有概念上的同时性，同时性的概念是相对于观察者而言的，时间的流逝也是相对于观察者而言的。同时，这一理论也表明，当事情发生在很远的地方时，我们需要时间来查明事情是否真的发生过。这个等待时间可能会很长。分布式系统可能比爱因斯坦的宇宙更糟糕。在分布式系统中，信息传播所需的时间范围是不可预测的，可能远远超过太阳光到达地球所需的8分钟。在此期间，无法知道网络另一端的计算机发生了什么。即使你可以通过发送消息来询问或探查，消息的传递和反馈也总是需要时间的。因此，系统延迟时间和超时值的设置是分布式系统的重要设计要点之一。“所有的抽象都是数学，所有的结论都是概率。”我们可以获得信息传播的统计结果，但是我们无法知道每条信息传递的准确时间。从这个角度来看，分布式系统的正确运行是靠运气的概率，概率小到我们认为它是高可靠的。关于时间的本质，恩斯特·马赫说：我们根本没有能力衡量事物随时间的变化。相反，我们通过事物的变化产生时间流逝的抽象概念。在《七堂极简物理课》中，作者指出：过去和未来只有在有热的时候才能区分。区分过去和未来的基本现象是热量总是从热的物体流向冷的物体。所以，爱因斯坦说时间是一种幻觉。从文学意义上讲，不是时间定义了我们的生活，而是我们的生活定义了时间。或许，这就是我们放弃物理时钟而使用逻辑时钟的背景吧！2物理时间：挂钟的物理时间在英文文献中也称为wallclock。挂钟时间，也称为真实世界时间或挂钟时间，是由时钟或挂钟等计时器确定的经过时间。（“墙”这个词最初的名字来源于对挂钟的引用。）在计算世界中，集中式系统明确地计时。例如进程A和B分别在时间t1和t2向系统内核发起系统调用获取时间，获取到的时间一定是t1。独立系统中的时间取决于石英钟，时钟漂移非常小。3逻辑时钟：对事件进行排序分布式系统中的同步和异步都假设了物理时间，但逻辑时钟是第一个摆脱物理时钟限制的时间。逻辑时钟认为，分布式系统中的机器可能无法在时间上达成一致，但它们会在时间发生的顺序上达成一致。消息在发送之前是无法接收的，所以如果进程A向进程B发送消息，我们可以假设A发生在B之前。这样，分布式系统中不同节点上的不同事件之间的因果关系是定义，后面推导的矢量时钟也采用同样的原理。本质上，逻辑时钟定义了事件到整数值的映射。因此，许多逻辑时钟实现使用单调递增的软件计数器，而这个计数器的值与任何物理时钟无关。当分布式系统中的节点和进程使用逻辑时钟时，它们会为事件添加逻辑时钟时间戳，例如文件读写和数据库更新。逻辑时钟的贡献来自LeslieLamport1978年发表的一篇论文《Time, Clocks, and the Ordering of Events in a Distributed System》。4Truetime：物理时钟的回归Google的Spanner提出了一个新的思路，使用一个高精度且可观察误差的本地时钟（TrueTimeAPI）在没有通信的情况下给事件加上时间戳，并据此比较分布公式中两个事件的顺序系统。通过这种方式，Spanner实现了事务之间的外部一致性（externalconsistency，如下图所示）。也就是说，一个事务结束后，另一个事务开始。Spanner可以保证第一个事务的时间戳早于第二个事务的时间戳，这样两个事务在序列化后一定是顺序正确的。.TrueTimeAPI是一个提供本地时间的接口，但它不同于Linux上的gettimeofday接口。除了返回时间戳t之外，它还会给出错误ε。例如返回的时间戳为1分30秒350毫秒，误差为5毫秒，那么实际时间在1分30秒345毫秒和355毫秒之间。在实际系统中，ε平均为4毫秒。使用TrueTimeAPI，Spanner可以保证给事务标记的时间戳在事务开始的实时时间和事务结束的实时时间之间。如果TrueTimeAPI返回的时间是交易开始时的{t1,ε1}，则此时的真实时间在t1-ε1和t1+ε1之间；交易结束时TrueTimeAPI返回的时间为{t2,ε2}，此时的真实时间在t2-ε2到t2+ε2之间。Spanner会选择t1+ε1和t2-ε2之间的一个时间点作为交易的时间戳，但这需要保证t1+ε1小于t2-ε2。为了保证这一点，Spanner在事务执行过程中会一直等待，直到t2-ε2大于t1+ε1时才会提交事务。由此可以推断，Spanner中的一笔交易至少需要2ε时间（平均8毫秒）才能完成。可以看出，虽然这种新方法避免了通信开销，但它引入了延迟。为了保证外部一致性，写延迟是不可避免的，这也印证了CAP定理所揭示的规律，即一致性和延迟之间存在一个trade-off。谷歌为什么采用这种设计？Truetime从根本上解决什么问题？Spanner是为了解决全球范围的分布式系统中关于时间的两个主要问题：在全球范围内同步数据中心之间的时间是非常困难和不确定的这些问题的解决方案是接受不确定性并使用GPS和原子钟来最小化不确定。对于像Spanner这样全球部署或者跨区域部署的系统，如何给事务分配时间戳，保证系统的响应时间在可接受的范围内？如果整个系统使用一个中心节点来分配时间戳，那么系统的响应时间就会变得非常不可控。对于距离中心节点半圈的用户，响应时间估计在100ms级别。如何理解turtime？要了解truetime在事务操作中的作用，首先要看一下Spanner支持的几种事务类型：简单的只读事务。Spanner设计的只读事务有如下要求：?客户端程序自己实现重试动作?读操作必须显式声明没有写入（例如打开文件只读）?系统不会需要获取锁，并且在读过程中不阻塞传入的写操作?系统选择一个时间戳来确定读副本的时间戳?任何满足时间戳的副本都可以用于读操作。当然快照读取更简单，可以不加锁的读取过去的快照。客户可以指定一个时间戳，或者让系统选择一个，不用多说。读写事务使用两级锁来保证外部一致性：Spanner使用truetime机制按照操作发生的顺序在系统中构造一个Linearizability运行记录。因此，我们说Spanner是一个实现了Linearizability的系统。综上所述，Spanner使用全局同步（有一定误差）的物理时间truttimestamp作为系统的时间戳，作为系统中各种操作的版本号。5区块链：重新定义时间中本聪在比特币文章中提出时间戳服务器模型——《Bitcoin: A Peer-to-Peer Electronic Cash System》，为区块链奠定了基础。为了解决双花问题，中本聪设想了一个去中心化的自我验证系统：在基于铸币的模型中，铸币方知道所有的交易并决定哪个先到。为了在没有受信任方的情况下实现这一点，交易必须公开宣布，我们需要一个系统，让参与者就收到他们的顺序的单一历史达成一致。收款人需要证明：对于一笔交易，大多数节点都同意它是第一个收到的。我们提出的解决方案从时间戳服务器开始。时间戳服务器的工作方式是将数据块的散列加盖时间戳并广泛发布散列，例如报纸或Usenet帖子。很明显，时间戳证明数据必须在当时存在，才能进入hash。每个时间戳哈希都包含前一个时间戳的哈希，从而形成一个链，每个后续时间戳都加强了前一个时间戳的有效性。这样就形成了区块链作为时间机器的滴答机制，一个区块高度对应一个时间窗口，这也是区块链也被称为时间机器的原因。为了让时钟均匀跳动，POW区块链会自动调整算法的难度，使滴答周期维持在一个平均的物理时间范围内，比如比特币大约10分钟，以太坊大约15秒。非POW区块链也保持这样的时钟滴答。例如filecoin测试网维持在45秒左右。此外，非POW区块链很难保持固定的时钟节拍。以filecoin为例，全网使用UTC时间戳（类似谷歌之前的做法）来实现固定的物理时间间隔，这就需要全网的服务器与NTP服务器同步，严格的时钟漂移范围（1s）是有限的。由于区块链的时间机器特性，链上数据在不分叉的情况下无法被篡改。也正因为如此，区块链让人联想到物理时间的流逝，熵的增加，能量的消散，“青春已逝，昨日已不复存在”。源于区块链的性质，研究人员正在努力寻找替代解决方案。其中一个非常有吸引力的方案是VDF。VDF是VerifiableDelayFunction的缩写。可验证延迟函数VDF的概念最早是由斯坦福大学计算机科学与电气工程教授、计算机安全实验室联合主任DanBoneh在Crypto2018大会上发布的《Verifiable Delay Functions》论文中提出的。函数显示VDF是一个函数，每个输入都有唯一的输出。延迟可以用时间T（walltime）表示。延迟函数在时间T完成计算，但不能通过并行加速在时间小于T时完成计算。可验证要求延迟函数的输出易于验证。详情请阅读文章《Paxos、PoW、VDF：一条美丽的黄金线》。Function:§uniqueoutputforeveryinputDelay:§可以在时间T内求值§不能在time内求值Verifiable:VDF计算过程中最重要的一点是计算时需要大量的计算资源，但计算量相对较少需要验证资源。这种计算和验证的不对称关系乍一看有点像工作量证明（PoW）。结果，批评接踵而至：“听起来我们又回到了工作量证明”，“我们不能在不烧掉CPU的情况下做到这一点吗？”-文献《VDF不是工作量证明》指出：虽然VDF和传统的PoW算法都具有“难以计算”和“易于验证”等属性。核心区别在于区块链工作量证明的共识算法是可并行的工作量证明，它只有成功的概率。种功能。相比之下，VDF是一种连续的工作量证明，它是一个确定性函数。关于VDF和PoW之间的区别一直存在很多争论。一般来说，PoW直接作为随机数来源是有缺陷的，VDF不能直接替代PoW。然而，这并不意味着VDF不能用于共识协议。原因如下：?PoW不抗并行计算加速，而VDF抗。事实上，PoW对并行计算加速的抵制符合中本聪“一个CPU一票”的愿景，而抵制并行加速的本质只会与这一目的背道而驰。VDF与单CPU计算器相比，多CPU计算器的优势不大。?对于固定的难度设置d，PoW可以有多个合法解，这也是保证PoW共识网络吞吐量稳定，激发矿工竞争的前提。对于给定的输入x，VDF具有唯一的输出（这就是它被称为函数的原因）。总体而言，VDF很好地描述了区块链对时间滴答机制的本质要求。在一些非PoW区块链和非区块链领域，有大量的研究和探索，比如ProtocolLabs和以太坊联合成立的实验室，还有大量对VDF感兴趣的项目。注意：filecoin的协议实现也在考虑VDF：未来版本的Filecoin协议可能会使用可验证延迟函数（VDFs）来强制执行块时间并满足这个领导人选举要求；我们选择明确假设时钟同步，直到硬件VDF安全性得到更广泛的证明。6其他影响与影响人们的生活一样，时间影响计算机系统的方方面面，自然也会影响我们。6.1NTP的时间同步在分布式系统中，时间上的共识是非常困难的。不同机器的石英钟频率可能不一致，会导致不同机器的时间不一致。为了同步不同机器的时间，人们提出了NTP协议。这样，一台机器的时间将取决于另一个外部时钟。NTP协议基于网络通信延迟来回相等的原则。以此为基础，可以得到两台机器的时间差。在NTP服务器上获取的时间（on）加上（时间滞后本机）或减去（时间领先本机）这个延迟就可以设置为本地时间，从而获得时间同步。6.2Impossibilityoflimitedtime1985年，Fischer、Lynch和Patterson发表了他们著名的FLP结果（Impossibilityofdistributedconsensuswithonefaultyprocess）：在异步系统中，如果出现进程故障，系统不可能达成共识.FLP表明，在至少有一个进程可能崩溃的情况下，没有一种算法可以确定性地解决异步环境中的共识问题。在工程应用中，该理论也可以理解为：在故障不稳定的异步系统中，不可能有完美的故障检测器。根本原因是时间。FLP结果并不意味着无法达成共识，只是它并不总是可以在有限的时间内达成。同步系统为进程和进程计算之间的消息传递提供了一个已知的上限。异步系统没有固定的上限。在《分布式系统：概念与设计》一书中，作者针对FLP指出：在分布式系统中，并不意味着如果一个进程出现故障，这个进程就永远无法达成共识。它使我们能够以大于0的概率达成共识，这也符合现实。比如运行在广域网上的分布式系统都是异步的，但是交易系统这么多年却能够达成共识。因此，FLP表现为：在有限的时间内，不可能达成一致。系统有可能或很可能会同意，但这并不能保证。即在异步系统中，不可能在有限的时间内达到一致性。在分布式计算中，试图在异步系统和不可靠的通道上达成共识是不可能的。因此，一般一致性前提需要保证：我们这里不考虑拜占庭式错误，假设消息系统是可靠的。因此，对一致性的研究一般都假设通道是可靠的，或者说没有异步系统在运行。概率深刻地影响分布式系统的可靠性。虽然世界的概率性不允许我们准确推断未来，但预测消息是否会被准确传递已经绰绰有余了。想一想，我们知道在有限的时间内不可能做到绝对一致，那为什么程序员会自信地将超时值设置为5秒呢？就像这个世界的概率本质一样，分布式系统也是建立在概率的基础上6.3延迟很多人把延迟归类为网络延迟，指的是数据在传输介质中传输所花费的时间，即，数据包开始进入网络和开始离开网络之间的时间。事实上，在计算机世界中，延迟无处不在。除了VDF，程序员可能还需要了解以下时序数字：L1cachereference.......0.5nsBranchmispredict。...................................5nsL2缓存参考..........................................................7ns互斥锁锁定/解锁..............................................25ns主存储器引用.........................100ns使用Zippy压缩1K字节......................3,000ns=3μs通过1Gbps网络发送2K字节.....................20,000ns=20μsSSD随机读取..........150,000ns=150μs从内存中顺序读取1MB......250,000ns=250μs在同一数据中心内往返......500,000ns=0.5ms从SSD中顺序读取1MB*......1,000,000ns=1ms磁盘寻道..........10,000,000ns=10ms从磁盘顺序读取1MB....20,000,000ns=20ms发送数据包CA->Netherlands->CA....150,000,000ns=150ms......6.4租约分布式系统中对租约的一般描述如下：租约由授权者授予一段时间授权人一旦签发租约，无论接收者是否收到，也无论后续接收者状态如何，只要租约未到期，授权人就必须遵守承诺，按照承诺执行时间和内容。接收方可在有效期内使用授权方的承诺。只要租约到期，接收方就会放弃授权，不会继续执行。如果重新执行，则需要重新申请租约。租约可以说是分布式系统的心跳机制，通过版本号，时间段，或者某个固定时间点的证书失效。在分布式系统中，分布式锁、集群领导者等角色随时可能发生变化。为了避免死锁或错误的leader认知，一般会设计一个lease机制。7小结本文主要回顾了计算机系统演化过程中的时间问题，尤其是经典分布式系统的时间问题，以及时间带来的顺序问题；讨论了支持拜占庭容错的最新区块链网络系统的时间特性，以及最近对可验证延迟函数的探索。目前的分布式系统无法超越时间和空间的限制运行，系统的设计也受到空间和时间考虑范围的制约。未来，量子计算机在时空约束方面会带来怎样的改变，值得期待。
