MySQL 5.7 对buffer pool list scan的优化

worklog: http://dev.mysql.com/worklog/task/?id=7047

原作者innam 跳槽到twitter后 将该特性合并到webscalesql: https://github.com/webscalesql/webscalesql-5.6/commit/c834781321d97b914c3712c663bd7209175a3fe2#diff-07468177c19cc3f32d25913fe731f936r1814

在该worklog中，主要对lru list 和flush list的扫描做了优化，通过设置hazard pointer的pointer的方式，避免多线程操作同一个buffer pool导致的回溯扫描list.该优化对buffer pool小于数据集的场景比较有益。用户线程驱逐获取空闲block，用户线程在同步checkpoint时做pre flush dirty page，以及page cleaner线程之间 都可能产生冲突。

新对象

通过如下几个指针作为hazard pointer，在需要扫描list时，存储下一个即将扫描的目标page，根据不同的目的:

flush_hp: 用作对flush list batch操作

lru_hp: 用作对lru list batch 操作

lru_scan_itr: 用作从lru链表上替换驱逐一个干净的page，总是从上一次扫描结束的位置开始，而不是lru尾部。

single_scan_itr: 用作从lru上刷新或驱逐一个page, 总是从上一次结束的位置开始，而不是lru尾部

后两类的hp，在到达lru->old时，会被重置到lru尾部

初始化

在buf_pool_init_instance初始化每个bp instance时分配并初始化hp，每个bp instance都拥有自己的hp

更新hazard pointer

当某个线程对buffer pool中的page进行时，例如需要从lru中移除page时，如果当前的page被设置为hp，就要将hp更新为当前page的前一个page

flush_hp: 如下函数中调整：buf_flush_remove， buf_flush_relocate_on_flush_list，每次batch flush list后清空

lru_hp: 在函数buf_lru_adjust_hp中调整，buf_lru_remove_block, buf_relocate，每次batch lru list后清空

lru_scan_itr/single_scan_itr, 对其adjust操作同样封装在buf_lru_adjust_hp中，另外在lruitr::start中有判断是否到达lru->old,如果到达了，hp也会重新指向到lru尾部。

几个主要的更改

buf_flush_lru_list_batch

在调用函数该函数扫描page时，从尾部开始，依次通过bpage = buf_pool->lru_hp.get()来操作下一个，每操作依次page，更新lru_hp为prev

而原始逻辑中，

当可以驱逐时，每次驱逐一个page, 都需要从lru尾部重新开始扫描。

当不可以驱逐时，保存前一个page, 调用buf_flush_page_and_try_neighbors 会释放并重新获取buffer pool mutex，因此需要从page hash中再次确认prev page

——新的逻辑省略了查找page hash 以确认prev page存在的开销 (因为中间会release bp mutex)

buf_do_flush_list_batch

—同样的设置flush_hp上的page指针

—5.6原始版本中，当发现了指针被重置后，会从尾部重新扫描；而新的逻辑不会回溯链表。

从最差o(n^2) 到真正的o(n)

buf_flush_single_page_from_lru

根据buf_pool->single_scan_itr扫描lru

lruitr是lruhp的子类

增加新的行为：

—原始行为：

从lru尾部开始，找一个脏页，flush it (buf_flush_ready_for_flush, buf_flush_page)

重新扫描lru，从尾部开始，找到一个可替换的page，将其加入到free list

—现在的行为：直接在一次扫描中完成，省去一次扫描

如果发现可replace的page，直接放到free list上

否则如果发现脏页，flush it， 并加入到free list上

buf_flush_lru_tail

—— 不再按照chunk by chunk的方式flush lru

划分成chunk(每次从lru上刷100个page)的原因是因为可能有用户线程可能在函数buf_lru_get_free_block中等待flush结束，但新的逻辑中，用户线程不再需要等待batch flush操作结束。

buf_lru_get_free_block

现在逻辑：

–不再判断buffer pool是否正在进行flush lru操作，因此无需 buf_flush_wait_batch_end

—尝试从lru上释放一个空闲block到free list上 （会调用到buf_lru_free_from_common_lru_list），如果失败，则唤醒page cleaner线程

buf_lru_free_from_common_lru_list

通常为用户线程调用 （上层函数buf_lru_scan_and_free_block）来获取一个空闲block

—原始逻辑：扫描lru深度最大为srv_lru_scan_depth

—现在逻辑：扫描lru深度最大为buf_lru_search_scan_threshold(100)

使用lru_scan_itr来进行扫描，找到一个空闲的block 加入到free list 。根据官方worklog的解释，如果扫描了100个page都没有clean的，那么最好返回做一次single page flush