9---innodb動態數組的實現 · 思考mysql內核之初級系列

在上一篇，bingxi和alex聊了關于list的內容。在本篇里，bingxi和alex會聊到innodb的動態數組，也稱為dyn。對應的文件為： D:/mysql-5.1.7-beta/storage/innobase/include/dyn0dyn.h D:/mysql-5.1.7-beta/storage/innobase/include/dyn0dyn.ic D:/mysql-5.1.7-beta/storage/innobase/dyn/dyn0dyn.c ## 1)常用結構體 Alex：“bingxi，我們前兩篇聊了常用結構hash、list，這兩個結構很常見。我們快要開始聊文件空間存儲了，在那里面有一個常用結構，我們看一下fsp0fsp.c中函數，比如fsp_get_space_header函數，調用參數里面有mtr_t。 ~~~ /************************************************************************** Gets a pointer to the space header and x-locks its page. */ UNIV_INLINE fsp_header_t* fsp_get_space_header( /*=================*/ ???????????????????? /* out: pointer to the space header, page x-locked */ ?????? ulintid,?? /* in: space id */ ?????? mtr_t*???? mtr)/* in: mtr */ ~~~ 我們接著看一下mtr_struct的定義，在結構體的定義前一行，我們可以看到Mini-transaction，稱為mini事務。用于鎖信息、mtr日志信息。 ~~~ /* Mini-transaction handle and buffer */ struct mtr_struct{ ?????? ulint??????? state;?????? /* MTR_ACTIVE, MTR_COMMITTING, MTR_COMMITTED */ ?????? dyn_array_t??? memo;??? /* memo stack for locks etc. */ ?????? dyn_array_t??? log;? /* mini-transaction log */ ?????? ibool????????????? modifications; ??????????????????????????? /* TRUE if the mtr made modifications to ??????????????????????????? buffer pool pages */ ?????? ulint??????? n_log_recs; ??????????????????????????? /* count of how many page initial log records ??????????????????????????? have been written to the mtr log */ ?????? ulint??????? log_mode; /* specifies which operations should be ??????????????????????????? logged; default value MTR_LOG_ALL */ ?????? dulint???????????? start_lsn;/* start lsn of the possible log entry for ??????????????????????????? this mtr */ ?????? dulint???????????? end_lsn;/* end lsn of the possible log entry for ??????????????????????????? this mtr */ ?????? ulint??????? magic_n; }; ~~~ 我們將要開始fsp0fsp.c的內容，為了便于內容的獨立，會將mtr的內容先剝離，在講完存儲之后，會繼續講B樹，然后會到事務。 ” Bingxi：“alex，我贊同這一點。不過我認為還是把該結構體中的一個常用算法講下，就是動態數組，mtr_t結構體中會有兩個這樣的結構成員： dyn_array_t??? memo;??? /* memo stack for locks etc. */ dyn_array_t??? log;? /* mini-transaction log */ 所謂動態數組，就是一個動態的虛擬線性數組，數組的基本元素是byte，主要用于存放mtr的鎖信息以及log。如果對于一個block數組不夠存放時，需要增加新的block，每個block對應的存放數據字段的長度是固定的(默認值是512)，但是不一定會用完。假設已經用了500個字節，這時候需要繼續存放18個字節的內容，就會在該塊中存放不了，會產生一個新的block用于存放。從而前一個block使用值為500。我們先看了結構體的定義： ~~~ typedef struct dyn_block_struct??????????? dyn_block_t; typedef dyn_block_t??????????????????? dyn_array_t; …… /*#################################################################*/ /* NOTE! Do not use the fields of the struct directly: the definition appears here only for the compiler to know its size! */ struct dyn_block_struct{ ?????? mem_heap_t*heap;?????? /* in the first block this is != NULL ??????????????????????????? if dynamic allocation has been needed */ ?????? ulint??????? used;?????? /* number of data bytes used in this block */ ?????? byte??????? data[DYN_ARRAY_DATA_SIZE]; ??????????????????????????? /* storage for array elements */???? ?????? UT_LIST_BASE_NODE_T(dyn_block_t) base; ??????????????????????????? /* linear list of dyn blocks: this node is ??????????????????????????? used only in the first block */ ?????? UT_LIST_NODE_T(dyn_block_t) list; ??????????????????????????? /* linear list node: used in all blocks */ #ifdef UNIV_DEBUG ?????? ulint??????? buf_end;/* only in the debug version: if dyn array is ??????????????????????????? opened, this is the buffer end offset, else ??????????????????????????? this is 0 */ ?????? ulint??????? magic_n; #endif }; ~~~ 在這個結構體中，我們可以看到上一篇聊到的list結構，可以通過list查找prev、next。 Alex，這里面就帶來了一些問題：1) dyn_array_t與dyn_block_t是同樣的定義，而一個動態數組只有一個首結點，那么UT_LIST_BASE_NODE_T(dyn_block_t) base成員是不是每個結構體都是有效的，2）一開始分配的時候只分配了一個結構體，也就是512字節的大小，如果不夠用，則擴展了一個，插入到鏈表里面，鏈表成員是1個還是2個？3）使用的時候，如何判斷一個block已經使用滿了，比如前面我們說到一個情況：500個字節剩下了12個不夠18個時候，產生了一個新的block，假設這時候要使用其中的10個字節，兩個block都是符合，用哪個？如果用后一個，怎么標識前一個是滿的。 ” Alex：“你的問題太多了，呵呵。我們先放下問題，看一下動態數組的初始化過程。這里面，我們還需要主意一點。雖然數據結構用的是同一個dyn_block_struct，但是我們稱第一個節點為arr，表明這個是動態數據的頭節點。其它的節點，我們稱為block節點。現在開始進行debug，在mtr0mtr.ic文件中的mtr_start函數體內設置斷點，這里也是動態數組創建的唯一入口，設置斷點進行調試。 ~~~ /******************************************************************* Starts a mini-transaction and creates a mini-transaction handle and a buffer in the memory buffer given by the caller. */ UNIV_INLINE mtr_t* mtr_start( /*======*/ ???????????????????? /* out: mtr buffer which also acts as ???????????????????? the mtr handle */ ?????? mtr_t*???? mtr)/* in: memory buffer for the mtr buffer */ { ??? //會創建兩個動態數組，在兩個創建的任一個設置斷點 ?????? dyn_array_create(&(mtr->memo)); ?????? dyn_array_create(&(mtr->log)); ? ?????? mtr->log_mode = MTR_LOG_ALL; ?????? mtr->modifications = FALSE; ?????? mtr->n_log_recs = 0; #ifdef UNIV_DEBUG ?????? mtr->state = MTR_ACTIVE; ?????? mtr->magic_n = MTR_MAGIC_N; #endif ?????? return(mtr); }??????????? ~~~ 點擊F11進入函數，查看動態數據的創建過程: ~~~ /************************************************************************* Initializes a dynamic array. */ UNIV_INLINE dyn_array_t* dyn_array_create( /*=============*/ ??????????????????????????? /* out: initialized dyn array */ ?????? dyn_array_t*? arr)? /* in: pointer to a memory buffer of ??????????????????????????? size sizeof(dyn_array_t) */ { ?????? ut_ad(arr); ?????? ut_ad(DYN_ARRAY_DATA_SIZE < DYN_BLOCK_FULL_FLAG); ?????? arr->heap = NULL; ?????? arr->used = 0; #ifdef UNIV_DEBUG ?????? arr->buf_end = 0; ?????? arr->magic_n = DYN_BLOCK_MAGIC_N; #endif ?????? return(arr); } ~~~ 執行該函數之后，結構體的情況見圖1： ![](https://box.kancloud.cn/2016-07-22_5791c9c14d83d.gif) 創建完成之后，我們就可以使用該動態數組了。作為例子，我們在mtr_memo_push函數體內設置斷點。 ~~~ /******************************************************* Pushes an object to an mtr memo stack. */ UNIV_INLINE void mtr_memo_push( /*==========*/ ?????? mtr_t*???? mtr,/* in: mtr */ ?????? void*????? object,???? /* in: object */ ?????? ulinttype)?????? /* in: object type: MTR_MEMO_S_LOCK, ... */ { ?????? dyn_array_t*???????? memo; ?????? mtr_memo_slot_t*slot; ?????? ut_ad(object); ?????? ut_ad(type >= MTR_MEMO_PAGE_S_FIX);???? ?????? ut_ad(type <= MTR_MEMO_X_LOCK); ?????? ut_ad(mtr); ?????? ut_ad(mtr->magic_n == MTR_MAGIC_N); ?????? memo = &(mtr->memo);????? //從動態中分配大小為sizeof(mtr_memo_slot_t)的空間 //然后對獲取的空間進行賦值 ?????? slot = dyn_array_push(memo, sizeof(mtr_memo_slot_t)); ?????? slot->object = object; ?????? slot->type = type; } ~~~ 從中我們可以得知dyn_array_pus是分配空間的地方（dyn_array_open函數有這樣的功能，本文后面會提到），我們按F11進入該函數體。 ~~~ /************************************************************************* Makes room on top of a dyn array and returns a pointer to the added element. The caller must copy the element to the pointer returned. */ UNIV_INLINE void* dyn_array_push( /*===========*/ ??????????????????????????? /* out: pointer to the element */ ?????? dyn_array_t*? arr,? /* in: dynamic array */ ?????? ulint??????? size)/* in: size in bytes of the element */ { ?????? dyn_block_t*? block; ?????? ulint??????? used; ? ?????? ut_ad(arr); ?????? ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N); ?????? ut_ad(size <= DYN_ARRAY_DATA_SIZE); ?????? ut_ad(size); //步驟1：取得使用的used //存在多個節點是，arr表示的是鏈表中的首節點 ?????? block = arr; ?????? used = block->used; //步驟2：如果首結點block有足夠的空間存儲，則返回指針，并修改used值。這種情況只出現在：該動態數組只有一個節點。 // used + size <= DYN_ARRAY_DATA_SIZE表示有足夠的空間存儲 ?????? if (used + size > DYN_ARRAY_DATA_SIZE) { ????????????? /* Get the last array block */ ??????? //步驟3：首結點沒有空間存儲，則取得base列表的最后一個結點 ??????? //該函數等價于：block =UT_LIST_GET_LAST(arr->base); ??????? //如果有多個節點，首先肯定不符合used + size <= DYN_ARRAY_DATA_SIZE，在后文中有描述。 ????????????? block = dyn_array_get_last_block(arr); ????????????? used = block->used; ??????? //步驟4：如果最后一個結點有足夠空間，則分配 ??????? //否則增加一個新的block ????????????? if (used + size > DYN_ARRAY_DATA_SIZE) { ???????????????????? block = dyn_array_add_block(arr); ???????????????????? used = block->used; ????????????? } ?????? } ?????? block->used = used + size; ?????? ut_ad(block->used <= DYN_ARRAY_DATA_SIZE); ?????? return((block->data) + used); } ~~~ 該函數的功能就是進行分配空間，如果有足夠的空間則分配，否則就調用函數dyn_array_add_block生成一個新的block。假象現在的情形是一個block擴展為兩個block的情況。查看該函數的實現。 ~~~ /**************************************************************** Adds a new block to a dyn array. */ dyn_block_t* dyn_array_add_block( /*================*/ ??????????????????????????? /* out: created block */ ?????? dyn_array_t*? arr)? /* in: dyn array */ { ?????? mem_heap_t*heap; ?????? dyn_block_t*? block; ?????? ut_ad(arr); ?????? ut_ad(arr->magic_n == DYN_BLOCK_MAGIC_N); //步驟1：結點是1擴展為2，還是n擴展為n+1（n>=2） // arr->heap=NULL則是1擴展為2，將自己作為首結點放在鏈表上，并分配一個內存堆 ?????? if (arr->heap == NULL) { ????????????? UT_LIST_INIT(arr->base); ????????????? UT_LIST_ADD_FIRST(list, arr->base, arr); ????? ??//1擴展為2的時候，創建一個heap，n擴展n+1（n>=2）時，則使用該heap ????????????? arr->heap = mem_heap_create(sizeof(dyn_block_t)); ?????? }???? //步驟2：取得最后一個結點，將該block的used字段進行DYN_BLOCK_FULL_FLAG與操作，表示該結點已經使用滿。每增加一個新的block總要將前一個block設置為已滿，因此只有最后一個block是可用的。即使如前文所例，500字節不夠用時創建了一個新的block，第二次有申請10個字節時，顯示顯示該塊的大小>512了，因為DYN_BLOCK_FULL_FLAG的值為：0x1000000UL ?????? block = dyn_array_get_last_block(arr); ?????? block->used = block->used | DYN_BLOCK_FULL_FLAG; ?????? heap = arr->heap; ??? //步驟3：創建一個新結點，并插入到鏈表尾 ?????? block = mem_heap_alloc(heap, sizeof(dyn_block_t)); ?????? block->used = 0; ?????? UT_LIST_ADD_LAST(list, arr->base, block); ?????? return(block); } ~~~ 1個結點擴展為2個結點后，見圖2（prev和next指向結構的首字節，便于繪圖進行了簡化，此處加以說明。list的prev和next參考前一篇文章）： ![](https://box.kancloud.cn/2016-07-22_5791c9c1678eb.gif) 2個結點擴展為3個結點，見圖3： ![](https://box.kancloud.cn/2016-07-22_5791c9c18435c.gif) 到這里，我們就解決了前面的三個問題。問題1：dyn_array_t與dyn_block_t是同樣的定義，而一個動態數組只有一個首結點，那么UT_LIST_BASE_NODE_T(dyn_block_t) base成員是不是每個結構體都是有效的？ ” Alex：“這個問題我明白，只有首結點的base是有效的。從圖1中可以看出，只有一個結點時，base是無效。圖2中，arr的base有兩個成員，首結點是第一個成員，新增加的結點在首結點的后面。圖3中，arr的base有三個成員，新增的成員在鏈表尾。” Bingxi：“問題2：一開始分配的時候只分配了一個結構體，也就是512字節的大小，如果不夠用，則擴展了一個，插入到鏈表里面，鏈表成員是1個還是2個？” Alex：“從1個擴展到2個，鏈表的成員是2。” Bingxi：“問題3：使用的時候，如何判斷一個block已經使用滿了，比如前面我們說到一個情況：500個字節剩下了12個不夠18個時候，產生了一個新的block，假設這時候要使用其中的10個字節，兩個block都是符合，用哪個？如果用后一個，怎么標識前一個是滿的。” Alex：“始終只有最后一個結點可能被使用，只有一個成員時，本身就是最后一個結點。新增結點時，會將前一個結點設置為已滿。設置方法如下： block->used = block->used | DYN_BLOCK_FULL_FLAG; 這樣進行分配操作時候，used + size > DYN_ARRAY_DATA_SIZE這個條件一定為真。表示首結點已經用滿了，然后取最后一個結點。該條件只有一種情況為否，就是動態數組只有一個成員。 ~~~ if (used + size > DYN_ARRAY_DATA_SIZE) { ????????????? /* Get the last array block */ ????????????? ????????????? block = dyn_array_get_last_block(arr); ????????????? used = block->used; ? ????????????? if (used + size > DYN_ARRAY_DATA_SIZE) { ???????????????????? block = dyn_array_add_block(arr); ???????????????????? used = block->used; ????????????? } ?????? } ~~~ ” Bingxi：“good，我現在問第4個問題：我們需要插入三個元素，我們插入一個元素，就需要修改一次used,再插入，又得調用push函數進行操作。頻繁的對dyn的數據結構進行操作。這樣的效率是很低的。” Alex：“稍等，我看下代碼。找到了，通過dyn_array_open、dyn_array_close函數可以解決這個問題。這兩個函數建議大家看下。另外，我也問你第5個問題，是不是大于512字節的數據就不能插入？” Bingxi：“這個問題，請參考函數dyn_push_string。其它的函數也看一下，養成看函數的習慣，呵呵。今天就到這兒吧。” Alex：“ok”