背景

为了提供外部一致性读，SI隔离级别的分布式事务能力，分布式数据库需要使用全局时间戳，PolarDB-X采用业内经典的TSO(TimeStampOracle)方案，包括TiDB[1]，Oceanbase2.0[2]都采用这种模式。TSO方案的优势是简单，没有外部依赖；缺陷是存在单点，因此我们设计的全局时间戳服务是基于GMS，其基于X-Paxos三副本机制保障高可用。

设计原则

• 任何时候(包含HA切换)，从TSO服务分配的时间戳是单调递增的。
• 由于Paxos/Raft协议不保证任何时候都不会出现“双主”，只能保证任何时候只有一个节点的写能达成多数派，因此TSO服务需要引入租约机制。
• TSO服务的三节点与计算节点尽量部署在同一个region，减少网络RT对事务吞吐的影响。
• TSO会使用物理时间戳，所以需要NTP服务同步三节点之间的系统时间。考虑到NTP误差都是毫秒级别，因此，租约设置为秒级别，减少时钟回退的代价同时减少续租代价。
• 为了保证外部一致性，用户批量取TSO只能用于group-commit，而不能缓存在本地。

时间戳格式

时间戳格式采用物理时钟+逻辑时钟方式，如有必要，以后也可以方便切换为HLC，物理时钟精确到毫秒。

• 时间戳采用物理时钟+逻辑时钟的方式，物理时钟在高42位，逻辑时钟在第16位，保留6位。
• 物理时钟精确到毫秒，物理时钟每个毫秒最多分配65536个，因此整体每秒可以分配6000w个时间戳。
• 按一个事务需要取两个时间戳（快照时间戳和提交时间戳），那么最多可以支持3000wTPS。
• 物理时钟使用UTC时间，采用gettimeofday接口分配，若精确到毫秒，采用42位，可以支持139年，物理时钟没有溢出风险
• 逻辑时钟如果1ms内超出了65536个请求，那么需要等待物理时钟变化后，再继续分配。
• 剩下6个bit作为保留字节，放置在时间戳最低位不影响时间戳大小比较。

租约机制

由于基于X-Paxos的三节点只能保证任何时候只有一个写请求能达成多数派，而TSO读请求可能不涉及写操作，因此无法简单依赖三副本数据节点来保证TSO时间分配的单调递增。为了解决极端情况下，“双主”同时分配时间戳，导致TSO分配的时间戳不满足单调递增问题，必须通过在三副本数据节点上进行写入操作以确定分配时间的唯一性和递增性，这里我们通过租约机制实现这个功能。

每个节点会预分配时间戳，假设在时间点current_time申请Lease，会将current_time+Lease持久化，记为Tsync，那么这个节点就有权限分配这段时间范围[current_time，current_time+Lease)的时间戳；正常情况下，这个节点会不断的续租，[current_time+Lease,current_time+2Lease)…。续租会有一定的提前量，确保整个TSO在提供服务时尽量平滑。

当发生主备切换后，新leader上任时，会首先读取Tsync，若发现current_time < Tsync + NTP最大误差，则说明已经预分配了一部分时间戳，这时候新leader需要等待，直到current_time > Tsync + NTP最大误差，然后将current_time+Lease持久化，持久化信息通过内部表存储。

租约表结构

create table gts_lease(ts_owner varchar(30) primary key, bigint ts);
-- ts_owner: 当前分配时间戳的owner
-- ts：目前已预分配的时间戳

租约设置

• Lease时间一般小于数据节点三副本选主超时时间，不宜设置过大。比如old-leader发生宕机故障后，new-leader需要一直等到预分配时间后，才能提供服务，导致TSO停服时间太久。
• Lease时间也不能设置太小，设置太小，需要频繁进行续租，轻微的网络抖动，就可能导致续租失败。
• 对于Switchover场景，切换很快完成，这个时候需要等待Lease时间才能提供服务，old-leader仍然可以继续提供服务，当old-leader时间戳使用完时，new-leader需要等待NTP误差，导致可能会有短暂的服务不可用。

脑裂问题

极端情况下，当old-leader在提供服务过程中，发生网络分区，new-leader上任，而old-leader还未感知降级，造成“双主”现象。这种情况三副本数据节点无法避免，借助于租约机制，我们确保任何时候都只有一个节点提供TSO服务，虽然提供服务的节点可能不是Leader，一旦它需要续租时，就会因为达不成多数派，导致续租失败。new-Leader在等待租约结束后，就能上任继续提供服务。因此，即使出现脑裂情况，借助于租约机制仍然能保证分配时间戳是单调递增的。

核心流程

流程图

主要逻辑

• 判断是否在租期内，如果不是则报错
• 优先获取物理时钟，如果大于上次获取值，逻辑时钟置0，如果等于上次时间值，逻辑时钟加1，如果小于上次时间（物理时间回卷），报错
• 如果逻辑时间加满，等待下一物理时间到来，最多等待1ms
• 续租由单独线程完成，更新gts_lease表续租成功后，更新内存中的租期

HA机制

新leader上任

1. 从租约表读取记录，如果不存在(第一次初始化)，则写入一条记录；
2. 从表中读取时间戳，如果发现租约还未到期，并且owner不是自己，则等待；
3. 续租，预分配时间戳，更新gts_lease表；
4. 在内存中保存最近一次预分配的时间戳，用于分配TSO线程判断是否在租期内。

failover

如上图所示，当leader从A节点变换成B节点，存在2种情况，一种是正常leader变更，全局只有一个节点认为自己是leader，另一种是发生了网络分区A/BC，A、B同时都认为自己是leader。下面从这两种情况讨论TSO服务的正确性。

1. 在leader A没有异常时，A正常提供TSO时间戳分配服务；
2. leader A发生异常，follower B发生三节点选举超时，进行选举成为新leader，TSO服务在收到TSO分配请求后，尝试续租TSO的lease，再等待物理时间大于Tsync + NTP最大误差后，正常续租，提供TSO服务；
3. leader A和B、C发生网络分区，部分TSO请求发到了B节点上，B节点尝试续租TSO的lease，A节点也在提供TSO服务，但由于A节点无法续租，A只能提供到物理时间到达Tsync之前的TSO服务，B在物理时间大于Tsync + NTP最大误差后，提供TSO服务。租期保证了A、B提供服务返回的TSO没有交叉，等待NTP最大误差又保证了B、A提供服务不存在交叉，因此提供的TSO满足单调增要求。

SLA分析

假设Paxos三节点的选主租约是5s，TSO服务的租约是2s，那么按以下几种故障情况分析

1. old-leader宕机重启，未超过选主租约时间，停服时间为重启时间，重启后继续服务。
2. old-leader永久性宕机，停服时间为5s，直到新主上任，比如选主200 ms。
3. old-leader网络分区，old-leader仍然能提供TSO服务，最好情况下，刚申请完租约，发生网络分区，可以继续提供服务2s，直到租约分配完；最坏情况，续租失败，则停服时间2s，停服时间为[2s, 5s]
4. 正常主备切换，访问角色为follower，会报错，需要client端重新路由到新leader。new-leader需要等待NTP误差，几乎不停服。

吞吐性能

TSO服务使用私有协议进行TSO的获取，直接采用类似RPC的方式进行获取，尽可能减少了额外的性能开销。

下图展示了并发场景下TSO获取性能，网络延迟在0.1ms左右，服务端为32c的数据节点，客户端为32个TCP连接的私有协议连接池（并发超过32时会采用会话连接解绑，复用TCP连接）。

Grouping优化

并发场景下，每个线程都通过一次RPC获取TSO，本身对服务器就是一个巨大的压力，这时我们通常会采用grouping优化，在牺牲部分RT的情况下，用batch的方式，通过一次RPC请求，拿到多个TSO。

Grouping优化基本思路是这样的，如下图所示，对于需要请求TSO的线程，在进入获取对应的函数后，首先进行一次排队，由队首的线程或额外的服务线程，统计队列中需要获取TSO的线程的数目，然后通过一次RPC流程获取对应数量的时间戳，并顺序分配给队列中的线程。因此通过grouping优化，可以在平均牺牲0.5 RT的情况下，将TSO请求的并发降到1。

总结

全局时间戳服务作为提供分布式事务外部一致性的重要保证，对整个分布式系统的可用性也起至关重要的作用。PolarDB-X提供了TSO的方案，并针对正确性、可靠性、可用性和性能做了很多优化，使其SLA可控，完全满足分布式数据库的使用。目前PolarDB-X分布式事务，未来也会考虑基于HLC逻辑时钟优化跨机房场景，大家可以敬请期待新的技术揭秘。

[1] https://docs.pingcap.com/zh/tidb/stable/optimistic-transaction
[2] https://zhuanlan.zhihu.com/p/78402011