bustub-private 性能优化

寒假的时候做了 15445 几个 projects 基础的功能，最近比较闲，优化一下性能玩玩...

Project #1 - Buffer Pool Manager

异步读写磁盘

因为最开始的做法是给在每个函数前面加上 std::scoped_lock lock(*bpm_latch_); 来支持并发。因为缺页或者写回脏页的时候涉及读写磁盘，显然是一个瓶颈，所以读写之前先拿到单个 frame 的锁，然后释放 bpm_latch_ 再到 disk_scheduler 推送读写任务。

但是我发现这样做在 latency=0 的时候，也就是非连续读没有惩罚的时候，确实提升很大。但是 latency=1 时还不如之前，暂时还没搞清楚原因，看了半天火焰图也没看出什么门道。 折磨了一天，才发现 DiskScheduler 还是单线程获取任务，一开始这么写是因为 DiskManager 读写的时候直接上了一把大锁，而我又不能改那部分代码。实际上 DiskScheduler 之间获取，释放锁的开销还是很大的，之前并发率低刚好减少了拿锁的竞争，所以写了一个多队列的线程池就解决了这个问题...

LRU-K

~~ 看火焰图的时候发现 lru-k 的效率其实挺低的，因为我的 lru 是 set 实现的不是双向链表...
之所以这样做是因为 pin 住的 frame 无论如何都不能删除，unpin 的时候如果用链表就只能从头遍历去找合适的位置插入。
不过实际上 lru-k 的 size 也就 16，bpm size 是 64, 所以遍历一遍的开销应该还好，因为理论上，驱逐的情况应该也不多。~~

实际上因为 lru-k 是根据最近的前 k 次使用时间，所以每次记录都可能要移动到非队首的地方，应该还是用 set 排序更好。

并且用 set 按权值排序还很容易实现按照 AccessType 来调整优先级，比如说 AccessType::Scan 应该被容易被驱逐，因为大概率不会回头再用到，加上这个优化 QPS 就从 10000 多变成了 35177.18399，减少了缓存污染。

Project #2 - B+Tree

这里我先把之前搞的幽默读锁来实现螃蟹锁删了。如果能实现读锁原地转换成写锁，应该是很有用的优化。但是我现在的实现是要保证祖先上一定有一个节点是写锁，这个 “优化” 除了增加锁的竞争和开销没什么用... 删除之后 QPS 大幅提升

奇怪的是我正确实现了螃蟹锁，contention ration 的测试比率 (多线程运行时间 / 单线程运行时间) 还是 1 左右，官网说大多正常是 [2.5, 3.5] 也就是说我的锁竞争并不激烈，不知道是好还是坏...

b+ tree 还有墓碑机制之类的优化，之后写了再更新吧,,,

Project #4 - Concurrency Control

记录一下修了很久的 bug...

写了 TranscationManager::Abort 之后，IndexConcurrentUpdateAbortTest 的时候要不就是事务 abort 率太高，要不就是数据一致性有问题... 用 gdb 点点点无效 debug 半天之后，终于想起了之前写的 helper function TxnMgrDbg，找到了问题，感觉多线程 debug 果然还是得打印调试...

先给 TxnMgrDbg 整个函数加锁，方便查看，日志保存到文件。

随便找一个 Abort 的 txn，看起来挺正常的

debug_hook: BEFORE abort txn: 10 table_oid: 1 rid::slot_num : 4
RID2/4 ts=txn10 tuple=(4, 1)
  txn10@0 (4, 0) ts=4

debug_hook: AFTER abort txn: 10 table_oid: 1 rid::slot_num : 4
RID2/4 ts=4 tuple=(4, 0)

翻到比较大的 txn，发现 txn700+ 时， RID2/4 的 tuple 还是一个未提交的事务 txn20 写的？

debug_hook: txn: 780 read_ts: 180
RID2/4 ts=txn20 tuple=(4, 0)

但是找到 txn20，发现早就 abort 了啊，但是显然这里的 Revert 不太对

debug_hook: BEFORE abort txn: 20 table_oid: 1 rid::slot_num : 4
RID2/4 ts=txn20 tuple=(4, 1)
  txn20@0 (4, 0) ts=4

!! txn 29  insert:  4
txn 29  can't insert:  3

debug_hook: AFTER abort txn: 20 table_oid: 1 rid::slot_num : 4
RID2/4 ts=txn29 tuple=(4, 1)
  txn29@0 (4, 0) ts=4611686018427387924

debug_hook: AFTER abort txn: 29 table_oid: 1 rid::slot_num : 4
RID2/4 ts=txn20 tuple=(4, 0)

推测这里应该是 txn20 revert RID2/4 之后，txn29 就插入了一个新 tuple。这里插入本身没什么问题，但是 txn29@0 (4, 0) ts=4611686018427387924 是错误的，这里 ts ^ (1ll<<62) 是 20，为什么 txn29 的 undolog 的 ts 是 txn20？正常应该是 txn10@0 (4, 0) ts=4 才对。

插入的时候用到了我自己写的 execution_common::Modify(const Schema *schema, const TableInfo *table_info, RID rid, const TupleMeta &tuple_meta,const Tuple *new_tuple, const Tuple *child_tuple, TableHeap *table_heap, TransactionManager *txn_mgr,Transaction *txn)，看看是不是这里有问题。

构造 undo_log 的部分:

auto log = GenerateNewUndoLog(schema, child_tuple, new_tuple, tuple_meta.ts_, *undo_link);
undo_link = txn->AppendUndoLog(log);

也就是说 tuple_meta.ts_ 不对，而 tuple_meta 是函数的参数，由调用者提供。

看到这里，我想到了一种可能的情况： 1. txn20 Abort 之后，还没有来得及 revert RID2/4

2. txn29 拿到旧的 tuple, 传给 Modify, 此时 tuple_meta.ts 是 4611686018427387924

3. 正常来说，txn29 插入新的 tuple 到 RID2/4 会发生 Write-Write conflict 而被中止。但是如果在实际插入前，txn20 revert 了 RID2/4, 此时的 cur_tuple_meta.ts 是 4。在插入的时候发现 new_tuple_meta.ts <= txn->GetReadTs() 于是可以写入

4. 于是成功插入入的新的 tuple 但是 undolog 的 ts 是函数被调用前的，也就是 txn20

于是发生了 TOCTTOU 问题，函数调用和实际插入之间的时间 RID2/4 的页面锁被释放了，出现了幽灵读的问题。解决方法也很简单，check Write-Write conflict 的时候，额外检查函数参数的 tuple_meta 和 cur_tuple_meta 是否一致就可以。不需要检查两次的 tuple 是否一致，因为如果 tuple_meta 一致就已经说明没有其他线程修改过该 RID 的 tuple，而单线程不需要考虑并发安全。