MySQL源码学习：简述InnoDB的BP LRU策略

本文简要说明InnoDB的Buffer Pool(BP)的结构、基本运行方式和策略。

 

1、LRU的基本形态

       由于涉及到淘汰机制，Buffer Pool (BP)内需要一个LRU链。这个LRU链表的基本形态如下：

 

 

 

从图中看到，LRU是一个链表（双向，图中没有画出反向指针）。

同时有一个LRU_old(buf_pool->LRU_old)指针指向链表中间的一个page。 LRU_old指向的page及之后直到end的page，都被称为”old page”, 内存中bpage->old==1。

       LRU_old之前到start的所有page，被称为”young page”, 内存中bpage->old==0.

 

2、 从头开始

     a)     在系统初始化时，所有的page都是空闲的，因此全部放在buf_pool->free链表中，此时buf_pool.LRU={count = 0, start = 0x0, end = 0x0}, 当然buf_pool->LRU_old=0x0.

     b)     当有page请求时，从buf_pool->free中取出page，放入LRU中。需要注意的是，在LRU->count小于512(BUF_LRU_OLD_MIN_LEN)时，所有的page都被标为young，插入队头。

     c)     当LRU->count达到512时候，依次作如下动作

          i.     将buf_pool->LRU_old, 赋值为LRU.start, 将LRU中的所有page都设置为old (buf_LRU_old_init)

          ii.       调用buf_LRU_old_adjust_len，调整buf_pool->LRU_old的适当位置，成为上图的基本形态。默认配置下old page数目占3/8. 

     d)     有新的page再进入LRU时，先插入到LRU_old的next位置，也就是先标为old，下次访问时再调整为LRU.start，再改为young。

     e)      当BP满了以后，即LRU.count为page总数，再需要访问新的page时，就只能从LRU末尾删除，再补入。

 

3、 一点讨论

1) 步骤d中所说的”下次访问”，实际上在放入LRU之后马上会发生。在buf_page_get_gen 调用 buf_page_set_accessed_make_young，若满足条件则将此page调整为LRU.start。

需要说明一个参数buf_LRU_old_threshold_ms。当一个old page距第一次被访问的时间大于等于buf_LRU_old_threshold_ms时，再次被访问的时候，就会被调整为LRU.start.

也就是说，当buf_LRU_old_threshold_ms为默认设置的0时，新插入的page都是先放到LRU_old之后，马上被调整到LRU.start。

而这个“调整”，也不是简单的指针重赋，而是将这个page 从LRU中移除，再插入到LRU头部。而从LRU中删除page的时候，若刚好碰到临界值(<512)，会遍历整个队列，全部设置为young。

虽然都是内存操作，但整个过程显得比较粗暴。大多数的系统中并不会修改buf_LRU_old_threshold_ms的默认值，因此这个过程则一直在被重复调用。

实际上，在第一次访问page需要入LRU队列的时候，完全可以先判断一下buf_LRU_old_threshold_ms的值，若为0，则直接插入到LRU头部。对应的代码在buf_page_init_for_read中的两处调用buf_LRU_add_block(bpage, TRUE)。

 

2) 当前的调用流程

    buf_page_set_accessed_make_young(&block->page, access_time);  -->     buf_LRU_make_block_young --> buf_LRU_remove_block(bpage); buf_LRU_add_block_low(bpage, FALSE);

 

4、 一点声明

本文基本上是为下周组里要来的小实习生作个介绍，因此写得又细又浅，欢迎拍砖。可以踩，但请果断留下意见。

评论

1 楼 db_code_peon 2017-12-12  

引用

而这个“调整”，也不是简单的指针重赋，而是将这个page 从LRU中移除，再插入到LRU头部。而从LRU中删除page的时候，若刚好碰到临界值(<512)，会遍历整个队列，全部设置为young。

请问，关于这句，如果调整时，正好有512个page，然后临时移除page，这时count小于512，然后全设为young，然后这个page插到start，这时count又达到512,然后又要做“从头开始”里的c步骤？

还是临时移除不判断count是否小于512,直接插到start？