MyTopling 创建索引的优化

原创 Topling 2024-07-15

210

（一）背景

开源数据库 MyTopling 是基于开源存储引擎 ToplingDB 的 MySQL，MyTopling 分叉自 MyRocks，兼容 MyRocks，ToplingDB 分叉自 RocksDB，兼容 RocksDB。

在阿里云的大力支持下，MyTopling 成功上线计算巢：私有化部署版，高级版，基础版，集成版（集成 LNMP/Wordpress），特价版 2核2G ￥99包年。

（二）MyTopling 数据编码

● ToplingDB Key 编码为 memcmp 格式，性能更高、适应性更强
　　◆ 不使用自定义比较器，使用字典序比较器(BytewiseComparator)
　　◆ Topling CSPP & SST 仅支持字典序比较器
　　◆ 索引 ID 占 4 字节，编码为大端存储(BigEndian)以便 memcmp

● 每个二级索引，对每行数据，有一个 ToplingDB 的 KV
　　◆ 其中 Key 一般很小， Value 一般为空
　　◆ 二级索引很多时，SQL 层写一条数据，对应到引擎层就要写多条数据。

（三）创建索引

在任何关系数据库中，二级索引都会产生较大的开销，所以在实践中，如果有机会，有可能，经验丰富的 DBA 一般都是先插入数据，再创建索引。

在 MySQL 中，创建索引（alter table .. add index ...，一条语句可以 add 多个 index）会被下推到引擎层，MyRocks 的做法是：

Scan 阶段：对每个 index，扫描 table，解析 Row，组装 IndexKey，在内存中创建 MergeTree（使用 std::set），MergeTree 达到预定大小时，将其写到磁盘上，这样生成多个按 key 有序的文件。
Commit 阶段（进行全排序）：对 Scan 阶段生成的多个按 key 有序的文件进行多路归并，归并后的结果使用 SstWriter 进行输出，每个 sst 文件达到预定大小时，结束该文件，开始新文件，最终生成多个 sst 文件。
Ingest 阶段：将 commit 阶段生成的多个 sst 文件 ingest 到 RocksDB 中。

（四）MyTopling 的改进

Scan 阶段：不使用 MergeTree，直接将组装好的 IndexKey 写入 SST，该 SST 允许输入的 Key 乱序，达到预定大小时，结束该 SST，此时会调用虚函数 sst->Finish()，在该函数中执行排序，然后写入磁盘文件，其中排序操作进行了高度优化，相比 MergeTree(std::set)，提速 10 倍以上。
Commit 阶段（进行全排序）：创建一个临时 DB，将 Scan 阶段生成的多个 SST Ingest 到该临时 DB，然后对该临时 DB 进行 Compact，Compact 过程可以使用 ToplingDB 的分布式 Compact。
Ingest 阶段：将临时 DB Compact 之后的多个 sst 文件 ingest 到 ToplingDB（对应rocksdb）。

进一步地，对 Scan 阶段进行深度优化：
　◆ 将 sst->Finish() 放入专门的线程中异步执行，因为 Finish 要执行排序，耗时较多
　◆ 扫描 table 时，每得到一个 Row，就对 alter table add index 语句中的每个 index，组装其 IndexKey 并写入相应 sst，避免了对 table 的多次扫描

其中有一些微秒之处：
　◆ sst->Finish() 时间复杂度为 O(nlogn)，但常数项较小
　◆ Scan 本身的耗时为O(n)，但常数项可能很大（当 Row 很长时）

理想情况下，Scan 与 Finish 构成一个 Pipeline：

（五）实战表现

在我们定制的 sysbench 测试中，通过一个 alter table add index 创建 60 个索引，虽然 Row 很长，解析 Row 开销很大，但架不住 60 个索引的每个 sst->Finish() 都是 O(nlogn)，Finish 就跟不上，在规格较低的机器上就把内存耗尽了！虽然这种极端情况在现实中几乎不会遇到，但数据库作为基础软件，必须应对所有可能发生的情况，所以我们对此进行流控，限制 Finish 队列的尺寸。

最终，MyTopling 创建索引的性能遥遥领先：