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、 一點聲明

本文基本上是為下周組裡要來的小實習生作個介紹，是以寫得又細又淺，歡迎拍磚。可以踩，但請果斷留下意見。