PolarDB-X 存储引擎核心技术 | Lizard B+tree 优化

简介: PolarDB-X 分布式数据库,采用集中式和分布式一体化的架构,为了能够灵活应对混合负载业务,作为数据存储的 Data Node 节点采用了多种数据结构,其中使用行存的结构来提供在线事务处理能力,作为 100% 兼容 MySQL 生态的数据库,DN 在 InnoDB 的存储结构基础上,进行了深度优化,大幅提高了数据访问的效率。

1. 背景

PolarDB-X 分布式数据库,采用集中式和分布式一体化的架构,为了能够灵活应对混合负载业务,作为数据存储的 Data Node 节点采用了多种数据结构,其中使用行存的结构来提供在线事务处理能力,作为 100% 兼容 MySQL 生态的数据库,DN 在 InnoDB 的存储结构基础上,进行了深度优化,大幅提高了数据访问的效率。


1.jpg

2. InnoDB 存储结构

2.1 B+tree 结构

真实世界中的应用负载是多种多样的,不同的数据系统会采用适用于其存储和检索特点的数据组织方式,常见的有 B-tree、LSM-tree、Hash Map、Heap Table、R-tree 等。其中,B-tree 及其变种在关系型事务系统要求的高效检索、磁盘 IO 优化、范围查询支持、并发控制、事务安全性等方面表现均衡,可谓「六边形战士」,因此被主流 OLTP 数据库所采用。MySQL InnoDB 使用 B+tree 作为索引组织结构。

2.jpg

2.2 数据表结构

在 InnoDB 存储引擎中,一个用户定义的表实际上由多个B+tree 索引来实现,主键对应的聚簇索引 (Clustered Index) B+tree 叶子节点上保存着全量的数据行信息,普通列上的二级索引 (Secondary Index) B+tree 叶子节点上仅存储相应的二级索引键和主键,如下图所示。

3.jpg

对 InnoDB 数据的访问可以分为两个步骤, B+tree 索引上的数据定位,以及数据可见性的判断和构建。

2.3 数据定位

B+tree 的行记录定位过程结合了树形查找和页内查找两种机制。

  • 树形查找:B+tree 是一种自平衡的多叉树,查找过程由根节点开始,沿着树结构自上而下进行页面跳转。树形查找的次数与树的高度相等,每层访问一个页面。
  • 页内查找:B+树的每个页面存储多个键值对。在叶子节点,记录对应实际的行数据;而在非叶子节点,键(Key)与叶子节点一致,值(Value)指向下一层级的页面。在非叶子节点中,通过二分查找目标键,决定跳转到下一层的具体页面;达到叶子节点后,再进行一次二分查找,便可准确找到所需的数据。

这种结合使得B+树能够高效地定位行记录,时间复杂度为 O(klogn),其中,k 表示 B+tree 树高度,n 表示页面内记录数量。3-4 层的 B+tree 即可满足绝大多数应用场景,据测算[1],分支因子 1000 左右的四层 B+tree 可容纳最多 26TB 的数据。

为了加速查询,一张 InnoDB 逻辑表上往往存在一个聚簇索引和多个二级索引。不同的查询条件可能命中不同的索引 B+tree 扫描。

聚簇索引定位

聚簇索引是InnoDB默认的主键索引,由于聚簇索引的叶子节点直接存储了完整的数据行,因此一旦找到叶子节点,查找过程就完成了。

二级索引回表定位

由于二级索引不包含完整的数据行,因此在使用二级索引查找时,可能需要进行回表操作。考虑上图中的表结构,对于查询语句select * from t1 where k > 1,选择二级索引可以避免全表扫描,但二级索引记录中并没有 c 字段的值,因此扫描到符合 k>1 的二级索引记录后,还需要根据记录上的 pk 值,「返回」聚簇索引上扫描得到完整的行记录。

上述场景就是回表查询的典型例子。所谓「二级索引回表查询」,就是由于二级索引存储信息的不充分,需要先扫描二级索引 B+tree,再扫描聚簇索引 B+tree 的查询过程

2.4 数据可见性

在InnoDB存储引擎中,数据定位只是数据访问的第一步。在某些场景下,出于多版本并发控制(MVCC)的需要,还需要进行数据可见性判断,以确保返回的数据符合事务隔离级别的要求。InnoDB 的 MVCC 实现主要依赖行记录上的隐藏系统列 trx_id/roll_ptr,可见性视图 Read View 和 Undo log。

每个数据行都有两个隐藏的列,用于记录事务信息:

trx_id:最近一次修改该行的事务ID。

roll_ptr:指向 undo log 的指针,用于存储该行的旧版本。

InnoDB MVCC 主要体现在两个方面:

  • 活跃事务判断。 Read View 是事务为了实现一致性读记录的当前活跃事务的快照,创建时拷贝了全局活跃事务数组。当事务定位到某条记录,会根据记录上的 trx_id 与事务的视图 Read View 进行比较来判断当前记录是否活跃。
  • 历史版本构建。Undo log 中记录着记录的历史版本数据,若记录当前版本不可见,则可以通过行上的 roll_ptr 指向事务对应的 undo log,构建出记录的前版本,实现快照读机制。

2.5 数据访问成本分析

  • 数据定位成本——二级索引回表。由于二级索引上不包含全量用户信息和可见性判断需要的系统列,二级索引的回表查询占据了数据定位的很大部分。如下图红色路径所示,回表查询相对于聚簇索引查询和不回表的二级索引查询,多了一次聚簇索引 B+tree 的完整扫描。多出来的这条 PK LOOKUP 路径会对磁盘 IO、BufferPool 空闲页、B+tree 并发控制等模块带来额外的压力。特别是在大 range 查询中,如果每条记录都要回表,那么回表代价将成为主要开销,对查询的 RT 和整体吞吐都会带来巨大影响。

4.jpg

  • 可见性判断成本——Read View。 InnoDB 可见性判断需要访问全局结构(全局活跃事务数组),这个过程需要在一个事务大锁的保护下完成,并且 MVCC 的视图 Read View 是一个数组,无法固定大小和高效传播。随着 CPU 多核能力的大幅加强,目前的设计越来越成为制约 InnoDB 事务性能的瓶颈。以 PolarDB-X DN 节点在公有云上目前售卖的最大规格(polarx.st.12xlarge.25, 90C, 720G, 最大并发连接数2W)为例,压测 Sysbench read_write 场景,CPU 有接近 17% 的时间耗在无用的等待上。

3. Lizard 索引结构

针对 InnoDB 的以上问题,Lizard 事务系统设计了特有的索引结构,显著降低了数据访问成本,提升了系统整体性能。

3.1 聚簇索引结构

针对可见性判断代价的优化,Lizard 事务系统在聚簇索引上引入 scn/uba 系统列,表达事务的提交顺序,解绑对全局结构的访问依赖,将 Read View 数组升级为只有一个 SCN 数字的 Vision,易于传播。详细的技术解读可见「PolarDB-X 存储引擎核心技术 | Lizard 分布式事务系统」[2]

5.jpg

3.2 GPP 二级索引结构

PolarDB-X Lizard 事务引擎通过实现 Guess Primarykey Pageno (GPP) 方案,大大减少二级索引回表代价。其索引行格式如下图所示。

6.jpg

针对回表查询路径的优化,在二级索引上,Lizard 新引入 gpp_no 系统列,表示对应的聚簇索引记录所处 page 的 "guess" pageno。所谓 "guess",意指 gpp_no 是对主键位置的一种猜测,不保证一定正确。下面通过 insert 流程来解释 gpp_no 是如何生成和记录的。

InnoDB 的插入流程遵循先插聚簇索引,后插二级索引的顺序。在主键插入成功之时,我们可以获知主键记录在当下的准确位置(pageno),后续插入二级索引时,我们将上一步获知的 pageno 作为 gpp_no 填入二级索引记录,以供之后的回表查询使用。

回表查询

借助 gpp_no, GPP 二级索引显著缩短了回表查询路径。如下图绿色路径所示,在二级索引 B+tree 上定位到记录后,我们首先取得 gpp_no 对应的页,对其二分查找尝试获取对应的主键记录,如果获取成功,那么就免去了一次聚簇索引上的完整 B+tree 扫描。GPP 是对回表查询的一种短路方法,直观地降低了回表查询的 RT,同时也降低了回表查询对系统整体的 Buffer Pool/IO 等资源的压力,可以显著提高系统整体吞吐量。

7.jpg

GPP 代价

  • 空间代价

Lizard 在二级索引上扩充了 gpp_no 隐藏系统列,会让二级索引单条记录增加 4B。以 Sysbench 测试的典型表结构为例,GPP 的引入使整张表的存储空间上涨 4.6%,相对于性能的显著提升,「以空间换时间」的策略在二级索引回表查询场景下特别合适。

  • 命中率代价

既为 "guess",那么自然会有 gpp_no ≠ 实际 pk pageno 导致无法命中的情况出现,这发生在 B+tree 树形结构变化后。当聚簇索引 B+tree 进行数据更新时,若数据的变动仅限于叶子页面内部,由于我们记录的 gpp 额外信息不包含记录的 offset,所以原记录在页内的地址变化不会造成 GPP MISS。

而当聚簇索引 B+tree 的数据更新引发叶子节点分裂时,原 page 中的一半数据会被移动至新的 page,那么这部分 pk 记录对应的二级索引 gpp_no 就会变为不准确的值;同理,叶子节点发生合并时,也会有 pk 记录的搬迁,造成命中率下降的问题。

虽然会有无法命中的概率出现,但在随机插入数据,命中率约 50% 的测试场景中,GPP 二级索引回表仍然表现出显著的性能提升,说明命中后短路操作的收益远大于未命中造成的额外代价。另外,对于表结构为隐藏主键,或是以主键顺序导入数据的场景,可以触发 InnoDB B+tree 插入点分裂优化,不搬迁原叶子节点中的数据,保证 GPP 命中率维持高位。

Cleanout

一条 pk 记录由于 B+tree 的分裂/合并而被搬迁到其他数据页后,其二级索引 gpp_no 将一直保持无法命中的状态。GPP 实现了回表查询的 Cleanout 方案,对命中率进行“事后补救”。回表查询过程中,如果当前记录的 gpp_no 为错误值,那么会记录重走聚簇索引扫描后准确的 page_no,将 gpp_no 回填为正确值,以便下次回表查询可以命中。

虽然 Cleanout 带来了部分代价,但可以为后续的查询奠定命中率基础,尤其在读多写少,B+tree 结构比较稳定的场景下,Cleanout 机制可以为系统整体吞吐带来提升。

业界对比

  • Oracle Heap-Organized Table

Oracle 默认的 Heap-Organized Table 将实际数据存储在堆表上,表上的 B-tree 索引不存储数据,只存储记录在堆表上的 row_id,B-tree 扫描到叶子节点记录后,还需要根据 row_id 定位到堆表中的实际数据。相对于 Lizard GPP,其优势在于:

  1. row_id 直接对应到堆表数据页中的记录,省去了 GPP 最后仍需页内二分查找的代价。
  2. B-tree 上记录的 row_id 一定能准确找到数据,没有 GPP 命中率问题。

劣势在于:

  1. 没有聚簇索引的概念,所有的索引扫描完毕后都需要访问堆表页(覆盖索引除外),而 InnoDB 聚簇索引扫描到叶子节点可以获得全部数据。
  2. 堆表有行迁移问题,row_id 的查找可能不止一跳。
  • PostgreSQL

与 Oracle 类似,PostgreSQL 同样采用数据存储在 Heap 上的策略,所有的索引都是二级索引,数据的访问需要经历 B-tree 和 Heap 两个结构。其与 Lizard GPP 的对比和 Oracle 相似。

  • Oracle Index-Origanized Table

Oracle 的 IOT 表与 InnoDB 索引设计方案类似,都是将数据存储在聚簇索引之上,二级索引需要回表。与 GPP 类似, IOT 表二级索引上记录着首次插入的聚簇索引 row_id,回表时首先尝试使用该 row_id 寻找聚簇索引记录,若命中,则可省去聚簇索引 B-tree 扫描。与 GPP 的区别在于:

  1. Oracle IOT row_id 直接查找到记录,无需页内二分查找。
  2. Oracle IOT 没有 cleanout 机制,row_id 失效没有补救手段。

4. 性能表现

我们在Intel 8269CY 104C 物理机上,部署polardbx-engine[3]。测试数据为 Sysbench 16 张 1 千万行数据的表。分别对聚簇索引 SCN 事务系统和 GPP 二级索引进行测试。

  • SCN MVCC 性能
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

上表为Lizard SCN 事务系统在 Sysbench oltp_read_write 场景下的测试数据。相比于MySQL-8032,Lizard SCN 事务系统性能提升 30%,延时降低 53%。

  • GPP 二级索引

我们仿照 Sysbench oltp_read_only/oltp_point_select 构造了回表查询的只读场景。

8.jpg


上图是 GPP 二级索引相对于未开启 GPP 的 polardbx-engine 在 qps 上的提升率。可以看到 GPP 在回表查询场景中全面领先,特别是在 range=100 的大 range 场景,查询性能提升可达 50%以上。


作者:易霏 夏花

作者介绍
目录

相关产品

  • 云原生分布式数据库 PolarDB-X