请不要将代码提交到公开仓库(包括提交带有题解的 Pull Request),同时也请不要抄袭其他同学或网络上可能存在的代码。
每次实验代码更新,需要将代码从远端仓库拉取下来,大家需要从 miniob 的 github 仓库上把代码拉取到本地。
- git remote add origin_ob https://github.com/oceanbase/miniob.git
- git pull origin_ob
- git merge origin_ob/main
- 解决git冲突
- 实现代码,推送到自己的github仓库上
LAB#3 事务引擎¶
在数据库系统实现原理与实践课程的 LAB#1,LAB#2 中,你已经完成了数据库系统中的存储引擎(基于 LSM-Tree 的存储引擎),查询引擎(实现查询算子,优化执行计划等)。在这个实验中,你需要为 LAB#1 中实现的 LSM-Tree 存储引擎支持事务,同时支持数据库的持久化和恢复。你需要根据此文档的指导,完成事务引擎以及数据库的持久化和恢复。
实验¶
本实验包含如下几个子任务:
- 任务1: 实现基于 LSM-Tree 的 MVCC 事务
- 任务2: 实现数据库的持久化和恢复
任务1: 实现基于 LSM-Tree 的 MVCC 事务¶
背景介绍¶
MVCC(Multi-Version Concurrency Control)是一种并发控制技术,其核心目标是:
- 支持事务语义:通过存储一个键的多个"版本",使事务读取到一致的快照,而不受其他事务更新的影响。
- 提高并发性能:避免因锁争用导致的性能问题,使读操作无需阻塞写操作。
- 实现数据的时间旅行(Time Travel):通过特定的历史版本读取支持点时间查询。
在 LSM-Tree 中,每条数据被存储为一个 Key-Value 对。为了支持 MVCC,需要为每个 Key-Value 增加一个时间戳。一个 Key-Value 对以如下方式编码存储。
key_size : internal_key.size()
key bytes : char[internal_key.size()]
seq : uint64(sequence)
value_size : value.size()
value bytes : char[value.size()]
在增加了时间戳之后,就可以通过在事务内部申请一个额外的 WriteBatch 的方式实现事务。每个事务操作会在事务内部申请一个 WriteBatch,所有事务提交之前的读都优先读该 WriteBatch(保证了同一个事务内可以看到该事务的写操作),写操作都直接写入该事务独有的WriteBatch中,事务提交时再依次写入 WAL 和 memtable。
实现¶
你需要实现 src/oblsm/include/ob_lsm_transaction.h::ObLsmTransaction
中未完成的函数,使 LSM-Tree 支持事务。你可以通过 unittest/oblsm/ob_lsm_transaction_test.cpp
中的测试用例来验证你的实现是否正确。
你需要实现 src/observer/storage/table/lsm_table_engine.h
中如下几个函数,以使 MiniOB 支持事务。
RC insert_record_with_trx(Record &record, Trx* trx) override;
RC delete_record_with_trx(const Record &record, Trx* trx) override;
RC update_record_with_trx(const Record &old_record, const Record &new_record, Trx* trx) override;
你可以通过开启多个 obclient 测试 MiniOB 中的事务。
提示 测试过程中,需要在启动 observer 时指定存储引擎为lsm,事务类型为lsm。即 -E lsm -t lsm
测试用例示例
client 1: client 2:
insert into t1 values(0, 0);
begin;
begin;
insert into t1 values(1, 1);
select * from t1;
select * from t1;
delete from t1 where id = 0;
select * from t1; select * from t1;
insert into t1 values(3,3);
select * from t1;
select * from t1;
commit;
select * from t1;
commit;
select * from t1;
提示 你需要实现快照隔离(Snapshot Isolation)级别的 MVCC 事务。
提示 事务提交时可以使用ObLsmImpl::batch_put
,来一次性写入一批数据,需要考虑这一批数据写入的原子性,以及写入过程中的失败回滚。
注意 update_record_with_trx
在LAB#3 中不做要求,在 LAB#4 中要求必须实现。
思考 当前的 WriteBatch 是完全在内存中的,如果事务中涉及的大小超过内存大小应该如何处理?
任务2: 实现数据库的持久化和恢复¶
背景介绍¶
在 LAB#1 中,你已经实现了 LSM-Tree 的基本功能,但是你应该发现如果关闭 LSM-Tree 之后重新打开,之前写入的数据可能并不会存在,这是由于 LAB#1 中还没有实现 LSM-Tree 的持久化和恢复机制。在本任务中,你需要实现 LSM-Tree 的持久化和恢复机制,同时基于 LSM-Tree 的 MiniOB 也要支持持久化和恢复。这里介绍下 LSM-Tree 的持久化和恢复机制的实现思路:
- 通过 Write Ahead Log(WAL)实现 MemTable 数据的持久化。
WAL 是一种常见的日志机制,用于确保数据的可靠性和持久性。在 LSM-Tree 中,每次数据写入之前,都会先写入 WAL 文件,这是一个文件日志,记录了数据变更的操作细节。即便系统发生故障,数据库可以通过 WAL 文件恢复写入到 MemTable 的数据,从而防止数据丢失。
- 通过 Manifest 文件实现 SSTable 状态的持久化。
Manifest 文件是 LSM-Tree 的 "元数据目录",用于记录某一时间点 LSM-Tree 的状态。它描述了 LSM-Tree 中每个 SSTable 文件的元数据(如编号、层级等),使数据库能够在重启或恢复时快速加载恢复 SSTable 的状态。
更多细节可参考LSM-Tree 设计文档
除此之外,还要考虑 MiniOB 中的持久化和恢复机制。
在 LSM-Tree 支持持久化和恢复之后,MiniOB 只需要支持与 MiniOB 相关的表元数据的持久化和恢复即可。例如,表的元数据TableMeta
,自增列 ID 等。
实现¶
你需要实现 src/oblsm/wal/ob_lsm_wal.h
中未完成的函数,完成 Write Ahead Log 功能,以使 LSM-Tree 支持持久化和恢复。你可以通过 unittest/oblsm/ob_lsm_wal_test.cpp
中的测试用例来验证你的实现是否正确。
除此之外,你还需要考虑在 ObLsm 重启时,从 WAL 中恢复记录到 MemTable 中。可参考 src/oblsm/ob_lsm_impl.h::ObLsmImpl::recover
你需要在 LsmTableEngine
初始化时,从 LSM-Tree 中恢复自增列 ID inc_id_
。
思考 MiniOB 中是否需要存储额外 LSM-Tree 存储引擎日志,用于持久化和恢复?