木慕的博客

Stay naive, stay simple.

0%

CMU-15441 关系型数据库实现-Buffer Pool

发表于 分类于 Valine：

assignment 0 C++ primter

目的是熟悉一下C++，这里的提交需要注意一下格式，比如statement必须在{}之间的要求等等，否则gradescope通过不了。我的第一次提交就有这样的问题，这个评测系统对于格式的要求很高。

GDB：

顺便复习了一下智能指针：

  • 某一时刻只能有一个 unique_ptr<T>指向对象，不支持拷贝赋值
  • shared_ptr<T>可以拷贝赋值，内有自己的计数器

本地测试结果：

1
2
3
4
5
6
7
8
9
10
[       OK ] StarterTest.ElementAccessTest (0 ms)
[ RUN      ] StarterTest.AdditionTest
[       OK ] StarterTest.AdditionTest (0 ms)
[ RUN      ] StarterTest.MultiplicationTest
[       OK ] StarterTest.MultiplicationTest (0 ms)
[----------] 5 tests from StarterTest (0 ms total)

[----------] Global test environment tear-down
[==========] 5 tests from 1 test suite ran. (0 ms total)
[  PASSED  ] 5 tests.

gradescope提交结果

Assignment 1 Buffer Pool

ass1主要需要实现数据库的存储管理部分，分为三部分：

  • LRU
  • Buffer Pool
  • Parallel Buffer Pool

首先第一个是实现一个LRU，这里主要使用hash list（一个unordered_map 和一个list）就可以：

1
2
3
4
size_t cap_; // the capacity
std::list<frame_id_t> q_list_; // linked list of frame_id
std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> cache_map_; // cache map
std::mutex latch; // mutex for thread safety

实现过程不复杂但是我这里看了好久，主要是任务说明刚开始没太看懂。它的意思是LRU模块是给上层缓存池用的，缓存池对于一个page进行pin，pin之后相当于DBMS要拿来用这个Page，所以这时候是不能淘汰的（即需要从LRU中删除）。当且仅当buffer unpin到pin_count=0时才丢给LRU进行管理，这时候可以淘汰。

注意写的时候要完全按照clang-format-tidy进行，否则语法检查不通过。

单元测试结果：

1
2
3
4
5
6
7
8
9
10
11
12
➜  build git:(ghess/p2-refinement) ✗ ./test/lru_replacer_test
Running main() from gmock_main.cc
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from LRUReplacerTest
[ RUN      ] LRUReplacerTest.SampleTest
[       OK ] LRUReplacerTest.SampleTest (0 ms)
[----------] 1 test from LRUReplacerTest (0 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (1 ms total)
[  PASSED  ] 1 test.

之后是缓冲池管理器的实现，BufferPoolManger从DiskManager中获取数据库页，存进内存，同样负责将脏页写回磁盘。

页表管理

在数据库原理的博客中我已经介绍了页表的管理，DBMS由于其特殊性（可知道缓存数据是否需要使用、查询临近）等原因可以自己设计缓冲池。

加锁
在数据库的背景下，locks和latches概念不同：
Locks：

  • 保护索引的逻辑内容不被别的txn改
  • 在整个txn过程中保持
  • 需要回滚

Latches：

  • 保护索引的内部关键数据结构不被别的线程改
  • 在整个操作的过程中保持
  • 不需要回滚（本身就没有事务的概念）

Page：

1
2
3
4
5
6
7
8
9
char data_[PAGE_SIZE]{};
/** The ID of this page. */
page_id_t page_id_ = INVALID_PAGE_ID;
/** The pin count of this page. */
int pin_count_ = 0;
/** True if the page is dirty, i.e. it is different from its corresponding page on disk. */
bool is_dirty_ = false;
/** Page latch. */
ReaderWriterLatch rwlatch_;

PAGE_SIZE 定为4096 Bytes，即4KB，page_id_ 唯一标注了Page，当一个进程pin了页的时候pin_count_就++，然后is_dirty_标注脏页，rwlathch_是封装的读写锁。

Buffer Pool Manager：

1
2
3
4
5
6
7
8
9
10
11
12
13
Page *pages_;
/** Pointer to the disk manager. */
DiskManager *disk_manager_ __attribute__((__unused__));
/** Pointer to the log manager. */
LogManager *log_manager_ __attribute__((__unused__));
/** Page table for keeping track of buffer pool pages. */
std::unordered_map<page_id_t, frame_id_t> page_table_;
/** Replacer to find unpinned pages for replacement. */
Replacer *replacer_;
/** List of free pages. */
std::list<frame_id_t> free_list_;
/** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
std::mutex latch_;
  • pages_是缓存池的page数组，由page id进行索引，是缓存池的核心数据
  • disk_manager 和log_manger 是指向磁盘管理器和日志管理器的指针
  • page_table_是page id和真实frame_id的映射，两者都是int32_t
  • replacer_ 是LRUReplacer对象，主要负责unpin之后的frame的管理
  • free_list_是一个空闲页的list，里面是frame的id
  • latch_是防止资源同时被多个进程读写

这里要搞明白几个概念，frame是缓存池中的缓存frame page，page_id是请求的页表编号，DBMS向缓存池请求的是page_id，磁盘中存储的也是。所以我们需要一个page_id到frame_id的映射来快速进行缓存选择，所以page_table_一定映射的是有效的页，故当淘汰页出缓存时需要将映射删除，这个我debug了好久。

下面是实现细节：
FetchPgImp:
本函数实现从缓存中拿page的操作，可以通过page_table_查询page_id对应的缓存frame，如果没查到就在free_list_里面找个空闲的frame_id，如果free_list_为空说明已经用完了缓存（buffer pool满了），这时候需要进行LRU，里面的replacer调用victim方法找到一个“牺牲”的frame_id，如果脏就读回disk，然后在page_table中删除（因为我们已经淘汰了这个页），并将新的page_id => frame_id映射加入page_table，最后更新frame就可以了（更新page_id，pin_count, is_dirty_）。

UnpinPageImpl
本函数主要处理unpin一个页的操作，如果pin_count > 0那么减一即可，之后如果==0就加入lru_replacer中。如果进程拿到的pin_count就是<= 0，那么直接return false。这里注意要在pin_count = 0时从page_table_中erase掉：

1
2
3
4
if (pages_[frame_id].GetPinCount() == 0) {
    page_table_.erase(page_id);
    replacer_->Unpin(frame_id); // give it to replacer_
}

FlushPageImpl
将page刷新到磁盘中,找到这个page然后WritePage就可以了，记得更新page信息。

FlushAllPgsImp
将所有有效地页面全部写回到disk中去，这里注意要在page_table_中找，因为其保存的都是有效的页。

NewPgImp
在buffer pool中创建一个新page，返回指向page的指针。这里麻烦的地方在于缓存池可能满，此时可能需要将页面写回磁盘，并删除映射和重置数据。
如果不能新建page（free_list_和LRU都满了），那么return nullptr。找到一个空闲的frame_id并更新data即可。新建页完成之后别忘了让replacer_ Pin一下frame_id（frame对应的页是新建的，不应该在LRU淘汰队列中）。

DeletePgImp
在buffer pool中删除某一个page。注意只能删pin_count>0的，之后更新frame即可。

这里主要的思路就是通过buffer pool 和lru_replacer进行frame的管理。buffer pool的page_table_是page_id到frame_id的映射，注意这里主要管理pinned page，而unpinned page则会交给lru_replacer进行管理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
➜  build git:(ghess/p2-refinement) ✗ ./test/buffer_pool_manager_instance_test
Running main() from gmock_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from BufferPoolManagerInstanceTest
[ RUN      ] BufferPoolManagerInstanceTest.BinaryDataTest
[       OK ] BufferPoolManagerInstanceTest.BinaryDataTest (3 ms)
[ RUN      ] BufferPoolManagerInstanceTest.SampleTest
[       OK ] BufferPoolManagerInstanceTest.SampleTest (0 ms)
[----------] 2 tests from BufferPoolManagerInstanceTest (4 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (4 ms total)
[  PASSED  ] 2 tests.

Parallel Buffer Pool Manager
这里的意思是如果只用一个buffer pool的话，虽然我们有互斥锁来保证线程安全，但是当交互的时候可能会产生大量争用，故我们可以设置多个buffer pool来缓解。具体思想就是根据页表编号进行分流，具体是编号page_id % buffer_pool_instance 的缓冲池负责page_id的缓存。

具体实现在ParallelBufferPoolManager，这里我的数据结构设计如下：

1
2
3
4
5
6
private:
  size_t num_instances_; // 缓冲池数量
  size_t pool_size_; // 缓冲池Page大小
  size_t start_index_; // 起始序号
  std::mutex parallel_latch_; // 互斥锁
  std::vector<BufferPoolManagerInstance *> buffer_pools_; // 存放缓冲池指针

初始化时new出所有的缓冲池，并由buffer_pools_进行管理。具体的page操作都只需要找到对应的缓冲池进行操作即可，这里注意NewPgImp的时候要加锁，因为涉及到start_index变量的修改问题：

1
std::scoped_lock scoped_db_latch(parallel_latch_);

加完锁之后从缓冲池

1
2
3
4
5
6
7
8
9
10
11
12
13
Running main() from gmock_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from ParallelBufferPoolManagerTest
[ RUN      ] ParallelBufferPoolManagerTest.BinaryDataTest
[       OK ] ParallelBufferPoolManagerTest.BinaryDataTest (2 ms)
[ RUN      ] ParallelBufferPoolManagerTest.SampleTest
[       OK ] ParallelBufferPoolManagerTest.SampleTest (1 ms)
[----------] 2 tests from ParallelBufferPoolManagerTest (3 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (4 ms total)
[  PASSED  ] 2 tests.

gradescope 测试：