以下為本人在工作中的碎碎念，記錄的比較凌亂……
........................................................................
在mysql裡面有一個參數table_cache，當設置過大時，會產生明顯的效率下降。這是因為掃描open_cache哈希表時，使用的線性掃描，時間復雜度為O(n)，mysql的bug list上有人提供了一個patch（http://bugs.mysql.com/bug.php?id=33948），可以把時間降到o(1)，其基本思想是為table實例增加三個指針，來維護一個空閒鏈表。
首先，我們分析一下mysql在打開一個表時如何工作：
在mysql裡，table_cache是一個比較重要的參數。由於多線程機制，每個線程獨自打開自己需要的標的文件描述符，而不是共享已經打開的。
1. table_cache key （見create_table_def_key）
在內存裡，table cache使用hash表來存儲，key為 database_name\0table_name\0+（可選的，用於臨時表）
這裡對於臨時表會做特殊處理，需要增加額外的信息來保證臨時表在slave端是唯一的
增加8個字節：前4個字節為master thread id，後4個字節為slavb
2.打開表時候的處理：open_table
***************
必要的檢查：線程棧是否足夠，thd是否被kill
**************
全局鎖：lock_open
*************************
首先判斷是否是臨時表
*************************
這裡有一段很有意思的邏輯，當需要打開表時，總是先從臨時表鏈表中查找表。也就是說，當存在一個與實際表同名的臨時表時，會總是操作臨時表
if (!table_list->skip_temporary)
{
for (table= thd->temporary_tables; table ; table=table->next)
{
**********************************************
非臨時表，且處於pre-locked 或lock_tables mode（thd->locked_tables || thd->prelocked_mode）
即該線程已經打開或鎖定了一些表，從thd->open_tables裡查詢，當不存在時，返回error
**********************************************
if (thd->locked_tables || thd->prelocked_mode)
{ // Using table locks
TABLE *best_table= 0;
int best_distance= INT_MIN;
for (table=thd->open_tables; table ; table=table->next)
{
*******************************************************
正常情況：
1. 首先嘗試從table cache中取table
2. 當找到的TABLE實例是nam-locked的，或者一些線程正在flush tables，我們需要等待，直到鎖釋放
3. 如果不存在這樣的TABLE，我們需要創建TABLE，並將其加入到cache中
！這些操作都需要全局鎖：LOCK_open,來保護table cache和磁盤上的表定義
*******************************************************
如果這是該query打開的第一個表：設置thd->version = refresh_version，這樣，當我們打開剩余表的過程中，如果version發生了變化，則需要back off，關閉所有已經打開的並重新打開表
目前refresh_version只會被FLUSH TABLES命令改變
if (thd->handler_tables)
mysql_ha_flush(thd); //刷新（關閉並標記為re-open）所有需要reopen的表
查詢table cache的過程：
for (table= (TABLE*) hash_first(&open_cache, (uchar*) key, key_length, //基於同一個key來查找hash表
&state);
table && table->in_use ;
table= (TABLE*) hash_next(&open_cache, (uchar*) key, key_length,
&state))
{
**********************************
flush tables marked for flush.
Normally, table->s->version contains the value of
refresh_version from the moment when this table was
(re-)opened and added to the cache.
If since then we did (or just started) FLUSH TABLES
statement, refresh_version has been increased.
For "name-locked" TABLE instances, table->s->version is set
to 0 (see lock_table_name for details).
In case there is a pending FLUSH TABLES or a name lock, we
need to back off and re-start opening tables.
If we do not back off now, we may dead lock in case of lock
order mismatch with some other thread:
c1: name lock t1; -- sort of exclusive lock
c2: open t2; -- sort of shared lock
c1: name lock t2; -- blocks
c2: open t1; -- blocks
*********************************
if (table->needs_reopen_or_name_lock()) //Is this instance of the table should be reopen or represents a name-lock?
{}
}
if (table)
************
從unused_tables鏈表中移除剛找到的table
************
else
***********
創建一個新的table實例，並插入到open cache中
***********
while (open_cache.records > table_cache_size && unused_tables) //當cache滿時，從中釋放未使用的TABLE實例
hash_delete(&open_cache,(uchar*) unused_tables);
if (table_list->create) //創建一個新表
{
*******
檢查表是否存在：check_if_table_exists
*******
在table cache的hash中創建一個placeholder(占位符)：table_cache_insert_placeholder
將占位符鏈到open tables list上：
table->open_placeholder= 1;
table->next= thd->open_tables;
thd->open_tables= table;
return table
}
創建一個新的table實例
分配內存table=(TABLE*) my_malloc(sizeof(*table),MYF(MY_WME))
error= open_unireg_entry(thd, table, table_list, alias, key, key_length,
mem_root, (flags & OPEN_VIEW_NO_PARSE));
如果是視圖or error < 0 釋放內存，返回;
my_hash_insert(&open_cache,(uchar*) table)
------------------------------------------------
patch:http://bugs.mysql.com/bug.php?id=33948
增加3個指針：
hash_head:
hash_prev: always point to unused table cached items
hash_next: always point to used table cached items
修改的函數：
free_cache_entry //釋放一個表的內存。
close_thread_table //move one table to free list
reopen_name_locked_table //重新打開表，保持鏈表結構
table_cache_insert_placeholder
open_table
------------------------------------------------------------------------
總結：
增加了三個指針:
hash_head:
hash_prev:
hash_next:
!.............................!head!.........................!
head的左邊為空閒item鏈表
head的右邊為占用的item鏈表
所有item通過hash_prev和hash_next進行雙向指針
右邊的item的hash_head指向head
操作鏈表：
1)插入新空閒item：在head節點前加入
2)插入新的被占用item:在head後面加入
3)從鏈表中刪除item:
---若該item為head，修改head右側的item的hash_head指向head->next
---否則，直接刪除item，並釋放內存。。
查詢空閒節點：
1) 找到head
2) 檢測head是否in_use，為False則table = head, true則找到table = head->prev
3)當table 不為NULL時，表示找到一個item，將其插入到head右側
3) table依舊為NULL---->創建新item，將其插入到head右側
------------------------------
轉載請注明：印風
