本来这是一篇要发到公司博客的技术文，但后来搁置了，最近又在写最新的分布式 TSO 技术分享，于是索性把之前这篇完善一下分享到博客上。由于开发改造，相关的代码存在一些改动，可能与最新的 master 分支存在不一致，所以本篇严格意义上仅针对 PD 的 release-4.0 或更早分支，但整体设计思想和细节还是一脉相承，没有太大变化。

一些背景

TiDB 的事务实现基于 Google Percolator 分布式事务协议，在整个过程中，我们需要一个严格保持线性增长的时间戳来保证事务的 Linearizability。而要在分布式系统中做到这一点，在业界有以下 3 个主流方式：

• True Time
• Hybird Logic Clock
• Timestamp Oracle

Google Spanner 使用的是 True Time，即用一套基于 GPS 全球同步的原子钟级别硬件设备来达到全球范围内的时间一致性，通过对外暴露几个简单的接口即可帮助分布式系统获得线性的时间戳。不过由于不是所有公司都有 Google 这样的财力，同时作为硬件解决方案，其很高的成本和通用性问题让 True Time 的使用对大多数公司只是不能望其项背的存在。

CockroachDB 采用的是 Hybird Logic Clock 方案，HLC 完全是一个算法方案，通过混合物理时间和逻辑时间来达成时间戳的线性增长。由于 HLC 基于 NTP（网络时间协议），考虑到同步错误等问题可能带来的物理时间误差，往往在 HLC 算法中会存在一个有效的时间边界范围，再结合一些事务机制，CockroachDB 实现了仅对单行事务保证线性一致，对于涉及多行的事务则无法保证绝对的线性一致。

TiDB 采用了 PD 进行全局单点统一授时的 Timestamp Oracle 方案。由于只涉及到全局单点且没有复杂的算法，实现起来较为简单。尽管比起上面两个方案，每一次 TiDB 进行事务时都会与 PD 进行网络通信造成额外的开销，但对于常同处于一个 DC 下的 TiDB 与 PD 集群，这部分开销往往在理想范围内。即便是涉及到多个 DC 的事务，我们也会通过一些机制（例如完全涉及本地表的事务可以只需要一个 Local TSO 而无需立即与全局 TSO 进行同步）来进行优化。经过多方面的考量，我们最终选择了 TSO 来作为分布式系统的时间解决方案。下为 TiDB 的架构图，其中 PD 为 TiDB 提供的两大主要功能就是 TSO 授时和数据位置元信息同步。

目标

由于整个集群的 TSO 授时工作都集中在了 PD 身上，所以怎样做到低延迟，高性能和良好的容错，是我们在实现时需要关注的几个目标点。我们主要通过基本结构，校时，授时以及递进这四个部分来讲解 PD TSO 的具体工作原理。

设计原理

基本结构

对于 PD 来说，我们要保证它能快速大量地为事务分配 TSO，同时也需要保证分配的 TSO 永远单调递增，即一旦分配了时间戳 t1，往后再也不可能出现一个时间戳 t2 满足 t2 <= t1。

TSO 是一个 int64 的整型，它由 Physical time 和 Logical time 两个部分组成。Physical time 是当前的 Unix 系统时间戳（毫秒），而 Logical time 则是一个范围在 [0, 1 << 18] 的计数器。这样一来便做到了在每毫秒的物理时间粒度上又可以继续细化成最多 262144 个 TSO，足以满足绝大多数使用场景了。

// server/tso/tso.go
// atomicObject represents a tso
type atomicObject struct {
    physical time.Time
    logical  int64  // maxLogical = int64(1 << 18)
}

实际使用 atomicObject 时，我们会始终将一个指向其值的 UnsafePointer 作为访存 TSO 的唯一方式。比起直接传值，这么做的目的是为了控制 TSO 在调用链之间传递时的行为，避免返回的 TSO 在某一个环节被更改，从而破坏 Linearizability 约束。

校时

PD 的 TSO 授时工作是由集群中 leader 来完成的。为了在 PD 集群中持久化当前分配的最大 TSO，避免因为 leader 挂掉而影响 TiDB 的事务，我们需要把 TSO 的物理时间戳存储到 etcd 中去。同时为了提高响应授时 RPC 请求的速度，我们也要避免与 etcd 交互得过于频繁，不能每有一次 TSO 更新就进行一次 etcd 读写。所以我们要存储的并不能是最近一次的授时结果，而是一个时间窗口的范围，这一点我们会在稍后的时间戳递进实现中做进一步阐述。

每当一个新的 PD leader 被选举出来时，便会进行一次校时，即从 etcd 中取出上一次保存的物理时间戳，并与本地物理时间做比较，进行校对处理。

// server/tso/tso.go
const updateTimestampGuard = time.Millisecond

// Load last timestamp stored in etcd
last, err := t.loadTimestamp()
if err != nil {
    return err
}

next := time.Now()
if typeutil.SubTimeByWallClock(next, last) < updateTimestampGuard {
    next = last.Add(updateTimestampGuard)

用当前系统时间 next 减去上一次在 ectd 中存储时间戳 last，如果小于我们设定的常量 updateTimestampGuard（默认为 1 毫秒），我们就认为需要使用 last 来作为下一次持久化时间戳的起点。不难理解，如果当前系统的时间戳和上一次使用的 TSO 靠的太近或者说甚至小于它，就会存在破坏线性一致性的潜在风险，于是需要通过使用 last 并强制增加一个精度范围来进行控制，从而保证新上任的 leader 所分配的 TSO 一定大于之前所有已分配的 TSO。

save := next.Add(t.saveInterval)
if err = t.saveTimestamp(save); err != nil {
    return err
}

current := &atomicObject{
    physical: next,
}
t.lease = lease
atomic.StorePointer(&t.ts, unsafe.Pointer(current))

紧接着，我们对选出的，需要进行下一次持久化的 TSO 物理时间部分加上一个时间间隔，默认是 3 秒，然后使用 saveTimestamp(save) 将其保存到 etcd 中。PD 这么做的目的是为了能够在这个时间间隔内能直接使用内存里面的 next 的时间戳，避免频繁的与 etcd 进行交互。在内存中直接进行 TSO 计算并返回的性能很高，我们自己内部测试每秒能分配百万级别的 TSO。同时，每当这个时间窗口过期之后，PD 会继续进行同样的动作把 etcd 中的时间更新为 save + 3s。

授时

在上述校时完成的基础上，我们已经在内存中存储了可用于授时的计算数据。为了进一步提高效率和减少开销，我们往往会批量地向 PD 获取 TSO。client 会首先收集一批事务的 TSO 请求，譬如 n 个，然后直接向 PD 发送命令，参数就是 n，PD 收到命令之后，会生成 n 个 TSO 返回给客户端。

// server/tso/tso.go
var resp pdpb.Timestamp
for i := 0; i < maxRetryCount; i++ {
    current := (*atomicObject)(atomic.LoadPointer(&t.ts))
    if current == nil || current.physical == typeutil.ZeroTime {
        return pdpb.Timestamp{}, errors.New("can not get timestamp, may be not leader")
    }
    
    resp.Physical = current.physical.UnixNano() / int64(time.Millisecond)
    resp.Logical = atomic.AddInt64(&current.logical, int64(count))
    if resp.Logical >= maxLogical {
        time.Sleep(UpdateTimestampStep)
        continue
    }
    if t.lease == nil || t.lease.IsExpired() {
        return pdpb.Timestamp{}, errors.New("alloc timestamp failed, lease expired")
    }
    return resp, nil
}

当客户端请求 PD 的 TSO 服务时，返回给客户端的是混合了物理与逻辑时间的 TSO。其中 PD 中的的物理时钟会随着系统时间递增，而逻辑时钟部分只会被动地随着授时请求原子增加。这里我们可以注意到：由于逻辑时钟有范围限制，如果超出这个限制，leader 会选择睡眠 UpdateTimestampStep 长度的时间（默认 50 毫秒）来等待时间被推进。UpdateTimestampStep 为 PD 更新系统时间戳操作的时间片间隔，所以至少等待这样一段时间，系统中的物理时间便一定会被推进，相应的逻辑时间也会重置归零，届时便可以继续分配时间戳。TSO 计算过程中，还需要实时对 leader 的 lease 进行检查，如果 lease 过期则不能继续再分配 TSO，保证 PD 集群中每时每刻有且仅有一个 leader 可以进行 TSO 的生成。

递进

TSO 的递进更新操作随着系统时间的流逝和 leader 续约 lease 一同进行。

// server/server.go
for {
    select {
    case <-leaderTicker.C:
        if lease.IsExpired() {
            log.Info("lease expired, leader step down")
            return
        }
        etcdLeader := s.member.GetEtcdLeader()
        if etcdLeader != s.member.ID() {
            log.Info("etcd leader changed, resigns leadership", zap.String("old-leader-name", s.Name()))
            return
        }
    case <-tsTicker.C:
        if err = s.tso.UpdateTimestamp(); err != nil {
            log.Error("failed to update timestamp", zap.Error(err))
            return
        }
    case <-ctx.Done():
        // Server is closed and it should return nil.
        log.Info("server is closed")
        return
    }
}

UpdateTimestamp 函数主要做三件事情，一是更新当前内存中 TSO 物理时间（逻辑时间只随着分配请求被动递增，不会主动增加），二是检查当前逻辑时间是否超过阈值，三是适时地更新 etcd 中的时间窗口。同时为了保证 TSO 的线性一致性，UpdateTimestamp 函数在整个过程中要保证以下几个约束：

• 物理时间严格单调递增
• 存储在 etcd 的时间戳严格单调递增
• 物理时间必须小于存储的时间戳

先来说一，更新当前内存中 TSO 物理时间，同时保证物理时间严格单调递增，其实只要让 TSO 的物理时间与现实世界同步流逝即可，所以符合直觉的做法就是将其实时地更新为当前系统时间。当然，当前系统时间并不能严格保证约束，系统时间被手动更改，网络校时后系统时间回溯，换选后的 PD leader 系统时间更慢等等都是我们需要考虑到的情况。PD 在这一点上也有做处理，即只有当系统时间大于当前（也就是旧）TSO 物理时间戳时才会对其进行更新，保证约束。在系统时间落后的机器上，TSO 的物理时间不会主动推进，仅在逻辑时间突破限制是被动增加，如此一来便可以做到让 TSO 慢下来等待系统时间追上它的进度。

// Physical time now minus prev.physical
jetLag := typeutil.SubTimeByWallClock(now, prev.physical)
// If the system time is greater, it will be synchronized with the system time.
if jetLag > updateTimestampGuard {
    next = now
}

再来说关于检查逻辑时间是否超过阈值，尽管逻辑时间有 [0, 1 << 18] 的范围，但我们还是要考虑这个范围有被突破的可能，为了避免溢出的发生，我们会实时检查逻辑时间值，当其超过最大范围的一半时（一半这个设定目前是写死的，经过我们的考量其足以覆盖大多数场景），便会清零逻辑时间并给物理时间加上 1 毫秒。

if prevLogical > maxLogical/2 {
    // The reason choosing maxLogical/2 here is that it's big enough for common cases.
    // Because there is enough timestamp can be allocated before next update.
    log.Warn("the logical time may be not enough")
    next = prev.physical.Add(time.Millisecond)
}

最后说三，前文我们提到过 PD 为了能在不频繁与 etcd 进行交互的前提下来进行存储并直接使用内存里的时间戳进行 TSO 分配，会向 etcd 内写入一个时间窗口，并适时地更新这个窗口。注意到代码中这个 updateTimestampGuard 常量，其值为一毫秒，当我们发现上一次存储在 etcd 中的值和当前时间已经接近到一毫秒及以内时，说明上一个窗口时间即将或已经到期耗尽，需要我们对时间窗口进行滑动，开辟新的可用时间空间，即加上默认的 3s 时间间隔并写入 etcd。

// The time window needs to be updated and saved to etcd.
if typeutil.SubTimeByWallClock(t.lastSavedTime.Load().(time.Time), next) <= updateTimestampGuard {
    save := next.Add(t.saveInterval)
    if err := t.saveTimestamp(save); err != nil {
        return err
    }
}

由此一来，我们完整回顾了 TSO 授时工作从一个 PD leader 上任进行初始校时到随时间流逝进行递进的过程设计，并且适时注意了 Linearizability 的约束保证。还通过引入时间窗口等概念提高 TSO 分配的速度，期以达到良好的性能，保证 TiDB 的事务效率。接下来我们会在此基础上，继续讨论一些还可能进行优化的点。

可能的优化点

PD 采用了中心式的时钟解决方案，本质上还是混合逻辑时钟。但是由于其是单点授时，所以是全序的。中心式的解决方案实现简单，但是跨区域的性能损耗大，因此实际部署时，会将 PD 集群部署在同一个区域，避免跨区域的性能损耗。但是有一个绕不开的场景便是跨 DC 授时，上图展示了这样一种情况——我们只能通过 PD leader 来分配 TS，所以对于 client 2 来说，它需要跨 DC 先从 DC1 的 PD 上面拿 TSO，而这样做势必会影响到 client 2 的延迟。但往往用户的业务是有 DC 关联特性的，如果一次事务所涉及的数据读写只会发生在一个 DC 上面，那么我们其实只需要保证当前 DC 内的 Linearizability，如下图所示。

怎样做到在做到本地 TSO Linearizability 的前提下提高效率，又同时能保证之后出现的跨 DC 事务能够不冲突，其实是一个我们现在正在进行，且将来会支持的一个优化点。

除此之外，由于 PD 使用 Go 开发，Go 的 runtime 调度并没有优先级的概念，当 goroutine 越多时，TSO 更新分配的 goroutine 越容易迟迟拿不到执行的机会，从而会致获取 TSO 变慢。goroutine 尽管为开发者提供了非常便利的并发编程体验，但是由于其抽象程度之高，开发者能对调度所做的干涉有限，我们做过诸如绕过 runtime 直接进行网络层面的 syscall 去完成请求的尝试，但效果均不理想，所以 goroutine 调度这一块也是我们需要持续关注去完成优化的一个点。

此外，PD 通过引入 etcd 解决了单点的可用性问题，一旦 leader 节点故障，会立刻选举新的 leader 继续提供服务，理论上来讲由于 TSO 授时只通过 PD 的一个 leader 提供，所以可能是一个潜在的瓶颈，但是从目前使用情况看，PD 的 TSO 分配性能并没有成为过 TiDB 事务中的瓶颈。

推荐阅读

• 分布式事务中的时间戳
• TiKV 功能介绍 - Placement Driver