BaikalDB技术实现内幕（二）-- 索引实现

索引能力是数据库查询加速的重要基础设施，HTAP数据库BaikalDB为应对复杂业务需求，充分实现了全局、局部、倒排索引，本文主要介绍BaikalDB的索引技术实现。

欢迎关注 Star github.com/baidu/BaikalDB

BaikalDB系统简介

BaikalDB是一个分布式可扩展的存储系统，兼容MySQL协议，整个系统的架构如下图所示：

• BaikalStore 负责数据存储，数据分区按region组织，三个Store的三个region形成一个Raft-group实现三副本，多实例部署，Store实例宕机可以自动迁移 Region数据；
• BaikalMeta 负责元信息管理，包括分区，容量，权限，均衡等， Raft保障的3副本部署，Meta宕机只影响数据无法扩容迁移，不影响数据读写；
• BaikaDB 负责前端SQL解析，查询计划生成执行，无状态全同构多实例部署，宕机实例数不超过qps承载极限即可；

Baikal 命名由来

贝加尔湖（Lake Baikal）是世界上最大的淡水湖，相当于北美洲五大湖水量的总和，超过整个波罗的海水量，淡水储量占全球20%以上。西伯利亚总共有336条河流注入贝加尔湖。冬天的贝加尔湖畔，淡蓝色的冰柱犹如分布式数据库一列列的数据密密麻麻但是有井然有序，令人惊艳。

BaikalDB索引介绍

BaikalStore 对数据按照主键进行 range 划分形成多个 region，region 按行存的形式将数据组织为主键索引及二级索引，这些主键索引、二级索引编码为key、value 值写入本地 Rocksdb 中。

BaikalDB 索引主要包含以下五种，其中主键索引存储主表数据的所有字段，二级索引存储主键字段。

• 主键索引（PRIMARY KEY）
• 主键索引是 BaikalDB 针对主键创建的索引，主键 key 值必须唯一。BaikalDB 使用主键值将整个表进行 range 划分为多个 region 分区。
• 局部二级索引
• 普通索引（KEY）
• 唯一索引（UNIQUE KEY）
• 全局二级索引（GLOBAL KEY）
• 倒排索引（FULLTEXT KEY）

本文以如下 schema 为例，对各索引类型的编码进行一一介绍。

CREATE TABLE example (
 field0 bigint(20) NOT NULL ,
 field1 bigint(20) NOT NULL DEFAULT '0' ,
 field2 bigint(20) NOT NULL DEFAULT '0' ,
 field3 bigint(20) NOT NULL DEFAULT '0' ,
 field4 bigint(20) NOT NULL DEFAULT '0' ,
 field5 varchar(20) NOT NULL DEFAULT '',
 PRIMARY KEY (field0),
 KEY index2 (field2),
 UNIQUE KEY index3(field3),
 KEY GLOBAL index4(field4),
 FULLTEXT KEY index5(field5)
)

主键索引

• 主键：PRIMARY KEY (field0)
• 主键索引将主键字段与一行数据做映射，并最终形成一个按主键 key 排序内存/磁盘结构，方便用户快速通过主键 key 进行定位或扫描。
• 主键 key 值包含64 Bit region_id、64 Bit index_id、primary key 值组成。其中 region_id 为 region 的标识 id，在 region 生成时指定。index_id 为索引标识 id， 在表创建时生成。在该示例中，primary key 值为字段 field0 的值，为64 Bit。
• 主键 value 值为表 schema 对应动态 protobuf 反序列化之后的值。上述 schema 对应的动态 protobuf 结构为:

message example {
 optional int64_t field0 = 0; 
 optional int64_t field1 = 1; 
 optional int64_t field2 = 2;
 optional int64_t field3 = 3;
 optional int64_t field4 = 4;
 optional string field5 = 5;
};

局部二级索引

• 所谓局部二级索引，就是主表数据和索引数据在同一分片上，每个分片就包含了该分片上信息的全部索引。局部二级索引又分为普通二级索引、唯一二级索引。
• 二级索引将二级索引字段与主键 key 做映射，可以加速二级索引字段的查找或扫描。

局部索引

• 索引：KEY index2 (field2)
• key 值 包含64 Bit region_id、 64 Bit index_id、8 Bit 空字节、 index key值、primary key 值组成。其中 index key 值为 字段 field2 的值，为 64 Bit。（注：其中8 Bit 空字节已废弃，不体现在索引使用示例小节中。）
• value 值 为空串 ""

局部唯一索引

• 唯一索引：UNIQUE KEY index3(field3)
• key 值 包含64 Bit region_id、64 Bit index_id、8 Bit 空字节、 index key 值。（注：其中8 Bit 空字节已废弃，不体现在索引使用示例小节中。）
• value 值为 64 Bit primary key 的值。

全局二级索引：GLOBAL KEY index4(field4)

• 所谓全局二级索引，就是主表数据和索引数据不在同一个分片上，所有分片的二级索引数据集中存储。
• 相对于局部二级索引，全局二级索引的优势是：在没有具体分片信息，利用二级索引反查主键时，局部二级索引需要扫描所有分片，而全局二级索引只需要扫描单分片。
• 全局二级索引也分为普通索引、唯一索引，编码规则与局部索引一致。

倒排索引：FULLTEXT KEY index5(field5)

• BaikalDB 支持倒排索引，主要用来进行快速的全文检索。BaikalDB 倒排索引主要涉及索引构建及检索：
• 构建：将正排字段切词为一或多个 term。构建 term 的有序倒排拉链，并按照格式进行存储。
• 检索：根据检索词，对多个倒排拉链进行布尔查询。下面对上述两个步骤，进行示例说明。
• 切词：下图为以field5作为倒排索引字段的切词示例：

• 倒排存储：将所有正排按照词（term）粒度进行合并，建立倒排索引，并使用 Rocksdb 进行存储。其中 key 值为 64 Bit region_id、64 Bit index_id、分词后的 term ，value 值为排序之后的主键键值。（下图为简化模型，BaikalDB中实际使用分层存储）

上述示例中 term 的倒排拉链的存储格式如下：

• 倒排检索：根据检索词对多个倒排拉链进行布尔逻辑检索。上例中检索词为 “倒排|索引”、“测试&倒排” 检索词的多排序表的合并结果如下图所示。其中“倒排|索引”检索词，将“倒排”及"索引"的倒排拉链进行并运算；“测试&倒排” 检索词，将“测试”及“倒排”的倒排拉链进行与运算。

索引使用示例

为了更好的说明 BaikalDB 中的索引使用方式，下面给出4个示例，分别展示在数据的写入及读取过程中，主键索引、二级索引、全局二级索引所起的作用。

示例一：insert

• sql : insert into example values (0,1,2,3,4,"测试倒排")
• 整体流程
• 根据表 example 的 schema 信息，生成动态 message，并设置各 field 值：{"field0" : 0, "field1" : 1, "field2":2, "field3" : 3, "field4":4, "field5":"测试倒排"}
• 根据主键值（field0=0），定位到目标 region 分片。
• 将动态 message 序列化之后，传给目标 region 分片。
• 目标 region 分片分别对各索引生成对应格式的 kv 值，写入底层rocksdb。
• 将全局索引写入全局索引分片。
• 完成写入
• 流程图

示例二：select（不使用二级索引）

• 不使用索引 sql:select * from example where field4 = 4;
• 整体流程：
• 根据sql，生成执行计划：因 field4 字段不在二级索引中，只能遍历主索引，并进行过滤。
• 因没有主键条件，向所有 region 分片广播执行计划。
• scan node 执行过程：在所有 region 分片中，编码主键前缀 key 值：（region_id、index_id），对 Rocksdb 中所有主键进行顺序扫描。
• filter node 执行过程：对扫描出的所有主键 kv 中， 使用动态生成 protobuf 对 value 值进行反序列化，并提取出 field4 值。对解析出的 field4 值进行过滤，获取满足条件（field4 = 4）的结果。
• 组装各 region 分片中的返回值，打包返回给用户。
• 流程图

示例三：select（使用二级索引）

• 使用索引 sql:select * from example where field2 = 2;
• 整体流程
• 根据sql，生成执行计划：使用索引 index2 进行扫描。
• 因没有主键条件，向所有 region 分片广播执行计划
• scan node 执行过程：在 region 分片中，编码 index2 的 key 值（region_id、index_id、field2、primay_key），在 Rocksdb 中前缀扫描。
• 在 Rocksdb 中 key 中，提取出 field0 值，构造主键 key，反查主键，解析所有字段。
• 组装各 region 分片中的返回值，打包返回给用户。
• 流程图

示例四：select（使用全局二级索引）

• 使用索引 sql:select * from example where field4 = 4;
• 整体流程
• 根据sql，生成执行计划：首先使用全局索引 index4 进行扫描，查出主键值之后，扫描主键值对应的分片。
• 全局索引 scan node 执行过程：根据全局索引字段 feild4 ，定位全局索引分片，发送请求获取主键键值。
• 根据主键键值，定位 region 分片信息。
• 主键索引 scan node 执行过程：在 region 分片中，编码主键 index0 的 key 值（region_id、index_id、field0），在 Rocksdb 中前缀扫描。
• 组装各 region 分片中的返回值，打包返回给用户。

示例分析

• 写入（insert）场景
• 可以很好的利用 region 分片特性，只对部分 region 进行写入操作。
• 查询（select）场景
• 局部二级索引：使用恰当的索引对整体性能的提升有很大帮助。如示例2中，在没有二级索引的情况下，需要扫描所有主键 kv；然后进行 protobuf 反序列化；最后进行字段过滤。而在示例3中，只需要扫描部分二级索引。
• 全局二级索引：在示例3中，虽然在单分片中，性能较好，但因为没有主键信息，所以需要广播所有分片，进行查询。考虑到较大的表可能有多达万级的分片数量，所以整个开销还是较大的。这种场景下可以使用全局二级索引，根据索引字段查出主键值，然后只需要查询已知主键值对应的分片即可，而不需要广播所有分片。

总结

本文对 BaikalDB 中的各种索引类型的编码方式、使用方法进行了简要的说明。

作者介绍：黄文亮，百度商业平台研发部资深研发工程师

主要负责BaikalDB索引能力，性能优化等方向的研发工作。