1. 背景
MyTopling 是拓扑岭(topling.cn)开发的 MySQL 兼容数据库，之前我们发布了文章 MyTopling：兼容 MySQL 的云原生数据库。
对于任何数据库来讲，事务处理都是核心中的核心，MyTopling 也一样。作为一个社会化分工协作的大型项目：
1.MyTopling fork 自 facebook 的 myrocks-8.0.23，对其中的关键模块进行全新设计
2.facebook 的 myrocks-8.0.23 fork 自 oracle 的官方 mysql-8.0.23
1.在 MySQL 的存储引擎架构中，加入了 rocksdb 存储引擎
2.rocksdb 存储引擎有两层含义
1.在 mysql 中，指的是一个名称为 rocksdb 的，实现了 mysql 存储引擎接口的插件
2.在更广泛的世界中，指的是 rocksdb 这个 Key Value 数据库
3.facebook 的 myrocks-8.0.23 还基于 myrocks-5.6.35，本质上是 myrocks-5.6.35 与 oracle 的官方 mysql-8.0.23 两个项目合并的结果
2. MyRocks 的事务处理
MyRocks 的事务处理是使用 rocksdb 这个 KV 数据库中的 TransactionDB 来实现的，TransactionDB 属于 RocksDB 这个项目，而不属于 MyRocks，然而，事实上，因为 MyRocks 和 RocksDB 都是 facebook 开发的，TransactionDB 本质上是为 MyRocks 量身定做的，但是为了实现“复用”，TransactionDB 相当于是强行从 MyRocks 中抽取出来，然后“通用化”成 RocksDB 的一部分，从而可以为 MyRocks 之外的其它项目所用。
在 MyRocks 中，默认的 TransactionDB 是 PessimisticTransactionDB，顾名思义，就是“悲观”事务处理，即先检查是否有冲突，无冲突就继续，有冲突就失败。关于 RocksDB Transaction 的详细分析，知乎上有朋友写了非常棒的回答：事务的实现原理，应该从哪些方面回答？ CPU 设计中有 ISA 和微架构，TransactionDB 相当于是个 ISA，我们在不改变 ISA 的前提下，对微架构进行优化：
2.1. WriteBatchWithIndex
在 RocksDB 中，每次写 DB 的单位是 WriteBatch，WriteBatch 只保证 ACID 中的 AC，不管 I（即 Isolation 事务隔离），TransactionDB 通过 WriteBatchWithIndex 实现了事务隔离，ACID 中的 D 则通过 WAL 来实现。
顾名思义，WriteBatchWithIndex 在 WriteBatch 的基础上加上了 Index，从而可以搜索 WriteBatch 中的内容。RocksDB 将它硬编码为使用 SkipList 实现，在事务处理中，我们发现 WriteBatchWithIndex 相关的 SkipList 是个巨大的性能热点。所以它是第一个优化的点，第一步，我们需要修改接口，增加相应的 Factory，然后，对相关的类进行泛化，同时保持对使用方的源码级兼容。这种代码修改方式，是我们一贯的原则，我称之为“微创手术法”。
先说结论，再说细节，我们的优化最终把 WriteBatchWithIndex 中 Index 的性能提高了 20 倍以上，并且内存占用更低！
我们使用 Topling CSPP Trie 替换 SkipList，但是 CSPP Trie 仅支持 BytewiseComparator，理论上还可以支持 ReverseBytewiseComparator，但是因为会引入额外的复杂性，所以我就只让它支持 (Forward)BytewiseComparator。CSPP Trie 除了速度快，内存占用小，还能多线程 Scaling，不过在 WriteBatchWithIndex 中，我们并不会多线程访问它，所以我们使用单线程模式（此模式下，CSPP Trie 占用的内存可以自由增长）。
WriteBatchWithIndex 有个 rep 成员，通过该 rep，使用 PImpl 惯例实现了代码隔离。从而，我们就有两种选择：
1.抽象 Rep
2.抽象 WriteBatchWithIndex
抽象 Rep 的好处是可以机械化地无脑替换，坏处是对现有代码改动很大，并且跟现有的实现逻辑紧密耦合，难以发挥 CSPP Trie 的全部优势。所以我选择了 抽象 WriteBatchWithIndex，对现有代码改动很小，把几乎所有的处理都放在 CSPP_WBWI （CSPP Trie WriteBatchWithIndex）中。
从而，在 CSPP_WBWI 中，WriteBatchWithIndex 的 rep 指针就是一个多余，但我们不管它，也就浪费一个指针（总是 null），就当它是人的阑尾。
WriteBatchWithIndex 主要有两块关键逻辑：
1.WBWIIterator
2.GetFromBatchAndDB
在 WriteBatchWithIndex 中：
1.包含多个 ColumnFamily，所以它的 Comparator 需要先区分 ColumnFamily
2.同一个 UserKey 会有多个版本，在 DB 中，多版本通过 SequenceNumber 来区分，但是在这里，还没有 Seq ，所以就通过其在内部缓存中的 offset 来区分
这样，这个 SkipList 就有一个相对比较复杂的 WriteBatchEntryComparator(github 代码)。更加雪上加霜的是:
1.要找到某个 CF中某个 key 最新的版本，需要非常复杂的操作(github 代码)！
2.插入 Index 时，必须先判断这个 key 是否存在，从而又多了一次查找
CSPP_WBWI 核心设计
在 SkipList 中要区分 ColumnFamily 和相同 key 的多个版本，同样，在 CSPP_WBWI 中，我们也要区分，但我们的设计思想跟 SkipList WBWI 完全不同：
1.区分 ColumnFamily：将 ColumnFamilyID 附加在 UserKey 前面，并编码为 BigEndian
2.区分多版本：同一个 UserKey 对应一个数组，数组中每个元素是 { OpType, Offset }，其中 offset 是指向该 KV 在 WriteBatch Buffer 中的偏移
这种设计非常简单直接，并且性能更好，除了 CSPP Trie 本身的性能优势，还有额外的好处：
1.插入 Index 时，不需要额外的查找操作来事先判断 Key 是否存在
2.要找到某个 Key 的最新版数据，只需要拿出 Key 对应的数组的最后一项即可
3.GetFromBatchAndDB 可以非常高效地实现
测试与验证
所有的优化都完成后，我们怎么保证代码的正确性呢？这里，再一次体现了“微创手术法”的优越性：因为 rocksdb 自身有非常完善完整的测试体系，我们没有改变(改变极小)代码接口，所以只需要通过这些测试，那我们代码的正确性就有了基础的保证。我们意料之中的测试诸如 Comparator 不是 Bytewise，带有 user timestamp 都失败了，只需要在 CSPP_WBWI 时跳过这些测试即可。
终极的“微创手术法”
然而有个诡异的测试失败，还是费了好大的脑力：在 WriteUnprepared 中，rocksdb 创建了一个新的 WriteBatchWithIndex，并将其与 Txn 中的 write_batch_ swap 掉，而原先 txn 中的那个 write_batch_ 对象被我改成了指针以便使用 CSPP_WBWI，这里 swap 了不同类型的对象！要处理这个问题，相关的代码修改太多了！思考再三，将之前这里修改的代码都回退掉，使用一种全新的修改方式，终极的“微创手术法”：
-WriteBatchWithIndexwrite_batch_;
+// topling spec: should use union{ptr,ref}, but ref can not be in union
+WriteBatchWithIndex*write_batch_pre_=nullptr;
+WriteBatchWithIndex&write_batch_;
把 write_batch_ 从对象变成引用，只需要修改 cons 和 destruct，并且，在原先 swap 的地方，这样修改：
+#if0
WriteBatchWithIndexwb(wpt_db_->DefaultColumnFamily()->GetComparator(),0,true,0);std::swap(wb,write_batch_);
+#else
+autoucmp=wpt_db_->DefaultColumnFamily()->GetComparator();
+autowbwi=dbimpl_->mutable_db_options_.wbwi_factory->NewWriteBatchWithIndex(ucmp,true);
+std::swap(wbwi,(&write_batch_pre_)[1]);// note trick!
+std::unique_ptr<WriteBatchWithIndex>wbwi_up(wbwi);
+auto&wb=*wbwi;
+#endif
write_batch_pre_ 的作用是用来通过 (&write_batch_pre_)[1] 来访问 write_batch_ 引用对应的指针，其实更简单直接的方式是使用 union { write_batch_(ref); write_batch_ptr_; }，但 C++ 的 union 成员不能为引用类型，所以才使用 write_batch_pre_。
理论上可以不使用这个 write_batch_pre_，而是使用 write_batch_(ref) 的前一个或后一个数据成员来定位 write_batch_(ref)，但这样做除了可读性会降低，还会跟 rocksdb 现有代码产生耦合，万一 rocksdb 在 write_batch_(ref) 之前或之后增加了新的成员，那就爆炸了！
最终，使用 write_batch_pre_ 这样的方式修改，相较于之前把 write_batch_ 改成指针，跟 rocksdb 的 code base 的 diff 要小得多，算是因祸得福吧！
结论
所有这些问题，在 CSPP_WBWI 中的处理都非常简单直接，本来 CSPP Trie 就比 SkipList 快了 8 倍，再加上执行流程的简化，简直飞起！我们测出来的 20 倍性能差距，还是在比较简单的场景下，在更复杂的场景中，CSPP_WBWI 还会更快！
使用 CSPP_WBWI，再搭配 CSPP MemTable，相比 rocksdb 的两者都使用 SkipList，性能优势不可同日而语！
2.2. Transaction Lock
当我们将 WriteBatchWithIndex 的热点消除后，原本不是热点的 Lock，成了新的热点。这里的优化，就更多是代码细节上的优化，更加“微架构”，理解起来也更简单直接：
1.使用 hash_strmap 替换 other_map，类似这样：KeyStrMap
2.Lock 调用链上 key 的类型是 std::string，应该使用 Slice，消除了拷贝
3.将 OtherMap<uint32_t, ...> 改成 VectorIndexMap，一个伪装成 Map 的 Vector，因为 uint32 的 key 都是非常小的值(0,1,2,3...)
4.这个就更是代码级的优化了，因为这个优化跟其它优化相对比较独立，我还给上游 rocksdb 提了 Pull Request
5.其它的优化，就不一一列举了
PointLockManager::UnLock 的优化：
该函数的执行逻辑是：先从 thread local 中拿到所有 key，再把这些 key 按照 stripe 分组，最后，在每个 stripe 内，仅通过一次 mutex lock/unlock，就 UnLock 该 stripe 中的所有 key，大幅减小了 mutex lock/unlock 开销。
实现细节上：原先 rocksdb 把每个 stripe 内的所有 key 放到一个 vector 中，并且这里还是通过 UnorderedMap<stripe num, vector<key> > 来实现的。这里可优化的点在于：
1.这个 UnorderedMap 没有必要存在，使用 vector<vector<key>> 即可
2.vector<key> 还能再优化吗？
在我们这里，因为 hash_strmap 中 Key Value 是通过数组实现的，所以每个 KV 都有一个整数的 Index，从而，我们就可以使用外部基于数组的链表，所以，我们的实现方式就是两个数组：
vector<uint32_t> stripe_heads(lock_map->num_stripes_, UINT32_MAX);
vector<uint32_t> keys_link(max_key_idx, valvec_no_init());
把 Key 对应的 Index，按照 stripe，使用基于数组 Index 的链表链接起来，这大大简化了操作，并且降低了内存用量，以及内存申请次数！
3. 性能测试
我们每次跑性能测试，都会查看火焰图，所有的热点，都是在火焰图中观察到的，做了这些优化之后，从火焰图中观察，引擎前台线程的开销降到了 40%，引擎的后台线程因为只剩下 Flush 和 L0->L1 的 Compact，也只有 13% 左右，其余都是 mysql 本身的开销了。所以，我们能在 6 年前的 E5-2682 v4 上，实际使用不到 30 个 CPU核心，把 sysbench 跑出每秒 70万行，538MB 的写入！
在公有云上，我们也会很快推出 MyTopling 的内测版，届时欢迎大家亲身体验！我们的官网是 topling.cn
