2021 CMU 15-445 实验笔记

陆陆续续终于把 CMU 15-445 刷完了(中间插了个 TinyKV),这也算是自己数据库的启蒙之课。编码耗时共计 98 小时 43 分钟。

我个人给整个项目难度评级:Project 1 < Project 4 < Project 3 << Project 2。其中 Project 2 难度最大,主要没啥参考资料,今年的是 Extendible Hash Table,不是噩梦 B+ 树(其实也挺噩梦的)。

我个人认为 15-445 并不是代码通过 Gradescope 就算可以了,很多东西即使你做完了还是模模糊糊的,强烈建议跟着 PPT 和《数据库系统概念 第七版》过一遍,着重看 Query Processing,Transaction 和 Concurrency Control,其中事务这块更是重中之重。

这里可以看看我自己总结的事务并发控制:https://www.inlighting.org/archives/database-concurrency-control/

如果想直接要答案源码的,发我邮件咨询就行了。

Project 0

Project 0 相当于一个热身项目,用于检查学员是否具备正常的 C++ 能力来进行这一门课程。

因为我学习这门课程前不会 C++,所以我没能力,因此我没做。。。

Project 1

Project 1 要我们实现一个 buffer pool,实验分为三个部分,我逐步说明。

LRU Replacement Policy

这个实验一开始主要是被方法名搞懵了,实际上其方法名是对应上层 BufferPool 来说的。LRU 管理的是 frame,存放 page 的那个 frame,而不是 page 本身。比如上层 BufferPool Pin() 了一个 page,然后上层找到该 page 的 frame,然后 LRU 需要移除这个 frame,不进行淘汰(因为上层在使用中)。反之,如果上层 BufferPool UnPin() 了一个 page,然后就要把该 page 对应的 frame 加入 LRU,等待被移除。

此外每个方法注意加锁,可以使用 std::lock_guard<std::mutex> 来进行处理,类似 go 语言的 defer ,可以优雅的解决锁释放的问题。

Buffer Pool Manager Instance

具体流程我不讲,大家自己琢磨琢磨就知道了,我就说说我几个犯了错误的地方。

NewPgImp(page_id_t *page_id) 中,不要一开始就调用 AllocatePage() 分配 pageId,只有当真的有空闲的 page 可以使用时,再调用 AllocatePage()分配一个 pageId 给它,不然你会过不去 gradescope 上面的 [RoundRobinNewPage] 这个测试点。至于为啥,你看看 AllocatePage() 的实现就知道了。

每一次获得一个新的 page,或者删除一个 page 时,请调用 page->ResetMemory() 方法将其数据重置掉,而不是放任不管,想着后面可以直接覆盖。

UnpinPgImp(page_id_t page_id, bool is_dirty) 时不要直接 page->is_dirty_ = is_dirty ,相反应该是:

if (is_dirty) {
  page->is_dirty_ = is_dirty; // 不然会直接把之前的 is_dirty 状态给覆盖了。
}

最后注意加锁!

Parallel Buffer Pool Manager

我在 Parallel Buffer Pool Manager 中维护了一个 next_instance_ 变量,用于判断下一次分配 page 的 Buffer Pool Manager 是谁,分配 page 的 round-robin 代码如下:

Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) {
  std::lock_guard<std::mutex> guard(latch_);
  for (size_t i = 0; i < num_instances_; i++) {
    BufferPoolManager *manager = *(managers_ + next_instance_);
    Page *page = manager->NewPage(page_id);
    next_instance_ = (next_instance_ + 1) % num_instances_;
    if (page != nullptr) {
      return page;
    }
  }
  return nullptr;
}

注意,这里只有 NewPgImp(page_id_t *page_id) 方法需要加锁,别的地方加锁没必要,不然还要 parallel 干啥。

Project 2

Project 2 是让我们实现一个 Extendible Hash Table,只能说很难,难度系数是 Project 1 的两倍,中间一度有点想放弃(主要网上还没别人的代码参考)。整个项目大约花了 10 天吧。

关于 Extendible Hash Table 的算法实现,可以看我的另一篇文章:https://www.inlighting.org/archives/extendible-hash-table-algorithm ,这里我说说我遇到的一些坑。

Bucket

先从 bucket 开始说起,首先就是 IsReadable()IsOccupied() 两个函数。在这里,如果一个元素被创建了,那么他的 readable_occupied_ 均要被标记。如果被删除了,你只需要将 readable_ 的标记清除即可,occupied_ 不用管,仍然占用。

Bucket 标记元素是否被占用的是 char 数组,一个 char 是 8 bit,能表示 8 个数据,设置 readable 和 occupied 时位运算是肯定跑不了了。

关于插入和查询操作,你直接遍历查找就行了,是的,你没有听错,就是一个一个遍历。一个 bucket 只占一个 page 的大小,4 KB 的空间你也玩不出什么数据结构。虽然常规下,Extendible Hash Table 的 bucket 应该使用前缀树,但是它太占空间了。

请不要在 bucket page 中定义额外的成员变量:一开始我想为了提升性能,在 bucket 中定义了一个 NumReadable 变量,用于统计当前 bucket 有几个可读的元素,这样判断 IsFull 和 IsEmpty 可以不需要遍历。但是实际上官方给你定义的数据结构有时候会正好占满 4096 KB,如果你自己定义了某个成员变量,会使得这个 bucket 超出范围了,然后你会越界访问到 Page 里面的内容,然后就莫名其妙的报错。我被这个问题卡了很久,不然早过了。

Directory

这块其实没啥好说的,你自己实现好 Hash Table 的 grow 和 shrink 的逻辑即可。锁也不用加。

Hash Table

Hash Table 这块锁的设计就有讲究,我个人建议的是,先不加锁实现,等能过基本的 Insert,Remove 测试点时,再加锁。加锁直接用全局的 table_latch_ 加写锁,先保证测试用例都能过了,100 分了,再考虑优化性能。我一开始全局写锁,gradescope 是 100 分了,不过 leaderboard 那里没有分数。

这里讲讲我优化后的锁设计:

Insert() 时,table_latch_ 是 ReadLock,对应的 bucket 为 WriteLock。这很好理解,因为你只对一个 bucket 就行修改操作。

SplitInsert() 时,因为一个 bucket 容量不够,你需要扩容,这里会涉及到 directory 的操作,所以这里我使用 table_latch_ 的 WriteLock,锁住全局。同理,合并 directory 的操作也需要 table_latch_ 的 WriteLock 锁住全局。

GetValue() 操作不用说,table_latch_ 和 bucket lock 均使用 ReadLock。

FetchDirectoryPage() 这块我使用了一个独立的锁,因为我在这个方法里面涉及到创建 directory 的逻辑,就是当 HashTable 刚被创建的时候需要一个初始的 directory 是一个 local depth 为 0 的 bucket。当然你也可以不用这么麻烦,直接在 Hash Table 的构造方法里面创建就行了。

注意事项

及时的 Unpin 不需要的 page,我就这么说吧,gradescope 中有些测试用例的 buffer pool size 只有 3,也就是 Hash Table 运行最小需要的 page 数量。(1 个给 directory,2 个给 bucket,因为 bucket 分裂的时候需要 2 个)。

善用 assert 语句,比如 Unpin 等操作时通过 assert 确定其是成功执行的。还有一些地方通过 assert 来确定数据是按照你的想法在执行。这样能帮助你更快的定位出程序的问题。

比如下面这段程序:

uint32_t mask = dir_page->GetLocalDepthMask(split_bucket_index);
for (uint32_t i = 0; i < origin_array_size; i++) {
  MappingType tmp = origin_array[i];
  uint32_t target_bucket_index = Hash(tmp.first) & mask;
  page_id_t target_bucket_index_page = dir_page->GetBucketPageId(target_bucket_index);
  assert(target_bucket_index_page == split_bucket_page_id || target_bucket_index_page == split_image_bucket_page_id);
  if (target_bucket_index_page == split_bucket_page_id) {
    assert(split_bucket->Insert(tmp.first, tmp.second, comparator_));
  } else {
    assert(split_image_bucket->Insert(tmp.first, tmp.second, comparator_));
  }
}

当一个 bucket 分裂后,我们需要将这个 bucket 中原有的数据分流。按照 split 逻辑我们肯定知道,分流的数据必定落在原来的 bucket page 和 split image bucket page 两个 bucket 中(注意是 page 哦,而不是 bucket 的 index)。这里我们可以使用 assert 进行确认,提前定位 bug。

Project 3

Project 3 中我们需要基于火山模型(Volcano model)实现基本的 SQL 语句,没啥难的,无非就是一些 API 不知道,要花点时间看源码。

常用代码:

根据 SELECT 的字段生成对应 tuple:

std::vector<Value> values;
for (size_t i = 0; i < plan_->OutputSchema()->GetColumnCount(); i++) {
  values.push_back(plan_->OutputSchema()->GetColumn(i).GetExpr()->Evaluate(tuple, schema_));
}

*tuple = Tuple(values, plan_->OutputSchema());

判断 tuple 是否满足 predicate 条件:

const AbstractExpression *predict = plan_->GetPredicate();
if (predict != nullptr && !predict->Evaluate(tuple, plan_->OutputSchema()).GetAs<bool>()) {
  // Satisfy predicate
}

如果存在 child executor,需要先 init 它:

void InsertExecutor::Init() {
  // ...
  child_executor_->Init();
  // ...
}

插入索引:

删除索引类似。

for (const auto &index : catalog_->GetTableIndexes(table_info_->name_)) {
  index->index_->InsertEntry(
    tuple->KeyFromTuple(table_info_->schema_, *index->index_->GetKeySchema(), index->index_->GetKeyAttrs()), *rid,
    exec_ctx_->GetTransaction());
}

具体实现

Sequential Scan

数据通过 TableHeap 的 Next() 获取,根据 SELECT 的字段生成对应 tuple。如果存在 predicate 条件则额外进行判断是否满足。

Insert

调用 TableHeap 的 InsertTuple() 方法,插入成功后需插入对应的索引。

Update

删除原来的索引,调用 GenerateUpdatedTuple() 生成新的 tuple,通过 TableHeap 的 UpdateTuple() 更新原有 tuple,最后再插入 新索引。

Delete

调用 TableHeap 的 MarkDelete() 删除对应的 tuple,再删除索引即可。

Nested Loop Join

没啥复杂的,主要是判断 join 的 predicate 条件的 API 复杂,示例代码如下:

if (plan_->Predicate() == nullptr || plan_->Predicate()
    ->EvaluateJoin(&left_tuple, left_executor_->GetOutputSchema(),
                   &right_tuple, right_executor_->GetOutputSchema())
    .GetAs<bool>()) {
  std::vector<Value> output;
  for (const auto &col : GetOutputSchema()->GetColumns()) {
    output.push_back(col.GetExpr()->EvaluateJoin(&left_tuple, left_executor_->GetOutputSchema(), &right_tuple,
                                                 right_executor_->GetOutputSchema()));
  }
  tmp_results_.push(Tuple(output, GetOutputSchema()));
}

Hash Join

Hash Join 需要自己仿照 SimpleAggregationHashTable 自己写一个 Hash Table,底层直接用 std::unorder_map 就行,不需要使用 Extendible Hash Table。

在 Init 时先把所有 left_child 的 tuple 插入 hash table,之后在 Next() 时每次匹配一个 right tuple 即可。

Aggregation

和 Hash Join 类似,就是输出时需要判断是否存在 having 条件,如果存在,判断是否满足。

// 判断Having条件,符合返回,不符合则继续查找
if (plan_->GetHaving() == nullptr ||
    plan_->GetHaving()->EvaluateAggregate(agg_key.group_bys_, agg_value.aggregates_).GetAs<bool>()) {
  std::vector<Value> ret;
  for (const auto &col : plan_->OutputSchema()->GetColumns()) {
    ret.push_back(col.GetExpr()->EvaluateAggregate(agg_key.group_bys_, agg_value.aggregates_));
  }
  *tuple = Tuple(ret, plan_->OutputSchema());
  return true;
}
return Next(tuple, rid);

Limit

太简单,直接贴出来得了。

void LimitExecutor::Init() {
  numbers_ = 0;
  child_executor_->Init();
}

bool LimitExecutor::Next(Tuple *tuple, RID *rid) {
  if (!child_executor_->Next(tuple, rid)) {
    return false;
  }

  numbers_++;
  return numbers_ <= plan_->GetLimit();
}

Distinct

一样需要和 Hash Join 一样实现一个自己的 hash table,然后通过 hash 表去重即可。

Project 4

事务的并发控制,建议过完实验后,看一遍书和 PPT,再回来看代码,会有更加深刻的理解。不然你有可能只是面向测试用例编程。

LockManager

这里直接和 deadlock prevention 一起讲了。

2PL 下不同隔离级别的行为:

Read uncommitted:读取不需要获得 shared lock,写需要获得 exclusive lock,用完直接放锁,不需要遵守 2PL 的两个 phase 规则。

Read committed:读取和写入均需要锁,用完直接放锁,不需要遵守 2PL 的两个 phase 规则。

Repeatable read:读取和写入均需要锁,需要遵守 2PL 的两个 phase 规则,只有在事务 commit 或 abort 时统一放锁。

等待获取锁细节:

在 LockRequestQueue 中排队获取锁时,我采用的设计是事务从小到大排列(older->younger)。假设一个事务 $T$ 申请锁后会将其锁追加在 RequestQueue 末尾,然后遍历整个 RequestQueue,如果存在大于事务 $T$ (也就是 younger)且会冲突的锁,则 abort 掉拥有该锁的事务。如果在遍历 RequestQueue 的过程中发生过 abort 行为,遍历完成后就 notify_all() 一次,尝试唤醒阻塞线程。

等待获取锁请使用 while 循环,而不是 if。

while (NeedWait(txn, lock_queue)) {
  lock_queue->cv_.wait(guard);
  if (CheckAbort(txn)) {
    return false;
  }
}

LockShared

  1. 如果已经 abort,直接 return false。
  2. 如果 IsolationLevel 是 READ_UNCOMMITTED,直接 abort,它不需要读锁。
  3. 如果不是处于 2PL 的 GROWING 阶段,直接 abort。
  4. 如果已经获取过 shared lock,直接 return true。
  5. 添加锁到 RequestQueue 和 txn 的 SharedLockSet 中,之后尝试等待获取锁。
  6. 获得锁成功后,将锁的 granted_ 设置为 true。

LockExclusive

和 LockShared 差不多,就是锁冲突的形式不一样,Exclusive 和任意锁都是冲突的。

LockUpgrade

同样和 LockShared 差不多,下面说几个不同点:

  1. 如果已经有了对应 rid 的 exclusive lock,说明之前可能已经 upgrade 成功,直接 return true。
  2. 只有当比你 older 的 txn 不含有 exclusive lock 时,你才可以 upgrade 你的 shared lock。
  3. 获得锁后,修改锁的信息,更改事务的 LockSet。

虽然 LockRequestQueue 提供了一个 upgrading_ 属性,不过我并没用到过。

Unlock

  1. 如果不含对应的锁,直接 return false。
  2. 如果当前事务隔离级别是 REPETABLE_READ,且处于 2PL 的 GROWING 阶段,将 2PL 设置为 SHRINKING 阶段。
  3. 移除事务的 LockSet 中对应的锁。

Execution

seq_scan_executor

如果不是 READ_UNCOMMITTED,读取均需要获取 shared lock。如果是 READ_COMMITTED,读完后需要立刻释放 shared lock。

insert_executor

任意隔离级别均需要获取 exclusive lock(如果本来有 shared lock,则通过 upgrade 升级得到)。READ_UNCOMMITTED 和 READ_COMMITTED 写入完成后立刻释放 exclusive lock。REPEATABLE_READ 会在整个事务 commit 时统一 unlock,不需要我们自己编写代码。

update_executor

同上

delete_executor

同上

总结

受益匪浅,就是不知道大脑能记多久,感谢 CMU!。

评论

  1. Alex Ye
    Windows Chrome 102.0.0.0
    1天前
    2022-6-25 19:52:42

    同求一份代码

    • Alex Ye
      Alex Ye
      Windows Chrome 102.0.0.0
      1天前
      2022-6-25 20:42:41

      不用发给我了,刚把proj 4满分调通。基本是follow博主的hint,多谢了!

      • 博主
        Alex Ye
        Macintosh Chrome 102.0.0.0
        1天前
        2022-6-25 22:14:52

        好的,正好还打算发的。

  2. 乐乐
    Windows Chrome 102.0.0.0
    2天前
    2022-6-25 3:40:20

    求源码,感恩

  3. Jack
    Macintosh Safari 15.5
    2天前
    2022-6-24 16:06:48

    求博主的一份源码参考,万分感谢博主
    1103206452@qq.com

  4. Downal
    Windows Edge 102.0.1245.44
    5天前
    2022-6-21 15:51:25

    求博主一份源码,感谢。
    469743591@qq.com

    • 博主
      Downal
      Macintosh Chrome 102.0.0.0
      5天前
      2022-6-21 15:53:41

      已发

      • Downal
        Smith
        Windows Edge 102.0.1245.44
        5天前
        2022-6-21 15:55:17

        感谢感谢

  5. kk
    Windows Chrome 102.0.0.0
    7天前
    2022-6-20 0:14:46

    您好,博主,能求一份代码吗,976911453@qq.com, 谢谢!
    刚做完project1中,只有下面这个测试没有通过。这个测试大概是来测什么的呢,内存泄露吗?还有出现timeout可能是啥原因啊?
    test_memory_safety (main.TestProject1) (0.0/10.0)
    Test Failed: False is not true : Timeout Happened during valgrind

  6. 小杨
    Windows Chrome 102.0.0.0
    1周前
    2022-6-19 20:13:43

    求博主的一份源码参考,感谢博主,邮箱
    1395498360@qq.com
    !!! 非常感谢!!!!

    • 博主
      小杨
      Macintosh Chrome 102.0.0.0
      1周前
      2022-6-19 21:18:36

      发了

      • 小杨
        Smith
        Windows Firefox 101.0
        1周前
        2022-6-19 21:28:46

        感谢感谢

  7. spike
    Windows Edge 102.0.1245.41
    1周前
    2022-6-17 22:44:45

    楼主,求一份源码 zrh20001004@163.com

  8. draper
    Android Chrome 83.0.4103.106
    2周前
    2022-6-16 2:54:26

    求博主的一份源码参考,感谢博主,邮箱
    1057690730@qq.com

    • 博主
      draper
      Macintosh Chrome 102.0.0.0
      1周前
      2022-6-17 0:59:24

      已发

  9. Tsunaou
    Windows Edge 102.0.1245.39
    2周前
    2022-6-15 20:04:49

    楼主求一份源码参考🙈

    • 博主
      Tsunaou
      Macintosh Chrome 102.0.0.0
      2周前
      2022-6-15 20:07:00

      已发

  10. hahaha
    Windows Chrome 102.0.0.0
    2周前
    2022-6-14 20:51:26

    老哥,我也求一份源码参考参考

  11. shawnyang
    Windows Chrome 102.0.5005.63
    2周前
    2022-6-11 8:53:53

    lz可以借鉴一下源码嘛?想学习一下!

    • 博主
      shawnyang
      Macintosh Chrome 102.0.5005.61
      2周前
      2022-6-11 12:22:49

      发了

  12. Kamille
    Windows Firefox 101.0
    2周前
    2022-6-11 2:32:21

    project2 有个奇怪的点,并发相关测试里,不知道为什么会主动调用 buffer 的 unpin 方法来做一些清理(我的实现逻辑里对 unpin 用宏封了一层,只能是测试代码中的调用了)。
    如果在构造函数里创建 directory page ,会出现 unpin pin_count 为 0 的页的情况,我刚好在 project 1 assert 了 pin_count <= 0,然后就懵逼了大半天。
    没法获取测试代码,真的蛋痛。。。 现在完全确定了出问题的点了,但还是没法推理清楚整个出问题的过程。

    • Kamille
      Kamille
      Windows Firefox 101.0
      2周前
      2022-6-11 2:33:49

      assert 了 pin_count > 0

      • 博主
        Kamille
        Macintosh Chrome 102.0.5005.61
        2周前
        2022-6-11 13:08:51

        额,没有很看懂你的描述,我发了你一份代码,你 look 一下。

  13. Lyrics
    Macintosh Chrome 101.0.4951.64
    3周前
    2022-6-05 0:42:12

    你好,关于project 3不同隔离级别的实现有个问题想问一下:
    我的理解是用不同的锁策略来实现三种不同的隔离级别,其中只有Repeatable Read这个隔离级别用到了(Strict) 2PL,并且保证了Serializability
    Read Uncommitted和Read Committed这两种隔离没有用到2PL,那他们是如何保证Serializability的呢(比如在一个并发场景下,同一个RID,如果一个old的txn还未发出一个锁请求,而另外一个young txn的锁请求已经被grant了,这种情况就违反了serializability了)
    我看了一下提供的基本测试样例并没有测试这两种隔离级别

    • 博主
      Lyrics
      Macintosh Chrome 102.0.5005.61
      3周前
      2022-6-05 10:05:14

      要说一点,这三种隔离级别都达不到 serializable,难道你忘了事务的四种隔离级别最高级的才是 serializable,所以从何谈“如何保证Serializability”?

      • Lyrics
        Smith
        Macintosh Chrome 101.0.4951.64
        3周前
        2022-6-05 10:19:13

        可能表达得不清楚,我是想问Conflict Serializability。四种隔离级别的serializable这个隔离级别是保证事务完全顺序执行,我是想问并行执行且保证conflict serializability的情况
        课件上的原话是“2PL on its own is sufficient to guarantee conflict serializability.”
        若另外两种隔离级别写完马上释放锁(不遵循2PL),那我理解是这两种隔离级别下是无法保证conflict serializability的,请问这样是没问题的吗
        虽然本地测试和自线测试似乎并没有测试这两种隔离级别,单纯好奇

        • 博主
          Lyrics
          Macintosh Chrome 102.0.5005.61
          3周前
          2022-6-05 10:32:21

          没有问题的吧,至少我在实现的时候没有考虑 conflict serializability。我觉得我们的实现只要满足这个隔离级别的定义就行了。

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇