7---innodb的hash表實現 · 思考mysql內核之初級系列

在上一篇里面，bingxi和alex談到了文件系統管理，在結構體里面出現了兩個常用的結構：hash_table_t、UT_LIST_NODE_T。這兩個結構比較常用，在本篇里面，bingxi和alex聊了下關于hash_table_t的內容。對應的文件為： D:/mysql-5.1.7-beta/storage/innobase/ha/hash0hash.c D:/mysql-5.1.7-beta/storage/innobase/include/hash0hash.h 1)常用結構體 Bingxi：“alex，我們今天聊下hash表，所謂hash表，常用的就是通過key，然后取模然后丟到相應的bucket里面。假設bucket的數量是13個，key值對應的bucket就是key%13，相同bucket值的放在一個鏈表里面。這里需要注意一點的是，1和27具有相同的bucket值，會放在同一個bucket里面，因此查找的時候，首先找到對應的桶(bucket)，然后對該桶的鏈表進行遍歷，每個成員里面記錄了原始的key，1對應的結構里面有一個字段表示1，27對應的一個結構里面有一個字段表示27，這樣就能找到對應的成員。 ” alex：“嗯，是的，bingxi。我們來看下hash表結構。同樣地，我們將結構定義的其他元素先忽略，直接看其中的主要成員。如果需要了解其它的成員，則推薦設置debug斷點進行調試。 ~~~ /* The hash table structure */ struct hash_table_struct { ?????? …… ?????? ulint??????? n_cells;????? //hash表的成員數量，也可以稱為bucket的數量 ?????? hash_cell_t*??? array; ??? //指向桶的數組 ?????? …… }; ~~~ 結構中，就是成員的數量，以及一個數組。因為使用hash表的結構是多種多樣的，比如前幾篇文章中提到過的buf_pool_t、fil_system_t。這兩者都使用到了hash，并且成員結構不一樣。對于每個桶對應的指針類型是不確定，因此bucket中記錄的指針是void*類型的。 ~~~ struct hash_cell_struct{ ?????? void*????? node;????? /* hash chain node, NULL if none */ }; ~~~ ” Bingxi：“alex，是這樣的，這里帶來兩個問題：1、hash表的n_cells是個素數用于做模操作，在創建的時候提供一個準確的素數是有難度的，2、對應整型的key可以通過key%n_cells的方法來獲得對應的桶，那么對于字符串型的如何處理？ ” Alex：“嗯，好吧。在說這兩個問題之前，我們先看下hash表的創建過程。我們在函數fil_system_create如下面所示的行中設置一個斷點。 system->spaces = hash_create(hash_size);? //在此行設置斷開 system->name_hash = hash_create(hash_size); 然后啟動mysql，執行到該斷點處我們可以發現對應的hash_size為50。F11進入該函數體，看看具體是怎么執行的。 ~~~ /***************************************************************** Creates a hash table with >= n array cells. The actual number of cells is chosen to be a prime number slightly bigger than n. */ hash_table_t* hash_create( /*========*/ ???????????????????? /* out, own: created table */ ?????? ulintn)??? /* in: number of array cells */ { ?????? hash_cell_t*??? array; ?????? ulint??????? prime; ?????? hash_table_t*? table; ?????? ulint??????? i; ?????? hash_cell_t*??? cell; ?????? ?????? //在該例中，我們根據輸入值50(n的取值)，得到一個素數151 ?????? prime = ut_find_prime(n); ? ?????? table = mem_alloc(sizeof(hash_table_t)); ? //sizeof(hash_cell_t)的值為4 ? //生成一個有151(prime)個桶的數組 ?????? array = ut_malloc(sizeof(hash_cell_t) * prime); ?????? //初始化結構成員 ?????? table->adaptive = FALSE; ?????? table->array = array; ?????? table->n_cells = prime; ?????? table->n_mutexes = 0; ?????? table->mutexes = NULL; ?????? table->heaps = NULL; ?????? table->heap = NULL; ?????? table->magic_n = HASH_TABLE_MAGIC_N; ?????? /* Initialize the cell array */ ???//取得每一個bucket成員，將對應的node指針初始化為NULL ?????? for (i = 0; i < prime; i++) { ??? //hash_get_nth_cell(table, i)的作用是取得第i個成員，即table->array + i ????????????? cell = hash_get_nth_cell(table, i); ????????????? cell->node = NULL; ?????? } ?????? return(table); } ~~~ 執行完成之后，我們生成了system->spaces的hash表，該hash表以space id作為key，接著我們又創建了system->name_hash的hash表，這個根據space name進行hash。我們看下space name對應的hash表創建后的情形，見圖1。 ![](https://box.kancloud.cn/2016-07-22_5791c9c0e0ff0.gif) 從中我們可以看出問題1是已經解決掉了的，根據輸入值產生一個素數，另外對于space name這樣的字符串型，也是可以的，我們看下面的兩個函數調用，調用函數ut_fold_string(name)生成了對應的整型key，插入的時候如此，查找、刪除的時候也是如此。 ~~~ HASH_SEARCH(name_hash, system->name_hash, ut_fold_string(name), space, ??????????????????????????? 0 == strcmp(name, space->name)); HASH_INSERT(fil_space_t, name_hash, system->name_hash, ?????????????????????????????????? ut_fold_string(name), space); HASH_DELETE(fil_space_t, name_hash, system->name_hash, ??????????????????????????? ?? ut_fold_string(space->name), space); ~~~ ” 2）常用的函數 Bingxi：“我們繼續往下看，怎么進行hash的操作，我們先看hash表的插入操作。繼續以space為例，在函數fil_space_create中創建了space結構，然后根據space id、space name插入相應的hash表。 ~~~ /*********************************************************************** Creates a space memory object and puts it to the tablespace memory cache. If there is an error, prints an error message to the .err log. */ ibool fil_space_create( /*=============*/ ??????????????????????????? /* out: TRUE if success */ ?????? const char*???? name,????? /* in: space name */ ?????? ulint??????? id,?? /* in: space id */ ?????? ulint??????? purpose)/* in: FIL_TABLESPACE, or FIL_LOG if log */ { …… ?????? //創建space結構，并初始化成員值 ?????? space = mem_alloc(sizeof(fil_space_t)); ? ?????? space->name = mem_strdup(name); ?????? space->id = id; …… ?????? //將新創建的space結構，根據space id插入system->spaces哈希表。 ?????? HASH_INSERT(fil_space_t, hash, system->spaces, id, space); ? //將新創建的space結構，根據space name插入system->name_hash哈希表 ?????? HASH_INSERT(fil_space_t, name_hash, system->name_hash, ????????????????????????????????????????? ut_fold_string(name), space); …… ?????? return(TRUE); } ~~~ 插入操作調用的是HASH_INSERT宏，我們來看下插入space name哈希表操作的參數值。 ~~~ //函數調用 HASH_INSERT(fil_space_t, name_hash, system->name_hash, ?????????????????????????????????? ut_fold_string(name), space); //宏定義 #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA) ~~~ TYPE：表示插入hash表的結構類型，本例中的類型為fil_space_t NAME：表示的是擁有同一個bucket值的成員，通過結構體中的該字段來指向擁有同bucket值的下一個成員，這里可以這么認為，space->name_hash用于指向同bucket的下一個成員。 TABLE：需要插入的hash表，這里我們可以看到，我們插入的hash表是system->name_hash FOLD：也就是我們所說的key，通過ut_fold_string(name)函數將name轉為key，本例子中name=’./ibdata1’ DATA：插入的結構體如果查對應的bucket中沒有其他的同bucket值成員，插入后的情形是什么樣的，假設對應的bucket為1（而實際上該例對應的bucket為51，為了繪圖的方便，假設為1）。見圖2。 ![](https://box.kancloud.cn/2016-07-22_5791c9c1010ac.gif) 從圖2中，我們可以看出如下的步驟： ~~~ //步驟1，將插入成員的name_hash設置為NULL，也就是說，如果同bucket鏈表上有多個成員，也是插入到末尾 //(DATA)->NAME = NULL; Space-> name_hash=NULL //步驟2：找出所在bucket //cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE)); hash_cell_t*??? cell3333; int i= hash_calc_hash(ut_fold_string(name), system->name_hash)) cell3333 = hash_get_nth_cell(system->name_hash,i); //步驟3：如果該bucket上沒有其他的成員則將該成員插入 if (cell3333->node == NULL) { ?????? cell3333->node = space; } ~~~ ” Alex：“是這樣的，假設我們繼續插入一個space，該space對應的bucket值也為1。那么執行到上面的步驟3不符合條件的時候，需要執行步驟4 ~~~ //步驟4：如果有其它成員，則將新結點插入到末尾 struct3333 = cell3333->node; //取得鏈表上最后一個結點 while (struct3333->name_hash != NULL) { ?????? struct3333 = struct3333->name_hash;? //取得下一個結點 } //將新結點插入到最后一個結點之后 struct3333->name_hash = space; ~~~ ? 假設name為’./itest’，對應的情形見圖3. ![](https://box.kancloud.cn/2016-07-22_5791c9c119bfc.gif) 完整的代碼如下： ~~~ /*********************************************************************** Inserts a struct to a hash table. */ ? #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)/ do {/ ?????? hash_cell_t*??? cell3333;/ ?????? TYPE*?????????? struct3333;/ / ?????? HASH_ASSERT_OWNED(TABLE, FOLD)/? //這個是個斷言，不考慮 / ?????? (DATA)->NAME = NULL;/?? //將新結點的指向的下一個結點設置為NULL /?? //找到對應的bucket ?????? cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));/ /?? //如果bucket成員為空，則直接插入，否則插入到最后一個結點之后 ?????? if (cell3333->node == NULL) {/ ????????????? cell3333->node = DATA;/ ?????? } else {/ ????????????? struct3333 = cell3333->node;/ / ????????????? while (struct3333->NAME != NULL) {/ / ???????????????????? struct3333 = struct3333->NAME;/ ????????????? }/ / ????????????? struct3333->NAME = DATA;/ ?????? }/ } while (0) ~~~ ” Alex：“嗯，是這樣的。我們再看看查找吧。假設這里需要查找的是./itest對應的space結構。 ~~~ Creates a space memory object and puts it to the tablespace memory cache. If there is an error, prints an error message to the .err log. */ ibool fil_space_create( /*=============*/ ??????????????????????????? /* out: TRUE if success */ ?????? const char*???? name,????? /* in: space name */ ?????? ulint??????? id,?? /* in: space id */ ?????? ulint??????? purpose)/* in: FIL_TABLESPACE, or FIL_LOG if log */ { …… ? //查看指定name的space是否存在，假設這里的name為./itest ?????? HASH_SEARCH(name_hash, system->name_hash, ut_fold_string(name), space, ?????????????????????????????????? 0 == strcmp(name, space->name)); …… ?????? return(TRUE); } ~~~ 同樣地，HASH_SEARCH也是宏定義，我們用相應的c偽碼來查看。從中我們可以看出首先找到對應的bucket，如果沒有成員，則查找的space為空 ~~~ my_key=ut_fold_string('./itest'); void hash_search(name_hash,system->name_hash,my_key,space,0 == strcmp(name, space->name)) { ?????? HASH_ASSERT_OWNED(system->name_hash, my_key);? //可以忽略 ?????? ?????? //取得fold對應的對應的key數據桶值 ?????? //取得對應的桶 ?????? bucket_id=hash_calc_hash(my_key, system->name_hash) ?????? //取得第一個元素 ?????? space = HASH_GET_FIRST(system->name_hash, bucket_id); ?????? ?????? while(space != NULL) ?????? { ????????????? //因為不同的值，可能屬于同一個桶，因此需要判斷名稱是不是相等 ????????????? //比如圖3中的第一個成員的space->name='./ibdata1'，不相等 ????????????? //獲取下一個成員之后，再判斷該條件，就相等了 ????????????? if(0 == strcmp('./itest', space->name)) //注意，第一個參數name是前面傳遞過來的 ????????????? ｛ ????????????? ? break; //表示已經找到了對應的元素 ????????????? ｝ ????????????? else ????????????? ｛ ???????????????????? //取得鏈表中的第一個元素 ???????????????????? //space = HASH_GET_NEXT(name_hash, space); ???????????????????? space=space->name_hash; ???????????????????? ????????????? ?｝ ????????????? ?????? } ?????? //如果該桶沒有元素或者沒有匹配的成員，則space為NULL } ~~~ 查看HASH_SEARCH的定義，我們可以更容易的理解。 ~~~ /************************************************************************ Looks for a struct in a hash table. */ #define HASH_SEARCH(NAME, TABLE, FOLD, DATA, TEST)/ {/ / ?????? HASH_ASSERT_OWNED(TABLE, FOLD)/ /?? //找到對應bucket的第一個成員 ?????? (DATA) = HASH_GET_FIRST(TABLE, hash_calc_hash(FOLD, TABLE));/ / ?????? while ((DATA) != NULL) {/ ????????????? if (TEST) {/?? //要符合TEST條件 ???????????????????? break;/ ????????????? } else {/ ???????????????????? (DATA) = HASH_GET_NEXT(NAME, DATA);/ ????????????? }/ ?????? }/ } ~~~ ” Bingxi：“嗯，除了HASH_INSERT、HASH_SEARCH，還有其它的宏定義：HASH_DELETE、HASH_DELETE_AND_COMPACT 、HASH_GET_FIRST、HASH_GET_NEXT。這幾個功能的實現也建議看下。這里面就不說這個了。” Alex：“ok，今天就說到這吧。”