一.时间戳事件戳分为两个read_ts 和 commit_ts当事务开始时会被分配一个读事件戳且这个读时间戳等于维护的 last_commit_ts。读时间戳决定了该事务可以正确且安全的读取哪些数据也就是说不同事务看到的当前版本是不同的。当事务提交时会被分配到一个提交时间戳提交时间戳决定事务的序列化/串行化的顺序。watermark也就是水印是当前所有活跃事务没提交且未终止的最小读时间戳。在watermark之前的所有事务都算作不活跃可以删除节省空间。1.1timestamp allocation最简单的一集啊xdm只要设置几个时间戳就行1.2 watermark实现两个函数一个插入事件一个删除事件这里很坑的一点是test中txn_n 1000000若在remove中仅采用给出的哈希表去暴力找寻最小的read_ts时间上是接受不了的。所以这里笔者的思路是去再维护一个map底层红黑树能直接返回最小值去代替暴力查找后来查阅相关资料的时候接触到了懒删除。懒删除和map其实思路差不多都是把查找最小值优化到O(1),但是map删除一个元素的时间是O(logn),而懒删除指不进行删除操作仅在getwatermark函数时进行删除但是笔者目前没有看到getwatermark的位置暂时还是用map吧有机会再回来优化。二.Storage Format and Sequential Scan这里涉及到undolog每个元组都会维护一个undologundolog可以理解为一个链表有next指针指向上一次修改。undolog仅仅存放修改痕迹也就是说我们无法用完整的schema去读取undolog中的修改需要重新用copy去新建一个特别的schema去读取。Undolog 如何维护是笔者开始很疑惑的一点。整体来讲一个元组能被多个事务不同时间修改每个事务独立维护本地undo_logs_当前Tuple仅仅维护一个undolink去指向最后一次更新。一个undolog通过undolink指向下一个undolog。笔者最初很疑惑为什么不直接维护一个vector去记录undolog这与空间和后续职责有关。vector在高并发下会无限膨胀超出单页容量不过这个不是主要。当一个事务出错需要回滚时需要撤回所有当前事务造成的影响那么如果在事务中独立记录undolog会使回滚更好操作方便高效以及后续实现垃圾回收时更加高效。2.1.Tuple Reconstruction这个小任务需要我们实现reconstruction函数用来读取当前元组的最早版本这个函数大概是需要在某个涉及read_ts的函数调用因此上层函数传递下来的undolog直到结束都一定符合要求。当undolog 为空时证明上层函数认为没有符合要求的更早版本直接返回当前元组即可这里需要注意对is_deleted的判断2.2 sql scan需要实现CollectUndoLogs 和 sqlscan的改写。Collectundologs 函数实现查找时间小于read_ts的最后版本并收集之后所有版本。分三类讨论// 2.有人抢跑分为两个可能// 2.1 一个还未提交的事物修改了这个元组// 2.2 一个已提交的事物修改过这个元组但是提交时间早于read_ts//直接沿着版本链回退直到结束或者找不到 read_ts的版本再返回// 3.当前元组最新提交时间戳小于我的read_ts直接读取// 1.该元组的临时时间戳为自身事物的未提交即直接查看自身即可// 返回一个空的vectorsqlscan即在原sql的基础上引入txn和txnmgx找到能看到的版本没有则continue整体难度不大。这里cmu建议同时实现TxnMgrDbg方便之后debug。Txn函数更像是scansql 和 collectundolog的结合体通过拿到iter去一路遍历表堆每个tuple打印出undolog。这个调试函数不要求实现但是反而有点难实现至少格式一样挺难实现。这里笔者想了下思路直接用ai了笔者认为主要理解debug函数给出的各个参数的意义即可。三.Task #3 - MVCC ExecutorsWirte_set 是Transaction下的表属于单个事务作用是管理当前修改的写集合后续回滚提交等都需要用到。一个事务对于一个RID也就是一个元组最多有且只有一个undolog第一次修改时新建undolog后续所有修改都会在该undolog上进行维护。事务不需要记录中间态。3.1insert函数insert是原子的具体体现在必须调用的InsertTuple函数中因此无需考虑并发竞争。这一步需要赋予插入数据一个临时时间戳并将修改痕迹加入writeset中。由于在插入前没有该tuple存在所以不存在undolink指向上一个版本故应该不需要维护undolink。3.2commit函数commit函数很好实现函数本身提供了mutex并上了锁在这一步需要做的是将临时时间戳改变为commit_ts,并改变last_commit_ts_。3.3Generate Undo Log函数这一步需要实现两个函数主要为了下文的delete和update算子做铺垫。当delete或update改变元组时创建或者改变当前事务的undolog来记录版本。3.3.1generatenewundolog函数这一步是该事务第一次对这个元组修改时调用。该函数主要目的是建立一个undolog记录第一次修改笔者思路如下函数传入base_tuple, const Tuple *target_tuple等参数。15445官方给出了提示需要考虑三种情况a.insertb.updatec.delete对于a我们只需创建一个空undolog指tuple为空is_delete为true因为在此之前并不存在该tuple。对于b我们需要对比basetuple 和 targettuple,不一样的地方进行标记同时创建一个新的tuple记录修改即可。对于cis_delete设置为false并将所有列置为true(全部删除等于全部修改)。同时undolog中的tuple设置为basetuple。3.3.2generateupdateundolog这一步怎么说呢和上一个函数思路很像不同的是这个函数相当于在一个undolog的基础上做并集。笔者的思路是将一个新的undolog初始化为当前undolog遍历当前tuple和basetuple找到修改列加入新undolog中。最后遍历新undolog记录的修改列若当前undolog也修改过当前列则返回当前undolog记录的列值否则返回basetuple记录的列值。有点绕但是我们的目的是存储版本痕迹所以undolog存储的应该是 修改部分 未修改前的数据。所以新undolog和undolog都记录修改过一列时应该去undolog取该列的最初值。3.4Update Delete Executor这一步445官方建议我们实现写写冲突的函数。判定可以分为下面几个a.元组已经被其他的事务修改且提交即判定为ts read_tsb.元组被一个尚未提交的事务修改过了即判定为ts TXN_START_ID只要满足上述任意一个就判定为写写冲突。解决完写写冲突后就可以着手于修改两个函数。Delete:整体框架不需要改内部大概分为第一次和第n次修改这么分的依据主要是undolink。undolink在一个tuple被insert时赋值为无效值也就是说一个未被修改过的tuple的undolink默认是无效值。当第一次被修改后才被赋值指向一个undolog。故第一次需要修改undolink剩余修改无需修改undolink只需要更换undolog即可。最后注意AppendWriteSet。update本质相同一个目标为nullptrdelete 一个目标为newtuple。3.5 Stop-the-world Garbage Collection垃圾回收需要回收所有不需要的undolog版本这里指当前所有活跃的事务都不会用到这个版本故需要用到watermark来判断是否仍有需求。这里笔者的思路是通过version_info_去遍历所有页的prev_link_通过prev_link_去取得对应的槽位偏移量以及对应的undolink。取出上一个undolink的时间点与watermark对比若满足则标记保留该undolink最后一次遍历清除。这里要注意为什么是取前一个undolink的时间点。比如最新 - 次新 - a -b只有上一个undolink的时间点大于watermark才能保证当前undolog需要被使用那么最新没有前一个undolog那么我们取TXN_START_ID保证大于watermark也就是保证最新undolog可用。再不断赋值pre_ts遍历查找最后一个需要使用的undolog。四4.1445官方给出了大概流程a.先检查索引中是否已经存在该元组对应的键。如果已经存在则终止当前事务b.在表堆上创建元组打上临时事务时间戳。c.将该元组插入索引。当唯一键约束被违反时索引接口应当返回 false。When the primary key is specified in a CREATE TABLE statement, BusTub will automatically create an index with its is_primary_key property set to true.由此可以看出可以通过遍历判断is_primary_key来进行第一轮筛选选出主键进行判断。接着对主键判断若指向一个元组则违反唯一性直接终止若没有更新undolog后再次判断。4.2indexdelete其实都差不多但是做第一个时可能有点难理解不太深入的话耗时还是有点长的。本质都是去undolog中修改或查找将p3中直接删除的做法更换成依据undolog来修改。Is_delete需要检验。4.3update这里涉及到主键的修改。从4.2开始索引append-only只增不删。并且一个key永远只对应一个tuple若原地修改主键那么会导致新的主键无法索引旧主键索引仍指向该tuple。因此应该先删除旧元组再添加新主键对应的新元组进入。此过程一定是统一的比如统一删除旧元组再统一加入否则可能会错误触发写写冲突。这里删除指的是对is_delete的更改。至此100分结束。总结一下难度吧P1肯定是最简单的P2在我做的时候认为很难现在想想应该是太多重复逻辑代码重复逻辑梳理好思路应该是略小于p3的。P3我认为反而是最难的一个任务。P3中有太多代码要去阅读了阅读量大到我都不想看代码了。同时看完又忘忘了又看。P4其实整一个任务都在围绕着undolog来进行难点在于最后的一个update有点绕。但是update的逻辑基本上都可以由delete和insert拼接来所以整体上只要对undolog逻辑梳理好问题不大。整体上笔者认为应该是p1 p2 p4 p3。感谢阅读。笔者只是个菜鸡笔记不可避免会有错误见谅。