最近在看 Greenplum 的分布式事务执行框架, 发现了一个较为有意思的 bug, 该 bug 出现在判定分布式事务先后次序的逻辑上面, 会导致在执行 21 亿事务之后, 准确来说是 2147483659 次事务之后, 后续的分布式事务可能会构造出错误的分布式快照, 导致了之前的事务插入的数据对之后的事务不再可见. 为了能够搞清楚这个 bug 是怎么发生的, 我们先简单介绍下 GP 中的分布式事务框架.
在 GP 中, 每个 query 在生成执行计划之后会以 motion 节点为界限切分为多个 slice, 针对每个 slice; GP 都会为其分配一个 Gang 来处理这个 slice; 每一个 Gang 由一个或多个位于不同 segment 的 backend 组成. 也即在 segment 视角上, 对于一个 query, 可能会启动多个 backend 来处理这一个 query. 这些 backend 被组织为 SegMates. SegMates 中的 backend 可分为 writer backend 与 reader backend, 其中 writer backend 有且仅有 1 个. reader backend 有 0 个或多个. writer backend 负责处理与 PG 事务模块的交互, 如 local transaction 的开启, local snapshot 的获取等. reader backend 中所有与 PG 事务相关的信息都是从 writer backend 获取的, 包括 xid, 所用到的 snapshot 等. reader backend 完全不会触碰 PG 的事务模块.
每次用户在 GP 中开启一个 distributed transaction 时, 位于每个 segment 上归属于当前 session 的 segmates 中的 writer backend 就会开启一个 local transaction, 之后 distributed transaction 的所有行为都发生在每个 segment 的 local transaction 中. 当 distributed transaction 被提交时, master 上的 QD 就会下发 PREPARE TRANSACTION 命令给每一个 local transaction, 在所有 local transaction 正确地完成 PREPARE 之后, QD 接着会下发 COMMIT PREPARED 命令给所有 local transaction 来完成每个 local transaction 的提交. 当所有 local transaction 提交完毕之后, 整个分布式事务也便认为已经提交完成了.
考虑到 GP 这里引入了 distributed transaction, 那么相应地就需要引入 distributed transaction id, distributed snapshot 这些机制来实现分布式事务下可见性的判定工作. GP 中针对 distributed transaction id, distributed snapshot 的实现基本上就是把 PG 中 xid, snapshot 的实现照搬了一遍, 只不过是把事务的概念扩展到分布式事务. 关于 PG 中 xid, snapshot 的介绍可参考 PG 中的事务: 快照. 这篇文章中所用到的设施都可以在 GP 中找到对等的实现, 比如与 xid 对应的是 distributed transaction id, 即 gxid. 与 ShmemVariableCache->latestCompletedXid 对应的是 ShmemVariableCache->latestCompletedDXid, 与 XidGenLock 对应的是 shmGxidGenLock 这个 lock, 与 PGXACT 对应的结构是 TMGXACT 等等. 在 PG 中, xid 使用 4 bytes 来表示. 可能会溢出轮转, 所以 PG 中引入了 XID WRAPAROUND 方案来解决溢出问题. 在 GP 中, gxid 使用 8byte 来表示, 其中前 4bytes 是当前实例启动时的时间戳 timestamp, 后 4bytes 是一个普普通通的自增计数器 dxid. 前 4bytes 表示的时间戳在 GP 实例一次生命周期中保持不变, 每当用户开启一个分布式事务时, 后 4bytes 的计数器就会自增加 1. 当后 4bytes 计数器到达了 UINT32_MAX, 即 0xFFFFFFFF 时, GP 便会主动 PANIC 触发一次重启开始一轮新的生命周期. 简单, 粗暴.
既然在 GP 实例一次生命周期中, gxid.timestmap 部分一直保持不变, 所以 GP 中针对运行中的事务的先后次序判定便是通过简单地对 dxid 比较来进行. 所以在 CreateDistributedSnapshot() 这个用来构造 distributed snapshot 的函数中: xmin 的计算便是朴素地:
if (gxid < xmin)
xmin = gxid;
与此对应的 PG 中用来构造快照的 GetSnapshotData() 函数, 其对 xmin 的计算则是:
if (NormalTransactionIdPrecedes(xid, xmin))
xmin = xid;
也即需要通过 NormalTransactionIdPrecedes() 这个函数来完成事务先后次序的判定.
到这里一切都没有问题, 平安无事, 直到看到了 GP 中对 ShmemVariableCache->latestCompletedDXid 的更新. GP 中使用 latestCompletedDXid 来存放已经提交的事务中最大的 dxid 值. latestCompletedDXid 将被用来计算 distributed snapshot 中 xmax 字段的取值. 理论上对 latestCompletedDXid 的更新应该是:
if (latestCompletedDXid < currentCompeletedDxid)
latestCompletedDXid = currentCompeletedDxid;
但是实际上 GP 代码中使用的则是:
if (TransactionIdPrecedes(latestCompletedDXid, currentCompeletedDxid))
latestCompletedDXid = currentCompeletedDxid;
也就是错误地使用了 TransactionIdPrecedes() 来完成事务先后次序的判定. 那么这样会不会导致什么问题呢?
在 PG 中的事务: 事务 id 这篇文章提到过 TransactionIdPrecedes() 使用了一种非常非常非常 trick 且高效的操作来完成了在 wraparound 存在的情况下, PG xid 先后次序的判定工作. 如果将 TransactionIdPrecedes() 用于 distributed transaction 先后次序的判定会不会有不符合预期的结果出现呢? 也即简化为: 会不会存在 uint32 类型的两个整数 i, j, 其中 i < j, 但是 TransactionIdPrecedes(i, j) 却返回了 false 呢? 简单, 直接暴力枚举好了:
for (uint32_t i = 3; i < UINT32_MAX; ++i) {
for (uint32_t j = i + 1, j < UINT32_MAX; ++j) {
if (((int32) (i - j)) >= 0) {
printf("%u, %u\n", i, j);
return;
}
}
}
可以看到有很多符合条件的 i, j 组合出现, 准确来说, 对于任意 i, j, i < j; 当 j - i >= 2147483649 时, 此时 i, j 组合都符合如上要求.
这就意味着如果我们先开启一个事务 T, 假设 T.gxid.dxid = 10. 然后我们执行 2147483649 次事务, 使得 ShmemVariableCache->latestCompletedDxid 被更新为 2147483659. 之后我们再提交事务 T, 那么由于 TransactionIdPrecedes(10, 2147483659) 返回了 false, 导致 GP 认为 dxid 10, 比 dxid 2147483659 还要大, 导致了 latestCompletedDxid 被错误地更新为 10. 导致了这之后的事务在构建分布式事务快照时, distributed snapshot 中的 xmax 也被错误地置为 11, 导致了这之前的所有分布式事务都将会被认为处在运行中, 导致了之前事务插入的数据不再可见.
目前已经针对这种情况向 GP 社区提供了 PR, 详细复现步骤可以参考 PR 中的说明.
