老刘原创文章，CSDN首发！转载请注明出处。
LRU模块组件
（1）LRU整体运行机制
完整了解bufpool子系统，必须要分模块逐个击破，以笔者目前的经验看是LRU -> flush -> buf read -> buddy allocator ->buf pool，这个顺序为宜。
首先是五模块关系图，从整体来看LRU在本系统内不仅仅是一种算法，也是一个链表，更是一个重要的组件模块。作者的这句“These statistics are not 'of' LRU but 'for' LRU.”是最好的诠释。
buf pool实例管理部分调用LRU的函数接口调用最多，读缓存、flush、伙伴系统也都有重要调用。
除此之外，存储子系统的文件表空间管理部分fil0fil.c文件也引用了LRU的其中一个函数接口。
（2）LRU链表结构和基础算法
LRU链表结构简单直接，分为old部分和头部分，这涉及到一个策略：
buf_pool_struct结构体有一个LRU_old对象，它是一个指向LRU链表“old部分”的buf_page_struct类型指针。
buf_page_t* LRU_old;
另一个对象，
ulint LRU_old_ratio;
配合宏BUF_LRU_OLD_RATIO_DIV定义buf pool的LRU链表OLD端指针的设置、old端长度，也是一个很重要的对象。
当LRU链表长度超过一定阀值后，就初始化该结构体的LRU_old对象，也就是下面这个逻辑：
UT_LIST_GET_LEN(buf_pool->LRU)== BUF_LRU_OLD_MIN_LEN
关于LRU链表的OLD部分涉及到4个宏定义：
第一个代表LRU长度达到多少个节点之后，触发LRU_old的初始化操作，长度是512；
#define BUF_LRU_OLD_MIN_LEN 512 /* 8 megabytes of 16k pages */
第二个代表buf_pool_struct结构体对象LRU_old_ratio的分母，作为决定LRU_old指针位置的一个重要定义。
#define BUF_LRU_OLD_RATIO_DIV 1024
old下限
#define BUF_LRU_OLD_RATIO_MIN 51
old上限
#define BUF_LRU_OLD_RATIO_MAX BUF_LRU_OLD_RATIO_DIV
现在把上面的信息进行合并整理，当LRU链表节点数低于BUF_LRU_OLD_MIN_LEN个数时候，LRU链表的old端不需要初始化，buf_pool_t->LRU_old=NULL;
同时buf_page_struct结构体的old对象值也是false。
上面几个宏都是在最初就完成了定义，而LRU_old_ratio是在buf pool初始化过程中完成的，由buf_pool_init（）函数内发起调用：
buf_LRU_old_ratio_update(100 * 3/ 8, FALSE);
十分明确，（LRU_old_ratio/BUF_LRU_OLD_RATIO_DIV）的预设值=3/8。
函数buf_LRU_old_ratio_update根据BUF_LRU_OLD_RATIO_DIV 和3/8的预设值计算LRU_old_ratio。相关代码：
。。。。。。
if (ratio < BUF_LRU_OLD_RATIO_MIN) {
ratio = BUF_LRU_OLD_RATIO_MIN;
} else if (ratio > BUF_LRU_OLD_RATIO_MAX) {
ratio = BUF_LRU_OLD_RATIO_MAX;
}
。。。。。。
以3/8比例计算如果大过上限值BUF_LRU_OLD_RATIO_MAX就按照上限赋值LRU_old_ratio，若小于下限值BUF_LRU_OLD_RATIO_MIN就设为下限值，使得old端长度灵活可变（也就是不一定每次调整完链表长度后old端长度都保持3/8的样子），最终可用于flush或者remove。
（3）函数分类详解
源代码的主体是43个函数，从功能角度对函数接口进行分类并综合调用关系进行梳理，基本上围绕着三方面进行，开篇曾经进行过概述：
15个重要的主函数：基本功能围绕分配块、释放块、LRU链表删除块、LRU链表添加块进行，但因为牵涉到flush机制、free空闲链表、LRU链表的old端控制、bufpool的虚拟内存磁盘置换就衍生出了多达15个供外部模块调用的主要函数接口。另外，所谓‘主函数’的称呼其实并不准确，只是按照被调用次数以及功能重要性做的一种模糊的定位，辅助函数中有很多虽然没有被外部调用，但从某种意义上来说重要性甚至更高！
14个与主函数关联密切的辅助函数：这14个函数很多都包含了上面第一类主函数的一些实现细节，是血肉的精华。
其它函数接口：43个函数中减去15个主函数和14个辅助接口之外的其余函数，归类此处暂不一一列举。
表格一栏如下，排名不分先后：
类型 | 功能 | 名称 |
主函数 | 删除给定表空间的全部页（上层接口） | buf_LRU_flush_or_remove_pages |
| 分配空闲块（上层接口） | buf_LRU_get_free_block |
| 将块加入LRU链表（上层接口） | buf_LRU_add_block |
| 释放块，从LRU删除块，并加入freeL链表 | buf_LRU_free_block |
| 释放块，从LRU删除块，并加入freeL链表（上层接口） | buf_LRU_search_and_free_block |
| 从free空闲链表获取块 | buf_LRU_get_free_only |
| 将已经完成刷新的块从LRU链表中删除并加入free链表 | buf_LRU_try_free_flushed_blocks |
| 将块放回free链表 | buf_LRU_block_free_non_file_page |
| 将块从LRU链表和hash表中删除 | buf_LRU_block_remove_hashed_page |
| 从LRU链表释放块并加入free链表（上层接口） | buf_LRU_free_one_page |
| LRU核心old参数更新 | buf_LRU_old_ratio_update |
| 将块加入到LRU头部 | buf_LRU_make_block_young |
| 将块置于LRU末端 | buf_LRU_make_block_old |
| 转储LRU页到disk | buf_LRU_file_dump |
| 从转储文件读取LRU页 | buf_LRU_file_restore |
关联辅助函数 | 删除所有buf pool中的给定表的内存页LRU链表节点 | buf_LRU_remove_all_pages |
| 删除或刷新bufpool中给定所属表空间的脏页（上层接口） | buf_flush_dirty_pages |
| 删除所属表空间脏页，是下一个函数的上层循环方法 | buf_flush_or_remove_pages |
| 删除所属表空间脏页 | buf_flush_or_remove_page |
|
| buf_LRU_drop_page_hash_for_tablespace |
| 判断是否需unzip_LRU链表末尾清理 | buf_LRU_evict_from_unzip_LRU |
| 从unzip_LRU链表释放非压缩页 | buf_LRU_free_from_unzip_LRU_list |
| 从LRU释放干净的页（实质是假如flush链表所以没有修改行为） | buf_LRU_free_from_common_LRU_list |
| 从LRU链表移除块 | buf_LRU_remove_block |
| 如果要移除的块也处于unzip_LRU，那就一起移除 | buf_unzip_LRU_remove_block_if_needed |
| 将一个块加入到LRU的末尾 | buf_LRU_add_block_to_end_low |
| 将一个块加入到LRU链表（底层实现方法） | buf_LRU_add_block_low |
| 把没有hash索引的文件页块添加到free链表 | buf_LRU_block_free_hashed_page |
| 更新buf_pool结构体重要对象LRU_old_ratio的方法 | buf_LRU_old_ratio_update_instance |
其它函数 | 暂无说明 | buf_LRU_old_init |
|
| incr_LRU_size_in_bytes |
|
| buf_LRU_old_adjust_len |
|
| 。。。。。。 |
注：1：（上层接口）表示在函数内没有实现细节或者主要实现细节，以引用其他主函数或者辅助函数完成功能。
2：函数的功能说明笔者并没有直接照搬注释，Heikki其实也是一代坑神，函数注释和功能说明有些并不详细准确，仅仅从功能概要说明是看不透方法的，甚至会觉得很多功能是多余的。
从这张表来看，会给人眼花缭乱的感觉，难以切中肯綮、直视LRU部分的函数调用主线。因此引出了下面章节，函数调用分析部分。
（4）函数调用主线详解
先做一个说明，本部分仅仅是函数调用主线和支线关系的详细分析，而不是函数详细分析。关于函数详细分析部分，本人会在完成LRU整体详细分析之后，从全部43个函数中挑选最具代表性和重要性的十余个函数，单独开辟一个章节，内容会较多，至于本节之内只会根据分析函数调用关系的需求，摘选部分源代码进行必要的、非常简略的说明。
LRU组件的函数繁杂，甚至有让人感觉有“功能交叠”的情况出现，实际上从调用关系来看并非不能通过简单直接的手段快速认知。这需要对几个函数源代码和调用展开分析：
buf_LRU_get_free_block
buf_LRU_search_and_free_block
buf_LRU_block_remove_hashed_page
buf_LRU_block_free_hashed_page
buf_LRU_flush_or_remove_pages
buf_LRU_add_block
基本上这6个函数涵盖了LRU中最重要的核心功能。
先从buf_LRU_get_free_block说起，该函数完成的作用就是一个，分配块（block）。分配的动作包含四个主函数的调用，其中三个来自LRU模块自身，一个来自flush模块的buf_flush_free_margin（作用是刷新LRU链表中的脏块，flush部分在做重点讲述）。
另外三个LRU模块的函数可以从图中看到，这四个函数都是在本函数内进行平行的调用，不是嵌套调用关系。
第一个调用buf_LRU_get_free_only，最开始分配blcok的动作都是从free链表中进行查找，如果满足条件，该函数即可直接返回了，该函数不超过40行，在buf0lru.c第1155行处开始。
第二个调用buf_LRU_search_and_free_block则要复杂的多，图里对功能的说明信息应该足够了。但要强调两点，第一点，分配块必然是从free链表处进行，即使从lru链表进行了清理动作，最后也需要把清理后的block加入到free才算完成；第二点，从lru移除链表，要么是非脏页（也就是所谓的“clean的LRU链表节点”）按照策略进行“evict”，要是脏页但是已经在flush链表中完成了刷新动作，可以移除。这两点请格外注意。
第三个调用是两个一体的函数，buf_flush_free_margin完成LRU脏页的刷新动作（上文第二点作了说明），没有完成刷新的脏页，在LRU内必然持有锁，必须等待同步或者唤醒异步IO线程完成fsync动作；至于另一个函数buf_LRU_try_free_flushed_blocks，可以看做与buf_LRU_search_and_free_block函数完全相同，属于上层接口调用。
关于buf_LRU_get_free_block函数分配块的主体调用分析已经完成了，现在开始分析buf_LRU_search_and_free_block这个函数的动作，因其内部调用支线错综复杂，且作用关键。
再来看buf_LRU_search_and_free_block函数的调用关系图。
函数首先进行两个分支的判断，buf_LRU_free_from_unzip_LRU_list完成非压缩页以及压缩页的释放（Heikki Tuuri的函数名很多时候不能反正真实作用），也就是同时释放unzip_LRU和LRU链表，buf_LRU_free_from_common_LRU_list只对压缩页的进行释放也就是仅限于LRU链表。
搞清楚了这个分支，再来看嵌套调用的下层函数buf_LRU_free_block，这个才是释放LRU的block并加入free链表的核心调用函数！图中可以看到分成两步，第一步是移除LRU链表，通过函数buf_LRU_block_remove_hashed_page完成，该函数内部存在释放LRU节点的很多细节动作与封装函数，会在下文分析；
第二步是加入free链表，通过buf_LRU_block_free_hashed_page函数完成。这两个动作在buf0lru.c的1897行到2059行之间。
。。。。。。
if(buf_LRU_block_remove_hashed_page(bpage, zip)
!= BUF_BLOCK_ZIP_FREE) {
ut_a(bpage->buf_fix_count == 0);
。。。。。。
if (have_LRU_mutex)
mutex_enter(&buf_pool->LRU_list_mutex);
mutex_enter(block_mutex);
if (b) {
mutex_enter(&buf_pool->zip_mutex);
buf_page_unset_sticky(b);
mutex_exit(&buf_pool->zip_mutex);
}
buf_LRU_block_free_hashed_page((buf_block_t*)bpage, FALSE);
再来看buf_LRU_block_remove_hashed_page函数的调用关系图，怎么完成移除LRU链表节点。
看到这里还没有晕的朋友应该是幸运且努力的，当然也可能说明老刘的作图水平可能很一般：），从一般意义应该认为LRU节点的删除操作是比较简单的，但在mysql的bufpool子系统内，LRU的管理机制为了平衡访问效率、容量限制、时效性等多方面因素必须要做很多折中的处理，hash表中存在节点信息就是为了加速定位该块。另外上文曾经说明，unzip_LRU是LRU链表的子集，移除LRU链表的一个块的同时在本函数内必须要判断该块（buf_page_t）所对应的非压缩页控制块（buf_block_t）是否也在unzip_LRU链表内，这就是前文所提到的6大链表中，5个链表（free、LRU、flush、zip_clean、zip_free[]）的节点都是buf_page_t，唯独buf_block_t处于unzip_LRU的原因。
再回过头来讲函数就应该清楚了，1清除LRU节点，2从hash表中（一个函数直接搞定），其中第一步又分为移除LRU节点和移除unizp_LRU节点两个动作，是否移除unzip_LRU节点在buf_unzip_LRU_remove_block_if_needed函数里完成，判断动作由在下一层的函数buf_page_belongs_to_unzip_LRU调用完成，函数buf_page_belongs_to_unzip_LRU在buf0buf.ic文件321行，对buf_page_t结构体对象zip的data对象、buf_page_t的状态、两个要素进行判断；
return(bpage->zip.data&&
buf_page_get_state(bpage) ==BUF_BLOCK_FILE_PAGE);
当buf_page_t状态是BUF_BLOCK_FILE_PAGE、且压缩页数据已经加载进入bufpool的LRU链表内情况下，是一定会存在于unzip_LRU链表的。
这又引出了另一个枚举结构和buf_page_struct结构体中的zip对象
enumbuf_page_state {
。。。。。。
BUF_BLOCK_ZIP_DIRTY, /*!< contains a compressed
page that isin the
buf_pool->flush_list*/
BUF_BLOCK_FILE_PAGE, /*!< contains a buffered file page */
。。。。。。
};//此处先列举2个好了，BUF_BLOCK_ZIP_DIRTY在flush链表，BUF_BLOCK_FILE_PAGE一般情况下必然在unzip_LRU链表。
struct buf_page_struct{
。。。。。。
page_zip_des_t zip; /*!<compressed page; zip.data
(butnot the data it points to) is
alsoprotected by buf_pool->mutex;
state== BUF_BLOCK_ZIP_PAGE and
zip.data== NULL means an active
buf_pool->watch*/
。。。。。。
}；//zip实际上是另一个结构体引用page_zip_des_struct，关于这个部分在存储文件系统老刘会做详细说明，此处吧zip.data看做压缩数据页的起始页帧即可。关于buf_page_struct等四个主要结构体和bufpool中的全部其余重要数据结构，也会单独开辟章节，对每一个要点进行归类和详细说明。
到现在为止，函数buf_LRU_get_free_block主线中三层嵌套调用分支中还剩一条没有做说明，也就是buf_LRU_block_free_hashed_page，来看关系图：
这应该是目前为止最简单的一层调用。
buf_LRU_block_free_non_file_page函数内，除了最终的加入free链表之外，还做了对入参buf_block_t的各项初始化。
//块状态改变，仍然涉及上文提到的枚举元素。
void* data;
buf_block_set_state(block, BUF_BLOCK_NOT_USED);
//非压缩页帧的初始化
memset(block->frame, '\0', UNIV_PAGE_SIZE);
//压缩页数据
data = block->page.zip.data;
//数据非空的情况下进行伙伴系统的内存释放
if (data) {
block->page.zip.data= NULL;
mutex_exit(&block->mutex);
//buf_pool_mutex_exit_forbid(buf_pool);
buf_buddy_free(
buf_pool,data, page_zip_get_size(&block->page.zip),
have_page_hash_mutex);
//buf_pool_mutex_exit_allow(buf_pool);
mutex_enter(&block->mutex);
page_zip_set_size(&block->page.zip,0);
}
//终于把块加到链表里了。
UT_LIST_ADD_FIRST(free,buf_pool->free, (&block->page));
到此为止，LRU块分配相关的一个调用主线buf_LRU_get_free_block、
三个调用分支的调用关系和概要流程图分析完毕了，在回顾一下，分别是：
buf_LRU_get_free_block（主线调用）
buf_LRU_search_and_free_block（二级支线，移除LRU，并加入free节点）
buf_LRU_block_remove_hashed_page（三级支线，移除LRU）
buf_LRU_block_free_hashed_page（三级支线，加入free链表）
函数整个流图老刘就不花了，如果理解了，这个图自己可以完成。
关于LRU部分的另外两条函数调用关系主（支）线buf_LRU_add_block和buf_LRU_flush_or_remove_pages复杂程度会低于buf_LRU_get_free_block很多。
buf_LRU_flush_or_remove_pages调用支线如下图所示，分成了两个基本分支，一条是BUF_REMOVE_ALL_NO_WRITE方式，一条是BUF_REMOVE_FLUSH_NO_WRITE，这两个值是枚举元素enum buf_remove_t中的对象。
enum buf_remove_t {
BUF_REMOVE_ALL_NO_WRITE,
BUF_REMOVE_FLUSH_NO_WRITE
};
本函数被fil0fil.c（文件存储子系统）部分中的删除表空间函数fil_delete_tablespace调用，用于将bufpool中的全部表空间对应的缓存页或只存在于flush链表中的缓存页清除掉。
我们先来看图右边的部分，枚举元素中的BUF_REMOVE_ALL_NO_WRITE代表的就是清除全部缓存页的动作，这一边中第一个函数buf_LRU_drop_page_hash_for_tablespace用于清除全部缓存页hash入口，buf_LRU_remove_all_pages函数完成LRU链表中给定表空间页的清理动作，实际上该函数里面隐藏了几个细节，会根据buf_page_t的oldest_modification值是否为0决定是否调用buf_flush_remove函数（flush模块的清除函数），如果oldest_modification！=0就说明做出过修改需要进行flush链表的清理；否则直接调用buf_LRU_block_remove_hashed_page，该函数上文曾经进行过详尽的分析。
。。。。。。
if (bpage->oldest_modification!= 0) {
buf_flush_remove(bpage);
}
。。。。。。
/* Remove from the LRU list. */
if(buf_LRU_block_remove_hashed_page(bpage, TRUE)
!= BUF_BLOCK_ZIP_FREE) {
buf_LRU_block_free_hashed_page((buf_block_t*)bpage, TRUE);
。。。。。。
}
。。。。。。
再来看图中左边的部分，枚举元素中的BUF_REMOVE_FLUSH_NO_WRITE，代表清理flush链表中对应要删除的表空间的缓存页，图中看复杂，实际上比右边要简单，三次单线直接完成对flush模块buf_flush_remove函数的调用，完成flush节点的删除即可。
上面的分析部分基本包含了buf_LRU_flush_or_remove_pages函数的主要细节。下面来看buf_LRU_add_block的调用支线图。
buf_LRU_add_block是buf_LRU_add_block_low的上层函数接口，实际上只是完成了调用buf_LRU_add_block_low函数的动作。
添加块到LRU链表的实质动作并不复杂，分成三个部分，LRU链表的加入，加入后根据LRU链表是否>BUF_LRU_OLD_MIN_LEN,设置old端（上文反复提到过）并调整链表长度，最后判断是否该压缩块是否存在已经decompress的块就需要加入到unzip_LRU链表当中。
if (!old|| (UT_LIST_GET_LEN(buf_pool->LRU) < BUF_LRU_OLD_MIN_LEN)) {
UT_LIST_ADD_FIRST(LRU,buf_pool->LRU, bpage);
。。。。。。
}
。。。。。。
if(buf_page_belongs_to_unzip_LRU(bpage)) {
buf_unzip_LRU_add_block((buf_block_t*)bpage, old);
}
这个函数的细节我会在buf_LRU_add_block_low的详细代码分析中给出完整版版。
到此为止LRU模块的脉络应该已经十分清晰了。这6个供外部子系统或者模块调用的函数接口并不代表LRU模块的全部重点，但优先掌握着6个主要函数的调用主线（支线）结构，对于全盘掌握LRU模块的整体结构、作用对外部模块的影响，对LRU部分设计思想的提炼起到至关重要的作用。
下一章节将对FLUSH模块进行全面分析。