今天聊一下时间的话题。在分布式系统中，“时间” 是一个挺有趣，但是很难处理的东西。我把自己的理解简单整理下来。

不可靠的物理时钟

首先，单一节点的物理时钟是不可靠的。

物理时钟本身就有偏差，可是除此之外，可以引起节点物理时钟不准确的原因太多了，比如 clock jump。考虑到 NTP 协议，它基于 UDP 通信，可以从权威的时钟源获取信息，进行自动的时间同步，这就可能会发生 clock jump，它就是说，时钟始终会不断进行同步，而同步回来的时间，是有可能不等于当前时间的，那么系统就会设置当前时间到这个新同步回来的时间。即便没有这个原因，考虑到数据从网络传输的延迟，处理数据的延迟等等，物理时钟是非常不可靠的。

如果一个分布式系统，多个节点想要仅仅依赖于物理时钟来完成什么操作，那么只能祈祷运气足够好了。在 《从物理时钟到逻辑时钟》这篇文中，我已经介绍了对于物理时钟不可靠的问题，我们有一个解决的办法，就是引入 Lamport 逻辑时钟，或者使用向量时钟，这里就不赘述了。

超时

分布式系统中什么样的执行结果最难处理，成功还是失败？其实都不是，最难处理的结果是超时，因为执行超时了，但是系统却并不知道它：

• 是没执行，
• 是执行成功了，
• 还是执行失败了。

所谓超时，一个显然的问题是，超过多少时间才算超时？往往没有一个公式，更没有一个标准答案，我觉得《Designing Data-Intensive Applications》这本书里面对这一点总结得很好——对于超时时间的定义，其实就是一个 tradeoff，一个基于 failure detection delay 和 risk of premature timeouts 之间抉择的平衡。如果超时时间设置长了，就会减少超时判定的误杀，但是对于系统失败的识别就会延迟；反之，如果超时时间设置过短，那就会触发更多看起来是超时的 case，但是它们本身其实并没有真正超时。

通常来说，对于超时的处理，其实办法也不多。一种是放弃，一种是重试。就像消息投递，如果要保证 “至多投递一次”，那在投递超时后，就直接放弃；如果要保证 “至少投递一次”，那在投递超时后，就重试。如果要重试，那就需要引入保证幂等性的机制。

分布式事务 SAGA 对于超时的处理，其实也是遵照上面的原则，在系统内单步都成为事务的基础上，把流程视作一个状态机，无论单步操作是成功还是失败，都会根据清晰的预定义逻辑，触发相应的正向流程或者反向流程，可是唯独超时，多数情况下最有意义的事情就是重试，也只能重试，因为谁也不知道它究竟实际是成功了还是失败了。

说完操作超时，再来说一下节点超时。很多分布式系统中都会使用一种 lease（租约）的机制，比如一个集群中的 leader，作为 leader 会扮演不同的角色，但是必须要 renew 这个 lease，否则超过一定的时间，无论它给不给响应，它都会被开除出 leader 的角色，而 follower 会重新选举（或者其他方式）一个 leader。

比较难处理的是，如果这个节点本来是被 hang 住了，导致了超时，它也已经被踢下 leader 的角色，但是之后它 “活” 过来了（比如经过了一个超长时间的 GC），它还以为自己是 leader，继续去干 leader 干的事，变成了一个假 leader。这其实就是出现了脑裂，本质上是一个一致性的问题。这种情况比较难处理，因为即便有 heartbeat 不断检测，在每两个 heartbeat 的间隙，可能这种重要的变动就发生了。

要解决这种问题，需要使用 token fence 的方法，即让每次最关键的状态数据的更改，携带一个单调递增的 token，这种情况下这个假 leader 发起更改的 token，已经小于系统中最新的 token 了，接收这个数据更改的子系统应该拒掉这个请求。上面说的节点超时的情况我在《谈谈分布式锁》里面有详细说明。

计算机的两种时钟

有两种时钟是计算机普遍支持的，一种叫做 time-of-day clock，就是我们一般意义上的时钟，代表着相对于 1970 年 1 月 1 日的 epoch 时间，也就是 Java 里面 System.currentTimeMillis() 返回的。网络时间协议 NTP 就是用来同步计算机这个时间的。

不过，其实还有一种时钟，叫做 monotonic clock（单调时钟），在 Java 里面相应的接口是 System.nanoTime()。这个时钟有一个特点，就是它永不回头。对于 time-of-day clock 来说，时间是可能 “回头” 的，对于很多应用来说，时间回头是要命的。不过这个时钟给出的具体时间却是毫无意义，如果在不同的机器上调用 System.nanoTime()，会得到完全随机的结果。API 的名字是纳秒，可是这个时钟并不给出到纳秒的时间精度，它的作用是用来帮助计算间隔时间的：在同一个节点，第二次调用的时间减掉第一次调用的时间，这个结果（时间间隔）是严格递增（不回头）的。从这个意义上说，除去时间这个视角本身，这个时钟更像是一个单调的计数器。既然是单调的计数器，就可以用来帮助产生系统严格自增的 ID。

下面是 System.nanoTime() Javadoc 上面的解释：

Returns the current value of the most precise available system timer, in nanoseconds.
This method can only be used to measure elapsed time and is not related to any other notion of system or wall-clock time. The value returned represents nanoseconds since some fixed but arbitrary time (perhaps in the future, so values may be negative). This method provides nanosecond precision, but not necessarily nanosecond accuracy. No guarantees are made about how frequently values change. Differences in successive calls that span greater than approximately 292 years (263 nanoseconds) will not accurately compute elapsed time due to numerical overflow.

TrueTime

一般来说，我们都知道计算机的时钟有误差，可是这个误差是多少，差 1 毫秒还是 1 分钟，并没有任何严格保证。绝大多数接触到的时间 API 也是如此，可是，Google 数据库 Spanner 的 TrueTime API 却。它使用了 GPS 时钟和原子钟两种完全独立的机制来冗余某一个机制失败导致的时钟问题，增加 reliability。此外，它还有和 System.nanoTime() 一样的严格递增的特点。

它有三个核心 API，很有意思：

• TT.now() 它返回 [earliest, latest] 这样一个范围，表示当前时间就在这个范围内；
• TT.after(t) 它返回当前时间是不是肯定在 t 之后
• TT.before(t) 它返回当前时间是不是肯定在 t 之前

有了 TrueTime，这让分布式系统中，本来无法通过物理时钟解决的问题也变得可解决了。比如对于操作冲突的问题，现在的新办法就是等一个 buffer 时间，TrueTime 认为已经前一个操作的结束时间肯定已经过去了，再来启动后一个操作。当然，这个方法的缺点是 throughput，因为整个操作周期因为 buffer 时间的关系变长了。

《四火的唠叨》文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接

不要使用分布式锁

就像 Martin Fowler 说的那样，“分布式调用的第一原则就是不要分布式”，谈分布式锁也要先说，不要使用分布式锁。原因很简单，分布式系统是软件系统中复杂的一种形式，而分布式锁是分布式系统中复杂的一种形式，没有必要的复杂性就不要引入。

有的逻辑是没有副作用的（纯函数代码），那就可以无锁执行；有的数据经过合理的 sharding 之后，可以使用单线程（单节点）执行，那就单线程执行。

比如一种常见的模式就是使用 queue（比如 Kafka），任务全部放到队列中，然后根据 sharding 的逻辑，不同的 consumer 来处理不同的任务，互相之间不会干扰冲突。

还有一个例子是 Kotlin Coroutine，通过指定一个单线程的 dispatcher，也可以保证它执行的操作之间互相不会有多线程的冲突问题。

有了这样的原则以后，再来谈谈几种分布式锁。

数据库锁

分布式系统中，我觉得我们最常见的锁就是使用一个中心数据库来做的。

一种是悲观锁，就是 “select xxx … for update” 这样的，相应的数据行会被锁上，直到 commit/rollback 操作发生。如果被别人锁了，当前线程没得到锁的话就会等着。

还有一种是乐观锁，就是使用版本号，“update … where … version=A” 这样的。如果 update 成功，表示获取锁成功，并且操作也成功；否则就是 update 失败，需要重新获取状态再来操作一遍。

大多数情况下，后者要更高效一些，因为阻塞的时间通常更短，不过在锁竞争比较激烈的情况下，反而效率会反过来。另外一个，悲观锁代码写起来会容易一些，因为 select 语句执行和 commit/rollback 是两步操作，因此二者之间可以放置任意逻辑；而乐观锁则是需要把数据的写操作和 version 的比较放在一条语句里面。

这两种都很常见，基本上我接触过的一半以上的项目都用过两者。这个数据库不一定非得是关系数据库，但是强一致性必须是保证的。

S3

使用 S3 来创建文件，让创建成功的节点得到锁，文件里面也可以放自定义的内容。我们去年的项目用到这个机制。这种方式是建立在 S3 2020 年 12 月 1 日，上线的 strong consistency 的 feature。

大致上，有这样两种思路：

1. 使用 S3 versioning，就是说，在 versioning 打开的情况下，文件的写入不会有 “覆盖” 的情况发生，所有内容都会保留。在创建文件的时候，response 种会有一个 x-amz-version-id header。节点写入文件后，再 list 一下所有的 version，默认这些 version 会根据创建的时间顺序递减排列，后创建的在前，因此比较其中最早的那个 version 和自己创建文件后得到的 version，如果两者相等，说明自己得到了锁。
2. 使用 S3 Object Lock，这个可以控制让第一次写成功，后面的操作全部失败，所以第一次写入成功的节点得到锁。

使用这种方式，对于那些本来就需要使用 S3 文件系统来共享任意信息的情况很方便，但是需要自己处理超时的问题，还有 retention 策略（该不该/什么时候删掉文件）。

Redlock

Redlock 就是 Redis 的锁机制。Martin Kleppmann（就是那个写《Design Data-Intensive Applications》的作者）几年前写过一篇文章，来吐槽 Redlock 在几种情况下是有问题的：

1. Clock jump：Redlock 依赖于物理时钟，而物理时钟有可能会跳（jump），并且这种状况是无法预测的。Clock jump 就是说，始终会不断进行同步，而同步回来的时间，是有可能不等于当前时间的，那么系统就会设置当前时间到这个新同步回来的时间。在这种情况下，依赖于物理时间的锁逻辑（比如超时的判断等等）就是不正确的。
2. Process pause：得到锁的节点，它的运行是有可能被阻塞的。比如 GC，下面这个图说的就是这个情况——client 1 一开始得到锁了，执行过程中有一个超长时间的 pause，这个 pause 导致锁超时并被强制释放，client 2 就得到锁了，之后 client 1 GC 结束，缓过来后恢复执行，它却并没有意识到，它的锁已经被剥夺了，于是 client 1 和 client 2 都得到了锁，对于数据的修改就会发生冲突。
3. Network delay：其实原理和上面差不多，网络延迟+锁超时被强制剥夺和重分配的逻辑，在特定情况下就是不正确的。

问题可以理解，可是仔细想想这个问题的本质是什么？它的本质其实就是消息延迟+重排序的问题，或者更本质地说，就是分布式系统不同节点保持 consistency 的问题，因为 lock service 和 client 就是不同的节点，lock service 认为之前的锁过期了，并重分配锁给了 client 2，并且 client 2 也是这样认为的，可是 client 1 却不是，它在 GC 之后认为它还持有者锁呢。

如果我们把数据的写操作和锁管理的操作彻底分开，这个问题就很难解决，因为两个节点不可能 “一直” 在通信，在不通信的时间段内，就可能会发生这种理解不一致的情况。但是如果我们把写操作和锁管理以某种方式联系上，那么这个问题还是可以被解决的。简单说，就是物理时钟不可靠，逻辑时钟可以解决这个问题。

之后 Martin Kleppmann 提出了解决方案，他的解决方案也就是按照这个思路进行的。他的方法很简单，就是在获取锁的时候，得到一个永远递增的 token（可以被称作 “fencing token”），在执行写操作的时候，必须带上这个 token。如果 storage 看到了比当前 token 更小的 token，那么那个写操作就要被丢弃掉。

Chubby

Chubby 是 Google 的分布式锁系统，论文在这里可以找到，还有这个胶片，对于进一步理解论文很有帮助。从时间上看，它是比较早的。

Chubby 被设计成用于粗粒度的（coarse-grained）锁需求，而非细粒度（fine-grained，比如几秒钟以内的）的锁需求。对于这样一个系统，文中开始就提到 consistency 和 availablity 重要性要大过 performance，后面再次提到首要目标包括 reliability，能够应对较多数量的 clients，和易于理解的语义，而吞吐量和存储容量被列在了第二位。

Chubby 暴露一个文件系统接口，每一个文件或者文件夹都可以视作一个读写锁，文件系统和 Unix 的设计思路一致，包括命名、权限等等的设计都是基于它。这是一个很有意思的设计。

对于一致性的达成，它使用 Paxos，客户端寻找 master 和写数据都使用 quorum 的机制，保证写的时候大部分节点成功，而读的时候则是至少成功读取大部分节点（R+W>N，这个思路最早我记得是 Dynamo 的论文里面有写）；如果 lock 有了变化，它还提供有通知机制，因为 poll 的成本太高。

内部实现上面，每一个 Chubby 的 cell 都是由作为 replica 的 5 个服务节点组成，它们使用 Paxos 来选举 master 和达成一致，读写都只在 master 上进行（这个看起来还是挺奢侈的，一个干活，四个看戏）。如果 master 挂掉了，在 master lease 过了以后，会重新选举。Client 根据 DNS 的解析，会访问到该 cell 里面的某一个节点，它不一定是 master，但是它会告知谁是 master。

分布式锁里面比较难处理的问题不是失败，而是无响应或者响应慢的超时问题。Chubby 采用一种租约的机制，在租约期内，不会轻易变动当前的 master 节点决定。在响应超时的时期，客户端的策略就是 “不轻举妄动”，耐心等待一段时间等服务端恢复，再不行才宣告失败：

这个图的大致意思是，第一次租约 C1 续订没有问题；第二次租约续订 C2 了之后，原来的 master 挂了，心跳请求无响应，这种情况客户端不清楚服务端的状况，就比较难处理，于是它只能暂时先阻塞所有的操作，等到 C2 过期了之后，有一个 grace period；接着再 grace period 之内，新的 master 被选举出来了，心跳就恢复了，之后租约续订的 C3 顺利进行。

这显然是一个异常情形，但是一旦这种情况发生，系统是被 block 住的，会有非常大的延迟问题。思考一下，这种情况其实就是从原来的 master 到新的 master 转换的选举和交接期间，锁服务是 “暂停” 的。再进一步，这个事情的本质，其实就是在分布式系统中，CAP 原理告诉我们，为了保证 Consistency 和 Partition Tolerance，这里的情形下牺牲掉了 Availability；同时，为了保证 consistency，很难去兼顾 performance（latency 和 throughput）。

此外，有一个有点反直觉的设计是，Chubby 客户端是设计有缓存的。通常来讲，我们设计一个锁机制，第一印象就是使用缓存会带来复杂性，因为缓存会带来一致性的难题。不过它的解决办法是，使用租约。在租约期内，服务端的锁数据不可以被修改，如果要修改，那么就要同步阻塞操作通知所有的客户端，以让缓存全部失效（如果联系不上客户端那就要等过期了）。很多分布式系统都是采用 poll 的方案——一堆 client 去 poll 一个核心服务（资源），但是 Chubby 彻底反过来了，其中一个原因也是低 throughput 的考虑，毕竟只有一个 master 在干活。

对于前面提到的 Martin Kleppmann 谈到的那个问题，Chubby 给了两个解决方法：

1. 一个是锁延迟，就是说，如果一切正常，那么持有锁的客户端在释放掉锁之后，另外的客户端可以立即获取锁。但是如果出现超时等等异常，这个锁必须被空置一段时间才可以被分配。这个方法可以降低这个问题出现的概率，但是不能彻底规避问题。
2. 第二个就是使用序列号了，对于写入操作来说，如果请求携带的序列号要小于前一次写入的序列号，那就丢弃请求，返回失败。

回过头思考 Chubby 的实现机制，我觉得有这样几个启发：

1. 不要相信任何 “人”（节点），必须询问到多数人（quorum），多数人的结论才可以认为是正确的。这个方式发生在很多操作上，比如寻找 master，比如选举 master，比如写数据。
2. 超时是很难处理的，它采用了租约的机制保证节点丢失时间的上限，使用 grace period 来容忍 master 选举发生的时延，使用序列号来保证正确性。

《四火的唠叨》文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接