本文是對整個undo生命周期過程的闡述，代碼分析基于目前最新的mysql5.7版本。本文也可以作為了解整個undo子產品的代碼導讀。由于涉及到的子產品衆多，是以部分細節并未深入。
undo log是innodb mvcc事務特性的重要組成部分。當我們對記錄做了變更操作時就會産生undo記錄，undo記錄預設被記錄到系統表空間(ibdata)中，但從5.6開始，也可以使用獨立的undo 表空間。
undo記錄中存儲的是老版本資料，當一個舊的事務需要讀取資料時，為了能讀取到老版本的資料，需要順着undo鍊找到滿足其可見性的記錄。當版本鍊很長時，通常可以認為這是個比較耗時的操作（例如bug#69812）。
大多數對資料的變更操作包括insert/delete/update，其中insert操作在事務送出前隻對目前事務可見，是以産生的undo日志可以在事務送出後直接删除（誰會對剛插入的資料有可見性需求呢！！），而對于update/delete則需要維護多版本資訊，在innodb裡，update和delete操作産生的undo日志被歸成一類，即update_undo。
為了保證事務并發操作時，在寫各自的undo log時不産生沖突，innodb采用復原段的方式來維護undo log的并發寫入和持久化。復原段實際上是一種 undo 檔案組織方式，每個復原段又有多個undo log slot。具體的檔案組織方式如下圖所示：
上圖展示了基本的undo復原段布局結構，其中:
rseg0預留在系統表空間ibdata中;
rseg 1~rseg 32這32個復原段存放于臨時表的系統表空間中;
rseg33~ 則根據配置存放到獨立undo表空間中（如果沒有打開獨立undo表空間，則存放于ibdata中）
如果我們使用獨立undo tablespace，則總是從第一個undo space開始輪詢配置設定undo 復原段。大多數情況下這是ok的，但假設我們将復原段的個數從33開始依次遞增配置到128，就可能導緻所有的復原段都存放在同一個undo space中。(參考函數trx_sys_create_rsegs 以及 bug#74471)
每個復原段維護了一個段頭頁，在該page中又劃分了1024個slot(trx_rseg_n_slots)，每個slot又對應到一個undo log對象，是以理論上innodb最多支援 96 * 1024個普通事務。
為了便于管理和使用undo記錄，在記憶體中維持了如下關鍵結構體對象：
所有復原段都記錄在<code>trx_sys->rseg_array</code>，數組大小為128，分别對應不同的復原段；
rseg_array數組類型為trx_rseg_t，用于維護復原段相關資訊；
每個復原段對象trx_rseg_t還要管理undo log資訊，對應結構體為trx_undo_t，使用多個連結清單來維護trx_undo_t資訊;
事務開啟時，會專門給他指定一個復原段，以後該事務用到的undo log頁，就從該復原段上配置設定;
事務送出後，需要purge的復原段會被放到purge隊列上(<code>purge_sys->purge_queue</code>)。
各個結構體之間的聯系如下：
當開啟一個讀寫事務時（或者從隻讀事務轉換為讀寫事務），我們需要預先為事務配置設定一個復原段：
對于隻讀事務，如果産生對臨時表的寫入，則需要為其配置設定復原段，使用臨時表復原段（第1~32号復原段），函數入口：<code>trx_assign_rseg -->trx_assign_rseg_low-->get_next_noredo_rseg</code>。
在mysql5.7中事務預設以隻讀事務開啟，當随後判定為讀寫事務時，則轉換成讀寫模式，并為其配置設定事務id和復原段，調用函數：<code>trx_set_rw_mode -->trx_assign_rseg_low --> get_next_redo_rseg</code>。
普通復原段的配置設定方式如下：
采用round-robin的輪詢方式來賦予復原段給事務，如果復原段被标記為skip_allocation（這個undo tablespace太大了，purge線程需要對其進行truncate操作），則跳到下一個；
選擇一個復原段給事務後，會将該復原段的<code>rseg->trx_ref_count</code>遞增，這樣該復原段所在的undo tablespace檔案就不可以被truncate掉；
臨時表復原段被賦予<code>trx->rsegs->m_noredo</code>，普通讀寫操作的復原段被賦予<code>trx->rsegs->m_redo</code>；如果事務在隻讀階段使用到臨時表，随後轉換成讀寫事務，那麼會為該事務配置設定兩個復原段。
當産生資料變更時，我們需要使用undo log記錄下變更前的資料以維護多版本資訊。insert 和 delete/update 分開記錄undo，是以需要從復原段單獨配置設定undo slot。
入口函數：<code>trx_undo_report_row_operation</code>
流程如下：
判斷目前變更的是否是臨時表，如果是臨時表，則采用臨時表復原段來配置設定，否則采用普通的復原段；
臨時表操作記錄undo時不寫redo log；
操作類型為trx_undo_insert_op，且未配置設定insert undo slot時，調用函數<code>trx_undo_assign_undo</code>進行配置設定；
操作類型為trx_undo_modify_op，且未配置設定update undo slot時，調用函數<code>trx_undo_assign_undo</code>進行配置設定。
我們來看看函數trx_undo_assign_undo的流程：
首先總是從cahced list上配置設定trx_undo_t （函數<code>trx_undo_reuse_cached</code>，當滿足某些條件時，事務送出時會将其擁有的trx_undo_t放到cached list上，這樣新的事務可以重用這些undo 對象，而無需去掃描復原段，尋找可用的slot，在後面的事務送出一節會介紹到）；
對于insert，從<code>trx_rseg_t::insert_undo_cached</code>上擷取，并修改頭部重用資訊（trx_undo_insert_header_reuse）及預留xid空間（trx_undo_header_add_space_for_xid）
對于delete/update，從<code>trx_rseg_t::update_undo_cached</code>上擷取， 并在undo log hdr page上建立新的undo log header(trx_undo_header_create)，及預留xid存儲空間（trx_undo_header_add_space_for_xid）
擷取到trx_undo_t對象後，會從cached list上移除掉。并初始化trx_undo_t相關資訊（trx_undo_mem_init_for_reuse），将<code>trx_undo_t::state</code>設定為trx_undo_active
如果沒有cache的trx_undo_t，則需要從復原段上配置設定一個空閑的undo slot（trx_undo_create），并建立對應的undo頁，進行初始化；
一個復原段可以支援1024個事務并發，如果不幸復原段都用完了（通常這幾乎不會發生），會傳回錯誤db_too_many_concurrent_trxs
每一個undo log segment實際上對應一個獨立的段，段頭的起始位置在undo 頭page的trx_undo_seg_hdr+trx_undo_fseg_header偏移位置（見下圖）
已配置設定給事務的trx_undo_t會加入到連結清單<code>trx_rseg_t::insert_undo_list</code>或者<code>trx_rseg_t::update_undo_list上</code>；
如果是資料詞典操作（ddl）産生的undo，主要是表級别操作，例如建立或删除表，還需要記錄操作的table id到undo log header中(trx_undo_table_id)，同時将trx_undo_dict_trans設定為true。(trx_undo_mark_as_dict_operation)。
總的來說，undo header page主要包括如下資訊：
當配置設定了一個undo slot，同時初始化完可用的空閑區域後，就可以向其中寫入undo記錄了。寫入的page no取自<code>undo->last_page_no</code>，初始情況下和hdr_page_no相同。
對于insert_undo，調用函數trx_undo_page_report_insert進行插入，記錄格式大緻如下圖所示：
對于update_undo，調用函數<code>trx_undo_page_report_modify</code>進行插入，update undo的記錄格式大概如下圖所示：
在寫入的過程中，可能出現單頁面空間不足的情況，導緻寫入失敗，我們需要将剛剛寫入的區域清空重置(trx_undo_erase_page_end)，同時申請一個新的page(trx_undo_add_page) 加入到undo log段上，同時将<code>undo->last_page_no</code>指向新配置設定的page，然後重試。
完成undo log寫入後，建構新的復原段指針并傳回（trx_undo_build_roll_ptr），復原段指針包括undo log所在的復原段id、日志所在的page no、以及page内的偏移量，需要記錄到聚集索引記錄中。
入口函數：trx_prepare_low
當事務完成需要送出時，為了和binlog做xa，innodb的commit被劃分成了兩個階段：prepare階段和commit階段，本小節主要讨論下prepare階段undo相關的邏輯。
為了在崩潰重新開機時知道事務狀态，需要将事務設定為prepare，mysql 5.7對臨時表undo和普通表undo分别做了處理，前者在寫undo日志時總是不需要記錄redo，後者則需要記錄。
分别設定insert undo 和 update undo的狀态為prepare，調用函數trx_undo_set_state_at_prepare，過程也比較簡單，找到undo log slot對應的頭頁面(trx_undo_t::hdr_page_no)，将頁面段頭的trx_undo_state設定為trx_undo_prepared，同時修改其他對應字段，如下圖所示（對于外部顯式xa所産生的xid，這裡不做讨論）：
tips：innodb層的xid是如何擷取的呢？ 當innodb的參數innodb_support_xa打開時，在執行事務的第一條sql時，就會去注冊xa，根據第一條sql的query id拼湊xid資料，然後存儲在事務對象中。參考函數<code>trans_register_ha</code>。
當事務commit時，需要将事務狀态設定為commit狀态，這裡同樣通過undo來實作的。
入口函數：<code>trx_commit_low-->trx_write_serialisation_history</code>
在該函數中，需要将該事務包含的undo都設定為完成狀态，先設定insert undo，再設定update undo（trx_undo_set_state_at_finish），完成狀态包含三種：
如果目前的undo log隻占一個page，且占用的header page大小使用不足其3/4時(trx_undo_page_reuse_limit)，則狀态設定為trx_undo_cached，該undo對象會随後加入到undo cache list上；
如果是insert_undo（undo類型為trx_undo_insert），則狀态設定為trx_undo_to_free；
如果不滿足a和b，則表明該undo可能需要purge線程去執行清理操作，狀态設定為trx_undo_to_purge。
在确認狀态資訊後，寫入undo header page的trx_undo_state中。
如果目前事務包含update undo，并且undo所在復原段不在purge隊列時，還需要将目前undo所在的復原段（及目前最大的事務号）加入purge線程的purge隊列（purge_sys->purge_queue）中（參考函數<code>trx_serialisation_number_get</code>）。
對于undate undo需要調用<code>trx_undo_update_cleanup</code>進行清理操作，清理的過程包括：
将undo log加入到history list上，調用<code>trx_purge_add_update_undo_to_history</code>：
如果該undo log不滿足cache的條件（狀态為trx_undo_cached，如上述），則将其占用的slot設定為fil_null，意為slot空閑，同時更新復原段頭的trx_rseg_history_size值，将目前undo占用的page數累加上去；
将目前undo加入到復原段的trx_rseg_history連結清單上，作為連結清單頭節點，節點指針為undo頭的trx_undo_history_node；
更新<code>trx_sys->rseg_history_len</code>（也就是show engine innodb status看到的history list），如果隻有普通的update_undo，則加1，如果還有臨時表的update_undo，則加2，然後喚醒purge線程；
将目前事務的<code>trx_t::no</code>寫入undo頭的trx_undo_trx_no段；
如果不是delete-mark操作，将undo頭的trx_undo_del_marks更新為false;
如果undo所在復原段的<code>rseg->last_page_no</code>為fil_null，表示該復原段的舊的清理已經完成，進行如下指派，記錄這個復原段上第一個需要purge的undo記錄資訊：
如果undo需要cache，将undo對象放到復原段的update_undo_cached連結清單上；否則釋放undo對象（trx_undo_mem_free）。
注意上面隻清理了update_undo，insert_undo直到事務釋放記錄鎖、從讀寫事務連結清單清除、以及關閉read view後才進行，調用函數trx_undo_insert_cleanup：
如果undo狀态為trx_undo_cached，則加入到復原段的insert_undo_cached連結清單上；
否則，将該undo所占的segment及其所占用的復原段的slot全部釋放掉（trx_undo_seg_free），修改目前復原段的大小(rseg->curr_size)，并釋放undo對象所占的記憶體（trx_undo_mem_free），和update_undo不同，insert_undo并未放到history list上。
事務完成送出後，需要将其使用的復原段引用計數rseg->trx_ref_count減1；
如果事務因為異常或者被顯式的復原了，那麼所有資料變更都要改回去。這裡就要借助復原日志中的資料來進行恢複了。
入口函數為：<code>row_undo_step --> row_undo</code>
操作也比較簡單，析取老版本記錄，做逆向操作即可：對于标記删除的記錄清理标記删除标記；對于in-place更新，将資料復原到最老版本；對于插入操作，直接删除聚集索引和二級索引記錄（row_undo_ins）。
具體的操作中，先復原二級索引記錄（row_undo_mod_del_mark_sec、row_undo_mod_upd_exist_sec、row_undo_mod_upd_del_sec），再復原聚集索引記錄（row_undo_mod_clust）。這裡不展開描述，可以參閱對應的函數。
innodb的多版本使用undo來建構，這很好了解，undo記錄中包含了記錄更改前的鏡像，如果更改資料的事務未送出，對于隔離級别大于等于read commit的事務而言，它不應該看到已修改的資料，而是應該給它傳回老版本的資料。
入口函數： <code>row_vers_build_for_consistent_read</code>
由于在修改聚集索引記錄時，總是存儲了復原段指針和事務id，可以通過該指針找到對應的undo 記錄，通過事務id來判斷記錄的可見性。當舊版本記錄中的事務id對目前事務而言是不可見時，則繼續向前建構，直到找到一個可見的記錄或者到達版本鍊尾部。（關于事務可見性及read view，可以參閱我們之前的月報）
tips 1：建構老版本記錄（<code>trx_undo_prev_version_build</code>）需要持有page latch，是以如果undo鍊太長的話，其他請求該page的線程可能等待時間過長導緻crash，最典型的就是備庫備份場景：
當備庫使用innodb表存儲複制位點資訊時（relay_log_info_repository=table），邏輯備份顯式開啟一個read view并且執行了長時間的備份時，這中間都無法對slave_relay_log_info表做purge操作，導緻版本鍊極其長；當開始備份slave_relay_log_info表時，就需要去花很長的時間建構老版本；複制線程由于需要更新slave_relay_log_info表，是以會陷入等待page latch的場景，最終有可能導緻信号量等待逾時，執行個體自殺。 （bug#74003）
tips 2：在建構老版本的過程中，總是需要建立heap來存儲舊版本記錄，實際上這個heap是可以重用的，無需總是重複建構（bug#69812）
tips 3：如果復原段類型是insert，就完全沒有必要去看undo日志了，因為一個未送出事務的新插入記錄，對其他事務而言總是不可見的。
tips 4: 對于聚集索引我們知道其記錄中存有修改該記錄的事務id，我們可以直接判斷是否需要建構老版本(<code>lock_clust_rec_cons_read_sees</code>)，但對于二級索引記錄，并未存儲事務id，而是每次更新記錄時，同時更新記錄所在的page上的事務id（page_max_trx_id），如果該事務id對目前事務是可見的，那麼就無需去建構老版本了，否則就需要去回表查詢對應的聚集索引記錄，然後判斷可見性（<code>lock_sec_rec_cons_read_sees</code>）。
從上面的分析我們可以知道：update_undo産生的日志會放到history list中，當這些舊版本無人通路時，需要進行清理操作；另外頁内标記删除的操作也需要從實體上清理掉。背景purge線程負責這些工作。
入口函數：<code>srv_do_purge --> trx_purge</code>
确認可見性
在開始嘗試purge前，purge線程會先克隆一個最老的活躍視圖（<code>trx_sys->mvcc->clone_oldest_view</code>），所有在readview開啟之前送出的事務所做的事務變更都是可以清理的。
擷取需要purge的undo記錄（<code>trx_purge_attach_undo_recs</code>）
從history list上讀取多個undo記錄，并配置設定到多個purge線程的工作隊列上（<code>(purge_node_t*) thr->child->undo_recs</code>），預設一次最多取300個undo記錄，可通過參數innodb_purge_batch_size參數調整。
purge工作線程
當完成任務的分發後，各個工作線程（包括協調線程）開始進行purge操作
入口函數： row_purge_step -> row_purge -> row_purge_record_func
主要包括兩種：一種是記錄直接被标記删除了，這時候需要實體清理所有的聚集索引和二級索引記錄（<code>row_purge_record_func</code>）；另一種是聚集索引in-place更新了，但二級索引上的記錄順序可能發生變化，而二級索引的更新總是标記删除 + 插入，是以需要根據復原段記錄去檢查二級索引記錄序是否發生變化，并執行清理操作（<code>row_purge_upd_exist_or_extern</code>）。
清理history list
從前面的分析我們知道，insert undo在事務送出後，undo segment 就釋放了。而update undo則加入了history list，為了将這些檔案空間回收重用，需要對其進行truncate操作；預設每處理128輪purge循環後，purge協調線程需要執行一次purge history list操作。
入口函數：<code>trx_purge_truncate --> trx_purge_truncate_history</code>
從復原段的history 檔案連結清單上開始周遊釋放undo log segment，由于history 連結清單是按照trx no有序的，是以周遊truncate直到完全清除，或者遇到一個還未purge的undo log（trx no比目前purge到的位置更大）時才停止。
關于purge操作的邏輯實際上還算是比較複雜的代碼子產品，這裡隻是簡單的介紹了下，以後有時間再展開描述。
當執行個體從崩潰中恢複時，需要将活躍的事務從undo中提取出來，對于active狀态的事務直接復原，對于prepare狀态的事務，如果該事務對應的binlog已經記錄，則送出，否則復原事務。
實作的流程也比較簡單，首先先做redo (recv_recovery_from_checkpoint_start)，undo是受redo 保護的，是以可以從redo中恢複（臨時表undo除外，臨時表undo是不記錄redo的）。
在redo日志應用完成後，初始化完成資料詞典子系統（dict_boot），随後開始初始化事務子系統（trx_sys_init_at_db_start），undo 段的初始化即在這一步完成。
在初始化undo段時(<code>trx_sys_init_at_db_start -> trx_rseg_array_init -> ... -> trx_undo_lists_init</code>)，會根據每個復原段page中的slot是否被使用來恢複對應的undo log，讀取其狀态資訊和類型等資訊，建立記憶體結構，并存放到每個復原段的undo list上。
當初始化完成undo記憶體對象後，就要據此來恢複崩潰前的事務連結清單了(trx_lists_init_at_db_start)，根據每個復原段的insert_undo_list來恢複插入操作的事務(trx_resurrect_insert)，根據update_undo_list來恢複更新事務(tex_resurrect_update)，如果既存在插入又存在更新，則隻恢複一個事務對象。另外除了恢複事務對象外，還要恢複表鎖及讀寫事務連結清單，進而恢複到崩潰之前的事務場景。
當從undo恢複崩潰前活躍的事務對象後，會去開啟一個背景線程來做事務復原和清理操作（recv_recovery_rollback_active -> trx_rollback_or_clean_all_recovered），對于處于active狀态的事務直接復原，對于既不active也非prepare狀态的事務，直接則認為其是送出的，直接釋放事務對象。但完成這一步後，理論上事務連結清單上隻存在prepare狀态的事務。
随後很快我們進入xa recover階段，mysql使用内部xa，即通過binlog和innodb做xa恢複。在初始化完成引擎後，server層會開始掃描最後一個binlog檔案，搜集其中記錄的xid（mysql_bin_log::recover），然後和innodb層的事務xid做對比。如果xid已經存在于binlog中了，對應的事務需要送出；否則需要復原事務。
tips：為何隻需要掃描最後一個binlog檔案就可以了？ 因為在每次rotate到一個新的binlog檔案之前，總是要保證前一個binlog檔案中對應的事務都送出并且sync redo到磁盤了，也就是說，前一個binlog檔案中的事務在崩潰恢複時肯定是出于送出狀态的。