CMU15445(2023fall) Project #4 - Concurrency Control踩坑历程

把树木磨成月亮最亮时的样子，

就能让它更快地滚下山坡，

有时会比骑马还快。

完整代码见：

SnowLegend-star/CMU15445-2023fall: Having Conquered the Loftiest Peak, We Stand But a Step Away from Victory in This Stage. With unwavering determination, we press onward, for destiny favors those brave enough to forge ahead, cutting through the thorns and overcoming every obstacle that dares to stand in their way.

目录

Task #1 - Timestamps

1.1 Timestamp Allocation

1.2 Watermark

Task #2 - Storage Format and Sequential Scan

2.1 Tuple Reconstruction

2.2 Sequential Scan / Tuple Retrieval

Task #3 - MVCC Executors

3.1 Insert Executor

3.2 Commit

3.3 Update and Delete Executor

3.4 Stop-the-world Garbage Collection

---

Task #1 - Timestamps

1.1 Timestamp Allocation

        建议上来把UndoLog、Transaction、Transaction_Manager这几个类粗略分析一遍，对lab04的基础框架有个大致的了解。第一个小task实现起来一共也没几行代码，正所谓授人以鱼不如授人以渔，关键是理解read_ts和write_ts到底是怎么来的。

        重点看下面这两段话：

1. 当一个事务开始时，它会被分配一个读时间戳，即最新已提交事务的提交时间戳。事务提交时，它会被分配一个单调递增的提交时间戳。其实这里说“提交时间戳”我个人认为是带有歧义的，用“时间戳”更为准确。但是由于“时间戳”只能是由“commit”带来增长，普通的read操作并不会导致时间戳的移动，所以这里才用“提交时间戳”。
2. 提交时间戳是事务提交的时间。它是一个逻辑计数器，每当事务提交时，提交时间戳都会增加 1。

        而read_ts是从1开始计数，那commit_ts就是从2开始计数了。一次只能有一个txn成功提交。在UndoLog的ts_字段中，指的就是这个undolog被提交的时间。我们在访问某个tuple的版本链时，就是用当前txn的read_ts和undolog的ts进行比较，当然这是后话。

1.2 Watermark

        核心就是一句话“Watermark is the lowest read timestamp among all in-progress transactions”，至于为啥需要watermark呢？答案在task 3.4的垃圾回收部分——对于那些ts_小于watermark的undolog，我们可以直接删除来节省空间，因为没有txn可以再访问这些过于老旧的undolog。

Watermark的执行流程如下：        

1. 当出现一个新的txn时，自动调用AddTxn来记录当前所有运行中的txn的read_ts。显然，AddTxn这个操作并不会改变watermark_的值，因为无论是read还是write都是在一条线性增加的时间线上顺序运行的。
2. 某个txn执行结束后，自动调用RemoveTxn来删除这个txn。但是，这个操作有可能改变watermark_的值！试想如果当前txn的read_ts是现存最小的，其他存在的read_ts都比它大，那删除这个txn后就需要寻找新的最小read_ts(即更新watermark_)了。

        实验说明还提到我们需要在O(log N)的时间复杂度上完成watermark的计算操作，这就间接提醒我们用某种堆来实现了。我这里采用的事优先队列，具体实现细节可以自己想想，给人一种刷LeetCode的感觉嘻嘻。

Task #2 - Storage Format and Sequential Scan

        到task2部分就嘻嘻不了了，首先摆在我们面前的难题是理清Undolog、UndoLink、VersionUndoLink和PageVersionInfo之间的区别。老规矩，是时候展示我的匠心图例了。

        PageVersionInfo是最为宏观的存在，每个page都会对应一份PageVersionInfo。version_info_我觉得是十分精妙的，利用了每个page_id的唯一性(由Project 02的bufferpool分配)，越过table_heap直接管理每个page的版本链信息。

        要访问某个tuple，首先就要定位这个tuple所在的page，之后我们就可以对tuple进行需要的操作了。VersionUndoLink应运而生，它作为版本链的头结点，直接指向真正的表头元素。UndoLink就是版本链的每个节点了，更准确地说就像链表节点的next部分，这里我感觉用UndoLinkNode会更加恰如其分，这个可恶的“UndoLink”最开始很容易看作为一条链表而不是一个节点。

        那UndoLog又是什么呢？同理，我认为这里叫UndoLogNode会更为恰当。每个对tuple进行操作的txn都会有一份undologs。而UndoLog其实也是有学问的，task3就是和这个问题作斗争。比如图中的TxnY，它的undologs就有两个元素，因为它更改了tuple A和tuple C两个元素。

        UndoLink和UndoLog在我看来更像是共生关系。因为UndoLink自己是没有实际的内容的，它只能指向真正有内容的UndoLog，这么看来UndoLog就相当于链表节点的value部分。每个UndoLog内部会包含指向下一个版本链节点的UndoLink，以此类推。

        至于版本链的尾节点也就是最后一个有效UndoLog包含的UndoLink，这个“next”指向一个无效的内容。用那张图上的内容来说，A1、B1等元素只是版本链最后一个有效的UndoLog，它们包含的UndoLink会指向一个空的内容，如下图。

        顺便一提，tuple的版本链顺序是从新版本指向旧的版本，就像这种图例一样。

2.1 Tuple Reconstruction

        从这里可以看出，bustub的Version Storage选择的是“Delta Storage”，我们需要根据update操作使用的partial tuple来构造出一个完整的tuple返回。实验说明给出的这张图是重中之重。

        我们需要根据表模式和已修改字段构造元组的部分模式，然后逐渐将这个partial tuple凑成完整的tuple。在# Vn+1版本的UndoLog中未进行修改的字段由# Vn版本UndoLog中修改的字段进行补足，若还是无法形成一个完整的tuple，继续遍历版本链。如果遍历完版本链还是无法形成tuple，就用base_tuple来补全剩余字段。一言蔽之，就是某个tuple[A*, B*, C*]的每个value都应该是最新的值。

总结一下可以分为三步走

1. 获得undoLog的schema，也就是undoLog中partial tuple的schema类型
2. 用base schema和partial schema进行比对，从而用undoLog中的partial tuple来修改原始的base tuple。
3. 一步步形成完整的tuple(可能需要借助版本链和base tuple)

2.2 Sequential Scan / Tuple Retrieval

这个task是让我们修改Project 03里面的SeqScan来支持MVCC，还是先回顾如何遍历table：

1. 利用table_heap提供的iter遍历表中的tuple
2. 用tuple的rid来获得它的VersionUndoLink，也就是版本链的头结点
3. 利用版本链和base tuple拼凑出完整的tuple，即调用reconstruction()
4. 利用filter_expr来判断tuple是否符合过滤条件

        OK，把最重要的框架搭建出来了以后，我们可以着手其中细节。需要注意的一点是区分tuple的ts状态——是正在被某个txn修改，还是已经被提交了呢？在执行MVCC版的SeqScan过程中，有三种情况需要我们特别注意：

1. Table heap中的元组是最新的数据，并且这个数据已经提交了，当前txn的read_ts>tuple.ts可以直接读取
2. 表堆中的元组包含当前事务的修改，即当前tuple的ts是一个很大的数字，而且恰好等于当前访问txn的id号，也可以直接访问
3. 表堆中的元组 (1) 被其他未提交事务修改，或 (2) 时间戳比事务的读时间戳更新。在这种情况下，我们需要遍历版本链

如果还是没有完全理解SeqScan的具体工作，可以从分析ScanTest入手，我当时就是这么干的。这里我放几张当时分析的图：

再贴上对应的debug过程

 

Tuple1的首链，它的prev_txn_id是5，对应txn_store3，正好是prev_log_2这个。

这里可以看到log的操作为Del。 

可以发现这个txn_store_2确实是有两个操作

Task #3 - MVCC Executors

3.1 Insert Executor

        Insert部分的逻辑还是比较简单的，对我们在Project 03中实现的代码稍加改进就可以通过测试了。老规矩，先总结出Insert的大体框架：

1. 创建新的tuple并设置meta，注意这里的ts应该设置为临时事务时间戳
2. 调用InsertTuple()插入到table heap中
3. 设置txn对应的write_set，在commit阶段一起提交所有的修改元组rid

        其他细枝末节和以前的是一样的，还有一点需要注意：到底要不要在Insert阶段生成一条UndoLog呢？我个人认为是需要的，别的不说，单从UndoLogs的可读性来讲为Insert操作生成UndoLog就是必要的，但是根据lab的测试点来说并不推荐这种做法。But，我认为咱们都是抱着学习而不是功利地通过测试点的态度来完成lab的，所以这里我坚持自己的做法——为每个完成的Insert操作生成一条UndoLog，作为版本链的起始节点。当然要是想修改也不是很麻烦，这就仁者见仁智者见智了。

3.2 Commit

Commit部分实在是过于友好，实验说明部分直接把大致框架帮我们罗列出来了：

1. 获取提交锁（commit mutex）。
2. 获取提交时间戳（但不要增加 last-committed timestamp，因为直到提交完成，提交时间戳的内容才会稳定）。
3. 遍历所有由此事务修改的元组（使用写集），将base tuple的时间戳设置为提交时间戳。你需要在所有修改执行器（插入、更新、删除）中维护写集。
4. 将事务设置为已提交状态，并更新事务的提交时间戳。
5. 更新 last_committed_ts。

在这里值得我们思考的问题是：为什么每个txn的write_set_需要table_oid呢？换个问法可能会更直观，我们怎么通过rid找到对应的tuple呢？

  std::unordered_map<table_oid_t, std::unordered_set<RID>> write_set_;

我的想法是：Catalog利用table_id找到对应的table info，接下来利用table info得到这个表的table heap。得到了table heap我们就可以根据写集中的rid找到对应的tuple了。

如果要为Insert生成UndoLog，在commit阶段生成比较好。在Insert executor中生成也行，不过最后还是需要在commit阶段修改这个UndoLog。

3.3 Update and Delete Executor

Update executor需要讨论的情况就比较多了，看实验说明那一大堆基本都是在说update的各种情况。先来过一遍实验说明的重点部分：

在检查完写写冲突后，你可以继续实现更新/删除逻辑。

1. 为修改生成 undo 日志。对于删除操作，生成包含原始元组完整数据的 undo 日志。对于更新操作，生成仅包含修改列的 undo 日志。将 undo 日志存储在当前事务中。如果当前事务已经修改过该元组并且有 undo 日志，它应当更新现有的 undo 日志，而不是创建新的。#没有就创建新的，有就直接append。
2. 更新元组的下一个版本链接，指向新的 undo 日志。
3. 更新表堆中的基础元组及其元数据。

        实验说明有一句话是核心：“检测写写冲突的唯一条件是检查基础元组元数据的时间戳”。从这句话可以看出每个txn是可以看到正在被处理(包括update和delete)的元组的ts的，只是它们此时就不具备修改这个正在更新的tuple的权限。

        这个task最核心的工作是总结修改操作会发生write-write conflict几种情况，大致可以分为以下几种：

1. 保证修改操作的原子性。Tuple1正在被txn1修改(包括update和delete)，即tuple1的ts_=txn1。此时如果其他txn想要修改tuple1就会出现写冲突，但是如果别的txn拥有的read_ts足够大是可以看到这个正在被修改的tuple1的。
2. 不可重复修改。Tuple1已经被txn1删除并且提交了，假设此时tuple1的ts_=5。Txn2的read_ts=4，则txn2只能读到旧版本的tuple1。假设txn2对这个旧版本的tuple1进行修改，那就会出现重复修改的写写冲突。

除了写冲突外，还有些特殊情况需要进行讨论。

1. 假如txn1进行insert操作(insert tuple1 with [1, 1, 1])，在这个insert操作还没提交的情况下，所有基于insert操作的后续update/delete都不应该生成新的undolog。
2. 假如tuple1的内容为[1, 1, 1]，txn1进行update tuple1 with [1, _, _]到底算不算update呢？从我个人的角度来看是不算的，但是测试点上却把这算作了一条update，这点我是不认可的。因为比较是否更新是用Value::CompareExactlyEquals判断新插入的value和旧value是否相等，这里显然不符合update的条件。
3. 假如tuple1的内容为[1, 1, 1]，txn1进行update tuple1 with [2, _, _]，但是没有提交。过了一会儿txn1又进行update tuple1 with [_, 3, _]，此时tuple1临时变为[2, 3, 1]，相应的修改位也就是[T, T, F]。而不仅仅是基于第二次update的[F, T, F]。

        理清上面几种情况之后，就可以着手完成代码了，顺带一提Delete Executor实现起来要比Update Executor简单得多。最后还有两个问题需要理清楚

Q：update的步骤

A：可以像以前一样删除旧的tuple再插入新的tuple吗？不可以，用UpdateTupleInPlace

就地更新。

Q：将删除的tuple的ts置为0有问题吗

A：没什么问题。因因为如果txn是在正常提交的话，那commit必然会大于0.

接下来分享我在实现时遇到的问题

①在修改tuple的meta时只修改了临时变量，没有真正修改tuple。属于是掩耳盗铃了。

②实验说明里面提到

搞得我还真以为是在某处代码中将时间戳设置为0，结果检查半天发现是我自己设置的

③注意：commit时一定要分清楚修改base tuple和修改对应版本链的区别，两者都需要修改。

④不能重复修改已经删除的tuple，就像下面这样

⑤在这种情况中，如果一个insert操作还没有提交，那基于这个insert操作的所有操作(update和delete)都不应该生成undolog。

⑥UpdateTest2中，如果一个update没有提交，那这个txn的后续update或者del都不用生成新的undolog。要注意后续的更改都是要基于base tuple，而不是基于前一个修改的tuple。

⑦UpdateConflict。这里出现的错误是txn3修改的时间小于tuple2提交的时间。

        更具体一点，txn3的read_ts=1，所以它只能看到tuple0的版本0，实际上tuple0的版本1也完成了提交。此时txn3试图更改tuple0在版本0的内容，这就会造成另一种写冲突。因为txn3如果成功更改了版本0，那它就会生成tuple0新的版本1，这样自然就和tuple0已有的版本1发生冲突，违背了可重复读的原则。也就是我之前提到的。

3.4 Stop-the-world Garbage Collection

        这个task还是比较简单的，简单过一遍实验说明就可以了。

你需要遍历表堆和版本链，识别仍然可以被任何正在进行的事务访问的 undo 日志。如果一个事务已经提交或中止，并且其不包含任何可以被正在进行的事务访问的 undo 日志，你可以简单地将其从事务映射中移除。

        需要注意的是， 不需要更新前一个 undo 日志来修改悬挂指针并使其成为无效指针，将其保留在那里是可以的。也就是说如果应该txn的所有undologs都过于老旧，对其他的txb都不可见，那就删除这个txn，不用手动释放它的undolog。