PolarDB-X 存储引擎核心技术 | Lizard分布式事务系统-阿里云开发者社区

作者：冷香、攒叶、宋格

PolarDB-X 分布式数据库

分布式数据库架构

关系型数据库作为支撑企业级数据的在线存储方案，发挥了无可替代的作用。随着海量数据的增长，以及面对创新业务爆发性增长的场景，如何能够快速，业务无损的进行在线数据库扩容，对数据库的架构提出了巨大的挑战，除此以外，企业的精细化经营，也要求数据库能够一站式提供事务处理能力和数据分析能力，为了应对这些挑战，分布式数据库应运而生，相比着传统的事务型数据库，分布式数据库着力解决的几个核心技术问题：

能否快速进行水平拆分，线性扩展事务处理能力
能否实现业务无损，像使用单机数据库一样，保证 ACID 特性
能否保证业务持续可用，实现企业级容灾能力
能否扩展多种结构化数据，应对灵活的事务处理和分析处理混合负载

分布式数据库的蓬勃发展，在技术的选型上，也经历了不同的阶段和技术发展路径：

1 基于中间件的 Sharding 分案

在分布式数据库发展的早期，使用数据库中间件实现数据的分片和路由，达到水平扩容的能力，高效的支撑业务的爆发增长。但这种方案使用的中间件部署在应用端，所有的数据分片变动，都要业务感知和配合，同时在分片之间也无法实现数据库的 ACID 特性，所以，中间件的 Sharding 方案只解决了部分数据写入能力的扩展，无法形成一个完整的分布式数据库。

2 基于共享资源池的 Scale Up 方案

在提升扩展能力方面，虽然水平线性扩展能力的 Scale Out 方案是终极形态，但阶段性的 Scale Up 方案能够轻量级的实现有限扩展能力，满足一个时期的要求。另一方面，数据库的云原生化 ( Cloud-Native) 的发展要求的极致弹性能力，同样需要基于资源的池化，形成了以 PolarDB，Aurora 为代表的 Cloud-Native 数据库，不断的分层资源池化，带来不断的弹性能力，并形成扩展能力。

3 基于 Share Nothing/Everthing 的水平扩展方案

在具有分布式计算和分布式存储能力之上，形成的 Share Nothing/Everthing 的方案，在不损失单机数据库所具有的 ACID 能力以外，能够做到对业务无感知的透明水平扩容能力，并能够在分布式协议的基础上，实现业务的持续可用，例如 PolarDB-X, OceanBase，TIDB 等。

PolarDB-X 简介

云原生数据库 PolarDB 分布式版，即 PolarDB-X 是阿里巴巴自主设计研发的高性能云原生分布式数据库产品，为用户提供高吞吐、大存储、低延时、易扩展和超高可用的云时代数据库服务，PolarDB-X 具有：

云原生化，基于存储计算分离的 Share Nothing 架构，实现极致的弹性能力和水平扩展能力
透明分布式，以单机数据库的体验，操作分布式数据库
自研的 Lizard 分布式事务系统，保证 ACID 特性和全局一致性
自研的分布式复制协议 X-Paxos，保证业务持续可用
高效的交互协议 X-Protocol，实现请求流水线处理
行列混合存储，实现 HTAP 处理能力
全面开源，拥抱 MySQL 生态，对 MySQL 全面的兼容

PolarDB-X 架构

PolarDB-X 采用了 Timestamp Oracle (TSO) 架构实现全局授时服务，由集群 GMS 提供，CN (Computing Node) 节点作为入口，除了提供基础的数据分片和路由功能，并实现了强大的执行引擎能力，DN (Data Node)，提供了基础的数据存储服务，并提供分布式事务和高可用能力，CDC (Change Data Capture)，作为数据流通道，提供了数据生态能力，PolarDB-X 总体架构如图所示：

PolarDB-X 分布式存储引擎

作为 DN 和 GMS 节点的存储引擎，其在 MySQL 开源生态的基础上，扩展和自研了大量的核心能力，有效的支撑 PolarDB-X 分布式数据库产品，其中包括：

连续递增的全局自增列
全局有序的TSO发号器
高效稳定的分布式事务
安全严格的全局一致性
持续可用的分布式协议
持久可靠的多副本存储

SEQUENCE 引擎

业务背景

在数据存储中，唯一递增的序列号是一个通用服务，通常用作 1) 数据的有序存储，2) 节点或全局的事件定序。 PolarDB-X 存储引擎实现一个 Sequence 服务，其通过一个逻辑引擎的方式来实现。

使用语法

Sequence 包括一系列属性，包括：起始值 (start value), 最小值 (min value), 最大值 (max value), 步长 (increment by), 缓存 (cache / nocache), 循环 (cycle / nocycle)，其语法如下：

创建 SEQUENCE

CREATE SEQUENCE [IF NOT EXISTS] <数据库名>.<Sequence名称>
   [START WITH <constant>]
   [MINVALUE <constant>]
   [MAXVALUE <constant>]
   [INCREMENT BY <constant>]
   [CACHE <constant> | NOCACHE]
   [CYCLE | NOCYCLE];

访问 SEQUENCE

SELECT Nextval(seq);
SELECT Currval(seq);

实现原理

逻辑引擎

Sequence 底层使用 InnoDB 存储引擎来保存这些属性，所以，Sequence Engine 被定义成一个逻辑引擎，负责sequence 的缓存策略和访问入口，真实的数据保存在 InnoDB 表中。

自治事务

为了保证 Sequence 的唯一特性，Sequence 窗口的滑动，涉及到对底层数据的修改，这一部分修改，使用的是自治事务，也就是脱离主事务上下文，自主提交，如果主事务回滚，获取的 sequence 号将会被丢弃，而不是回滚，以保证其唯一性。

租约窗口

Sequence 根据租约 (lease) 类型的不同，支持了两类 sequence，一类是数字型即 Number Sequence，数字窗口用来实现最大吞吐能力和最少可丢弃数字的最佳平衡。另外一类是时间型既 Time Sequence，时间窗口用来实现最大吞吐能力和最少不可用时间的最佳平衡。

高可用

Sequence 的高可用依赖其所在的存储引擎的高可用方案，Sequence 的修改日志通过 BINLOG 日志和 X-Paxos 协议进行复制，如果发生切换，Sequence 丢弃一个租约窗口的数据，来保证唯一性。在性能上能达到 3万 QPS / Core，并能轻松在上百核的 CPU 上运行并且没有性能热点。

全局自增列

在 MySQL 生态中，Auto Increment 使用非常广泛，在单机数据库 MySQL 下，能够保证其 ID 生成是唯一递增，并尽量连续，在分布式数据库中，数据可能分布在不同的节点中，通常的 Auto Increment 的兼容方法，例如分段法，

如果业务有四个分片，就可以为每个分片进行分段：

分片 1：{ 0001 - 1000 }

分片 2：{ 1001 - 2000 }

分片 3：{ 2001 - 3000 }

分片 4：{ 3001 - 4000 }

使用这种方法，可以达到唯一特性，但无法从全局看到，是连续递增的表现，在分片之间摆动跳号。

SEQUENCE 默认实现了数字型生成器，也就是其窗口租约类型是数字，比如窗口是 100，其 Cache Size 就等于 100，窗口内的数字从内存获取，cache 使用完，就推进到下一个窗口。异常情况，最大可丢失一个窗口的数字，来保障其唯一性，所以，Cache Size 的设置，需协调尽量提升性能和尽可能少丢失窗口数字的平衡。PolarDB-X 分布式数据库中的 Auto Increment 可以对应一个 Sequence，用 nextval 来为这个字段生成唯一连续的数字，保障分布在多节点的数据分片中，实现自增列按照插入的顺序生成。

TSO 发号器

TSO 发号器用来为 PolarDB-X 分布式数据库事件来定序，是分布式事务和全局一致性的基础，同样需要保证，唯一递增，并且实现高吞吐能力，除此以外，TSO 为了表达可读性时间，其设置了特殊的格式：

物理时钟	逻辑时钟	保留位
42位	16位	6位

Sequence 实现的时间型生成器，也就是 lease type 等于 Time，定制 TSO 的格式，使用 42 个 bit 表达毫秒级的物理时间，16 个 bit 表达一个递增的自然数，理论设计上秒级可以实现最大 3000w 的 TPS 吞吐能力，足够支撑一个超大规模的分布式数据库。

其中租约窗口用 Cache Size 来表达，比如：cache size = 2s，其代表租约窗口是 2 秒钟，2秒窗口内的数字从内存生成，并提前推高所有高可用节点到下一个未来2秒的开始，也就是这个窗口，代表异常切换后，TSO发号器可用的最大等待物理时间，以保证唯一性，对于 Cache Size 的设置，需协调最大吞吐能力和最小不可用时间的最佳平衡。

Lizard 分布式事务系统

PolarDB-X 存储引擎，想要实现全局分布式事务的 ACID 特性，和全生态一致性，必须依赖一套分布式事务系统，而MySQL 社区版本的 InnoDB 事务系统，存在诸多的弊端。

InnoDB 单机事务系统

弊端1：Read/Write 冲突严重

InnoDB 事务系统在内存结构中维护了全局活跃事务，包括活跃事务 (transaction) 链表，活跃视图 (read view)链表等结构，并由一把大锁保护，其简略结构如下：

写路径上：

事务启动时，分配事务 ID，并插入到全局的活跃事务 ID 数组中
事务过程中，修改操作会将事务 ID 更新到行记录上来，表示该行记录的最新修改者
事务提交后，将事务 ID 从全局的活跃事务 ID 数组删除

读路径上：

查询启动时，启动 Read View，并将全局的活跃事务 ID 数组拷贝到 Read View 上
查询过程中，根据行记录上的事务 ID 号，判断是否在 Read View 上的活跃事务 ID 数组中来决定可见性

可以看到，无论是写路径还是读路径，都需要访问全局结构（全局活跃事务数组），这个过程需要在一个事务大锁的保护下完成。在过去，这样的设计是高效且可靠的。随着单机 CPU 多核能力的大幅加强，这样的设计越来越成为制约性能提升的瓶颈。以 PolarDB-X DN 节点在公有云上目前售卖的最大规格（polarx.st.12xlarge.25, 90C, 720G, 最大并发连接数2W）为例，压测 Sysbench read_write 场景，CPU 有接近 17% 的时间耗在无用的等待上：

弊端2：Commit 无法外部定序

在 InnoDB 事务系统中，其提交的真实顺序，由内部确定，其产生的提交号为 trx->no，其由内部来递增，外部既不能访问，也不能修改，当在分布式数据库集群中，使用两阶段提交协议进行提交分布式事务时，不同分片的提交号都由自己产生，各不相同，无法实现由 TSO 来统一定序的能力。

弊端3：MVCC 视图无法传播

InnoDB 事务系统的 MVCC 依赖视图 Read View，而 Read View 是由一个活跃事务 ID 数组来表达，其实现：

事务 ID 无法在分片之间同步和识别
数组大小跟当时活跃事务数量有关，无法固定大小和高效传播

这就带来了很大的限制：

在单机存储计算分离的模式下，无法高效使用 read view 进行存储计算下推
在分片集群模式下，无法得到全局一致性版本
在生态上下游下，无法存储 read view 版本

所以，PolarDB-X 存储引擎，自研了 Lizard 分布式事务系统，来替换传统的 InnoDB 单机事务系统。针对 InnoDB 事务系统的弊端，Lizard 事务系统，分别设计了 SCN 单机事务系统和 GCN 分布式事务系统来解决这些弊端，有效的支撑分布式数据库能力。

Lizard SCN 单机事务系统

SCN 事务系统架构

关系型数据库的 MVCC 机制，依赖数据的提交版本来决定其可见性，所以，Lizard 单机事务系统，引入了 SCN (System Commit Number) 来表达事务的提交顺序，并设计了事务槽 (Transaction Slot) 来持久化事务的提交版本号即 SCN，其架构图如下：

写事务：

事务启动时，申请事务槽 Transaction Slot，地址记为 UBA
事务过程中，对修改的记录填入 (SCN=NULL, UBA) 两个字段
事务提交时，获取提交号 SCN，并回填到事务槽上，并完结事务状态，返回客户提交完成

读事务：

查询启动时，启动事务视图 Vision，即从 SCN 生成器上获取当前 SCN，作为查询的 Vision
查询进行时，根据行记录的 UBA 地址找到对应的事务槽，获知事务的状态以及提交号
根据记录 SCN 和视图 SCN 进行数字大小比较，就可以判断可见性

FlashBack 查询

许多用户在线上运维数据库过程中，可能会出现一些误操作，常见的比如更新操作或删除语句没有带限定条件或指定了错误的限定条件，导致数据因为人工误操作而被破坏或丢弃。特别是如果操作的是重要的配置信息，则会严重影响业务运行。这个时候往往需要 DBA 快速对数据进行回滚操作以恢复业务。

然而，数据库进行业务回滚的代价通常是很高的。以 MySQL 数据库为例，通常的手段是：拿最近的一个备份好的全量数据库，然后重放 BINLOG 日志到指定的时间点。这个过程取决于用户备份的频率，可能需要持续一天以上。除此之外，该功能依赖于 BINLOG 日志，在未开启binlog功能的情况下，想要恢复数据库到指定时间点，几乎是没有手段的。

Lizard事务系统提供了 Native Flashback Query 的能力，让用户能够及时回查到过往某个时间点的数据，从而对数据进行回档，以挽救数据库。

FlashBack 查询是数据库针对过去某一个时间点的一致性查询，其需要确定过去某一个时间点的版本号，以及针对这个版本号，保留了数据相应的 undo，以得到一致性的版本。为了满足 FlashBack 查询，Lizard SCN 事务系统支持了可定制的 undo 保留策略和 [SCN - TIMESTAMP] 之间的转换机制。

FlashBack 语法

SELECT ... FROM tablename
  AS OF [SCN | TIMESTAMP] expr;

TIMESTAMP 和 SCN 转换

Lizard SCN 事务系统的视图 Vision，无法识别 Timestamp 作为版本号进行可见性比较，所以，系统启动了一个 SCN snapshot 后台任务，按照用户设置的 Interval 来记录 SCN 和 Timestamp 之间的对应关系，根据保留周期保存在 mysql 库中的系统表中，其表结构如下：

CREATE TABLE `innodb_flashback_snapshot` (
  `scn` bigint unsigned NOT NULL,
  `utc` bigint unsigned NOT NULL,
  `memo` text COLLATE utf8mb3_bin,
  PRIMARY KEY (`scn`),
  KEY `utc` (`utc`)
) /*!50100 TABLESPACE `mysql` */

用户的 AS OF TIMESTAMP 查询，在事务系统内部，首先会查询 snapshot 表，找到对应的 SCN，使用这个 SCN 作为查询视图，再进行可见性比较。

UNDO 保留周期

Lizard SCN 事务系统，保留了两个维度的设置，来灵活制定 undo 的保留周期：

时间维度

参数 innodb_undo_retention 可以制定 undo 保留多长时间，单位为秒

空间维度

参数 innodb_undo_space_reserved_size 可以制定 undo 保留多大的空间，单位为 MB

保留的时间或者空间越大，可以支持的过去的时间点查询也就越久，但也会带来空间上的使用。

实现原理

闪回查询的核心在于历史版本。在 DN 存储引擎中，Purge 系统负责清理Undo中不再需要的历史版本数据。目前Purge系统的推进策略是尽力且及时，导致历史版本数据一旦不被需要，则马上有被清理的可能性。

基于此，引入了Undo Reservation机制。该机制会阻挡Purge系统的推进，让历史版本数据能够在Undo中保留一段足够长的时间，让用户在出现误操作的时候，能够找回误操作之前的数据版本。

当然，如果将所有的历史版本数据都保留下来，Undo空间会膨胀地非常快。针对这种情况，目前Undo Reservation机制会综合考虑两个维度来阻挡Purge系统的推进：时间与空间。

用户可以根据实际需求，调整Undo Reservation阻挡Purge系统的程度。比如，用户可以要求只要Undo的空间不超过10G，就可以一直保留历史版本数据。那么，如果一个数据库在一年内的更新量非常少，则通过Flashback Query功能，甚至可以找回一年前的数据。

下面结合下图以“SELECT ... FROM tablename AS OF $SCN”为例，简单阐述本方案的运作流程。

从图中可以看到，Purge系统的推进被Undo reservation机制所阻挡，仅仅推进到：清理掉SCN小于等于80的事务所产生历史数据。

SELECT * FROM t1 AS OF SCN 150 发起闪回查询。
扫描到一条行记录，发现SCN是无效值，则通过UBA回查Transaction Table，获取事务状态信息。可以看到，该记录的SCN=200，并非本次闪回查询所需要的版本。
通过Rollptr找到本记录的上一个历史版本，发现SCN=150，显然该数据版本是本闪回查询所需要的，返回该行记录给用户。

另外，如果再次进行闪回查询：SELECT * FROM t1 AS OF SCN 60。沿着历史版本链找也没有找到该版本数据，则说明该历史数据已经被 Purge 系统清理掉，此时返回 "Snapshot too old." 错误

SCN 事务系统的代价

相比于 InnoDB 事务系统，Lizard SCN 事务系统带来了巨大的优势：

解绑对全局结构的访问依赖，读写冲突得到大幅缓解
视图升级为 Vision，只有一个 SCN 数字，不再有活跃事务ID 数组，易于传播
支持自定义的 FlashBack 查询

但同时也引入了一些代价，因为事务提交只修改了事务槽，行记录上的 SCN 一直为 NULL 值，所以，每次的可见性比较，都需要根据 UBA 地址访问事务槽，来确定真实的提交版本号 SCN，为了减轻事务槽的多次重复访问，我们在Lizard SCN 事务系统上引入了 Cleanout，一共分为两类，Commit Cleanout 和 Delayed Cleanout。

Commit Cleanout

事务在修改过程中，收集部分记录，在事务提交后，根据提交的 SCN，回填部分收集的记录，因为需要尽量保证提交的速度不受影响，仅仅根据当前记录数和系统的负载能力，回填少量的记录，并快速的提交返回客户。

Delayed Cleanout

查询过程中，在根据 UBA 地址回查事务槽 SCN，判断其事务状态以及提交版本号之后，如果事务已经提交，就尝试帮助进行行记录的 Cleanout，我们称之为 Delayed Cleanout，以便下次查询的时候，直接访问行记录 SCN 进行可见性判断，减轻事务槽的访问。

Transaction Slot 复用

由于事务槽不能无限扩展，为了避免空间膨胀，采用 Reusing 方案。事务槽会持续的保存到一个 free_list 链表上，在分配的时候，优先从 free list 中获取进行复用。

另外频繁的访问 free_list 链表以及从 free_list 链表上摘取，需要访问多个数据页，这带来了巨大的开销，为了避免访问多个数据页，事务槽 page 会被先放入 cache 快表中，下次获取时直接从 cache 快表上获取，这大大降低了读多个数据页带来的开销。

SCN 事务系统性能表现

虽然 Cleanout 带来了部分的代价，但由于分担到了查询过程中，并且没有集中的热点争抢存在，在测试结果上，相比 InnoDB 事务系统，Lizard SCN 事务系统整体的吞吐能力大幅提升。

	QPS	TPS	95% Latency (ms)
Lizard-8032	636086.81	31804.34	16.07
MySQL-8032	487578.78	24378.94	34.33
MySQL-8018	311399.84	15577.15	41.23

（注：以上数据测试环境为 Intel 8269CY 104C，数据量为1600万，场景为 Sysbench Read Write 512 并发）

相比于MySQL-8032，Lizard SCN 事务系统性能提升 30%，延时降低 53%。

Lizard GCN 分布式事务系统

分布式事务模型

能否完整支持事务ACID是企业级分布式数据库最核心的特性。目前，主流的分布式事务模型有：

1.Percolator模型

Percolator 是 Google 在 2010 年提出的一种分布式事务处理模型，它的设计目标是在大规模分布式系统中实现高效的事务处理。Percolator 是一种乐观的事务模型，写写冲突被延迟到事务提交时才会进行检测。可见性与冲突检测依赖于事务的开始时间戳以及提交时间戳。Percolator 模型，包括后续的 Omid 模型，其特点是：实现原理容易理解且易于工程实现，作为一种高效且直接的分布式事务处理模型，被广泛应用于主流分布式数据库，其代表包括：TiDB、OceanBase 等。另外，由于其事务过程数据存放于内存中，事务大小会受到内存资源的限制。

2.Calvin模型

Calvin 模型由 Brown 等人于2012年提出。它旨在提供高性能、高可用性和强一致性的分布式事务处理。Calvin 模型的核心思想是通过全局调度器，事先确定好各个调度节点的子事务执行顺序，从根源上规避掉并发事务的锁资源、缓存资源等资源的开销。为此，Calvin 模型还引入了一种称为 "transaction flow graph"（事务流图）的数据结构，用于描述事务的执行顺序和依赖关系。事务流图是一个有向无环图，其中节点表示子事务，边表示子事务之间的依赖关系。通过事务流图，Calvin 模型可以在分布式环境中实现事务的一致性和原子性。

尽管 Calvin 模型具有许多优点，但也存在一些缺点和挑战。在 Calvin 模型中，每个事务的执行都是独立的，并且在分布式环境中以并行方式执行。这种并行执行可能导致一些数据一致性问题，例如读取到过期或不一致的数据。虽然Calvin 模型提供了一些机制来解决这些问题，如版本控制和冲突检测，但仍然无法完全消除数据一致性的风险。其次，Calvin 模型需要一个全局调度器来协调和管理所有事务的执行。全局调度器需要考虑诸多因素，如事务的依赖关系、并发控制、负载均衡等，这增加了调度的复杂性。此外，全局调度器也可能成为系统的瓶颈，限制了整个系统的扩展性和可伸缩性。

3.XA模型

XA 模型是一种用于管理分布式事务的标准接口规范。它定义了在分布式环境中进行事务处理所需的协议和操作。XA模型的名称来自于 X/Open 组织（现在是The Open Group），它制定了 XA 接口规范，以便不同的事务处理管理器（Transaction Manager）和资源管理器（Resource Manager）之间能够进行协作，实现数据的一致性。

在 XA 模型中，事务管理器（Transaction Manager）负责协调和管理事务的执行，而资源管理器（Resource Manager）则负责管理和操作特定的资源，XA 模型通过定义一组标准的接口和操作，使得事务管理器和资源管理器之间可以进行协作。

XA 模型的核心是两阶段提交（Two-Phase Commit，2PC）协议。在2PC协议中，事务管理器和资源管理器之间通过一系列的消息进行通信，以确保所有参与的资源管理器都在一个事务中执行相应的操作，并且最终要么全部提交，要么全部回滚。在这个过程中，事务管理器作为协调者（Coordinator），负责发起和管理2PC协议的执行。

XA模型的具体实现需要事务管理器和资源管理器都遵循 XA 接口规范。事务管理器需要实现事务的开始、提交、回滚等操作，以及协调 2PC 协议的执行。资源管理器需要实现参与 2PC 协议的相关操作，如准备（Prepare）、提交（Commit）、回滚（Rollback）等。

PolarDB-X 分布式事务模型

PolarDB-X 作为一款企业级的分布式数据库，数据天然分片到不同的存储节点上，跨节点的修改和访问变成了常态，保障数据库的 ACID 特性，以及如何做到透明分布式也变成了一项有挑战的事情。

业务场景和挑战

1.转账模型，如何保证 ACID 特性

如下图所示，一个经典的转账模型，在跨节点的情况下，如何保证事务的原子性，以及跨节点查询的一致性，单机的事务系统已经无法完成。

2.多维度分区键，如何做到业务透明访问

在业务模型设计的时候，对应的业务访问，通常会涉及到多个维度，传统的本地索引无法多维度路由，这就需要引入全局二级索引来应对多维度的业务访问诉求，以便达到业务无感知，并高效的多维度路由访问方式，如何在跨节点的维护全局二级索引，同样需要分布式事务来保证。

Two-Phase Commit 协议

为了实现 PolarDB-X 具有数据库的 ACID 特性和强一致性，其分布式事务模型采用了两阶段提交 (Two-Phase Commit，2PC) 协议，按照严格的 XA Spec 的定义，其中：

1.Transaction Manager

CN 节点承担事务管理的职责，作为协调器 (Coordinator) , 负责分布式事务状态的持久化和分布式事务的推进流转

2.Resource Manager

DN 节点承担事务参与者的职责，作为参与方 (Participants)，负责接受用户数据的修改和事务状态的变化

GCN 分布式事务系统架构

为了实现严格的 2PC 协议， PolarDB-X 存储引擎在 SCN 单机事务系统的基础上，实现了 GCN ( Global Commit Number) 分布式事务系统，其架构图如下：

Lizard 事务系统的事务槽 (Transaction Slot) 在原有的基础上扩展了一个字段，用于保存一个 GCN，即 Global Commit Number，这个 GCN 来源于 TSO 发起号，至此，跨节点的事务将使用 GCN 来代替 SCN 为分布式事务全局定序。

事务原子性

跨节点的分布式事务，严格按照 2PC 协议的标准来实现，根据 XA Spec 定义的接口，CN 节点通过以下的语法来操作 DN 节点，

XA {START|BEGIN} xid
XA END xid
XA PREPARE xid
XA COMMIT xid [ONE PHASE] $GCN
XA ROLLBACK xid $GCN
XA RECOVER

在 XA COMMIT / ROLLBACK 的时候，CN 节点从 GMS 获取一个 TSO，作为本次的外部提交号，也就是 GCN，传给所有 DN 参与方，并持久化。

通过 2PC 协议， PolarDB-X 严格保证用户跨节点事务的原子性。

读强一致性

在用户的跨节点访问中，CN 节点将获取一个 TSO 作为本次查询的 MVCC 视图，并通过 AS OF 查询下发到 DN 存储节点，其语法如下：

SELECT ... FROM tablename
  AS OF GCN expr;

在 GCN 事务系统中，由于分布式事务由 GCN 定序，所以查询的可见性比较，也从单机的 SCN 比较转换成 GCN 比较，来保证全局的强一致性，由于外部定序和两阶段的提交过程，在可见性比较的时候，对于无法决策的 Prepare 状态，PolarDB-X 采用了等待的策略，等事务状态完结，再进行 GCN 的大小比较。

XA 协调日志下沉

协调日志

分布式数据库中，两阶段提交协议（Two-Phase Commit，2PC）是一种经典的分布式事务处理协议。该协议分为两个阶段：准备阶段和提交阶段。在准备阶段，各个节点会将数据状态反馈给协调节点，协调节点再根据各节点的状态，决定是否进行提交。在提交阶段，协调节点通知各个节点进行提交或者回滚操作。

虽然2PC协议可以确保数据的一致性，但其在性能上存在较大问题。一个典型的问题是：两阶段提交过程中，多个节点需要进行通信：发起请求和等待应答。多节点之间的交互次数要比单机数据库要多得多，这导致了严重的延时问题，极大地限制了分布式数据库事务提交的性能和可扩展性。特别是对于OLTP型的业务，其大部分事务都是短平快类型，提交性能对于整个分布式数据库影响巨大。

其次，两阶段提交必须保证故障容灾，各个节点、各个环节都有可能发生异常。因此，协调者通常需要记录协调日志来保证最终各个节点事务的状态是一致的。

可以看到，协调者与协调日志是整个两阶段提交流程的关键，如何降低两阶段提交协议的交互次数，如何保证持久化协调日志，如何善后清理协调日志，如何保证协调日志高可用是分布式数据库设计中的核心问题之一。

日志下沉

在Lizard事务系统中，这些问题都将被妥善处理。其核心思想是：协调日志会被下沉到存储引擎上。当发生分布式事务时，其中一个参与方会被选为主分支。主分支负责持久化协调日志，并提供协调日志反查能力。主分支在事务启动时，会开辟一块事务槽空间；当事务提交或回滚时，相关事务状态会被持久化到事务槽上。其他节点在做故障恢复时，必须先找到主分支，并根据主分支的事务状态驱动本分支的事务完成提交或回滚。

其次，事务槽会被 Lizard 事务系统有目的的保留一段时间，直至事务状态信息不再被需要。随后，事务槽会随着数据库的清理系统自动被清理回收。也就是说，提交和回滚并不是事务的最终状态，当代表事务存在的事务槽信息被清理后，事务最终进入 Forget 状态。

同时，协调日志在内部会通过 X-Paxos 协议实现多副本，彻底保证了协调日志的可靠性。

故障恢复

当发生故障时，协调日志是故障恢复的重要环节。Lizard事务系统提供了协调日志回查能力，以协助故障恢复。

Status	Explain	Action
ATTACHED	正在有 Session 处理该 XA 事务	等待重试
DETACHED	没有 Session 处理该 XA 事务	尝试 attach 该 XA 事务，进行提交或回滚
COMMIT	已提交	提交其它分支
ROLLBACK	已回滚	回滚其它分支
FORGET	事务信息已被清理	事务完结

值得注意的是，XID 是 XA 分布式事务模型里对事务的唯一标识，是一个外部指定的事务标识号，区别于 InnoDB 的 trx_id 以及 MySQL 的 GTID。通过 XID 回查事务状态信息，对于原生 MySQL 是困难的，可能需要触发大量的 IO 操作，影响在线业务。Lizard 事务系统却没有这个顾虑，原因在于：

乐观查找：在 prepare 阶段，会给 CN 节点返回事务槽地址的 Hint 信息，通过 Hint 信息乐观地查找事务槽，大部分情况下以最多一个 IO 的代价查找到相关的事务信息。
悲观查找：Lizard 事务系统捆绑了 XID 与事务槽地址的映射关系，最坏情况下，只需要查找一组事务槽即可，而不需要对事务槽进行全量搜索。另外，为了防止 HA 后退化到全量搜索，这个映射关系会被 X-Paxos 协议广播到所有的副本。

日志下沉 VS 传统2PC

协调日志下沉到存储引擎对于传统 2PC 提交有显著的改进：

协调日志跟随 COMMIT / ROLLBACK 操作，一起完成持久化，甚至是多副本同步，但并不会带来额外的开销
协调日志的清理跟随事务槽的清理，不需要额外复杂的清理机制
缩短了 prepare 的时间，提高了 2PC 提交的吞吐能力。
降低了分布式读/单分片读因为读取到 prepare 事务的记录而被迫阻塞的可能性。

单分片优化

分布式事务的代价

分布式事务相比于单机事务，需要更多的代价：

提交过程需要从 TSO 获取全局事务提交号
提交过程需要进行 2PC 提交，涉及到多个节点之间交互，通信开销显著提升

目前，分布式事务需要完成一个完整的 2PC 提交，同步开销为 3 RT + 2 BINLOG。与之对比，单机事务的同步开销仅为 1 RT + 1 BINLOG。

单分片事务

如果数据的修改仅仅涉及到一个分片，在提交过程中，则完全可以采用一阶段提交来完成，从而节省掉 2PC 提交带来的开销。这样的单机（写）事务在 PolarDB-X 中被称为单分片（写）事务。

同样的，如果数据的查询仅仅涉及到单个分片，也可以不通过与 TSO 交互，直接在 DN 节点上完成查询操作。这样事务在 PolarDB-X 同样被称为单分片（读）事务。

单分片事务与纯粹的单机本地事务看起来很像，但内部逻辑是完全不同。最关键的区别是，单分片事务的可见性判断依赖于全局事务提交号 GCN，而纯粹的单机本地事务的可见性仅仅取决于本地提交号 SCN。

单分片事务提交序

单分片事务的提交号不能从 TSO 获取，因此如何确定单分片事务的提交号，是单分片事务最核心的问题。一个直观的理解是，单分片事务发生在本节点已提交的分布式事务之后，以及本节点已发起的分布式查询之后。即它的提交号必须比本节点所有已提交的分布式事务的提交号大，并且比分布式查询的快照号大。

为此，Lizard 事务系统内部维护了本节点的全局 GCN，该 GCN 被称为 narrow_GCN（narrow GCN, 狭隘的全局提交号）。narrow_GCN 在以下场景会被推高：

分布式查询事务会推高 narrow_GCN
分布式写事务会推高 narrow_GCN

当单分片（写）事务提交时，会获取本节点的 narrow_GCN 作为自己的全局提交号。

另外，单分片（写）事务之间也有提交顺序，该提交顺序仅仅由本地提交号 SCN 决定。

至此，单分片（写）事务的提交号可以确定为（narrow_GCN，SCN），该提交号反映了单分片事务的提交序。

单调递增 narrow_GCN

narrow_GCN 作为提交号，必须要满足单调递增永不回退。narrow_GCN 会被持久化到 Lizard 系统表空间中。然而，如果每次事务提交都需要持久化 narrow_GCN，则会形成严重的性能热点，限制了数据库的整体吞吐能力。

为此，Lizard 事务系统优化了 narrow_GCN 的持久化性能。其核心思想是，对 narrow_GCN 的修改只记录重放日志，而不对实际的数据页进行修改。也就是说，数据页的实际修改会被延后，期间所有的修改都被合并为一次修改，大幅度改善了 narrow_GCN 持久化的性能问题。

可见性

单分片事务与分布式事务并存时，可见性判断会面临巨大的挑战，因为同时会存在分布式读与分布式写，分布式读与单分片写，单分片读与分布式写，单分片读与单分片写的情况。一个典型的案例是：

单分片读启动，并使用当时DN节点的最大 GCN（假设为95）为 Snapshot_GCN 作为视图
单分片写启动，账户A（转账前余额为1000）向账户B（转账前余额为1000）转账100块，并最终提交，取得提交号为 DN 节点的最大 GCN（同样为95）

单分片读可能会读到一个不一致的状态：

当单分片写未提交时，单分片读到账户A的余额为1000块。
当单分片写提交后，单分片读此时才读取到账户B的余额，发现已提交，并且余额为1100

显然，这违反了事务的原子性以及一致性。类似的不一致性问题其它场景下也会发生。

可见性判断的关键在于定序，Lizard 事务系统通过全局提交号加本地提交号组合的方式准确给所有的事务确定先后顺序。更具体地说，可见性判断先依据全局提交号 GCN 来确定顺序，而当 GCN 已经无法确定先后顺序时，会进一步依据本地提交号 SCN 来确定先后顺序。

二级索引可见性

MySQL 的二级索引的修改并不会产生 UNDO，也就是说，二级索引没有多版本。MySQL 原生事务系统对于二级索引可见性判断，主要依赖于数据页上的 max_trx_id 字段，该字段表示了所有修改该二级索引数据页上的事务中，最大的事务ID号。

当 MySQL 查询生成视图时，同时会获取当时数据库里最小的活跃事务ID号。当读取二级索引时：

如果数据页上的 max_trx_id 小于视图的最小的活跃事务ID号，则本数据页上所有的二级索引记录都可见
否则，无法判断出该二级索引的可见性，需要回到主键索引上进行可见性判断。这个过程一般称为回表。

回表需要回到主键上进行 B+Tree 的查找，直到找到对应的主键记录。显然，回表会带来巨大的查询开销，特别是可能会带来大量的随机 IO。一个设计优秀的事务系统，应该尽量减少回表的次数。

MySQL 的二级索引可见性判断是一个很自然的解决方案。然而在分布式查询场景，这个方案就不再可行，原因在于所有的分布式查询，都采用了 Flashback Query。在这种查询下，需要的不是现在的（最新的）系统里的最小的活跃事务ID号，而是当时的（历史的）最小的活跃事务ID号。

一个可靠的方案是：对于所有的二级索引查询都进行一次回表。然而，从上面分析可以获知回表的代价是很高的。

Lizard事务系统采用 TCS (Transaction Commit Snapshot) 方案彻底解决了分布式读查询二级索引总是需要回表的问题。其核心思想是，每间隔一段时间内部产生一个事务系统提交快照信息。该快照信息里保存了当时的事务系统状态，如 GCN, SCN, min_active_trx_id 等等。根据系统配置，保留一段时间内的所有事务系统提交快照信息。

当分布式查询构建视图时，需要拿着视图的 Snapshot_GCN，到 TCS 里查找，找到一个最贴近的 min_active_trx_id来作为数据库在 Snapshot_GCN 时的近似 min_active_trx_id 值，并用该值与二级索引数据页上的 max_trx_id 进行比较来决定二级索引的可见性。

测试结果显示，Lizard事务系统在二级索引可见性上的优化，相比全回表方案，提升在400%以上。

XA 完整性

PolarDB-X的分布式事务依赖于XA模型。然而，MySQL XA事务在多副本策略下，容易导致主备不一致。经过测试，直到 MySQL 8.0.32 版本，经过多轮完善修改后，XA 事务仍然有概率导致主备不一致。该问题的根源在于，BINLOG 日志作为 XA 事务参与方之一，由于其本身为文本追加的格式，事实上并不支持回滚能力。这个问题在 PolarDB-X 的分布式模型中会被放大，原因在于 PolarDB-X DN 节点内部依赖 X-Paxos 的多数派协议，BINLOG 日志同时作为协议的载体，需要承担更多更复杂的状态流转逻辑。

Lizard 事务系统针对 MySQL XA 事务完整性问题，提出了基于 GTID 的全量事务日志回补方案，彻底解决了 MySQL 由来已久的 XA 事务完整性问题。其核心思想是，BINLOG 日志除了承担了内部协调日志功能外，还保存了全量的事务操作日志。在故障恢复中，存储引擎会提供 GTID executed 集合，binlog 日志会根据 GTID 集合，回补在存储引擎中丢失的事务。

全局分布式一致性

异步复制节点一致性

事务型的分布式数据库一般会采用读写分离的模式提升读的性能，因此分布式事务除了保障主库的一致性以外，还需要保证用户在使用读写分离模式下对于备库的一致性。

PolarDB-X 产品上支持主实例和只读实例，主实例由基于 X-Paxos 多数派的 Leader/Follower 角色组成，只读实例由基于 X-Paxos 的 Learner 角色组成。PolarDB-X 针对分布式事务一致性的设计，除了在存储节点（DN）的 Leader 主副本中保存事务信息之外，也会将数据的事务多版本信息同步到 Learner 副本中，可以保证只读实例上的多个分区数据读的一致性。

为了实现异步复制一致性，Learner 节点内部需要维护 apply_index，表达 Learner 节点已经应用的日志位点，如何尽快推高 apply_index 是异步复制一致性的关键部分。 PolarDB-X DN 存储引擎在 Learner 节点上采用多线程并发重放 X-Paxos 日志，内部会维护一段乱序区间，允许局部乱序并发，全局仍然保证有序性。经过测试，这种设计能够充分利用 Learner 节点的并发性能。

异构复制节点一致性

MySQL BINLOG 是MySQL记录变更数据的"二进制日志"，它可以看做是一个消息队列，队列中按顺序保存了MySQL 中详细的增量变更信息，通过消费队列中的变更条目，下游系统或工具实现了与 MySQL 的实时数据同步，这样的机制也称为 CDC（Change Data Capture，增量数据捕捉）。

PolarDB-X 存储引擎为全局提交版本号 GCN，新增了一种 binlog event 类型，保存了全局提交版本号，并作为事务日志的一部分写入到了 BINLOG 文件中，CDC 可以同时为下游的结构化数据，提供版本能力，构建异构节点的一致性。

全局备份一致性

关系型数据库一般会采用全量 + 增量的备份来保障数据安全，在多个存储节点的分布式环境下，如何同时恢复所有存储节点到一个相同的时间点，是全局备份一致性的要求。

PolarDB-X 在存储节点（DN）的数据和变更日志中都保存了分布式事务的全局时钟（包含了时间戳信息），任意时间点的数据恢复（PITR，point-in-time recovery）都可以快速将时间戳转化为分布式的全局时钟，在备份恢复中按数据的版本可见性进行处理，使集群的所有 DN 节点，共同恢复到一个一致的时间点。

PolarDB-X 存储引擎核心技术 | Lizard分布式事务系统