消除 TSO 单点

2020-05-27
PD 分布式事务 TiDB

在 TiDB 中,分布式事务的一致性需要依赖 PD 作为 TSO (Timestamp Oracle,时间戳分配器) 分配的严格单调递增的 ts。这里一个很显然的问题就是,作为一个分布式系统,唯独 TSO 是单点的,看上去总让人觉得哪里不对。

好在大多数情况下,这里的担心是多余的。比如 TSO 在实现上做了大量的并发和 batch 优化,几乎不会遇到性能问题(出了问题往往是因为客户端并发太高,Go runtime 调度不过来)。另外,PD 虽然只有一个在工作,但是也有多个 PD 作为 standby,出了状况随时顶替上来,实际上也没有高可用的问题。

有一种情况确实是受制于 TSO 单点的,就是在跨数据中心的场景。很多时候,本地事务只会访问本地数据,但是由于要去远程获取 ts,这会导致延迟降不下来。因此在这种场景下,消除 TSO 单点还是有意义的。

问题范围界定

单一 TiDB 集群部署在多个数据中心,每个数据中心承载不同的业务,大多数情况下,业务都只访问对应数据中心的数据,另有一些跨多个数据中心的业务。

要求:

  1. 只涉及单个数据中心的事务,不用付出跨数据中心取 ts 的代价。
  2. 跨数据中心的事务,可以接受较高的延迟,但是必须要保证事务一致性,特别是外部一致性(参阅数据库的外部一致性)。

使用 RPC 同步 ts

要满足第一条,显然我们要赋予每个 PD 节点分配 ts 的能力,每个数据中心各自维护一个 ts。

真正棘手的是第二条,为了满足外部一致性,全局事务所拿到的 ts 需要满足:

不难看出,取全局 ts 时涉及到与所有数据中心的 PD 进行同步的过程,鉴于全局事务本身没那么在乎延迟(无论如何都要跨数据中心读写数据了),可以直接通过发 RPC 的方式完成同步。

比如最直接的,类似逻辑时钟的两阶段方案:

  1. client 从所有 PD 取一个最新 ts
  2. 收到所有回复后,client 取所有回复中最大的值 Tmax
  3. client 把 Tmax 发送给所有 PD
  4. PD 收到 Tmax 后,更新自己的内存状态保证后续分配的 ts 一定大于 Tmax
  5. client 收到所有 PD 的回复后,把 Tmax 返回

其中,2 保证了 Tmax 足够大,4 保证了 Tmax 足够小,故而返回的 Tmax 是能满足外部一致性的。

要注意两阶段的过程不涉及到“锁”,每个 PD 在第 1 步返回 ts 后不必等待 client 发过来 Tmax,即便是在收到 Tmax 之前分配了比 Tmax 更大的 ts 也没关系。原因是这些事务是并发的关系,没有确定的外部时序,这个在数据库的外部一致性中也说明过了。

在两阶段方案上进行改进,可以改进成大多数情况下只用 1 次远程 RPC。

  1. client 从所在数据中心取最新 ts 并估算一个 Tmax = ts + x
  2. client 把 Tmax 发给所有 PD
  3. PD 收到 Tmax 后,如果 Tmax 大于自己分配过的最大 ts,则更新自己的内存状态后返回 (ok),否则取一个最新 ts 返回 (fail, ts)
  4. client 判断若所有 PD 都返回 ok,表示 Tmax 符合约束,返回给客户端。否则将 Tmax 设置成所有 (fail, ts) 回复中最大的 ts,并再将 Tmax 发送给所有PD
  5. PD 收到 Tmax 后,更新自己的内存状态保证后续分配的 ts 一定大于 Tmax
  6. client 收到所有 PD 的回复后,把 Tmax 返回

补充说明几点:

使用带误差范围的时钟

如果不想做 RPC 的话,还可以使用类似 Spanner 的方案,也就是维护不同节点之间的时间误差范围。

有了误差范围上界就比较好做了,只访问本地的事务 ts 还是直接取。对于跨数据中心的事务,也是先取本地 ts,假设取到的是一个范围 {t-ε, t+ε},此时需要 sleep(2ε) 后再返回 t+ε 给客户端。

这么做的道理是什么呢?我们来分析一下。

  1. 假想另外的数据中心运行了这个事务的前序事务T1(T1 结束之后,T 才开始),T1 的 ts 最大可能的取值是 t+ε(误差最大,且两个事务间隔无限短),因此 T 的 ts 应该大于 t+ε。
  2. 假想还有一个数据中心运行了这个事务的后序事务T2(T 结束之后,T2 才开始),而 T2 的最小可能的取值是 t-ε(误差最大,且两个事务间隔无限短),因此 T 的 ts 应该小于 t-ε。

显然,这两个条件不能同时满足。除非在这里 sleep 一下。

在 sleep(2ε) 之后,本地的时间范围就变成了 {t+ε, t+2ε},此时再考虑 T2,其最小可能的取值是 t+ε 了。所以此时返回 t+ε 就能同时满足足够大和足够小,进而能保证外部一致性。

还剩下一个问题,就是怎么计算误差上界。可以参考 Spanner 加硬件搞一套 TrueTime,或者使用 NTP 然后手动设置一个上界,不过这样是有风险的,万一 NTP 出了问题超出了上界就有出问题了。

还有一种办法就是不同的 PD 节点之间参考 NTP 的算法,不断互相发 RPC 进行对时,原理大致是这样的,节点给 leader 发一个请求,leader 返回自己的时间戳,比如 12:00:00,节点收到回复后看这次 RPC 花了多长时间,假如是 10s,那说明此时 leader 的时钟范围就是 {12:00:00, 12:00:10},随后节点记录自己本地时钟与 leader 时钟的差异,并在之后不断重复发请求进行校正。

用这个方法,最后误差范围也会在 RTT 附近,和每次直接 RPC 差不多,不对在网络延迟不稳定的时候,可以多次请求取最小值,会比直接 RPC 稳定一些。另外注意要考虑 CPU 频率不稳的情况,留出一些容错窗口。


欢迎加入技术讨论 QQ 群: 481269635 (硬盘在歌唱)
comments powered by Disqus

TiDB1024谜题解题报告

2020-10-24
TiDB Bash

数据库的外部一致性

2020-05-26
数据库 分布式事务

分布式事务的 Commit Point

理解分布式事务原子性(atomic)的关键所在
数据库 分布式系统 TiDB