前言
為什麼MySQL InnoDB需要Purge操作？明确這個問題的答案，首先還得從InnoDB的并發機制開始。為了更好的支援并發，InnoDB的多版本一緻性讀是采用了基于復原段的的方式。另外，對于更新和删除操作，InnoDB并不是真正的删除原來的記錄，而是設定記錄的delete mark為1。是以為了解決資料Page和Undo Log膨脹的問題，需要引入purge機制進行回收。下面我們來描述下purge整個過程。（代碼分析基于MySQL 5.7）
Purge資料産生的背景
- Undo log和Undo history list
- Mark deleted資料
Undo log
Undo log儲存了記錄修改前的鏡像。在InnoDB存儲引擎中，undo log分為：
- insert undo log
- update undo log
insert undo log是指在insert操作中産生的undo log。由于insert操作的記錄，隻是對本事務可見，其他事務不可見，是以undo log可以在事務送出後直接删除，而不需要purge操作。
update undo log是指在delete和update操作中産生的undo log。該undo log會被後續用于MVCC當中，是以不能送出的時候删除。送出後會放入undo log的連結清單，等待purge線程進行最後的删除。
下面列出了undo log類型，後續在purge工作線程的時候會針對性的講述不同的處理方式：
-
從表中删除一行記錄
TRX_UNDO_DEL_MARK_REC (将主鍵記入日志)，在删除一條記錄時，并不是真正的将資料從資料庫中删除，隻是标記為已删除。
-
向表中插入一行記錄
TRX_UNDO_INSERT_REC (僅将主鍵記入日志)
TRX_UNDO_UPD_DEL_REC (将主鍵記入日志) 當表中有一條被标記為删除的記錄和要插入的資料主鍵相同時， 實際的操作是更新這個被标記為删除的記錄。
-
更新表中的一條記錄
TRX_UNDO_UPD_EXIST_REC (将主鍵和被更新了的字段内容記入日志)
TRX_UNDO_DEL_MARK_REC和TRX_UNDO_INSERT_REC，當更新主鍵字段時，實際執行的過程是删除舊的記錄然後，再插入一條新的記錄。
Undo history list
事務送出後，對于有update_undo的事務，首先會調用trx_serialisation_number_get函數生成一個目前最大的事務号，并且把該事務加到全局trx_serial_list連結清單中。接下來會根據該事務所在的復原段資訊
last_page_no == FIL_NULL，來決定是否講該復原段加入到purge_sys->ib_bh全局隊列當中。其次，會調用trx_undo_update_cleanup->trx_purge_add_update_undo_to_history函數，将undo log加入到history list上，同時記錄這個復原段上第一個需要purge的undo log資訊，防止rseg再次被添加到purge隊列中，然後喚醒purge線程。
/* Add the log as the first in the history list */
flst_add_first(rseg_header + TRX_RSEG_HISTORY,
undo_header + TRX_UNDO_HISTORY_NODE, mtr);
......
if (rseg->last_page_no == FIL_NULL) {
rseg->last_page_no = undo->hdr_page_no;
rseg->last_offset = undo->hdr_offset;
rseg->last_trx_no = trx->no;
rseg->last_del_marks = undo->del_marks;
} 注意insert_undo并不會放到History list上。
Mark deleted的資料可能會是由于一次delete操作或者一次update操作，InnoDB會調用btr_rec_set_deleted_flag->rec_set_deleted_flag_old/rec_set_deleted_flag_new設定record的delete标志位。
那麼可以标記為mark delete的資料都有哪些類型呢？包括主鍵記錄、二級索引記錄：
btr_cur_del_mark_set_clust_rec
btr_cur_del_mark_set_sec_rec
更新主鍵索引的情況
ha_innobase::update_row -> row_update_for_mysql -> row_upd_step -> row_upd -> row_upd_clust_step -> row_upd_clust_rec_by_insert -> btr_cur_del_mark_set_clust_rec -> row_ins_index_entry
更新非主鍵值，但是影響二級索引的情況
ha_innobase::update_row -> row_update_for_mysql -> row_upd_step -> row_upd -> row_upd_sec_step -> row_upd_sec_index_entry -> btr_cur_del_mark_set_sec_rec -> row_ins_sec_index_entry
Purge操作流程
- 建立srv_purge_coordinator_thread協調線程和srv_worker_thread工作線程
- 啟動purge流程
- 初始化purge
- purge工作線程流程
- 清理復原段undo資料
Purge線程包括協調線程和工作線程，總共數量由innodb_purge_threads設定，最大不能超過32個，線程在Innodb啟動時在函數innobase_start_or_create_for_mysql中建立。
/* Create the master thread which does purge and other utility
operations */
if (!srv_read_only_mode) {
os_thread_create(
srv_master_thread,
NULL, thread_ids + (1 + SRV_MAX_N_IO_THREADS));
}
if (!(srv_read_only_mode)
&& srv_force_recovery < SRV_FORCE_NO_BACKGROUND) {
os_thread_create(
srv_purge_coordinator_thread,
NULL, thread_ids + 5 + SRV_MAX_N_IO_THREADS);
ut_a(UT_ARR_SIZE(thread_ids)
> 5 + srv_n_purge_threads + SRV_MAX_N_IO_THREADS);
/* We've already created the purge coordinator thread above. */
for (i = 1; i < srv_n_purge_threads; ++i) {
os_thread_create(
srv_worker_thread, NULL,
thread_ids + 5 + i + SRV_MAX_N_IO_THREADS);
}
srv_start_wait_for_purge_to_start();
} else {
purge_sys->state = PURGE_STATE_DISABLED;
} 另外，啟動過程還要調用trx_purge_sys_init初始化purge_sys相關的變量和建立purge view，後續會講到purge view的作用。
purge的主要任務是将資料庫中已經mark del的資料删除，另外也會批量回收undo pages。資料庫的資料頁很多，要清除被删除的資料，不可能周遊所有的資料頁。由于所有的變更都有undo log， 是以，從undo作為切入點，在清理過期的undo的同時，也将資料頁中的被删除的記錄一并清除。 整個purge操作的入口函數是srv_do_purge->trx_purge。
-
初始化Purge的記錄：
Purge操作會克隆最老舊的read_view：purge_sys->view->open_purge()，這個purge view包括了重要的兩個資訊：
m_low_limit_no：trx_sys->trx_serial_list最小的送出事務号no，不是事務id。
m_up_limit_id：目前最老read_view中，最小的活躍事務id。
然後，開始擷取那些可以被purge掉的undo records（trx_purge_attach_undo_recs->trx_purge_fetch_next_rec），然後轉化為purge_rec， 輪流放在purge thread的上下文purge_node_t *node->undo_recs中。
那麼從什麼位置開始purge還需要關心purge_sys的兩個變量：
purge_iter_t iter; /* Limit up to which we have read and
parsed the UNDO log records. Not
necessarily purged from the indexes.
Note that this can never be less than
the limit below, we check for this
invariant in trx0purge.cc */
purge_iter_t limit; /* The 'purge pointer' which advances
during a purge, and which is used in
history list truncation */ 下面看看如何擷取更新這兩個變量：
首先，先需要确定purge_sys->iter是不能大于purge_sys->limit的，原因是由于purge->limit是用來truncate對應的undo log并且更新history list，而iter用于找到對應del的data record進行purge，我們一定要保證purge del的data後才能purge對應的undo log。
/* Track the max {trx_id, undo_no} for truncating the
UNDO logs once we have purged the records. */
if (purge_sys->iter.trx_no > limit->trx_no
|| (purge_sys->iter.trx_no == limit->trx_no
&& purge_sys->iter.undo_no >= limit->undo_no)) {
*limit = purge_sys->iter;
} 其次，需要根據purge_sys->next_stored判斷是否目前purge系統中有儲存的purge record，如果沒有就要通過purge queue中儲存的需要purge的復原段rseg來進行purge record的生成，詳細見函數trx_purge_choose_next_log。在函數trx_purge_get_rseg_with_min_trx_id會更新purge_sys->iter.trx_no成為purge rseg的last_trx_no，也就是指定復原段上最早送出的事務号。
最後，通過調用trx_purge_get_next_rec找到真正需要purge的undo log，并且更新purge_sys->iter。如果該rseg指向的last_page_no的page上并沒有其他可以需要purge的mark del的undo log，那會繼續調用trx_purge_rseg_get_next_history_log來擷取下一個history list下的undo page。
在擷取undo log的過程中，還有一個重要的判斷：
if (purge_sys->iter.trx_no >= purge_sys->view->low_limit_no()) {
return(NULL);
} 這意味着，如果purge_sys->iter的trx_no已經大于等于最老讀事務的事務送出号，就放棄該undo log的purge過程，隻處理目前已經可以purge的undo log。
目前purge一次處理的undo log為預設300個，可通過參數innodb_purge_batch_size參數調整。
-
Purge工作線程流程：
Purge工作線程啟動，是借助于MySQL中的查詢計劃圖（que0que.cc）來排程的，也就是借助了MySQL Innodb的執行Process Model。簡單可以通過代碼中的注釋了解：
舉例說明
X := 1;
WHILE X < 5 LOOP
X := X + 1;
X := X + 1;
X := 5
将會生成下面的架構，x軸代表下一個執行關系，Y軸代表父子關系
A - W - A
|
|
A - A
A = assign_node_t, W = while_node_t. 啟動并行purge的代碼流程如下：
que_run_threads->que_run_threads_low-> que_thr_step-> row_purge_step-> row_purge
每個work thread需要處理的流程如下：
row_purge->row_purge_record
case TRX_UNDO_DEL_MARK_REC:
->row_purge_del_mark->row_purge_remove_sec_if_poss
->row_purge_remove_clust_if_poss
case TRX_UNDO_UPD_EXIST_REC:
->row_purge_upd_exist_or_extern->row_purge_remove_clust_if_poss
可以看出work thread要隻需要處理兩種情況，一種是由于删除或者更新導緻的mark delete的資料能夠删除老版本，包括可能的二級索引和一級索引，另一種是處理由于更新非mark delete的資料導緻的可能的二級索引老版本。
另外還需要介紹兩個函數row_purge_parse_undo_rec，也就是從undo log裡解析出行引用資訊和其他資訊，傳回值為true表明需要執行purge操作。通過函數trx_undo_rec_get_pars獲得undo記錄的類型，主要包括以下幾個類型：
#define TRX_UNDO_INSERT_REC 11 /* fresh insert into clustered index */
#define TRX_UNDO_UPD_EXIST_REC \
12 /* update of a non-delete-marked \
record */
#define TRX_UNDO_UPD_DEL_REC \
13 /* update of a delete marked record to \
a not delete marked record; also the \
fields of the record can change */
#define TRX_UNDO_DEL_MARK_REC \
14 /* delete marking of a record; fields \
do not change */
#define TRX_UNDO_CMPL_INFO_MULT \
16 /* compilation info is multiplied by \
this and ORed to the type above */
#define TRX_UNDO_MODIFY_BLOB \
64 /* If this bit is set in type_cmpl, \
then the undo log record has support \
for partial update of BLOBs. Also to \
make the undo log format extensible, \
introducing a new flag next to the \
type_cmpl flag. */
#define TRX_UNDO_UPD_EXTERN \
128 /* This bit can be ORed to type_cmpl \
to denote that we updated external \
storage fields: used by purge to \
free the external storage */ 通過trx_undo_update_rec_get_sys_cols函數擷取對應的table_id，trx_id，和roll_ptr。另外，為了防止所有對表的DROP操作，還會對dict_operation_lock加S全局鎖。
-
Purge一級索引（row_purge_remove_clust_if_poss）：
Purge一級索引首先會嘗試樂觀删除，即直接删除leaf
row_purge_remove_clust_if_poss_low(BTR_MODIFY_LEAF)->btr_cur_optimistic_delete
失敗後，會不斷嘗試（最多100次）悲觀删除，即修改tree本身
row_purge_remove_clust_if_poss_low(BTR_MODIFY_TREE)->btr_cur_pessimistic_delete
-
Purge二級索引（row_purge_remove_sec_if_poss）：
二級索引purge時，同樣先樂觀删除（row_purge_remove_sec_if_poss_leaf），失敗再進行悲觀删除（row_purge_remove_sec_if_poss_tree）。不同的是，需要通過row_purge_poss_sec判斷該二級索引記錄是否可以被Purge，當該二級索引記錄對應的聚集索引記錄沒有delete mark并且其trx id比目前的purge view還舊時，不可以做Purge操作。