事务、全局索引、透明分布式
再见，分区健！
——陈默（墨城）
阿里云数据库技术专家
了解更多PolarDB-X 内容：https://developer.aliyun.com/topic/polardbx_release
在刚刚发布的PolarDB-X 2.1.0版本中，开源了透明分布式能力，能带给用户完全不同的透明分布式数据库使用体验。其中，一个最明显的不同，就是用户不再需要关注分区健这个概念，这也是副标题《再见，分区健》的来由。
一、从“分区”开始
1970 年代末，分区的概念首先在并行数据库系统中出现，用来代表一组记录的集合。在并行数据库中，表首先按照某种规则被切分为若干分区，每个分区存入数据库节点，每个数据库节点都有独立的 CPU 内存和存储节点，节点通过网络交换数据。由于没有共享应硬件资源，该结构也被称为 shared-nothing 架构。
引入分区和 shared-nothing 架构，是为了通过增加节点的方式来提升存储和计算能力，也称为水平扩展。
从水平扩展的角度出发，用户肯定希望尽可能均匀地将数据分散到各个分区中，比如随机分配。但这会导致查询时需要扫描全部分片，性能上无法接受。而可行的办法是按照某些列的值来确定一行数据应该落在哪个分片，这些用来确定一行数据应该落在哪个分片的列，就是分区键。
2000 年以后，随着互联网的普及，需要处理的数据量越来越大，超过了单机系统能够承载的容量上限，分区+ shared-nothing 带来的水平扩展能力重新受到重视。
这一阶段的实现大致可以分为两类：
第一类是 NoSQL 系统，通常是从零开始实现的全新系统，强调高可用和可扩展性。引入分区之后，由于事务和 SQL 的执行代价升高，通常这些系统不支持跨行事务和 SQL 接口，因此也被称为 NoSQL 系统。代表性的实现有 Google 的 BigTable 和 Amazon 的 Dynamo。
第二类是中间件。通过在系统和单机数据库之间增加中间层，将查询请求路由到数据所在的数据库节点。这类系统通常不支持跨分片事务和全局索引，支持 SQL 接口，但要求 SQL 语句中必须包含分区键上的条件。
整体上看，这一阶段数据库将重心放在了解决高可用和扩展性问题上，代价是放弃了对事务和 SQL 的支持。从开发人员的角度来看，最直观的感受是设计业务逻辑时需要考虑分区键如何选择。
但是，开发者真的愿意设计分区键吗？开发者真的能设计分区键吗？如果系统有数十甚至上百张表，又该怎么做？除此之外，缺少分布式事务也不符合很多用户的使用习惯。
Google 在论文中总结道，许多工程师将过多精力放在处理数据一致性上，原本封装在数据库内部的逻辑溢出到应用代码中，大幅提高了应用代码的复杂度。因此，不支持分布式事务和要求开发者选择分区键是使用分布式数据库最主要的障碍。
接下来，一起看看 PolarDB-X 在支持分布式事务中使用的关键技术，全局索引如何提升查询性能、以及如何为用户提供无需关注分区健的透明分布式体验。
二、分布式事务
数据库系统需要面对各种各样的复杂情况，硬件故障可能导致系统在写入数据的任何阶段崩溃，比如应用系统可能在一系列连续操作中突然退出，多个客户端可能并发地修改同一条记录等。
出现异常时，数据库需要提供可靠性保证，而事务就是对可靠性保证的简化描述。事务是一系列读写操作的集合，对读写操作系统提供四个方面的保障：
① 原子性：如果出现异常，用户可以通过重试事务来解决，无需担心失败的事务对数据产生影响。
② 一致性：用户无需担心数据操作会违反约束定义，比如唯一约束外键等。
③ 隔离性：用户可以认为只有自己在操作数据库，无需担心多个客户端并发读写相同的数据会产生异常。
④ 持久性：一旦事务提交成功，用户就无需担心事务产生的变更会因为其他异常而丢失。
分布式事务中由于存在多个分区，原子性和隔离性受到影响。
对于原子性，需要协调所有分区在提交阶段的行为，保证一起提交或一起回滚。业界通常使用两阶段提交协议来解决此问题。常见的实现有 Percolator 和 XA 协议。Percolator 在提交阶段延迟较高，只在提交阶段汇报冲突错误，且仅支持乐观锁场景，与传统的关系数型数据库基于悲观事务的模型有较大区别。因此 PolarDB-X 选择通过 XA 协议支持两阶段提交。
对于隔离性，要求能够对不同分区上发生的单分区事务进行全局排序。业界常见的实现方法有基于 GTM 和 TSO 两种实现。 GTM 方案过于依赖中心化的事务管理器，容易出现系统瓶颈。因此 PolarDB-X 选择通过基于 TSO 的 MVCC 方案来实现隔离性。
上图为分布式事务具体的执行过程。
启动事务后，首先向 TSO 获取一个 star_ts ，作为读取的快照，接收并处理用户请求。过程中根据数据对应的事务状态、快照时间戳和数据提交时间戳来判断数据是否可见，以保证隔离性。在提交过程中，CN节点先通知所有参与写操作的分区执行 prepare ，记录事务状态，最后通知所有参与者 commit。在记录事务状态成功之前产生的异常都会导致事务退出，以此保证原子性。
采用 2PC 和 TSO + MVCC 方案实现的分布式事务经常被质疑的问题是提交阶段延迟增加和 TSO 单点问题。
针对上述两个问题，PolarDB-X 都进行了工程上的实现优化。
两阶段提交由于增加了 prepare 阶段，延迟高于单分片事务。实际上，对于单分片写多分片读的事务，无论读取是否跨分区，依然可以使用一阶段提交来保证原子性。 PolarDB-X 支持自动识别此类情况，能够显著减少这类场景下的提交延迟。
TSO 方案采用单点授时，潜在问题是存在单点故障和单点性能瓶颈。 PolarDB-X 的 GMS 服务部署在三节点集群上，通过 X-Paxos 协议保证服务高可用。同时对多种场景进行了优化，使得带分区条件的点查、点写可不依赖 GMS ,提升查询性能的同时也降低了 GMS 的压力。
另外，单个 CN 进程默认采用 grouping 的方式，将同一时间发生的多个 TSO 请求合并为 batch 操作一次性获取，进一步保证 GMS 不会成为系统瓶颈。
下面通过 Flashback Query 示例来展示 MVCC 带来的特殊能力。
三、全局索引
上图为一张按照主键拆分的表，t1 表 partition by Hash(ID)。 当提供的查询条件是 id 上的等值查询时，比如 id=14，算出 14 的分区哈希值之后，即可快速定位到 p3 分片。
但是如果按照 name 进行查询应该怎么处理？如果只能全分片扫描，代价过大，不可接受。为了找到答案，先看单机数据库如何解决此问题。
在 MySQL 中，同样的表结构是一棵 B+ 树，按照主键 id 有序。当以 id 为条件进行查询时，数据库会在 B+ 树上做二分查找，从而快速定位到数据所在叶子节点。同样当以 name 为条件进行查询时，则无法进行二分查找，只能将整棵 B+ 树都进行遍历，即全表扫描，代价较高。
在 MySQL 中，为了避免全表扫描，会在 name 上创建二级索引，即创建了另一棵 B+ 树，按照索引列有序，此处为按照 name 列有序，其叶子节点记录了 name 对齐以及其对应的主键 id 。对于 name 上的等值查询，数据库会先在二级索引的 B+ 树上进行二分查找，找到对应的 id 之后再使用此 id 在主键 B+ 树上进行查找，即回表操作。
二级索引的理念在计算机中非常常见，其本质是用空间换时间。在 MySQL 中设计主键更多的是考虑其业务上的唯一性，而不在意某列是否为查询使用最多的列，背后的原因是创建二级索引的成本非常低。
分布式数据库中，按照主键分区后如何进行 name 列查询，同时还能避免全表扫描？参考空间换时间的思路，以 name 为分区键，再将数据做一份冗余，将 name 映射到 id ，这份冗余的数据称为全局二级索引。
如上图所示，按照 name=Megan 做查询时，先通过全局二级索引定位到 Megan 所在分片，找到 Megan 的 id 值，用 id 值到主表上查询整条记录所在的分区，此过程也称为回表。
那么，如果在分布式数据库上创建全局二级索引能够像在单机数据库上一样方便，则无须再关注分区键。因此，关键就在于全局二级索引。全局索引要尽可能地做到与单机数据库一样的兼容性，兼容度越高就越透明，开发者就能够使用单机数据库的经验来使用分布式数据库。此处兼容性体现在很多方面，包括一致性、创建方式、使用方式和兼容其他 DDL。
首先是数据的一致性。 PolarDB-X 支持强一致事务，通过事务来保证主表和索引表的数据一致，所有对包含索引表的表进行写入的操作都会默认包装在强一致的分布式事务中。
分布式数据库中，实现 Online Schema Change 需要面临的主要挑战是： schema 变更过程中，不同的 CN 节点上，不同事务看到的元数据版本并不一致。
单机据数据库解决此问题的办法是通过对元数据加锁，保证任意时刻所有事务都只能看到同一版本的元数据。但分布式系统中，由于网络延迟存在不确定性，跨节点实现加锁可能导致明显的读写卡顿，因此并不符合 online 的定义。
PolarDB-X 参考了 Google F1 实现的 Online Asynchronous Schema Change ，通过增加两个互相兼容的中间状态，允许系统中同时存在至多两个元数据版本，使得 DDL 过程中无需加锁，不会阻塞任何读写请求。有了 Online Schema Change 的支撑，在 PolarDB-X 中使用 create index 语句即可轻松创建全局索引，无需依赖任何第三方组件。
在各种 DDL 操作中维护索引表数据一致，工作量很大。 PolarDB-X 支持无锁化的 Online DDL ，根据 DDL 类型可以自动选择合适的执行方式，且能自动维护全局二级索引。
创建完索引后，如果需要手动指定 SQL 使用全局二级索引，也不是一种友好的使用体验。合理的方式应该类似于单机数据库，由数据库自动选择使用全局二级索引。
由于索引本身也是一张逻辑表，且回表操作可以理解为索引表和主表在主键上做 Join，可以复用大部分分区表上执行计划的代价估计逻辑，使用估算主表上的执行计划代价的逻辑来估算索引表上的执行计划代价。
难点在于，两个表做 Join，一个包含三个全局索引，而另一个没有全局索引，执行计划的空间有非常大差异，需要更复杂的执行计划枚举算法以及性能更加强劲的 CBO 设计。
PolarDB-X 支持基于代价的优化器，可以自动完成索引选择。
下面通过一个 Demo 来展示如何通过全局索引优化查询性能。
从上面演示可以看到，有了全局二级索引的支持，可以像使用单机数据库一样，建表时无须指定额外的拆分键，之后通过 MySQL 原生语法创建索引来提升查询性能。
四、透明分布式
除了分布式事务和全局索引，分区算法的设计也是提供透明分布式体验的另一个关键。
单机数据库中，索引可以很好地支持前缀查询。而全局索引应该如何解这类问题？
创建多列索引时，PolarDB-X 会分别对每一列进行哈希，在匹配到前缀的情况下依然能做一定的分区裁剪。
在单机数据库中创建索引较为随意，比如在性别列上创建索引，索引的区分度较低，一般不会被使用，写入时也会有一定争抢，但不会导致太大的问题；如果是分布式数据库，索引只有两个值，按照哈希进行分区，则只会分布在两个节点上。假如业务是以写入为主，则无论集群有多少台机器，最后瓶颈都在这两个节点上，也就失了分布式数据库扩展性的初衷。
因此全局索引一定要解决 BigKey 问题，才能降低使用门槛。
PolarDB-X 通过将主键和索引 key 一起作为分区键，使得热点出现时依然能够按照主键进行进一步分裂，从而消除热点。
对于拆分算法和分区分布相同的两张表或索引， PolarDB-X 支持将 Join 下推到存储节点上执行，在 OLTP 场景下可以显著降低网络开销，提升查询性能。但如果不对分区操作进行限制，可能会由于分区的分裂合并或分区迁移，导致两张表分区的分布变得不同，使得 Join 无法下推。从用户角度看，可能是出现了一些分区操作后反而导致查询执行性能下降，导致用户产生一些使用上的疑惑。
为了解决上述问题，PolarDB-X 在后台引入了两个概念：Table Group 和 Partition Group。
Table Group 是一组 Global Index 的集合，系统会确保 Table Group 中的索引具备相同的数据分布。当发生分区分裂合并时，Table Group 中的索引会一起进行分裂和合并，保证数量一致。
处于同一个 Table Group 中的 Global Index ，相同的分区会组成一个 Partition Group。 PolarDB-X 会保证相同 Partition Group 中的分区始终落在相同的 DN 上，保证分区迁移操作不会影响 Join 的下推。
合理规划 Table Group 可以降低分区迁移等操作的代价。PolarDB-X 使用 Table Group 与 Partition Group 来对全局索引上的 Join 下推进行优化。
分区+ shared-nothing 架构带来了良好的可扩展性，但需要额外支持分布式事务和解决跨分区查询性能问题。 PolarDB-X 的分布式事务基于 2PC 和 TSO+MVCC ，通过 1PC 优化降低提交阶段的延迟，通过 TSO 合并优化确保 GMS 不成为瓶颈。透明全局索引良好地兼容了单机数据库上的索引使用体验，显著提升跨分区查询的性能。
PolarDB-X 以分布式事务和透明全局索引为核心的透明分布式技术，显著地降低用户使用分布式数据库的门槛。
