MyTopling 的 AutoSort SST

1. 背景

MyTopling 是基于 ToplingDB 的 MySQL，分叉自 MyRocks，ToplingDB 则分叉自 RocksDB，兼容 RocksDB 接口，从而 MyTopling 可以复用 MyRocks 的大部分成果。

ToplingDB 早已开源，MyTopling 也会于近期开源。

2. MyRocks 的 bulk_load

在 MyRocks 中，数据可以批量加载(bulk_load)，在 bulk_load 中，MyRocks 实现了一个 MergeTree，其实现方式是：把数据插入 std::set，当内存占用到达一定数量(可配置)时，将整个 std::set 中的数据写到外存（硬盘，ssd）文件中，一次 bulk_load 可能会生成多个外存文件。然后对多个文件使用最小堆进行多路归并，归并后的数据，使用 SstWriter，直接生成（多个） SST 文件，最后将这些 SST 文件 Ingest 到 RocksDB。

这个方案，就是一个标准的，教科书式的外排序实现，非常适合 MyRocks + RocksDB 这样的组合，跟 DB 中其它组件的性能比较相配，但是在 MyTopling 中，DB 其它组件的性能有了极大的提升，这样的处理方式就显得太慢了。

代码实现上，MyRocks 使用 std::set 的方式非常简单粗暴：

  struct merge_record {
    uchar *m_block; /* points to offset of key in sort buffer */
    const rocksdb::Comparator *const m_comparator;
    bool operator<(const merge_record &record) const {
      return merge_record_compare(m_block, record.m_block, m_comparator) < 0;
    }
    merge_record(uchar *const block, const Comparator *const comparator)
        : m_block(block), m_comparator(comparator) {}
  };
  std::set<merge_record> m_offset_tree;

std::set 的每个元素中，都有一个 Comparator 指针，而实际上，这个 Comparator 指针应该包装成 stl 风格的比较器，通过 std::set 的第二个模板参数传进去，然后，再依照 ToplingDB 的去虚拟化(devirtualization) 中描述的方法消除虚函数调用。

但是，这样的优化，在我们看来，根本就算不上是优化，我们要进行彻底的优化，要获得10倍以上的性能提升。

3. 一个可行的改进：使用 std::sort

首先，std::set 底层用的是红黑树，所以 MyRocks 实际上是用红黑树来进行排序，比起先乱序收集数据，再使用 std::sort 进行排序，性能要低不少。因为 sort 是静态算法，自然比红黑树这样的动态算法更高效，但 std::set 可以及时地发现重复 key，这大概就是 MyRocks 使用 std::set 的原因。

实际上重复 key 这个错误的概率非常低，从而并不需要那么“及时”地进行检测，完全可以在写文件的时候进行检测，这样就可以使用 sort，提高性能。这会比简单地优化掉 merge_record 中的 Comparator 指针并消除虚函数调用要高效很多，但是，这样的优化，远远不可能达到 10 倍的性能提升。

4. MyTopling 对 bulk_load 的改造

Topling 有 CSPP 这种杀手级算法，作为一种动态算法，将数据逐条插入 CSPP，比先乱序放在内存中，再进行 sort 更快！有 CSPP 作为算法底座，我们的选择空间就大了很多，但我们希望找到这样一个方案：

1. 性能提升最大化
2. 代码复用最大化：这个改进要输出可复用的成果
3. 协同作用最大化：要充分利用到 ToplingDB 生态现有的成果
4. 代码改动最小化：git diff 最少并且是局部性修改

经过仔细思考，我们竟还真得到了这样的方案，对 ToplingDB 和 MyTopling 都有修改，其中对 ToplingDB 的修改可以复用到 MyTopling 之外的其它项目。

4.1. 对 ToplingDB 的修改

1. 在 ToplingDB 中增加 AutoSort SST，内部使用 CSPP 实现，可以乱序添加 KV
   1. ToplingDB 和 RocksDB 的所有 TableBuilder 都需要加入的 KV 有序，只有 AutoSort SST 放宽了这个要求
   2. AutoSort SST 的 TableReader 实现 TableReader 接口的所有功能
2. 在 ToplingDB SstWriter 中增加对 AutoSort SST 的支持
   1. SstWriter 中有对 Key 顺序的验证，我们给 SstWriter 增加一个 auto_sort flag 变量，auto_sort flag 为真时，跳过对 Key 顺序的验证

4.2 对 MyTopling 的修改

增加相应配置，当使用 AutoSort SST 时，跳过 MyRocks 的 MergeTree 代码，直接将数据写进 AutoSort SST，以这样的方式，会生成多个 SST。

在提交整个 bulk_load 任务时，将多个 SST 进行 Compact，compact 的方式是，创建一个新的临时 DB，将这些 SST Ingest 到该临时 DB，然后对该临时 DB 进行 ManualCompact，在这里，可以使用分布式 Compact！然后将临时 DB 中 Compact 之后的 SST Ingest 到 MyTopling 中！软件组件之间的协同作用在这里得到了充分的体现！

一切圆满！

4.3 进一步提升

MyTopling 创建索引时会使用 bulk_load，而索引的 Value，在绝大多数情况下，都是空的，而我们的 AutoSort SST，是支持变长 Value 的，自然就有变长 Value 的成本。

所以，我们加了相关的配置项，fixed_key_len 和 fixed_value_len，这个配置项要从 MyTopling 中一路传递到 AutoSort SST，所以，传递路径上的相关参数，都要增加这两个配置变量。在 AutoSort SST 中，针对fixed_value_len 进行特殊处理。

4.4 热点转移

我们使用 create index ... on table 测试这个改进，提升了 10 多倍，原先 std::set 相关的热点，对应到现在是 AutoSortTable 相关的函数，其中耗时最多的，竟然是 Rdb_tbl_prop_coll，这是 MyRocks 的 TablePropertiesCollector，用来收集一些统计信息，以及最重要的，Index Cardinality！这在火焰图中原本是几乎完全看不到的，却成了新的热点。

Index Cardinality 用来衡量 Index 对 key 的区分度，对于 SQL 优化器非常重要，作为 DBA 需要深刻理解，备战面试的同学也可以研究下

仔细思考一下，AutoSort SST 创建好之后，马上就要被分布式 Compact 转化成 ZipTable，而在分布式 Compact 中还会再次执行 Rdb_tbl_prop_coll，所以 AutoSort SST 中执行的 Rdb_tbl_prop_coll 完全是浪费。

通过配置，禁止在 AutoSort SST 中调用 TablePropertiesCollector，相比 MyRocks 的 std::set MergeTree，性能提升 20+ 倍，最高时超过 30 倍！