本文首发于2018年。
仓氐，OceanBase高级研发工程师。
随着业务的快速发展，其对数据库的数据访问规则是不断变化的，在数据库中新建索引来加速业务查询是很常见的需求。
互联网的业务规模和发展速度对数据库的索引构建提出了更高的要求，一方面，在海量的业务规模下，非故障导致的停机是不可接受的，这意味着索引构建的同时，正常业务的读写请求不能被影响；另一方面，业务的快速发展和迭代，对索引构建的效率也有着更高的要求，索引更快速的生效，能加速新业务的开发和迭代过程。
传统单机关系数据库经过几十年的发展，逐渐实现了索引实时生效功能，这些数据库主要解决的问题是在索引构建的时候，避免长时间的锁表影响正常的业务请求。而分布式数据库由于其分布式的特性，在实现索引实时生效时，面临和单机数据库不同的问题.
OceanBase 1.x中通过把索引构建放在合并流程中避免了这些问题，但并没有做到索引实时生效，从用户执行创建索引表语句到索引表生效需要经过一或两次合并，OceanBase 2.0中解决了其中的问题，索引构建不再与合并耦合，用户执行创建索引后，能立即进入索引构建流程，较大地缩短了索引构建生效时间。
本文首先介绍了关系型数据库索引构建的发展现状，接着描述了OceanBase 1.x中索引构建遇到的问题，最后分析了OceanBase 2.0的索引构建设计，并给出了解决这些问题的方法。
索引构建的现状
根据架构不同，关系型数据库分为单机数据库和分布式数据库。不同的架构下，索引构建的方案有所不同，本节将分别介绍业界单机数据库和分布式数据库的索引构建方案。
单机数据库
我们以MySQL为例，来描述单机数据库的索引构建方案。MySQL从5.6开始支持索引实时生效，首先，执行完创建索引语句之后，新事务中新索引表的数据会写入到Row Log中，与此同时，会等待未往索引表中写入过数据的事务都结束。当所有的事务都结束后，开始索引构建流程，主要是处理两部分数据，一部分是等事务结束之后的主表快照点数据，此部分数据在索引表中是不存在的，需要通过主表数据构建出来，另一部分数据是记录在Row Log中的数据，需要应用到最终的索引表中。构建完成之后，将索引设置成可读写状态，进而优化器能使用该索引来优化用户的查询。
MySQL索引构建的特点如下：
- 是为In Place Update的存储引擎设计的，为了避免索引构建和用户事务对索引表更新的并发问题，索引构建过程中的更新数据会记录到Row Log的特殊存储中，这部分数据需要重新写入到索引表中，写入的时候会有一定的加锁时间。
- 基于快照点的构建流程是串行的，面对大数据量场景下性能可能存在不足。
- 元数据只有单版本，在更新相关元数据时，会加锁。
分布式数据库
和单机数据库不同的是，分布式数据库的数据分布和请求执行可能是分布在多台机器上的，导致索引构建方案也有所不同。本节将介绍Google研发的分布式数据库F1的索引构建方案。
如下图，Google F1采用的是存储计算分离的架构，架构上总共分为三层，最底层是分布式Key-Value存储引擎，第二层是无状态的计算层F1 Server，第三层为代理层，应用程序通过代理层和F1交互。
在此种架构下，事务执行时，有可能出现不同的SQL语句在不同的F1 Server执行的情况，那么不同的语句可能使用了不同版本的关系型元数据（为了设计和实现简单，F1只允许系统中同时出现两种不同版本的元数据），这会导致如下问题。
假设元数据版本S1 < S2，且S2比S1多了一张索引表，有如下执行过程。
- 在S2版本的F1 Server上执行INSERT语句，由于S2版本包括索引表，因此会生成索引表相关的KV记录。
- 在S1版本的F1 Server上执行DELETE语句，且和1中INSERT语句使用相同的主键，由于S1版本不包括索引表，因此索引表相关的KV记录不会被删除。
当上述事务执行完成后，索引表将会有多余的中间数据，导致数据表和索引表的数据不一致。
F1为了解决这个问题，引入了中间状态和最终状态，其中中间状态包括，delete-only和write-only，delete-only表示索引表只能被delete和update，而write-only表示索引表只能被insert、delete和update。最终状态包括absent和public，分别表示索引表不存在和索引表生效。在上述出问题的场景中，添加索引表的变更经过了absent->write-only->public的过程，由于absent状态时，索引表不存在，导致无法删除索引表的数据，因此，F1将添加索引的流程变成了absent->delete-only->write-only->public，这样就能保证索引构建完成后，数据和主表保持一致。
总体来看，Google F1的索引构建方案有这样的特点：F1 Server中最多存在两个不同版本的元数据，这意味着如果有机器在一个元数据更新租约时间内没有刷新到新版本元数据，那么F1 Server必须要自动退出以保证这个约束，使得这种方案比较适用于计算存储分离的架构，另外，为了避免F1 Server频繁因网络抖动主动退出，元数据更新租约时间一般是分钟级别，因此，对于数据量较小的表格构建索引，也需要分钟级别才能生效。
OceanBase 索引构建方案
本节先简单介绍下OceanBase的整体架构、存储引擎特点以及索引表的写入流程，接着讨论OceanBase 1.x索引构建中碰到的问题，最后描述了OceanBase 2.0中的索引构建方案。
整体架构
OceanBase的一个集群通常由多个zone组成，一个zone由一个或多个ObServer组成的，每个ObServer都具有计算和存储的功能。在ObServer中有一个较为特殊，负责总控服务的节点称为RootService，负责管理集群的元数据和路由信息，其中，元数据是按照多版本方式管理的。OceanBase按照分区的方式管理数据，一张表包含一个或多个分区，每个分区的数据会存储在多个zone中，每个zone都是一份完整的数据拷贝（副本）。每个分区的副本中会有一个Leader副本，负责处理该分区的读写请求。
存储引擎
OceanBase的存储引擎是按照Log Structured Merge Tree（LSM Tree）方式组织的，分为基线数据和增量数据两部分。基线数据存储在基线SSTable中，增量数据存储在Memtable和转储SSTable中。基线SSTable按照版本递增的方式来管理，某个版本的基线SSTable一旦生成后就变成只读状态，修改的数据会存储在Memtable中，当达到一定内存阈值后会先进行minor compaction（转储）转换成转储SSTable，当转储SSTable达到一定数量时，会将基线SSTable和转储SSTable做major compaction（合并），生成更高版本的基线SSTable。
在SSTable和Memtable中数据都是按照表的主键排序的，例如，有一张数据表test，包含列c1、c2、c3、c4和c5，其中主键为c1，那么test的数据是按照列c1的升序方式存储的；如果在数据表test上创建一个索引index，假设包含列c3和c2，那么index是按照主键c3、c2和c1的升序方式存储的，其中存储c1列是为了方便回表查询。
索引表的写入流程
在介绍索引表写入流程之前，先来看看OceanBase索引表的分区管理方式。OceanBase中索引表分为局部索引和全局索引。
局部索引是指分区规则和主表相同的索引，由于分区规则相同，局部索引和主表共用相应的分区，因此，局部索引分区和主表是在同一台机器上的。全局索引是指分区规则和主表不同的索引，分区规则的不同导致了全局索引和主表无法共用分区，而分区是OceanBase管理的基本单位，分区不同意味着全局索引和主表的分区是可能不在同一台机器上的。
索引表的写入通常是由主表驱动的，对主表的写入操作一般分为INSERT、DELETE和UPDATE，以上面的test主表和index索引表为例，对于INSERT，假如对test主表执行INSERT INTO test values(a,b,c,d,e)，会根据索引表的列生成索引行(c,b,a)，写入到索引表中；对于DELETE，假如对test主表执行DELETE FROM test where c1 = 'a'，会通过主表中的数据，获取索引列c3和c2，假设值为c和b，拼成完整的索引行(c,b,a)并删除索引表中对应的行；对于UPDATE，假如对test主表执行UPDATE SET c3 = c' where c1 = 'a'，首先会先获取主表中的数据，获取索引列c3和c2的数据，假设值为c和b，拼成完整的行(c,b,a)并删除索引表中对应的行，然后生成新的行(c',b,a)并写入索引表。对于唯一索引，更新时会检查写入的数据是否满足唯一性约束，具体地，需要检查索引表已有的数据中是否存在将要写入的行，如果存在，则会报唯一性冲突。
OceanBase 1.x 索引构建面临的问题
在OceanBase 1.x中，用户执行创建索引语句后，会等到集群下次合并时开始构建，构建过程中先等待主表合并到新版本后，再基于主表的最新版本的基线SSTable数据，构建出索引表的数据。OceanBase 1.x索引构建有如下问题：
- OceanBase 1.x缺少指定快照点读取数据的功能，索引构建依赖合并的快照点。
- OceanBase 1.x中只有局部索引，能通过同台机器的主表数据构建索引表的数据，而OceanBase 2.0中新增了全局索引，构建过程变成了分布式排序，如何以较小代价实现分布式排序呢？
- OceanBase 1.x中主表和索引表SSTable版本号是统一管理的，两者的版本号需要统一推进，而如果索引实时构建的话，可能在索引构建的同时，主表数据已经更新了多个版本，OceanBase 1.x的SSTable版本管理方法无法满足该需求。
OceanBase 2.0 索引构建方案
本节通过描述整个索引构建的流程，来介绍索引构建的方案设计以及如何解决相关问题的。总体上，OceanBase 2.0中，索引构建分为准备、构建、拷贝和收尾共四个阶段。
准备阶段
在索引构建准备阶段主要做了两件事情：
第一，生成索引表的元数据信息，其中索引表设置成只写状态，根据LSM Tree存储引擎的特点，索引表构建期间的数据直接写入到索引表的Memtable中，带来的好处是这部分数据直接成为索引表的一部分，后面无须再将这部分数据插入到索引表中，并且可以复用前面小节描述的索引表写入流程的代码。
第二，等待之前未往索引表插入过数据的事务结束，当所有的事务都结束后，获取构建快照点，构建阶段将基于此快照点扫描主表数据，并写入到索引表基线SSTable中，而用户事务产生的数据写入到Memtable中，这样就无须处理索引表构建和用户事务同时对索引表写入导致的并发更新问题。
第一件事中涉及到元数据的变更，OceanBase中采用多版本方式管理元数据，为了避免分布式环境下不同ObServer元数据版本不同带来的问题，采用如下方案解决。
- ObProxy将同一个事务的请求发送给同一个中控ObServer处理，这样可以保证事务的不同语句在中控ObServer看到的元数据版本是递增的，从而避免语句级别的元数据版本回退导致数据不一致的问题。
- 同一条语句可能会涉及到多个ObServer，可能会出现多个ObServer的元数据版本不同的情况，如果出现和中控ObServer的元数据版本不一致时，则进行语句重试。
准备阶段最重要的输出为快照点，在传统单机数据库中，获取快照点比较容易的，一般获取系统当前时间戳即可，但在分布式数据库中，由于每台机器的时间戳不可能是完全一致的，因此，不能简单的获取某个机器的时间戳作为快照点。OceanBase 2.0中实现了租户级全局时间戳，每个租户提供一个授时服务，每个租户的事务版本号都通过授时服务来获得，同样，索引构建准备阶段的快照点也通过授时服务来获得。
构建阶段
构建阶段的目标是基于主表快照点扫描出索引表所需数据，并按照索引列排序规则生成索引表基线SSTable数据。
在OceanBase 1.x中，Memtable转换成转储SSTable时，多版本的数据会被归并成单版本的，因此，数据一旦发生转储，且快照点落在转储SSTable范围内，则无法读取快照点数据。为了能够基于某个快照点扫描主表的数据，OceanBase 2.0中，Memtable转成转储SSTable时，会把Memtable中所有数据及其版本号都记录下来，从而扫描数据时，能根据快照点和数据的版本号，读取到所需版本的数据。
排序根据索引类型不同，执行过程也不相同，对于局部索引，索引表分区和主表相同，因此，构建阶段的数据流动仅仅是在本机，而对于全局索引，索引表分区和主表不同，一个索引表分区的数据通常来自主表的多个分区，而这些分区可能是在不同ObServer上的，是一个分布式排序过程，整个构建过程描述成了一个SQL的plan。
和面向OLTP的分布式执行不同，索引构建的分布式排序更关注容灾，在机器故障等情况下，能以较小的代价快速恢复，OceanBase 2.0的SQL执行框架中支持构建过程的中间结果持久化，构建过程出现机器宕机时，只需要选择其他机器重新执行故障机器相关的任务。同时，为了加速构建过程，将数据扫描和排序都做了并行化，充分利用磁盘和CPU的并行能力。
构建阶段可能会遇到合并，此时主表的基线SSTable的版本会增加，在索引表构建好之后，其版本号是落后于主表的。为了能描述这种场景，我们对基线SSTable管理功能做了重构，每个SSTable单独管理版本号，能够保证索引构建时，即使索引表落后主表多个版本，也能构建成功。
在生产环境，主表数据量通常比较大，索引构建往往是比较耗时的操作，为了避免索引构建对正常用户请求产生影响，OceanBase 2.0中会基于用户IO请求来限速，当用户请求的IO响应时间超过一定阈值时，会自动限制构建过程中IOPS。
拷贝阶段
鉴于索引构建比较耗时，OceanBase 2.0中只在单副本上构建索引表，其他副本从构建好的副本拷贝数据。在单副本构建期间写入索引表的数据会通过一致性算法同步到索引表多个副本上，因此，拷贝阶段仅仅需要将构建好的基线SSTable拷贝到其他的副本上。和构建一样，我们对拷贝过程也做了并行化，每个分区会按照数据量切分成多个任务，由多个线程批量地执行任务。为了避免并行拷贝过度的消耗资源，会对拷贝阶段整体网络带宽作限制，同时也提供了拷贝的并行度控制，方便运维。
收尾阶段
收尾阶段分为两步，分别是数据校验和索引生效。数据校验根据索引类型的不同，会做不同的操作，对于普通索引，会根据构建阶段计算的主表的列校验和索引表的列校验和进行比对，保证构建出来的索引表的数据和主表的数据是一致的；对于唯一索引，因为构建过程中也有可能写入数据，而构建过程中索引表的基线数据还未构建完成，唯一性校验可能不完整，因此，需要在索引表基线数据构建和拷贝完成后，对唯一索引做唯一性校验，同时为了保证索引构建的数据正确性，我们采用将主表和索引表数据进行校验，既验证了数据正确性，也验证了索引是否满足唯一性。
‘
当数据校验通过时，将索引表设置成可读写状态，进而SQL优化器能使用新的索引来加速查询，当数据校验不通过时（一般是唯一索引唯一性约束不满足），会将索引设置成不可用状态。
总结
OceanBase的索引实时生效包括两层含义，第一是索引构建过程从合并中解耦，用户触发后能立即进行构建流程，第二是通过专门为LSM Tree存储引擎优化的构建流程，构建流程的并行化，单副本构建，副本拷贝的并行化，以及容灾时快速恢复等技术手段，有效地加快了索引生效的速度。
OceanBase的索引构建时能对占用的资源做控制，减少对正常用户请求的影响。通过完备的数据校验，保证了构建完成的索引表的数据正确性。另外，当前的索引构建方案对计算存储一体化以及计算存储分离的架构都是适用的。
参考文献
1. Innodb Online DDL Operations
2. Online, Asynchronous Schema Change in F1
