2# Lab 5.1 事务基础功能

1 本KV引擎的MVCC和事务设计

通过事前的MVCC运行机制的分析可知, 在可重复读级别下, 我们需要记录这个事务开始的时间, 其实只需要记录这个事务的id就可以了, 因为我们可以设计一个事务管理器, 使得事务开始的时间严格按照事务id排序.

另一方面, 如果是读已提交, 我们需要按理说需要记录每个读操作的时间, 但是实际上, 我们的KV存储引擎是追加写入的, 我们本身读取的相同key就是按照最近时间读取的, 不需要额外记录本次操作的时间戳。换句话说，假设你遍历整个存储引擎的键值对，其都是按照插入时间从近到久排序的。

故我们首先需要在键值对中记录事务id，你应该在之前的Lab中已经实现了, 只是那是你不知道其具体的含义:

trac_id

同时, 你现在应该也明白了我们为什么需要在每个SST中记录事务id的范围, 这样我们才能在查找指定事务的记录时能够通过SST的元数据快速定位到对应的SST文件：

MemTable-SST

2 代码修改

现在，我们需要对之前的Lab中涉及到事务操作的函数进行修改, 其实也就是参数列表中包含了tranc_id或者max_tranc_id的函数进行逻辑补全。

本章你需要修改的代码文件：

之前Lab中所有涉及tranc_id的函数

注意, 如果tranc_id == 0, 表示当前操作没有开启事务功能, 你的执行逻辑相当于事务不存在

2.1 SkipList 部分修改

2.1.1 put

之前的Skiplist中, 你的实现思路可能是这样的:

定位到指定位置
判断是否需要插入
1. key不存在则插入
2. key存在则更新

现在而言, 以上的逻辑就错误了, 因为之前旧的键值对的记录也需要保留, 其可能会被比当前事务id更小的事务使用, 因此这里就不能进行原位更新了, 而是应该插入一个新的键值对, 同时保留旧的键值对。

你可以查看 SkiplistNode 的比较运算符重载函数, 看看为什么如此设计

2.1.2 remove

由于LSM Tree中的remove就是将插入一个value为空的键值对进行标记, 因此这里的修改逻辑和put类似, 不再赘述。

2.1.3 get

加入事务属性后, get函数需要判断查询数据的可见性(也就是实现事务属性中的隔离性), 传入的tranc_id参数表示当前操作所属的事务的id, 因此查询的数据不能是比当前id更大的事务创建的, 如果找到了这样的数据, 你需要进行滤除或跳过。

新的查询逻辑步骤为：查询时, 我们需要指定一个事务id, 通过id判断如何启用mvcc机制, 目前我们实现的隔离级别只有(读未提交, 读已提交, 可重复读)

若为0表示我们的事务隔离级别是读未提交或读已提交(因为直接查询最新的记录即可, 不需要判断失误id是否合法)
若指定的事务id, 并指定了事务的隔离级别为可重复读, 则需要判断id是否合法, 若不合法, 则返回nullptr

本项目只在commit后才将事务更改的键值对加入数据库, 否则只会暂存, 因此读已提交不需要判断事务id

2.1.4 iters_monotony_predicate && begin_preffix && end_preffix

其实这些范围查询等函数也需要进行修改, 但这不是必须的, 因为范围查询函数被上部组件MemTable包裹, 你可以选择在上层组件中统一实现事务id的滤除逻辑。因此这里的更改你可以选择性实现。

2.2 MemTable 部分修改

2.2.1 iters_preffix && iters_monotony_predicate

MemTable部分对范围查询是内存部分的最顶级组件了, 在上层就是整个LSM Tree的控制结构LSMEngine了, 因此推荐你在此处根据事务可见性原则对键值对进行滤除。

不过这里也有另一个方案, 我们的返回值类型是std::optional<std::pair<HeapIterator, HeapIterator>>, 因此你也可以在HeapIterator中实现类似的根据事务id的滤除逻辑, 这样上层组件就不需要额外处理了。如果你选择用这种方式的话, HeapIterator的运算符重载、之前标记的skip_by_tranc_id函数都需要更改。

HeapIterator中的更新是强烈推荐你实现的, 因为这个去重+排序的组件你可能会在其他地方进行复用, 因此实现其功能的完善有助于简化复用过程中的数据处理

2.2.2 其余接口

其余接口基本上是对底层Skiplist的封装, 因此你只要更新了Skiplist的接口, MemTable的接口则只需要做简单的参数传递, 不需要额外的更新。

2.3 Block 部分修改

2.3.1 add_entry

之前的src/block/block.cpp中的Block::add_entry函数需要写入tranc_id, 当然你大概率已经写入了, 虽然你当时不知道这个tranc_id具体是干嘛的, 如果你之前已经完成了tranc_id的编码, 请跳过这一部分。

除了Block之外, SST的文件编码部分应该只是调用Block的接口, 因此你只需要修改Block

2.3.2 adjust_idx_by_tranc_id

这是之前Lab中标记的一个遗留函数:

int Block::adjust_idx_by_tranc_id(size_t idx, uint64_t tranc_id) {
  // TODO Lab5.1 找到最接近 tranc_id 的键值对的索引位置
  return -1;
}

这里说明下这个函数的作用:

你进行查询定位时发现idx位置的key是你的目标
但idx位置的tranc_id并不愉参数匹配

因此你需要调用adjust_idx_by_tranc_id函数, 找到最接近tranc_id的键值对索引位置。当然, 这里的最接近不能大于指定的事务id。这个辅助函数有助于你实现新的get_idx_binary函数。

2.3.3 get_idx_binary

get_idx_binary函数用于二分查找定位key在Block中的索引位置, 你需要修改这个函数, 使其能够支持tranc_id的滤除。(可以借助刚刚实现的adjust_idx_by_tranc_id函数)

2.3.4 get_monotony_predicate_iters && iters_preffix

这里的get_monotony_predicate_iters函数需要修改, 使其能够支持tranc_id的滤除。不过和SKiplist中的范围查询类似, Block::get_monotony_predicate_iters会被SST部分的范围查询接口调用, 因此你也可以选择在上层统一实现根据事务id的滤除工作, 这里的实现是可选的。

2.5 各类迭代器

我们实现了多种迭代器都需要在其自增运算符中实现事务id的滤除逻辑, 因此你需要更新的迭代器包括：

HeapIterator
BlockIterator
SSTIterator
ConcactIterator
LevelIterator
TwoMergeIterator

当然, 你不一定需要再每一个迭代器中都实现类似的逻辑, 以TwoMergeIterator为例, 如果其中的it_a和it_b都实现了基于事务id的滤除功能, 那么TwoMergeIterator就不需要再实现一次了。

不过这里it_a和it_b都是基类BaseIterator的指针, 因此你如果想要少实现这个逻辑, 需要好好地进行设计, 提供其是否实现了滤除逻辑的接口。当然，你在所有迭代器全部都实现一次这个滤除逻辑是最保险的做法。

2.6 Engine部分修改

LSMEngine的大部分接口都是对下层组件(包括MemTable、SST等)的封装, 因此你只需要想对应的接口传递正确的tranc_id即可, 不需要额外的修改。

这里只有范围查询(谓词查询)需要你注意, 这里是对包括谓词查询、前缀查询等接口的最顶层封装, 你需要在上层组件中实现根据事务id的滤除逻辑。

2.7 其余部分修改

作者列出了大部分在引入事务id后需要修改的代码部分, 但由于每个人在之前的Lab中实现的方案不同, 因此你可能还需要在其他地方进行一些修修补补。

TODO: 这一部分给参与者的自由度稍高, 引导可能也弱了一点, 后续版本更新的指导书应该加以改正

3 测试

由于事务功能的耦合度较高, 因此现在还没有办法进行单元测试, 你可以按照自己的需要编写测试用例进行测试, 测试用例的编写思路和之前的Lab类似, 你可以参考src/test中的测试用例进行编写。

TODO: 后续版本中补全这里的阶段性测试, 而不是2个Lab完成后才有一个大测试

Toni-LSM-Lab