本文首发于2018年。
作者：乔治国，OceanBase高级技术支持专家。
前言
在数据库领域中，“分区表”的概念大家并不陌生，但是分区表中“本地索引（Local Index）”和“全局索引（Global Index）”的概念，未必每个朋友都关注过。和本地索引相比，全局索引在使用上更加灵活方便，在很多场景下也能提供更好的查询性能，对开发人员来说更加友好。但是全局索引的实现也会有更大的难度，尤其是在分布式环境下，实现难度更大。
本文将帮助读者简单回顾一下全局索引相关的概念，并介绍OceanBase数据库如何在2.0版本中实现全局索引的功能。
本地索引和全局索引概述
为了方便大家阅读，我们先约定一些固定的术语，后文的描述中会统一采用这些术语。
- 主表
指使用CREATE TABLE语句创建的表对象。也是索引对象所依赖的表（即CREATE INDEX语句中ON子句所指定的表）。
- 索引（索引表）
指使用CREATE INDEX语句创建的索引对象。有时为了便于大家理解，也会把索引对象类比为一个表对象，即索引表。
此外，为了方便大家理解文字描述，我们会以一个实际的数据库表来演示各种情况，这个表的名字叫employee（员工信息表），表的结构如下：
employee
{
emp_id, /* 员工ID */
emp_name /* 员工名字*/
dpet_id, /* 部门ID */
...
}
首先，我们来简单回顾一下传统的“非”分区表中，主表和索引的对应关系。主表的所有数据都保存在一个完整的数据结构中，主表上的每一个索引也对应一个完整的数据结构（比如最常见的B+ Tree），主表的数据结构和索引的数据结构之间是一对一的关系，如下图所示：
上图展示了employee表中，以emp_id创建的索引。
当分区表出现之后，情况发生了变化：主表的数据按照分区键（Partitioning Key）的值被分成了多个分区，每个分区都是独立的数据结构，分区之间的数据没有交集。这样一来，索引所依赖的单一数据结构不复存在，那索引需要如何应对呢？这就引入了“本地索引”和“全局索引”两个概念。
1）本地索引（Local Index）
分区表的本地索引和非分区表的索引类似，索引的数据结构还是和主表的数据结构保持一对一的关系，但由于主表已经做了分区，主表的“每一个分区”都会有自己单独的索引数据结构。对每一个索引数据结构来说，里面的键（Key）只映射到自己分区中的主表数据，不会映射到其它分区中的主表，因此这种索引被称为本地索引。从另一个角度来看，这种模式下索引的数据结构也做了分区处理，因此有时也被称为本地分区索引（Local Partitioned Index）。本地索引的结构如下图所示：
在上图中，employee表按照emp_id做了范围分区，同时也在emp_name上创建了本地索引。
2）全局索引（Global Index）
和分区表的本地索引相比，分区表的全局索引不再和主表的分区保持一对一的关系，而是将所有主表分区的数据合成一个整体来看，索引中的一个键可能会映射到多个主表分区中的数据（当索引键有重复值时）。更进一步，全局索引可以定义自己独立的数据分布模式，既可以选择非分区模式也可以选择分区模式；在分区模式中，分区的方式既可以和主表相同也可以和主表不同。因此，全局索引又分为以下两种形式：
- 全局非分区索引（Global Non-Partitioned Index）
索引数据不做分区，保持单一的数据结构，和非分区表的索引类似。但由于主表已经做了分区，因此会出现索引中的某一个键映射到不同主表分区的情况，即“一对多”的对应关系。全局非分区索引的结构如下图所示：
在上图中，虽然employee表按照emp_id做了分区，但是创建在dept_id上的全局索引并没有分区，因此同一个键值可能会映射到多个分区中。
- 全局分区索引（Global Partitioned Index）
索引数据按照指定的方式做分区处理，比如做哈希（Hash）分区或者范围（Range）分区，将索引数据分散到不同的分区中。但索引的分区模式是完全独立的，和主表的分区没有任何关系，因此对于每个索引分区来说，里面的某一个键都可能映射到不同的主表分区（当索引键有重复值时），索引分区和主表分区之间是“多对多”的对应关系。全局分区索引的结构如下图所示：
在上图中，employee表按照emp_id做了范围分区，同时在emp_name上做了全局分区索引。可以看到同一个索引分区里的键，会指向不同的主表分区。
由于全局索引的分区模式和主表的分区模式完全没有关系，看上去全局索引更像是另一张独立的表，因此也会将全局索引叫做索引表，理解起来会更容易一些（和主表相对应）。
这里特别说一点：“非”分区表也可以创建全局分区索引。但如果主表没有分区的必要，通常来说索引也就没有必要分区了。后文中会忽略这种特殊情况，主要讨论分区表中的本地索引和全局索引。
本地索引和全局索引的比较
那么，对于分区表来说，本地索引和全局索引哪一种更好呢？其实两种索引是各有优劣势的，下面分别加以说明。
首先来说本地索引。它最明显的好处就是实现简单，但本地索引的问题也很明显，尤其是“索引键没有包含主表所有的分区键字段”的情况，此时对某一个索引键值来说，对应的索引数据在所有分区的本地索引中都可能存在，这会引发两个突出的问题。
问题一：由于本地索引只处理一个主表分区的数据 ，因此只能在一个主表分区内保证索引键的“唯一性约束”，无法在全表范围内保证索引键的唯一性约束 ，如下图所示：
上面的图中，employee按照emp_id做了范围分区，但同时想利用本地索引建立关于emp_name的唯一约束，这是根本无法实现的。
针对这个问题，有些数据库在分区表中会增加限制，要求主键和唯一索引的定义中必须包含主表所有的分区键字段。有了这个限制，索引中的某一个键所对应的索引数据只可能存在于一个分区中，因此只要在每一个分区内保证唯一性约束，即可在全表范围内保证唯一性约束。这个限制虽然解决了数据库的难题，却大大增加了开发人员的烦恼，因为它会导致主键和唯一索引的可选范围大大缩小（只能是主表分区键的“超集”），很多业务需求因此无法满足，这也是本地索引最被诟病的地方。
问题二：由于某一个索引键值在所有分区的本地索引上都可能存在，任何索引扫描必须在所有的分区上都做一遍，以免造成数据遗漏。
这会导致索引扫描效率低下，并且会在全局范围内造成CPU和IO资源的浪费。采用“分区间并行”的手段可以提高效率，但不能从根本上解决这个问题。
下面来看看全局索引。相比本地索引来说，全局索引具有诸多优势，尤其是针对前面谈到的，当“索引键没有包含主表所有的分区键字段”时本地索引所面临的两个突出问题。
1. 不能实现全局唯一性约束的问题。
对于全局索引来说，可以为索引数据指定自己的分区方式，并且索引的分区键一定是索引键的子集，因此可以很容易解决这个问题。下面分别以几种情况做说明：
- 全局非分区索引。此时索引的结构和“非分区”表没有区别，只有一个完整的索引树，自然很容易保证唯一性。
- 全局分区索引。这种情况下，对于某一个索引键来说，由于包含了所有的索引分区键，它的数据只可能落在一个固定的索引分区中，因此只要在每一个索引分区内保证唯一性约束，就可以在全表范围内保证唯一性约束。而单个索引分区内只有一个索引数据结构，很容易保证唯一性约束，因此问题就得到了解决。
2. 必须扫描“所有”分区所带来的性能和资源浪费问题。
这个问题也可以分几种情况分别说明：
- 全局非分区索引。前面讲述唯一性约束的问题时提到了，此时只有一个完整的索引树，自然没有多分区扫描的问题。
- 全局分区索引。前面讲述唯一性约束的问题时提到了，全局索引能保证某一个索引键的数据只落在一个固定的索引分区中。对于索引键值的范围扫描，我们希望索引扫描按单向顺序在每个分区内都只执行一次，而不必在索引分区之间来回穿梭，因此我们要求索引的分区键是索引键的“前缀（Prefix）”：比如索引键是"a,b"，那么索引的分区键可以是"a"或者"a,b"，但不能是"b"，即要求分区的排序规则和索引树的排序规则一致。这样一来，无论是针对固定键值的索引扫描，还是针对一个键值范围的索引扫描，都可以直接定位出需要扫描的一个或者几个分区，而不是像本地索引一样盲目地在所有分区上扫描，这样就解决了本地索引面临的问题。
解决了上述问题之后，从使用者的角度来看，分区表的全局索引和非分区表的索引已经没有太大区别，除了一点：全局索引需要定义索引的分区模式。这里虽然也可以使用全局“非分区”索引，但是引进全局索引的目的就是针对数据量较大的分区表，对应的索引数据量往往也是非常大的，因此还是推荐使用全局分区索引，不但可以突破非分区索引面临的单点容量限制，在并发较大的情况下也能获得更好的性能。
当然，全局索引也面临一些问题，主要是架构复杂，实现难度大，以及由此引发的一些相关问题，比如当索引数据和对应的主表数据位于不同的机器时，在事务内会面临数据一致性和性能方面的挑战。但考虑到全局索引给数据库使用者带来的巨大便利，付出一点代价也是值得的。
综合二者的特点来看，本地索引和全局索引的适用场景是不一样的：
- 本地索引比较适合“索引键包含主表所有的分区键字段”这种特殊情况。
- 除了上面的特殊情况之外的其它场景，全局索引更加合适。
可以说，全局索引具有更强的通用性。
OceanBase中的全局索引
关于全局索引的实现原理，以及全局索引和本地索引的比较，前面都已经有过详细的描述，这是业界实现全局索引的基本思路，也是OceanBase中实现全局索引的基本思路。但是，前面我们更多的是讨论索引数据结构和主表数据结构的映射关系（一对一、一对多、多对多等），而忽略了另外一个很重要的因素要，那就是数据的物理分布。
对于传统的单点数据库来说，每个数据结构之下都是“本地可访问”的存储层，比如一个本地数据库表空间（里面包含若干本地文件或者设备），无论有多少个主表分区或者索引分区，数据库总是可以通过本地机器访问到，即Share-Everything的架构。
但是对于OceanBase这样的分布式数据库来说，每一个主表分区和索引分区都可能分布在不同的机器上，比如“N个主表分区+M个全局索引分区”这种多对多的复杂情况，可能是（N+M）台物理机器上形成的（N*M）种索引键到主表分区的映射关系，这会带来诸多挑战：
- 如果一个事务中要修改的N条记录分别位于N台不同的机器上，而它们对应的全局索引数据又位于另外M台不同的机器上，如何在这（N+M）台机器间保证主表数据和索引数据的同步更新？
- 还是上面所说的主表数据和索引数据分布在不同机器的场景，在保证数据一致性的前提下，如何进一步缩短跨机器访问的时间，进一步提高查询效率？
- 如何保证全局索引数据在全局范围内的读写一致性？一台机器上更新的索引数据，如何确保一定能被其它机器上后续的访问者读到？
可以说，如果不能解决上述问题，全局索引在分布式数据库中就失去了存在的基础。因此，虽然业内有很多分布式数据库，但全局索引功能却并不是一个标配，很多大家所熟悉的分布式数据库产品（如MongoDB，Cassandra，Hbase等）并不提供全局索引功能，只有少数产品才能提供，比如Google F1/Spanner和CouchBase，这也从一个侧面印证了在分布式数据库中实现全局索引的难度。下面我就简单给大家介绍一下，OceanBase数据库是如何跨越上述的一个个难关，在2.0版本中实现了全局索引的功能。
首先来看第一个问题，如何保证主表数据和索引数据的跨机器同步更新。这个问题的本质，其实是分布式数据库中“分布式事务一致性”问题，主表数据和索引数据是同一个事务中的两部分数据，当它们分布在不同的机器上时，分布式事务需要保证事务的原子性（Atomicity）：两部分数据要么全部更新成功，要么全部失败，不会因事务异常而导致主表数据和索引数据的不同步。
OceanBase数据库在几年前的1.0版本中就提供了分布式事务功能，利用Paxos协议和经过改良的“两阶段提交（Two-phase Commit）”方法，能在跨机器的分布式事务内保证ACID，即使事务的参与者发生异常（如机器宕机），也能确保分布式事务的完整性，避免了传统两阶段提交方法会导致的“事务部分未决（In-doubt Transaction）”问题，因此OceanBase完全可以保证跨机器事务中主表数据和索引数据的同步。关于OceanBase数据库分布式事务的详细内容，读者可以查阅本文末尾参考文档中的相关文章。
解决了分布式事务的一致性问题，我们来关注一下第二个问题，就是索引数据和主表数据分跨机器访问时的效率问题。这里面临的最大挑战就是分布式事务的网络延迟和多次日志落盘，而这种物理开销是没有办法完全消除的，为此Google在F1的论文中明确说明不推荐太多的全局索引，并且应尽量避免对有全局索引的表做大事务访问。那OceanBase是如何应对这个问题的呢？
前面提到过，OceanBase使用了经过改良的两阶段提交方法，这种改良不仅体现在保证数据的一致性上，也体现在性能上：和传统的两阶段提交相比，OceanBase的两阶段提交过程中会有更少的网络交互次数以及更少的写日志次数，而这些恰恰都是分布式事务中最耗时的操作。有了这样的优化，在很大程度上缩短了分布式事务的处理时间，提高了全局索引的处理效率。
最后一个问题，则是分布式数据库中全局（跨多台机器）的读写一致性问题。对OceanBase这样实现了快照隔离级别（Snapshot Isolation）和多版本并发控制（MVCC）的分布式数据库来说，如何在机器间有时钟差异的情况下，仍能维持时间戳（即版本号）在全局范围内的前后一致性，这是一个很重要的问题。
在OceanBase数据库的2.0版本中，我们提供了“全局一致性快照”功能，并在此基础上实现了全局范围内的快照隔离级别和多版本并发控制，这样就能保证全局范围内前后事务的读写一致性，满足了全局索引的要求。关于OceanBase数据库全局一致性快照的详细内容，读者可以查阅本文末尾参考文档中的相关文章。
因此，OceanBase数据库的2.0版本解决了上述所有的技术难题，我们也正式推出了全局索引功能。对于数据库用户来说，可以不再担心本地索引在分区表使用中的诸多不便，利用全局索引实现任意模式的全局一致性约束，并且为更多的复杂查询场景提供更优的性能，尽情体验“全局索引+分布式架构”带来的完美体验！
