企业官网建设流程全解析

一.时间戳

事件戳分为两个，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

每个元组都会维护一个undolog，undolog可以理解为一个链表，有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.该元组的临时时间戳为自身事物的未提交，即直接查看自身即可

// 返回一个空的vector

sqlscan即在原sql的基础上引入txn和txnmgx，找到能看到的版本，没有则continue，整体难度不大。

这里，cmu建议同时实现TxnMgrDbg，方便之后debug。

Txn函数更像是scansql 和 collectundolog的结合体，通过拿到iter去一路遍历表堆，每个tuple打印出undolog。

这个调试函数不要求实现，但是反而有点难实现，至少格式一样挺难实现。这里笔者想了下思路直接用ai了，笔者认为主要理解debug函数给出的各个参数的意义即可。

三.Task #3 - MVCC Executors

Wirte_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.insert

b.update

c.delete

对于a，我们只需创建一个空undolog（指，tuple为空，is_delete为true），因为在此之前并不存在该tuple。

对于b，我们需要对比basetuple 和 targettuple,不一样的地方进行标记，同时创建一个新的tuple记录修改即可。

对于c，is_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_ts

b.元组被一个尚未提交的事务修改过了，即判定为ts >= TXN_START_ID

只要满足上述任意一个就判定为写写冲突。

解决完写写冲突后，就可以着手于修改两个函数。

Delete:

整体框架不需要改，内部大概分为第一次和第n次修改；这么分的依据主要是undolink。undolink在一个tuple被insert时赋值为无效值，也就是说，一个未被修改过的tuple的undolink默认是无效值。当第一次被修改后才被赋值指向一个undolog。

故，第一次需要修改undolink，剩余修改无需修改undolink，只需要更换undolog即可。最后注意AppendWriteSet。

update本质相同，一个目标为nullptr（delete） ，一个目标为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.1

445官方给出了大概流程：

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.2index，delete

其实都差不多，但是做第一个时可能有点难，理解不太深入的话耗时还是有点长的。

本质都是去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。

感谢阅读。笔者只是个菜鸡，笔记不可避免会有错误，见谅。