文章目录
InnoDB Buffer Pool
在前面的文章中,通过对读写操作的调试,大致梳理了执行这些SQL语句过程中主要调用的一些函数,但并没有提及直接操作磁盘的相关函数。由于磁盘相对于处理器的速度较慢,因此数据库会在内存中维护一个缓存池。在InnoDB存储引擎中,与Buffer Pool 相关的代码主要在storage/innobase/buf
目录下。一个具备最基本功能的Buffer Pool 包含一个保存大量页面的内存空间以及记录这些内存页面状态的控制变量,比如记录空闲页面的链表、用于页面替换的LRU。而InnoDB中实现的Buffer Pool 则具有更多的功能,包括double write buffer、预读预写、压缩页面等。
接下来首先从源码文件的主要结构体出发,梳理一下Buffer Pool的内存组织方式以及相关的一些主要函数。之后通过一个project 实现一个具备基本功能的Buffer Pool。
源码组织
在MySQL的源码目录storage/innobase/buf
以及storage/innobase/include
目录下包含了Buffer Pool实现的源码文件。
-
buf0buddy
:用于压缩页面管理的伙伴内存管理系统 -
buf0buf
: Buffer Pool 的核心代码,包含结构体buf_pool_t
、控制块、空闲块链表、预读等相关结构体与函数 -
buf0checksum
:数据落盘时的校验码计算 -
buf0dblwr
:doule write buffer,用于解决宕机导致页面写入不完整问题 -
buf0dump
:Buffer Pool 的load/dump操作,将页面的space id 和 page no 写入外部文件以及加载,用于数据库重启时状态的快速恢复 -
buf0flu
:包含flush list,用于处理将脏页刷到磁盘上 -
buf0rea
:最底层的文件读写/预读相关的操作
Buffer Pool 核心数据结构
在源码文件storage/innobase/buf/buf0buf.cc
中有两百行左右的注释,总体上介绍了Buffer Pool实现包含的主要结构以及对应的功能。
buf_pool_t
InnoDB中Buffer Pools保存在一个动态数组中,extern buf_pool_t* buf_pool_ptr; /*!< The buffer pools of the database */
,该数组长度的最大值通过宏定义 #define MAX_BUFFER_POOLS (1 << MAX_BUFFER_POOLS_BITS)
指定,其中MAX_BUFFER_POOLS_BITS
的默认值为 6。
buf_pool_t 中主要的变量包括:
ib_mutex_t mutex // buffer pool 数组中当前位置的互斥量
uint instance_no // buffer pool 编号
ulint n_chunks // 当前buffer pool 包含的chunks 个数
buf_chunk_t *chunks // 保存内存中的frames 以及对应的控制块,内存中的frame 对应磁盘上的页面
ulint curr_size // buffer pool 中当前保存的页面个数
hash_table_t *page_hash // 通过 (table space )space id 以及offset 定位页面
hash_table_t *zip_hash // 用于定位分配给buddy的内存页面
/*========================*/
ib_mutex_t flush_list_mutex // 用于控制flush list访问的互斥量
const buf_page_t *flush_list_hp // hazard pointer,为了提升刷脏页的效率
/*==========================*/
UT_LIST_BASE_NODE_T(buf_page_t) free // 空闲块链表
UT_LIST_BASE_NODE_T(buf_page_t) LRU // LRU 链表节点
buf_page_t *LRU_old // 指向LRU链表old 部分的指针,如果LRU的长度小于 BUF_LRU_OLD_MIN_LEN,则该指针为NULL
每个Buffer Pool 都有一个互斥量控制访问,其中chunks 保存内存页面以及对应的控制块,内存中的页面数据与磁盘上的对应,不过控制块上的信息并不需要写入到磁盘上面。page_hash
用于通过space id 以及页面偏移快速定位到内存中的页面,同样对于负责管理压缩页面的buddy 系统也有一个zip_hash
。
Buffer Pool 中还包含了刷脏页用的flush list
以及用于页面替换的 LRU。其中flush list
使用了 hazard
指针用于解决并行情况下普通方式需要每次重新从list尾部扫描导致的效率问题,而hazard
指针会在释放锁之前调整指针到 list 中的下一个节点[1],这样另外一个线程无需从list 尾部扫描寻找起始位置。
InnoDB 中Buffer Pool的实现,当LRU 的长度大于 BUF_LRU_OLD_MIN_LEN
之后,LRU划分为 old 和 young 两部分。当free
中的空闲块用完之后,优先从LRU 的old部分替换页面。在buf_pool_t
结构体中,指针 buf_page_t *LRU_old
指向LRU的old 部分。
buf_chunk_t
在结构体buf_pool_t
中,chunks
变量中保存内存中的页面frames 以及对应的控制块。结构体buf_chunk_t
的定义如下:
struct buf_chunk_t{
ulint mem_size; /*!< allocated size of the chunk */
ulint size; /*!< size of frames[] and blocks[] */
void* mem; /*!< pointer to the memory area which
was allocated for the frames */
buf_block_t* blocks; /*!< array of buffer control blocks */
};
其中void *mem
就是内存中的frames,blocks
中是对应每个frame的控制块。
源码 storage/innobase/buf/buf0buf.cc
buf_chunk_init
函数用于初始化一个chunk,其中包括为chunk中的frames分配内存空间。函数的声明如下:
static
buf_chunk_t*
buf_chunk_init(
/*===========*/
buf_pool_t* buf_pool, /*!< in: buffer pool instance */
buf_chunk_t* chunk, /*!< out: chunk of buffers */
ulint mem_size) /*!< in: requested size in bytes */
其中buf_pool
为chunk 所属的Buffer Pool 实例,chunk
返回初始化并分配内存的frames以及控制块,mem_size
是以字节为单位的请求分配的内存空间大小。该函数的执行过程中主要调用的函数以及说明如下:
buf_chunk_init --
|
|
-- ut_2pow_round(mem_size, UNIV_PAGE_SIZE) # 按照页面的大小,计算需要的页面个数,这里UNIV_PAGE_SIZE 默认为 14,即页面的大小16KB,如果这里mem_size如果不是刚好为2的次方,则计算页面时会向下取
|
|
-- ut_2pow_round((mem_size / UNIV_PAGE_SIZE) * (sizeof *block) + (UNIV_PAGE_SIZE - 1), UNIV_PAGE_SIZE) # 这里为控制块分配空间
|
|
-- chunk->mem = os_mem_alloc_large(&chunk->mem_size) # 为frames 以及控制块分配内存空间
|
|
|
-- frame = (byte*) ut_align(chunk->mem, UNIV_PAGE_SIZE) # 按照页面的大小内存对齐,之后会执行 chunk->size = chunk->mem_size / UNIV_PAGE_SIZE - (frame != chunk->mem),即如果分配的内存空间是需要对齐的,则页面个数减1
|
|
-- buf_block_init(buf_pool, block, frame) # 在前面的步骤完成frames的内存分配之后,初始化frames对应的控制块
|
|
-- buf_pool_index(buf_pool) # 函数的操作为当前buf_pool 指针减去系统buffer pools 指针得到当前buf_pool的序号
其中,函数os_mem_alloc_large
根据宏定义HAVE_LARGE_PAGES
和 UNIV_LINUX
决定是否使用大页内存。系统默认的内存页面大小一般是4KB,不同架构的处理器所支持的页面大小也不完全相同。比如x86架构的CPU支持4KB、2MB甚至1GB大小的内存页[3]。使用更大内存页面可以减少内存表项,并且可以减少缺页中断的次数。如果系统是基于 Unix System V的,可以使用 shmget
、shmat
[4]等操作,或者也可以通过mmap[5] 完成。
buf_page_t
首先来看内存页面的八种状态
-
BUF_BLOCK_POOL_WATCH
:处于该状态的页面会被purge线程删除 -
BUF_BLOCK_ZIP_PAGE
:未修改过的压缩页面 -
BUF_BLOCK_ZIP_DIRTY
:修改过的压缩页面 -
BUF_BLOCK_NOT_USED
:处于该状态的页面在空闲链表中 -
BUF_BLOCK_READY_FOR_USE
:从free list 中获取页面,页面处于该状态。从LRU替换页面也需要先放到free list里面 -
BUF_BLOCK_FILE_PAGE
:表示已加载了磁盘上的数据,被解压的页面也会被设置为该状态 -
BUF_BLOCK_MEMORY
:用于存储InnoDB行锁,压缩页面数据等 -
BUF_BLOCK_REMOVE_HASH
:加入到free list之前的过渡状态,在加入到free list 之前需要先把 page hash 移除,此时页面处于该状态
结构体 buf_page_t
中包含的主要成员变量包括:
-
space
: tablespace id -
offset
:页号 -
io_fix
:当前的I/O 操作状态,当前页面没有读写操作为BUF_IO_NONE
,有读操作为BUF_IO_READ
,有写操作为BUF_IO_WRITE
,处于BUF_IO_PIN
状态时,不能更改在内存中的位置以及从flush list中删除 -
buf_pool_index
:当前页面所属的Buffer Pool instance 序号 -
newest_modification
:页面最早的修改操作的lsn(log sequence number),如果没有被修改过则为0 -
oldest_modification
:未被写入到磁盘上的最后一次修改操作的起始lsn,如果所有的修改都更新到磁盘,则值为0
在buf0buf.cc
中,函数buf_block_alloc
用于创建新的block,该函数的执行流程如下,在获得一个可用的block之前可能需要多次迭代,这取决于free list以及LRU的状况。调用该函数需要传入一个指向Buffer Pool的指针。
buf_block_alloc--
|
-- buf_pool_from_array # 如果传入的buf_pool 为空指针,则会从buffer pools 中找一个buffer pool
|
-- buf_LRU_get_free_block # 从buf_pool 中获得空闲块
| |
| -- buf_LRU_get_free_only # 如果free list 中有可用block,则获取,校验并memset之后return
| |
| -- buf_flush_wait_batch_end # 如果double write buffer 启用并且此时后台线程正在进行LRU flush,则等待其结束
| |
| -- buf_LRU_scan_and_free_block # 如果前面的步骤尝试从free list 获取可用block失败,则从LRU list 中尝试获取,第一轮迭代中只检查LRU的尾部,之后的迭代会遍历整个LRU
| |
| -- buf_flush_single_page_from_LRU # 如果前面的尝试都失败,则尝试从LRU list flush 一个页面
|
-- buf_block_set_state(block, BUF_BLOCK_MEMORY) # 设置新创建的block 状态为 BUF_BLOCK_MEMORY
接下来看一下真正进行磁盘文件读写操作的函数 buf_page_get
,在buf0buf.h
中,这是一个宏定义:
#define buf_page_get(SP, ZS, OF, LA, MTR) buf_page_get_gen(\
SP, ZS, OF, LA, NULL,\
BUF_GET, __FILE__, __LINE__, MTR)
最终调用的是 buf_page_get_gen
这个函数,首先来看一下这个函数的声明:
UNIV_INTERN
buf_block_t*
buf_page_get_gen(
/*=============*/
ulint space, /*!< in: space id */
ulint zip_size,/*!< in: compressed page size in bytes
or 0 for uncompressed pages */
ulint offset, /*!< in: page number */
ulint rw_latch,/*!< in: RW_S_LATCH, RW_X_LATCH, RW_NO_LATCH */
buf_block_t* guess, /*!< in: guessed block or NULL */
ulint mode, /*!< in: BUF_GET, BUF_GET_IF_IN_POOL,
BUF_PEEK_IF_IN_POOL, BUF_GET_NO_LATCH, or
BUF_GET_IF_IN_POOL_OR_WATCH */
const char* file, /*!< in: file name */
ulint line, /*!< in: line where called */
mtr_t* mtr) /*!< in: mini-transaction */
传入的参数包括tablespace id、针对压缩页面的大小、页面的偏移位置、读写锁、获取模式、目标文件的名称以及当前所处的mini transaction。其中 mode
有以下几种:
-
BUF_GET
:总是获取 -
BUF_GET_IF_IN_POOL
:如果在Buffer Pool 中则获取 -
BUF_PEEK_IF_IN_POOL
:如果在Buffer Pool 中则获取,相比于上面的多一个PEEK
,指的是不会导致页面在LRU list中从old 区到yound 区 -
BUF_GET_NO_LATCH
:不加锁获取 -
BUF_GET_IF_IN_POOL_OR_WATCH
:如果在Buffer Pool中则获取,否则给page 加watch(watch 类型page 提供给purge线程使用) -
BUF_GET_POSSIBLY_FREED
:总是获取,不关心page是否已经被free掉
接下来梳理以下该函数的执行流程。
buf_page_get_gen ---
|
|
-- buf_pool_get(space, offset) # 通过tablespace id 以及页面的偏移获得当前所属的buffer pool,计算方式为:(space_id << 20 + space_id + page_no >> 6) % instance_num
|
|
-- buf_page_hash_get_low # 通过page hash 尝试查找页面的控制块,如果没有找到返回null
|
|
-- buf_pool_watch_set # 如果前面的步骤block没有找到,并且当前的模式是BUF_GET_IF_IN_POOL_OR_WATCH,则为该页面添加watch
|
|
-- # 如果当前的模式为 BUF_GET_IF_IN_POOL、BUF_PEEK_IF_IN_POOL、BUF_GET_IF_IN_POOL_OR_WATCH,则返回null
|
|
-- buf_read_page-
| |
| |
| -- buf_read_page_low # 采用AOI 同步模式读取,减少线程切换
| |
| |
| -- buf_LRU_stat_inc_io # 增加I/O计数,用于LRU策略
-- buf_read_ahead_random # 如果Buf_read_page成功,则对非system header page、bitmap page 预读
|
|
-- # 如果当前block为 BUF_BLOCK_ZIP_PAGE或者 BUF_BLOCK_ZIP_DIRTY 执行
| |
| |
| -- buf_LRU_get_free_block # 和前面讲到的buf_page_alloc 调用的buf_LRU_get_free_block函数相同
|
-- buf_relocate # 将压缩页面解压到block->page
|
|
-- block->lock_hash_val = lock_rec_hash(space, offset) # 为page 计算哈希
|
|
-- buf_unzip_LRU_add_block # 将解压后的page 放到unzip LRU list的头部(非old 区)
小结
以上对InnoDB Buffer Pool 基本的page、chunk的数据结构以及主要函数的流程做了介绍,不过并未涉及到管理压缩页面的buddy 系统以及处理半写问题的double write buffer,详细内容可以参考[1]。
接下来,通过CMU 15-445 的Bustub 实现一个具备基本功能的Buffer Pool,project的具体要求说明详见 https://15445.courses.cs.cmu.edu/fall2020/project1/。
DIY
实现目标与代码结构
接下来要实现的包括基本的Buffer Pool 内存页面以及LRU list的管理。首先来看一下要实现的LRU管理的相关函数,以下将内存中管理的页面成为frame,对应磁盘上的页面称为page。
LRU 部分需要实现以下函数:
-
Victim
:删除LRU list末尾的frame -
Pin
:被Pin 住的页面需要从LRU中移除,因为此时有线程正在使用这个页面 -
Unpin
:表示此时没有线程使用该页面,可以放到LRU list里面 -
Size
:返回当前LRU list的实际存放的页面个数
Buffer Pool Manager 需要实现以下函数:
-
FetchPageImpl
:根据page_id 尝试获取页面,如果不存在,则需要尝试从free list 或者 LRU list 中找到可用frame 并从磁盘加载page -
NewPageImpl
:创建一个新的page -
UnpinPageImpl
:某个线程结束对某frame的使用,pin_count减1,如果pin_count等于0,则需要移入到LRU list中 -
FlushPageImpl
:强制将frame写到对应的磁盘页面上 -
DeletePageImpl
:尝试删除内存中某个page相关的数据,并将对应的frame放到free list中,如果此时有其他线程正在使用这个页面,则不能删除 -
FlushAllPagesImpl
:将所有内存中frame的数据写到对应磁盘页面上
在系统启动后,一开始所有的可用frame 都在free list 中,buffer pool manager 中 pages_
存储这些frame以及控制信息,并且有一个page_table_
记录page 编号到 frame编号的映射关系。此外还有用于操作磁盘的disk_manager
、记录日志的log_manager
。
LRU replacer 几个函数的实现比较简单,链表使用 STL 的 list,并且使用一个unordered_map 记录frame 与 list iterator 之间的映射。函数的具体实现如下:
bool LRUReplacer::Victim(frame_id_t *frame_id) {
if (this->real_len_ <= 0) {
return false;
}
*frame_id = this->frm_lst_.back();
this->mp_.erase(*frame_id);
this->frm_lst_.pop_back();
this->real_len_--;
return true;
}
void LRUReplacer::Pin(frame_id_t frame_id) {
if (this->mp_.find(frame_id) == this->mp_.end()) {
return;
}
this->frm_lst_.erase(this->mp_[frame_id]);
this->mp_.erase(frame_id);
this->real_len_--;
}
void LRUReplacer::Unpin(frame_id_t frame_id) {
if (this->mp_.find(frame_id) != this->mp_.end()) {
return;
}
this->frm_lst_.push_front(frame_id);
this->mp_.insert(std::make_pair(frame_id, this->frm_lst_.begin()));
this->real_len_++;
}
size_t LRUReplacer::Size() { return this->real_len_; }
Buffer pool manager的实现需要使用到上面的LRU。在buffer pool manager 中有一个mutex用于处理并行访问。不过感觉控制粒度缩小到frame级别会更好一点,此外对page_table_的访问做并发控制。Page 有读写锁,实现的方式为当有写操作正在进行时,其他的读操作等待;只要有一个读操作正在进行,写操作等待。
按照代码中预设的函数实现会有部分重复的地方,所以下面把可以重用的代码提取,独立出来三个函数,分别是find_page_by_id
、find_avail_frame
以及replace_page
。这三个函数的声明如下:
/**
* Find page with page_id
* @param[in] page_id the page id of the page
* @param[out] frm the frame index of the page
* @return the pointer of the page
*/
Page *find_page_by_id(page_id_t page_id, frame_id_t *frm);
/**
* Find available frame from free_list and LRU list
* @return available frame's id
*/
frame_id_t find_avail_frame();
/**
* Take a frame for another use
* @param page the page will be used
* @param new_page_id the page will be filled with new page's data
* @param target_frame the frame the page will be placed
* @param is_need_read whether load data from disk
* @param pin_count the pin_count for the page
* @return the pointer to the page after been processed
*/
Page *replace_page(Page *page, page_id_t new_page_id, frame_id_t target_frame, bool is_need_read = false,
int pin_count = 1);
以下是buffer pool manager 前面提到的几个函数的具体实现,其中__glibc_unlikely
为分支预测,可以帮助编译器优化。不过需要在比较确定的情况下使用,使用不当可能会负优化。
Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
// 1. Search the page table for the requested page (P).
// 1.1 If P exists, pin it and return it immediately.
// 1.2 If P does not exist, find a replacement page (R) from either the free list or the replacer.
// Note that pages are always found from the free list first.
// 2. If R is dirty, write it back to the disk.
// 3. Delete R from the page table and insert P.
// 4. Update P's metadata, read in the page content from disk, and then return a pointer to P.
frame_id_t frm = -1;
std::unique_lock<std::mutex> unq_lk(this->latch_);
Page *page = find_page_by_id(page_id, &frm);
if (page != nullptr) {
page->pin_count_++;
} else if ((frm = find_avail_frame()) != -1) {
page = &this->pages_[frm];
replace_page(page, page_id, frm, true);
}
return page;
}
bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
frame_id_t frm = -1;
std::unique_lock<std::mutex> unq_lk(this->latch_);
Page *page = find_page_by_id(page_id, &frm);
if (page->GetPinCount() == 0) {
return false;
}
if (--page->pin_count_ == 0) {
this->replacer_->Unpin(frm);
}
page->is_dirty_ = is_dirty;
return true;
}
bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
// Make sure you call DiskManager::WritePage!
frame_id_t frm = -1;
std::unique_lock<std::mutex> unq_lk(this->latch_);
Page *page = find_page_by_id(page_id, &frm);
page->WLatch();
this->disk_manager_->WritePage(page_id, page->GetData());
page->WUnlatch();
page->is_dirty_ = false;
return true;
}
Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
// 0. Make sure you call DiskManager::AllocatePage!
// 1. If all the pages in the buffer pool are pinned, return nullptr.
// 2. Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
// 3. Update P's metadata, zero out memory and add P to the page table.
// 4. Set the page ID output parameter. Return a pointer to P.
std::unique_lock<std::mutex> unq_lk(this->latch_);
*page_id = this->disk_manager_->AllocatePage();
frame_id_t frm = find_avail_frame();
if (frm == -1) {
this->disk_manager_->DeallocatePage(*page_id);
return nullptr;
}
return replace_page(&this->pages_[frm], *page_id, frm);
}
bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
// 0. Make sure you call DiskManager::DeallocatePage!
// 1. Search the page table for the requested page (P).
// 1. If P does not exist, return true.
// 2. If P exists, but has a non-zero pin-count, return false. Someone is using the page.
// 3. Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
std::unique_lock<std::mutex> unq_lk(this->latch_);
this->disk_manager_->DeallocatePage(page_id);
frame_id_t frm = -1;
Page *page = find_page_by_id(page_id, &frm);
if (__glibc_unlikely(page == nullptr)) {
return true;
}
if (page->GetPinCount() > 0) {
return false;
}
this->page_table_.erase(page_id);
page->page_id_ = INVALID_PAGE_ID;
page->ResetMemory();
page->pin_count_ = 0;
page->is_dirty_ = false;
this->free_list_.push_front(frm);
return true;
}
void BufferPoolManager::FlushAllPagesImpl() {
// You can do it!
for (size_t i = 0; i < this->pool_size_; ++i) {
Page *page = &this->pages_[i];
page->WLatch();
this->disk_manager_->WritePage(this->pages_[i].GetPageId(), this->pages_[i].GetData());
page->WUnlatch();
}
}
Page *BufferPoolManager::find_page_by_id(page_id_t page_id, frame_id_t *frm) {
auto res = page_table_.find(page_id);
if (__glibc_likely(res != page_table_.end())) {
*frm = res->second;
return &this->pages_[res->second];
}
return nullptr;
}
frame_id_t BufferPoolManager::find_avail_frame() {
frame_id_t ans = -1;
if (!this->free_list_.empty()) {
ans = this->free_list_.front();
this->free_list_.pop_front();
} else {
this->replacer_->Victim(&ans);
}
return ans;
}
Page *BufferPoolManager::replace_page(Page *page, page_id_t new_page_id, frame_id_t target_frame, bool is_need_read,
int pin_count) {
// Before replace, check if the page need to flush to disk
BUSTUB_ASSERT(page != nullptr, "Assert page non null!");
if (page->IsDirty()) {
page->WLatch();
this->disk_manager_->WritePage(page->GetPageId(), page->GetData());
page->WUnlatch();
}
this->page_table_.erase(page->GetPageId());
page->page_id_ = new_page_id;
page->ResetMemory();
page->is_dirty_ = false;
page->pin_count_ = pin_count;
if (is_need_read) {
page->RLatch();
this->disk_manager_->ReadPage(new_page_id, page->data_);
page->RUnlatch();
}
this->page_table_.insert(std::make_pair(new_page_id, target_frame));
return page;
}
参考
[1] MySQL · 引擎特性 · InnoDB Buffer Pool
[2] MySQL · 引擎特性 · InnoDB Buffer Pool 浅析
[3] HugeTLB Pages
[4] System V Shared Memory
[5] mmap(2) — Linux manual page