数据库内核那些事｜PolarDB分布式版存储引擎之事务系统（上）

阿里云数据库 2023-09-15

269

导

读

云原生数据库PolarDB分布式版（PolarDB for Xscale，简称“PolarDB-X”）是阿里云自主设计研发的高性能云原生分布式数据库产品。作为PolarDB for Xscale分布式数据库产品存储引擎的核心技术模块， Lizard事务系统承担了重要角色。本篇文章将分为两部分对其进行深度解读，上篇介绍Lizard SCN单机事务系统，下篇介绍 Lizard GCN分布式事务系统。

PolarDB for Xscale 分布式数据库

分布式数据库架构

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

1. 能否快速进行水平拆分，线性扩展事务处理能力；

2. 能否实现业务无损，像使用单机数据库一样，保证ACID特性；

3. 能否保证业务持续可用，实现企业级容灾能力；

4. 能否扩展多种结构化数据，应对灵活的事务处理和分析处理混合负载。

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

1. 基于中间件的Sharding分案

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

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

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

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

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

PolarDB分布式版简介

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

● 云原生化，基于存储计算分离的 Share Nothing 架构，实现极致的弹性能力和水平扩展能力

● 透明分布式，以单机数据库的体验，操作分布式数据库；

● 自研的 Lizard 分布式事务系统，保证 ACID 特性和全局一致性；

● 自研的分布式复制协议 X-Paxos，保证业务持续可用；

● 高效的交互协议 X-Protocol，实现请求流水线处理；

● 行列混合存储，实现 HTAP 处理能力；

● 全面开源，拥抱 MySQL 生态，对 MySQL 全面的兼容。

PolarDB分布式版架构

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

PolarDB for Xscale分布式存储引擎

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

● 连续递增的全局自增列

● 全局有序的TSO发号器

● 高效稳定的分布式事务

● 安全严格的全局一致性

● 持续可用的分布式协议

● 持久可靠的多副本存储

SEQUENCE 引擎

业务背景

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

使用语法

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

1. 创建 SEQUENCE

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

2. 访问 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分布式版中的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分布式版存储引擎，想要实现全局分布式事务的 ACID 特性，和全生态一致性，必须依赖一套分布式事务系统，而MySQL社区版本的 InnoDB 事务系统，存在诸多的弊端。

InnoDB 单机事务系统

▶︎ 弊端1：Read/Write 冲突严重

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

写路径上：

1. 事务启动时，分配事务ID，并插入到全局的活跃事务ID数组中；

2. 事务过程中，修改操作会将事务ID更新到行记录上来，表示该行记录的最新修改者；

3. 事务提交后，将事务ID从全局的活跃事务ID数组删除；

读路径上：

1. 查询启动时，启动Read View，并将全局的活跃事务 ID 数组拷贝到Read View 上；

2. 查询过程中，根据行记录上的事务 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 数组来表达，其实现：

1. 事务 ID 无法在分片之间同步和识别；

2. 数组大小跟当时活跃事务数量有关，无法固定大小和高效传播。

这就带来了很大的限制：

1. 在单机存储计算分离的模式下，无法高效使用 read view 进行存储计算下推；

2. 在分片集群模式下，无法得到全局一致性版本；

3. 在生态上下游下，无法存储 read view 版本。

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

Lizard SCN 单机事务系统

▶︎ SCN 事务系统架构

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

写事务：

1. 事务启动时，申请事务槽 Transaction Slot，地址记为 UBA；

2. 事务过程中，对修改的记录填入 (SCN=NULL, UBA) 两个字段；

3. 事务提交时，获取提交号 SCN，并回填到事务槽上，并完结事务状态，返回客户提交完成。

读事务：

1. 查询启动时，启动事务视图 Vision，即从 SCN 生成器上获取当前 SCN，作为查询的 Vision；

2. 查询进行时，根据行记录的 UBA 地址找到对应的事务槽，获知事务的状态以及提交号；

3. 根据记录 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 的保留周期：

1. 时间维度：

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

2. 空间维度：

参数 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的事务所产生历史数据。

1. SELECT * FROM t1 AS OF SCN 150 发起闪回查询。

2. 扫描到一条行记录，发现SCN是无效值，则通过UBA回查Transaction Table，获取事务状态信息。可以看到，该记录的SCN=200，并非本次闪回查询所需要的版本。

3. 通过Rollptr找到本记录的上一个历史版本，发现SCN=150，显然该数据版本是本闪回查询所需要的，返回该行记录给用户。

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

▶︎ SCN 事务系统的代价

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

1. 解绑对全局结构的访问依赖，读写冲突得到大幅缓解

2. 视图升级为 Vision，只有一个 SCN 数字，不再有活跃事务ID 数组，易于传播

3. 支持自定义的 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 事务系统整体的吞吐能力大幅提升。