innoDB源碼閱讀筆記--緩衝池_ZenDei技術網路在線

最開始學Oracle的時候，有個概念叫SGA和PGA，是非常重要的概念，其實就是記憶體中的緩衝池。InnoDB的設計類似於Oracle，也會在記憶體中開闢一片緩衝池。眾所周知，CPU的速度和磁碟的IO速度相差可以用鴻溝來形容，因此聰明的前輩們使用了記憶體這個ROM來彌補這道鴻溝，那麼資料庫的設計者們也繼承 ...

最開始學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代碼，有指針勉強能懂），但是加上註釋和參考資料，還是感覺比簡單的看文檔要來的痛快的多。

http://www.cnblogs.com/wingsless/p/5571292.html