最開始學Oracle的時候,有個概念叫SGA和PGA,是非常重要的概念,其實就是內存中的緩沖池。InnoDB的設計類似於Oracle,也會在內存中開辟一片緩沖池。眾所周知,CPU的速度和磁盤的IO速度相差可以用鴻溝來形容,因此聰明的前輩們使用了內存這個ROM來彌補這道鴻溝,那麼數據庫的設計者們也繼承了這個優良的設計理念,在內存中開辟了一片區域,存放緩沖數據,提高數據庫效率。
可以將磁盤的緩沖區理解成一個簡單的模型--由數據塊組成的一片區域,數據塊(block/page)默認大小是16KB。那麼現在可以畫出一個好理解的模型出來了:
這裡的每一個格子都代表一個page。在代碼裡這個區域有兩個關鍵的數據結構:buf_pool_struct和buf_block_struct。其中buf_pool_struct是緩沖池的數據結構,buf_block_struct是數據塊的數據結構。
對於緩沖池的管理,InnoDB維護了一個free鏈表,該鏈表中記錄了沒有被使用的內存塊,每次申請數據塊都是要從free鏈表中取。但是,一般來說數據庫的緩沖池都會比實際數據量小,因此緩沖池總有用完的一天,也就是說free鏈表的所有頁都被分配完了,這個時候另一個數據結構開始發揮作用--LRU鏈表。
LRU是一個經典的算法,全稱是最近最少使用(Lastest Least Used)。使用最頻繁的頁總是在鏈表的前面,而最後的頁就是要被釋放掉的頁。然而InnoDB沒有采用這種大路貨,而是另辟蹊徑的搞了個改進版的LRU,有人管他叫做midpoint LRU,是這樣的:
InnoDB的主要改進點在於每次將磁盤上讀出的數據不是直接放到鏈表的頭部,而是放在鏈表的3/8處(該值可配置),只有在下次訪問該頁時,才會將該頁移動到鏈表頭部。這樣改進的原因在《MySQL內核--InnoDB存儲引擎》一書中有論述(p250)。這個鏈表就被分為了兩部分,midpoint前叫做young list,midpoint後叫做old list。鏈表尾部的數據塊會被釋放掉,buf_LRU_search_and_free_block函數會完成這個操作:
block = UT_LIST_GET_LAST(buf_pool->LRU); while (block != NULL) { ut_a(block->in_LRU_list); mutex_enter(&block->mutex); freed = buf_LRU_free_block(block); mutex_exit(&block->mutex); if (freed) { break; }
上面代碼片段裡體現了上面說的釋放過程。
之前說的所有都是建立在一個假設上--free鏈表中的頁分配完。那麼數據庫剛啟動的時候,free鏈表有充足的頁可以去分配,InnoDB是如何運作的呢?
buf_LRU_add_block函數的注釋中明確寫道,該函數用於將block加入LRU list中。因此任何將block加入LRU的操作都是該函數完成的,無論free鏈表是否還有頁可以被分配。在查看這個函數的時候我注意到了一個常量:BUF_LRU_OLD_MIN_LEN。在5.1.73的代碼裡它被設置成80。該函數會判斷block的young標記,在系統初始化時,這個函數會將所有的block置為young,並放在鏈表頭部,直到LRU鏈表的長度大於等於BUF_LRU_OLD_MIN_LEN。
在LRU長度大於等於BUF_LRU_OLD_MIN_LEN之後,InnoDB會將LRU中所有的頁置為old(buf_LRU_old_init),然後調用buf_LRU_old_adjust_len函數去調整位置,直到鏈表呈現上面的狀態。下面是代碼:
void buf_LRU_old_adjust_len(void) /*========================*/ { ulint old_len; ulint new_len; ut_a(buf_pool->LRU_old); ut_ad(mutex_own(&(buf_pool->mutex))); ut_ad(3 * (BUF_LRU_OLD_MIN_LEN / 8) > BUF_LRU_OLD_TOLERANCE + 5); for (;;) { old_len = buf_pool->LRU_old_len; new_len = 3 * (UT_LIST_GET_LEN(buf_pool->LRU) / 8); ut_a(buf_pool->LRU_old->in_LRU_list); /* Update the LRU_old pointer if necessary */ if (old_len < new_len - BUF_LRU_OLD_TOLERANCE) { buf_pool->LRU_old = UT_LIST_GET_PREV( LRU, buf_pool->LRU_old); (buf_pool->LRU_old)->old = TRUE; buf_pool->LRU_old_len++; } else if (old_len > new_len + BUF_LRU_OLD_TOLERANCE) { (buf_pool->LRU_old)->old = FALSE; buf_pool->LRU_old = UT_LIST_GET_NEXT( LRU, buf_pool->LRU_old); buf_pool->LRU_old_len--; } else { ut_a(buf_pool->LRU_old); /* Check that we did not fall out of the LRU list */ return; } } }
可以看出來,函數采用了一個無條件循環不停地移動buf_pool->LRU_old的位置,直到滿足了條件。
至於LRU鏈表的插入操作,其實很簡單,就是每次將新插入的頁放置到buf_pool->LRU_old的next位置,以後再次訪問該數據頁的時候,調用buf_LRU_make_block_young函數將其移動到鏈表的頭部。
UT_LIST_INSERT_AFTER(LRU, buf_pool->LRU, buf_pool->LRU_old, block);
UT_LIST_INSERT_AFTER的注釋裡寫的很明白:Inserts a NODE2 after NODE1 in a list. 這裡的node1是指buf_pool->LRU_old,node2是指block。而buf_LRU_make_block_young函數中關鍵的一步:
UT_LIST_ADD_FIRST(LRU, buf_pool->LRU, block);
UT_LIST_ADD_FIRST的注釋裡這麼寫道:Adds the node as the first element in a two-way linked list.
至此基本上了解了一個數據頁是如何被讀取到內存中的。總結一下,從啟動開始的過程如下:
1 系統初始化時,free鏈表中的所有頁都可以被分配。
2 有數據請求的時候,將從磁盤讀取到的block放入LRU鏈表中,該操作直接將所有的block置為young並插入鏈表頭部,直到LRU長度達到BUF_LRU_OLD_MIN_LEN。
3 當LRU長度達到BUF_LRU_OLD_MIN_LEN時,InnoDB會做如下操作:
3.1 將所有的LRU塊都置為old(buf_LRU_old_init)
3.2 調度buf_LRU_old_adjust_len函數,將buf_pool->LRU_old調整到合適的位置。
4 之後,每次有新的頁要插入LRU時,調度buf_LRU_add_block函數,並將old標記為true,將該頁插入到buf_pool->LRU_old的next位置
5 若第四步中的數據頁再次被訪問,InnoDB調度buf_LRU_make_block_young函數將該頁放到LRU鏈表頭部。
6 free鏈表分配完,此時需要從LRU尾部尋找可以釋放的block,該操作由buf_LRU_search_and_free_block執行。
tips:
這裡需要注意一點,LRU鏈表尾部的block確實可以被釋放,但是要滿足兩個前提:頁不是髒的;頁沒有被其他線程使用。因為髒頁總是要刷新到磁盤的,所以當髒頁要被替換的時候,需要首先將其刷入磁盤中。用於釋放尾部block的函數buf_LRU_free_block中有一個約束:
if (!buf_flush_ready_for_replace(block)) { return(FALSE); }
如果該頁不滿足條件,就會返回false,那麼這個時候,buf_LRU_search_and_free_block函數就會繼續尋找尾部block的上一個block:
block = UT_LIST_GET_PREV(LRU, block)
然後繼續判斷該block是否能被釋放。完整的代碼如下,我自己加了部分注釋:
ibool buf_LRU_search_and_free_block( /*==========================*/ /* out: TRUE if freed */ ulint n_iterations) /* in: how many times this has been called repeatedly without result: a high value means that we should search farther; if value is k < 10, then we only search k/10 * [number of pages in the buffer pool] from the end of the LRU list */ { buf_block_t* block; ulint distance = 0; ibool freed; mutex_enter(&(buf_pool->mutex)); freed = FALSE; block = UT_LIST_GET_LAST(buf_pool->LRU); while (block != NULL) { ut_a(block->in_LRU_list); mutex_enter(&block->mutex); freed = buf_LRU_free_block(block); //該函數會首先判斷block能否被釋放 mutex_exit(&block->mutex); if (freed) { //如果上面判斷頁不能被釋放,這裡的循環就不能跳出 break; } block = UT_LIST_GET_PREV(LRU, block); //尾部的頁不能被釋放,尋找其前面的block,繼續循環 distance++; if (!freed && n_iterations <= 10 && distance > 100 + (n_iterations * buf_pool->curr_size) / 10) { buf_pool->LRU_flush_ended = 0; mutex_exit(&(buf_pool->mutex)); return(FALSE); } } if (buf_pool->LRU_flush_ended > 0) { buf_pool->LRU_flush_ended--; } if (!freed) { buf_pool->LRU_flush_ended = 0; } mutex_exit(&(buf_pool->mutex)); return(freed); }
這兩天都在看InnoDB的緩沖池源碼,暫時來說只有這一點收獲。這裡使用的C語言雖然超過了我的認識水平(我基本上只能看懂簡單的C代碼,有指針勉強能懂),但是加上注釋和參考資料,還是感覺比簡單的看文檔要來的痛快的多。