关于后端:PolarDBX-全局二级索引

简介：索引是数据库的根底组件，早在 1970 年代，SystemR 就曾经通过减少索引来反对多维度查问。单机数据库中，索引次要依照用处和应用的数据结构分为 BTree 索引、Hash 索引、全文索引、空间索引等。通常，每张表中蕴含一个主键索引(Primary Index)，主键索引以外的索引，统称为二级索引(Secondary Index)。背景索引是数据库的根底组件，早在 1970 年代，SystemR 就曾经通过减少索引来反对多维度查问。单机数据库中，索引次要依照用处和应用的数据结构分为 BTree 索引、Hash 索引、全文索引、空间索引等。通常，每张表中蕴含一个主键索引(Primary Index)，主键索引以外的索引，统称为二级索引(Secondary Index)。采纳存储计算拆散和 shared-nothing 架构的分布式数据库具备良好的程度扩大能力，通过数据分区和无状态的计算节点，容许计算和存储独立扩缩容，大量分布式数据库都采纳这种架构(Spanner, CockroachDB, YugabyteDB 等)。

全局索引解决什么问题？shared-nothing 架构引入了 分区 的概念，数据须要依照固定的 分区键 进行切分，这导致蕴含分区键的查问能够疾速定位到一个具体分区，而其它查问须要全分区扫描。这个状况相似单机数据库中依照主键进行查问能够疾速定位到数据所在的 page，而依照非主键查问须要全表扫描。与单机数据库不同的是，全分区扫描对于分布式数据库，除了会减少慢查问数量升高零碎吞吐，还可能导致系统丢失线性扩大能力。参考下图的例子

扩容前：两个存储节点 (Data Node, DN)，两个数据分区，假如单个 DN 能承载的物理 QPS 为 3，整体物理 QPS 为 6，每个查问都是全分区扫描，逻辑 QPS: 6/2= 3 扩容后：三个存储节点，三个数据分区，整体物理 QPS 为 9，每个查问都是全分区扫描，逻辑 QPS: 9/3=3。机器成本上升 50%，查问性能没有任何晋升！单机数据库应用二级索引来防止全表扫描，具体来说，二级索引抉择非主键列作为 key，value 局部保留主键的值（也可能是到行记录的援用，具体实现不影响解题思路）。应用二级索引的查问过程变为，首先依据二级索引的索引列定位到 page，读取主键的取值，而后返回主键索引查问整行记录（这一步称为回表）。实质上，二级索引通过冗余一份数据的形式，防止了全表扫描，属于系统优化的规范思路“空间换工夫”分布式数据库要打消全分区扫描，也能够采纳相似的思路，冗余一份索引数据，索引采纳与主表不同的分区键。查问时首先依据索引的分区键定位到一个分区，而后从分区中查到主表的分区键和主键，回表失去残缺数据，整个只须要扫描固定数量的分区（比方对于点查，至少扫描两个分区）。这种与主表分区维度不同的索引，咱们称之为全局二级索引（Global Secondary Index, GSI, 也常常简称为全局索引），对应的与主表分区维度雷同的索引，称为部分索引(Local Secondary Index，LSI) 为什么肯定须要全局索引？后面始终在说，全分区扫描会导致系统不可扩大，那么如果用户可能严格保障所有 SQL 都蕴含分区键，是不是就不须要全局索引了? 是的，这种状况的确不须要，但现实情况的复杂性决定了这是小概率事件，更常见的场景是：● 用户表须要反对用户依照手机号和用户 ID 登录，分区键选哪个？● 电商零碎，须要依照买家 ID 和卖家 ID 查问订单，订单表分区键怎么选？● 现有业务代码是外包公司写的，大范畴批改 SQL 不事实，怎么办？更多场景剖析能够参考 TPCC 与通明分布式，论断：要想提供与单机数据库类似的“通明分布式”应用体验，必须反对全局索引。用户想要怎么的全局索引应用体验? 单机数据库中索引是十分罕用的组件，用户接受度很高，全局索引如果可能做到与单机数据库索引类似的应用体验，就能够称得上是“通明”的索引应用体验。以下从用户应用视角登程，列举四个影响索引应用体验的要害个性

要满足这四个个性并不容易，读、写、schema 变更流程都须要做相应的设计。相干问题大到分布式事务，CBO 索引抉择，Asynchronous Online Schema Change 如何实现，小到包含 on update current_timestamp 属性的列如何解决，affected rows 如何兼容 MySQL 行为，都须要思考，同时还须要保障高性能。以下介绍 PolarDB-X 在实现兼容 MySQL 索引应用体验的全局二级索引过程中，做出的技术摸索。全局二级索引实现一致性对于 OLTP 零碎中的全局索引，首先须要保证数据与主表强统一，解决这个问题须要用到分布式事务、逻辑多写和 Asynchronous Online Schema Change (AOSC)。数据写入的一致性数据写入时，因为主表和 GSI 的数据可能位于不同分区，须要分布式事务保障原子提交，同时 因为写入存在并发，还须要解决写写抵触。对于没有全局索引的表，能够将 DML 语句路由到数据所在的分区，由 DN 实现并发管制，但对于蕴含 GSI 的表，更新数据时须要首先读取并锁定要变更的数据，而后依照主键更新主表和索引，这种先读后写的办法称为逻辑多写。

先读后写听下来并不难实现，只是 SELECT + UPDATE/DELETE 而已，但理论状况比设想的要简单一些。首先，晚期 DRDS 的 DML 实现齐全依赖下推执行，短少相应的逻辑打算，MySQL 的 DML 语法大概有 13 种，每种都须要反对，并且对于可能下推的场景，仍然保留下推执行计划；其次，MySQL 很多细节行为并没有在官网文档上介绍，须要依据代码逐个适配，比方 类型转化、affected_rows、隐式 default 值等。另外为了反对全局惟一索引，还须要减少冲突检测的流程，导致 INSERT 语句的执行形式又减少了四种。上图展现了逻辑多写的执行流程，具体介绍能够参考源码解读索引创立的数据一致性保证数据一致性的第二个方面，是在索引创立过程当中保证数据统一。比方，上面右边这幅图，分布式场景下，多个节点对元数据的感知可能存在时间差。参考图中的状况，一个节点已知存在索引，所以它对索引进行了插入，同时写入主表和索引表。另一个节点并不知道索引的存在，所以它只对主表上的内容进行删除，没有删除索引表上的内容，这就导致索引表上多了一条数据。

PolarDB-X 为了解决这问题，参考 Google F1 的计划，通过引入多个互相兼容的阶段，来保障元数据的过渡是平滑的，具体实现参考这篇文章。同时因为 Schema Change 过程中，切换元数据版本的次数减少，咱们也对单个 CN 上的元数据版本演进做了优化，使得 DDL 齐全不会影响读写执行，具体参考这篇文章。引入以上技术之后，咱们的整个 DDL 框架就能够对全局索引进行不阻塞的创立了。值的一提的是，MySQL 从 8.0 版本开始反对原子 DDL，这方面 PolarDB-X 也有本人的实现，详见这篇文章索引扫描的数据一致性数据写入过程中因为存在并发，须要解决写写抵触，同样的，数据读取过程中因为存在并发读写，还须要解决读写抵触。古代数据库根本都通过 MVCC 来解决读写抵触，查问开始前从发号器获取一个版本号，通过版本号来判断数据行的最新版本是否对以后事务可见，使得读取到的数据满足指定隔离级别。PolarDB-X 反对基于 TSO 的 MVCC 实现，可能保障回表过程中索引表和主表读到雷同的快照，MVCC 实现参考这篇文章。索引抉择索引抉择的外围指标是让用户在应用 GSI 的时候不须要手动指定索引，计划是基于 CBO 的主动索引抉择，实现上波及优化器如何评估和抉择蕴含索引扫描 (特指二级索引上的索引扫描，常见名称有 IndexScan,IndexSeek 等，以下统称为 IndexScan)的执行打算。单机数据库的做法是将 TableScan 替换为 IndexScan，如果索引不能笼罩所需的列，则再减少一步回表操作，对 IndexScan 的优化次要是列裁剪和谓词下推，应用独立的算法计算 IndexScan 和回表的代价。

代价评估方面一个比拟要害的问题是如何去评估回表的代价，GSI 自身也是一张逻辑表，回表操作相当于索引表和主表在主键上做 Join。因而咱们做了工程上的优化，将索引回表的动作适配为 Project 加 Join 的操作，由此能够把整个对于索引的代价评估适配到一般查问打算的代价评估当中。

为了可能将蕴含 IndexScan 的打算纳入执行打算枚举流程，须要将索引扫描和回表算子适配到现有 CBO 框架。具体实现如上图所示，通过 AccessPathRule 生成应用 GSI 的执行打算，在后续迭代中通过比拟代价选出最合适的打算。对于 CBO 框架参考这篇文章。同时，因为分布式数据库中回表须要网络 IO，比单机数据库的回表代价更高，PolarDB-X 还反对将 Join/Limit 等操作提前到回表之前，与索引扫描一起下压到 DN 上执行，达到缩小回表的数据量升高网络 IO 的目标，具体参考这篇文章笼罩索引笼罩索引是一种非凡的索引，容许用户在索引中保留更多列的数据，目标是满足更多查问语句对援用列的需要，尽量避免回表。单机数据库中笼罩索引是一种常见的优化伎俩，比方 Sql Server 很早就反对通过笼罩索引优化查问性能。

对于分布式数据库，回表还可能影响零碎的程度扩大能力。参考上图的例子，订单表依照 buyer_id 分区，当依照 seller_id 查问时须要全分区扫描。创立一个 seller_id 上的 GSI 来优化，因为索引表默认仅蕴含分区键、主表分区键和主键，没有 content 列，须要回表。随着卖家销售的订单数量减少，回表操作波及的分区越来越多，最终也会变成一个全分区扫描，通过减少索引防止全分区扫描的指标并没有实现。为了防止这种状况呈现，PolarDB-X 反对创立“笼罩索引”，通过 COVERING 语法在 GSI 中增加指定列，使得 GSI 更容易达到索引笼罩的状况。除了短少列，短少历史版本也可能导致回表，比方 MySQL 没有为二级索引保留版本信息，仅在二级索引每个 page 头部保留了执行最初一次写入的事务 id，导致如果须要查问历史版本必须回表。PolarDB-X 在写入过程中为 GSI 独自记录 undo-log，可能读取到索引的历史版本，不会因为查问历史版本而产生额定的回表操作，并且反对将闪回查问 (Flashback Query) 间接下发到 GSI 上执行。性能优化因为写入数据时必须应用分布式事务和逻辑多写，有额定的开销，须要优化写入性能，保证系统吞吐。具体来说，分布式事务依赖两阶段提交保障原子性，相比单机事务减少了 prepare 阶段和写入 commit-point 的步骤，同时依赖 TSO 获取提交工夫戳，TSO 服务的吞吐量也可能成为瓶颈。针对分布式事务的优化，包含一阶段提交优化、单机多分区优化、TSO Grouping 等内容，能够参考分布式事务实现和全局工夫戳服务设计。逻辑多写须要先读取数据到 CN，起因有两个，首先 PolarDB-X 兼容 MySQL 的乐观事务行为，写入操作应用以后读，对于 UPDATE、DELETE 等依据谓词确定更新范畴的语句，须要先查问并锁定须要批改的数据，防止不同分支事务读取到不统一的快照。其次对于 INSERT 语句，如果指标表上有惟一束缚，也须要先读取数据进行惟一束缚冲突检测。单机数据库中也存在相似的流程，比方 MySQL 执行 DML 时先由 server 层从 innodb 中查问并锁定须要批改的数据，而后调用 ha_innobase::write_row 写入数据，MySQL 的惟一束缚实现也要求 INSERT 前先做惟一束缚查看。区别在于 MySQL server 层和 innodb 层的交互产生在单台机器内，只波及内存和磁盘 IO，代价较低，分布式数据库中 CN 和 DN 通过网络机交互，代价更高。

PolarDB-X 执行 DML 时，优先选择下推执行，对于必须应用逻辑多写的场景，针对“查问并锁定须要批改的数据”和“惟一束缚冲突检测”别离进行了工程优化● 读写并行：思路很简略，将“读取 - 缓存 - 写入”的串行执行过程转变为多个小批次的并行的“读取“和”写入”过程。要解决的一个关键问题是，MySQL 的事务与连贯是绑定的，事务内如果创立多个读连贯，会呈现数据可见性问题。为了解决这个问题，咱们引入了事务组的概念，使得多个连贯能够共享雷同的 ReadView，由此来解决事务内读写连贯绑定的问题，使得不同批次的读取和写入能够并行执行。● 惟一束缚冲突检测下推：次要解决数据导入场景下的性能问题，数据导入为了做断点续传，通常会应用 INSERT IGNORE 这样的语句，但实际上插入的数据简直都是没有抵触的，于是每条数据都做冲突检测就显得很不划算。咱们优化的办法是采纳乐观解决的思路，通过 RETURNING 语句 加弥补的形式。使得数据导入场景下，INSERT IGNORE 的性能与 INSERT 雷同。DDL 兼容性良好的 DDL 兼容性是“通明”全局索引必须要关注的局部。试想一下，如果每次批改列类型之前，都须要先删除援用这一列的全局索引，类型变更实现后在重建索引，是如许令人“头大”的事件。PolarDB-X 全面兼容 MySQL DDL 语句，表、列、分区变更相干的语句都会主动保护 GSI。DDL 执行算法分为 Instant DDL 和 Online DDL 两种，Instant DDL 次要用于加列，Online DDL 基于 AOSC，针对不同 DDL 语句有细化设计，上面简略介绍比拟有代表性的 ADD COLUMN 和 CHANGE COLUMN 的实现 ADD COLUMNPolarDB-X 反对全局聚簇索引（Clustered Secondary Index, CSI），特点是始终保持与主表雷同的构造，保障对所有查问都不须要回表。因而，主表加列时须要在 CSI 上也减少一列，个别状况下依照 AOSC 流程实现就能够保障加列过程中索引数据统一，但如果新增列蕴含了 ON UPDATE CURRENT_TIMESTAMP 属性，则可能产生问题。比方上面的场景，物理表加列实现，但 CN 还不晓得新增列的存在，于是由 DN 独立填充主表和索引表中的值，导致数据不统一。为了解决这个问题，咱们会在所有 CN 都感知到元数据更新后，应用回填流程从新刷新一遍索引上新增列的值，保障索引与主表数据统一。CHANGE COLUMN 变更列类型是 DDL 中最简单的操作，对写入有比拟大的影响，比方 MySQL 8.0 在变更列类型过程中仍然须要锁表。PolarDB-X 反对 Online Modify Column（OMC），通过“加列 - 复制数据 - 批改元数据映射”的形式，联合 Instant Add Column，实现反对 GSI 的不锁表列类型变更。

上图展现了在一张没有 GSI 的表上执行 CHANGE COLUMN 的过程。分为七个阶段，首先减少一个对用户不可见的 COL_B，在写入过程中应用雷同的值填充 COL_A 和 COL_B，而后对表中已有的数据用 COL_A 的值回填到 COL_B，最初替换 COL_A 和 COL_B 的元数据映射，并删除 COL_A，实现列类型变更。存在 GSI 的场景也采纳雷同的流程，只是在每个步骤中都对 GSI 做雷同解决。DDL 兼容性应用的底层技术与创立 GSI 雷同（AOSC、数据回填、逻辑多写、异步 DDL 引擎等），但实现上须要思考每种 DDL 语句的语义，还须要思考 MySQL 的细节行为，比方变更列类型中通过 UPDATE 语句在新老列之间回填数据，但 MySQL ALTER TABLE 和 UPDATE 的类型转换逻辑并不相同，为此咱们实现了专门的类型转换逻辑在 UPDATE 中模仿 ALTER TABLE 的行为。总的来说，DDL 兼容性看起来只是反对了一些语法，但外面的工作量其实是很大的。性能测试全局索引对读写性能的影响，与具体业务场景有比拟大关系，实质上是就义一部分写入性能换取读性能的大幅晋升，下图以 Sysbench 场景为例，展现该场景下 GSI 对读写吞吐的影响。

总结基于存储计算拆散和 shared-nothing 架构的分布式数据库，须要反对全局二级索引来打消全分区扫描，保障线性可扩展性。单机数据库很早就引入了二级索引，应用体验用户接受度很高，良好的全局索引应用体验应该向单机数据库看齐，须要保证数据强统一，反对通过 DDL 语句创立，反对主动抉择索引，同时索引的存在不该当妨碍其余 DDL 语句执行。PolarDB-X 通过分布式事务和逻辑多写保障索引数据强统一；反对 Online Schema Change，索引创立过程能够与写入并行；反对笼罩索引，解决回表带来的全分区扫描问题；精细化解决了蕴含 GSI 表的 DDL 语句兼容性。为用户提供”通明“的索引应用体验，升高分布式数据库的应用门槛。作者：墨城本文起源：PolarDB- X 知乎号原文链接：https://click.aliyun.com/m/10… 本文为阿里云原创内容，未经容许不得转载。