Undo Log是InnoDB十分重要的組成部分，它的作用橫貫InnoDB中兩個最主要的部分，并發控制(Concurrency Control)和故障恢復(Crash Recovery)，InnoDB中Undo Log的實現亦日志亦數據。本文將從其作用、設計思路、記錄內容、組織結構，以及各種功能實現等方面，整體介紹InnoDB中的Undo Log，文章會深入一定的代碼實現，但在細節上還是希望用抽象的實現思路代替具體的代碼。本文基于MySQL 8.0，但在大多數的設計思路上MySQL的各個版本都是一致的。考慮到篇幅有限，以及避免過多信息的干擾，從而能夠聚焦Undo Log本身的內容，本文中一筆帶過或有意省略了一些內容，包括索引、事務系統、臨時表、XA事務、Virtual Column、外部記錄、Blob等。

一、Undo Log的作用

數據庫故障恢復機制的前世今生中提到過，Undo Log用來記錄每次修改之前的歷史值，配合Redo Log用于故障恢復。這也就是InnoDB中Undo Log的第一個作用：

1.事務回滾

在設計數據庫時，我們假設數據庫可能在任何時刻，由于如硬件故障，軟件Bug，運維操作等原因突然崩潰。這個時候尚未完成提交的事務可能已經有部分數據寫入了磁盤，如果不加處理，會違反數據庫對Atomic的保證，也就是任何事務的修改要么全部提交，要么全部取消。針對這個問題，直觀的想法是等到事務真正提交時，才能允許這個事務的任何修改落盤，也就是No-Steal策略。顯而易見，這種做法一方面造成很大的內存空間壓力，另一方面提交時的大量隨機IO會極大的影響性能。因此，數據庫實現中通常會在正常事務進行中，就不斷的連續寫入Undo Log，來記錄本次修改之前的歷史值。當Crash真正發生時，可以在Recovery過程中通過回放Undo Log將未提交事務的修改抹掉。InnoDB采用的就是這種方式。

既然已經有了在Crash Recovery時支持事務回滾的Undo Log，自然地，在正常運行過程中，死鎖處理或用戶請求的事務回滾也可以利用這部分數據來完成。

2.MVCC(Multi-Versioin Concurrency Control)

淺析數據庫并發控制機制中提到過，為了避免只讀事務與寫事務之間的沖突，避免寫操作等待讀操作，幾乎所有的主流數據庫都采用了多版本并發控制(MVCC)的方式，也就是為每條記錄保存多份歷史數據供讀事務訪問，新的寫入只需要添加新的版本即可，無需等待。InnoDB在這里復用了Undo Log中已經記錄的歷史版本數據來滿足MVCC的需求。

二、什么樣的Undo Log

庖丁解InnoDB之REDO LOG中講過的基于Page的Redo Log可以更好的支持并發的Redo應用，從而縮短DB的Crash Recovery時間。而對于Undo Log來說，InnoDB用Undo Log來實現MVCC，DB運行過程中是允許有歷史版本的數據存在的。因此，Crash Recovery時利用Undo Log的事務回滾完全可以在后臺，像正常運行的事務一樣異步回滾，從而讓數據庫先恢復服務。因此，Undo Log的設計思路不同于Redo Log，Undo Log需要的是事務之間的并發，以及方便的多版本數據維護，其重放邏輯不希望因DB的物理存儲變化而變化。因此，InnoDB中的Undo Log采用了基于事務的Logical Logging的方式。

同時，更多的責任意味著更復雜的管理邏輯，InnoDB中其實是把Undo當做一種數據來維護和使用的，也就是說，Undo Log日志本身也像其他的數據庫數據一樣，會寫自己對應的Redo Log，通過Redo Log來保證自己的原子性。因此，更合適的稱呼應該是Undo Data。

三、Undo Record中的內容

每當InnoDB中需要修改某個Record時，都會將其歷史版本寫入一個Undo Log中，對應的Undo Record是Update類型。當插入新的Record時，還沒有一個歷史版本，但為了方便事務回滾時做逆向(Delete)操作，這里還是會寫入一個insert類型的Undo Record。

1.insert類型的Undo Record

這種Undo Record在代碼中對應的是TRX_UNDO_insERT_REC類型。不同于Update類型的Undo Record，insert Undo Record僅僅是為了可能的事務回滾準備的，并不在MVCC功能中承擔作用。因此只需要記錄對應Record的Key，供回滾時查找Record位置即可。

其中Undo Number是Undo的一個遞增編號，Table ID用來表示是哪張表的修改。下面一組Key Fields的長度不定，因為對應表的主鍵可能由多個field組成，這里需要記錄Record完整的主鍵信息，回滾的時候可以通過這個信息在索引中定位到對應的Record。除此之外，在Undo Record的頭尾還各留了兩個字節用戶記錄其前序和后繼Undo Record的位置。

2.Update類型的Undo Record

由于MVCC需要保留Record的多個歷史版本，當某個Record的歷史版本還在被使用時，這個Record是不能被真正的刪除的。因此，當需要刪除時，其實只是修改對應Record的Delete Mark標記。對應的，如果這時這個Record又重新插入，其實也只是修改一下Delete Mark標記，也就是將這兩種情況的delete和insert轉變成了update操作。再加上常規的Record修改，因此這里的Update Undo Record會對應三種Type：TRX_UNDO_UPD_EXIST_REC、TRX_UNDO_DEL_MARK_REC和TRX_UNDO_UPD_DEL_REC。他們的存儲內容也類似：

除了跟insert Undo Record相同的頭尾信息，以及主鍵Key Fileds之外，Update Undo Record增加了：

Transaction Id記錄了產生這個歷史版本事務Id，用作后續MVCC中的版本可見性判斷

Rollptr指向的是該記錄的上一個版本的位置，包括space number，page number和page內的offset。沿著Rollptr可以找到一個Record的所有歷史版本。

Update Fields中記錄的就是當前這個Record版本相對于其之后的一次修改的Delta信息，包括所有被修改的Field的編號，長度和歷史值。

四、Undo Record的組織方式

上面介紹了一個Undo Record中的存放的內容，每一次的修改都會產生至少一個Undo Record，那么大量Undo Record如何組織起來，來支持高效的訪問和管理呢，這一小節我們將從幾個層面來進行介紹：首先是在不考慮物理存儲的情況下的邏輯組織方式;之后，物理組織方式介紹如何將其存儲到到實際16KB物理塊中;然后文件組織方式介紹整體的文件結構;最后再介紹其在內存中的組織方式。

1.邏輯組織方式 - Undo Log

每個事務其實會修改一組的Record，對應的也就會產生一組Undo Record，這些Undo Record收尾相連就組成了這個事務的Undo Log。除了一個個的Undo Record之外，還在開頭增加了一個Undo Log Header來記錄一些必要的控制信息，因此，一個Undo Log的結構如下所示：

Undo Log Header中記錄了產生這個Undo Log的事務的Trx ID;Trx No是事務的提交順序，也會用這個來判斷是否能Purge，這個在后面會詳細介紹;Delete Mark標明該Undo Log中有沒有TRX_UNDO_DEL_MARK_REC類型的Undo Record，避免Purge時不必要的掃描;Log Start Offset中記錄Undo Log Header的結束位置，方便之后Header中增加內容時的兼容;之后是一些Flag信息;Next Undo Log及Prev Undo Log標記前后兩個Undo Log，這個會在接下來介紹;最后通過History List Node將自己掛載到為Purge準備的History List中。

索引中的同一個Record被不同事務修改，會產生不同的歷史版本，這些歷史版本又通過Rollptr穿成一個鏈表，供MVCC使用。如下圖所示：

示例中有三個事務操作了表t上，主鍵id是1的記錄，首先事務I插入了這條記錄并且設置filed a的值是A，之后事務J和事務K分別將這條id為1的記錄中的filed a的值修改為了B和C。I，J，K三個事務分別有自己的邏輯上連續的三條Undo Log，每條Undo Log有自己的Undo Log Header。從索引中的這條Record沿著Rollptr可以依次找到這三個事務Undo Log中關于這條記錄的歷史版本。同時可以看出，insert類型Undo Record中只記錄了對應的主鍵值：id=1，而Update類型的Undo Record中還記錄了對應的歷史版本的生成事務Trx_id，以及被修改的field a的歷史值。

2.物理組織格式 - Undo Segment

上面描述了一個Undo Log的結構，一個事務會產生多大的Undo Log本身是不可控的，而最終寫入磁盤卻是按照固定的塊大小為單位的，InnoDB中默認是16KB，那么如何用固定的塊大小承載不定長的Undo Log，以實現高效的空間分配、復用，避免空間浪費。InnoDB的基本思路是讓多個較小的Undo Log緊湊存在一個Undo Page中，而對較大的Undo Log則隨著不斷的寫入，按需分配足夠多的Undo Page分散承載。下面我們就看看這部分的物理存儲方式：

如上所示，是一個Undo Segment的示意圖，每個寫事務開始寫操作之前都需要持有一個Undo Segment，一個Undo Segment中的所有磁盤空間的分配和釋放，也就是16KB Page的申請和釋放，都是由一個FSP的Segment管理的，這個跟索引中的Leaf Node Segment和Non-Leaf Node Segment的管理方式是一致的，這部分之后會有單獨的文章來進行介紹。

Undo Segment會持有至少一個Undo Page，每個Undo Page會在開頭38字節到56字節記錄Undo Page Header，其中記錄Undo Page的類型、最后一條Undo Record的位置，當前Page還空閑部分的開頭，也就是下一條Undo Record要寫入的位置。Undo Segment中的第一個Undo Page還會在56字節到86字節記錄Undo Segment Header，這個就是這個Undo Segment中磁盤空間管理的Handle;其中記錄的是這個Undo Segment的狀態，比如TRX_UNDO_CACHED、TRX_UNDO_TO_PURGE等;這個Undo Segment中最后一條Undo Record的位置;這個FSP Segment的Header，以及當前分配出來的所有Undo Page的鏈表。

Undo Page剩余的空間都是用來存放Undo Log的，對于像上圖Undo Log 1，Undo Log 2這種較短的Undo Log，為了避免Page內的空間浪費，InnoDB會復用Undo Page來存放多個Undo Log，而對于像Undo Log 3這種比較長的Undo Log可能會分配多個Undo Page來存放。需要注意的是Undo Page的復用只會發生在第一個Page。

3.文件組織方式 - Undo Tablespace

每一時刻一個Undo Segment都是被一個事務獨占的。每個寫事務都會持有至少一個Undo Segment，當有大量寫事務并發運行時，就需要存在多個Undo Segment。InnoDB中的Undo 文件中準備了大量的Undo Segment的槽位，按照1024一組劃分為Rollback Segment。每個Undo Tablespace最多會包含128個Rollback Segment，Undo Tablespace文件中的第三個Page會固定作為這128個Rollback Segment的目錄，也就是Rollback Segment Arrary Header，其中最多會有128個指針指向各個Rollback Segment Header所在的Page。Rollback Segment Header是按需分配的，其中包含1024個Slot，每個Slot占四個字節，指向一個Undo Segment的First Page。除此之前還會記錄該Rollback Segment中已提交事務的History List，后續的Purge過程會順序從這里開始回收工作。

可以看出Rollback Segment的個數會直接影響InnoDB支持的最大事務并發數。MySQL 8.0由于支持了最多127個獨立的Undo Tablespace，一方面避免了ibdata1的膨脹，方便undo空間回收，另一方面也大大增加了最大的Rollback Segment的個數，增加了可支持的最大并發寫事務數。如下圖所示：

4.內存組織結構

上面介紹的都是Undo數據在磁盤上的組織結構，除此之外，在內存中也會維護對應的數據結構來管理Undo Log，如下圖所示：

對應每個磁盤Undo Tablespace會有一個undo::Tablespace的內存結構，其中最主要的就是一組trx_rseg_t的集合，trx_rseg_t對應的就是上面介紹過的一個Rollback Segment Header，除了一些基本的元信息之外，trx_rseg_t中維護了四個trx_undo_t的鏈表，Update List中是正在被使用的用于寫入Update類型Undo的Undo Segment;Update Cache List中是空閑空間比較多，可以被后續事務復用的Update類型Undo Segment;對應的，insert List和insert Cache List分別是正在使用中的insert類型Undo Segment，和空間空間較多，可以被后續復用的insert類型Undo Segment。因此trx_undo_t對應的就是上面介紹過的Undo Segment。接下來，我們就從Undo的寫入、Undo用于Rollback、MVCC、Crash Recovery以及如何清理Undo等方面來介紹InnoDB中Undo的角色和功能。

五、Undo的寫入

當寫事務開始時，會先通過trx_assign_rseg_durable分配一個Rollback Segment，該事務的內存結構trx_t也會通過rsegs指針指向對應的trx_rseg_t內存結構，這里的分配策略很簡單，就是依次嘗試下一個Active的Rollback Segment。之后當第一次真正產生修改需要寫Undo Record的時，會調用trx_undo_assign_undo來獲得一個Undo Segment。這里會優先復用trx_rseg_t上Cached List中的trx_undo_t，也就是已經分配出來但沒有被正在使用的Undo Segment，如果沒有才調用trx_undo_create創建新的Undo Segment，trx_undo_create中會輪詢選擇當前Rollback Segment中可用的Slot，也是就值FIL_NUL的Slot，申請新的Undo Page，初始化Undo Page Header，Undo Segment Header等信息，創建新的trx_undo_t內存結構并掛到trx_rseg_t的對應List中。

獲得了可用的Undo Segment之后，該事務會在合適的位置初始化自己的Undo Log Header，之后，其所有修改產生的Undo Record都會順序的通過trx_undo_report_row_operation順序的寫入當前的Undo Log，其中會根據是insert還是update類型，分別調用trx_undo_page_report_insert或者trx_undo_page_report_modify。本文開始已經介紹過了具體的Undo Record內容。簡單的講，insert類型會記錄插入Record的主鍵，update類型除了記錄主鍵以外還會有一個update fileds記錄這個歷史值跟索引值的diff。之后指向當前Undo Record位置的Rollptr會返回寫入索引的Record上。

當一個Page寫滿后，會調用trx_undo_add_page來在當前的Undo Segment上添加新的Page，新Page寫入Undo Page Header之后繼續供事務寫入Undo Record，為了方便維護，這里有一個限制就是單條Undo Record不跨page，如果當前Page放不下，會將整個Undo Record寫入下一個Page。

當事務結束(commit或者rollback)之后，如果只占用了一個Undo Page，且當前Undo Page使用空間小于page的3/4，這個Undo Segment會保留并加入到對應的insert/update cached list中。否則，insert類型的Undo Segment會直接回收，而update類型的Undo Segment會等待后臺的Purge做完后回收。根據不同的情況，Undo Segment Header中的State會被從TRX_UNDO_ACTIVE改成TRX_UNDO_TO_FREE，TRX_UNDO_TO_PURGE或TRX_UNDO_CACHED，這個修改其實就是InnoDB的事務結束的標志，無論是Rollback還是Commit，在這個修改對應的Redo落盤之后，就可以返回用戶結果，并且Crash Recovery之后也不會再做回滾處理。

六、Undo for Rollback

InnoDB中的事務可能會由用戶主動觸發Rollback;也可能因為遇到死鎖異常Rollback;或者發生Crash，重啟后對未提交的事務回滾。在Undo層面來看，這些回滾的操作是一致的，基本的過程就是從該事務的Undo Log中，從后向前依次讀取Undo Record，并根據其中內容做逆向操作，恢復索引記錄。

回滾的入口是函數row_undo，其中會先調用trx_roll_pop_top_rec_of_trx獲取并刪除該事務的最后一條Undo Record。如下圖例子中的Undo Log包括三條Undo Records，其中Record 1在Undo Page 1中，Record 2，3在Undo Page 2中，先通過從Undo Segment Header中記錄的Page List找到當前事務的最后一個Undo Page的Header，并根據Undo Page 2的Header上記錄的Free Space Offset定位最后一條Undo Record結束的位置，當然實際運行時，這兩個值是緩存在trx_undo_t的top_page_no和top_offset中的。利用Prev Record Offset可以找到Undo Record 3，做完對應的回滾操作之后，再通過前序指針Prev Record Offset找到前一個Undo Record，依次進行處理。處理完當前Page中的所有Undo Records后，再沿著Undo Page Header中的List找到前一個Undo Page，重復前面的過程，完成一個事務所有Page上的所有Undo Records的回滾。

拿到一個Undo Record之后，自然地，就是對其中內容的解析，這里會調用row_undo_ins_parse_undo_rec，從Undo Record中獲取修改行的table，解析出其中記錄的主鍵信息，如果是update類型，還會拿到一個update vector記錄其相對于更新的一個版本的變化。

TRX_UNDO_insERT_REC類型的Undo回滾在row_undo_ins中進行，insert的逆向操作當然就是delete，根據從Undo Record中解析出來的主鍵，用row_undo_search_clust_to_pcur定位到對應的ROW， 分別調用row_undo_ins_remove_sec_rec和row_undo_ins_remove_clust_rec在二級索引和主索引上將當前行刪除。

update類型的undo包括TRX_UNDO_UPD_EXIST_REC，TRX_UNDO_DEL_MARK_REC和TRX_UNDO_UPD_DEL_REC三種情況，他們的Undo回滾都是在row_undo_mod中進行，首先會調用row_undo_mod_del_unmark_sec_and_undo_update，其中根據從Undo Record中解析出的update vector來回退這次操作在所有二級索引上的影響，可能包括重新插入被刪除的二級索引記錄、去除其中的Delete Mark標記，或者用update vector中的diff信息將二級索引記錄修改之前的值。之后調用row_undo_mod_clust同樣利用update vector中記錄的diff信息將主索引記錄修改回之前的值。

完成回滾的Undo Log部分，會調用trx_roll_try_truncate進行回收，對不再使用的page調用trx_undo_free_last_page將磁盤空間交還給Undo Segment，這個是寫入過程中trx_undo_add_page的逆操作。

七、Undo for MVCC

多版本的目的是為了避免寫事務和讀事務的互相等待，那么每個讀事務都需要在不對Record加Lock的情況下， 找到對應的應該看到的歷史版本。所謂歷史版本就是假設在該只讀事務開始的時候對整個DB打一個快照，之后該事務的所有讀請求都從這個快照上獲取。當然實現上不能真正去為每個事務打一個快照，這個時間空間都太高了。InnoDB的做法，是在讀事務第一次讀取的時候獲取一份ReadView，并一直持有，其中記錄所有當前活躍的寫事務ID，由于寫事務的ID是自增分配的，通過這個ReadView我們可以知道在這一瞬間，哪些事務已經提交哪些還在運行，根據Read Committed的要求，未提交的事務的修改就是不應該被看見的，對應地，已經提交的事務的修改應該被看到。

作為存儲歷史版本的Undo Record，其中記錄的trx_id就是做這個可見性判斷的，對應的主索引的Record上也有這個值。當一個讀事務拿著自己的ReadView訪問某個表索引上的記錄時，會通過比較Record上的trx_id確定是否是可見的版本，如果不可見就沿著Record或Undo Record中記錄的rollptr一路找更老的歷史版本。如下圖所示，事務R開始需要查詢表t上的id為1的記錄，R開始時事務I已經提交，事務J還在運行，事務K還沒開始，這些信息都被記錄在了事務R的ReadView中。事務R從索引中找到對應的這條Record[1, C]，對應的trx_id是K，不可見。沿著Rollptr找到Undo中的前一版本[1, B]，對應的trx_id是J，不可見。繼續沿著Rollptr找到[1, A]，trx_id是I可見，返回結果。

前面提到過，作為Logical Log，Undo中記錄的其實是前后兩個版本的diff信息，而讀操作最終是要獲得完整的Record內容的，也就是說這個沿著rollptr指針一路查找的過程中需要用Undo Record中的diff內容依次構造出對應的歷史版本，這個過程在函數row_search_mvcc中，其中trx_undo_prev_version_build會根據當前的rollptr找到對應的Undo Record位置，這里如果是rollptr指向的是insert類型，或者找到了已經Purge了的位置，說明到頭了，會直接返回失敗。否則，就會解析對應的Undo Record，恢復出trx_id、指向下一條Undo Record的rollptr、主鍵信息，diff信息update vector等信息。之后通過row_upd_rec_in_place，用update vector修改當前持有的Record拷貝中的信息，獲得Record的這個歷史版本。之后調用自己ReadView的changes_visible判斷可見性，如果可見則返回用戶。完成這個歷史版本的讀取。

八、Undo for Crash Recovery

Crash Recovery時，需要利用Undo中的信息將未提交的事務的所有影響回滾，以保證數據庫的Failure Atomic。前面提到過，InnoDB中的Undo其實是像數據一樣處理的，也從上面的組織結構中可以看出來，Undo本身有著比Redo Log復雜得多、按事務分配而不是順序寫入的組織結構，其本身的Durability像InnoDB中其他的數據一樣，需要靠Redo來保證，像庖丁解InnoDB之REDO LOG中介紹的那樣。除了通用的一些MLOG_2BYTES、MLOG_4BYTES類型之外，Undo本身也有自己對應的Redo Log類型：MLOG_UNDO_INIT類型在Undo Page舒適化的時候記錄初始化;在分配Undo Log的時候，需要重用Undo Log Header或需要創建新的Undo Log Header的時候，會分別記錄MLOG_UNDO_HDR_REUSE和MLOG_UNDO_HDR_CREATE類型的Redo Record;MLOG_UNDO_insERT是最常見的，在Undo Log里寫入新的Undo Record都對應的寫這個日志記錄寫入Undo中的所有內容;最后，MLOG_UNDO_ERASE_END 對應Undo Log跨Undo Page時抹除最后一個不完整的Undo Record的操作。

如數據庫故障恢復機制的前世今生中講過的ARIES過程，Crash Recovery的過程中會先重放所有的Redo Log，整個Undo的磁盤組織結構，也會作為一種數據類型也會通過上面講到的這些Redo類型的重放恢復出來。之后在trx_sys_init_at_db_start中會掃描Undo的磁盤結構，遍歷所有的Rollback Segment和其中所有的Undo Segment，通過讀取Undo Segment Header中的State，可以知道在Crash前，最后持有這個Undo Segment的事務狀態。如果是TRX_UNDO_ACTIVE，說明當時事務需要回滾，否則說明事務已經結束，可以繼續清理Undo Segment的邏輯。之后，就可以恢復出Undo Log的內存組織模式，包括活躍事務的內存結構trx_t，Rollback Segment的內存結構trx_rseg_t，以及其中的trx_undo_t的四個鏈表。

Crash Recovery完成之前，會啟動在srv_dict_recover_on_restart中啟動異步回滾線程trx_recovery_rollback_thread，其中對Crash前還活躍的事務，通過trx_rollback_active進行回滾，這個過程跟上面提到的Undo for Rollback是一致的。

九、Undo的清理

我們已經知道，InnoDB在Undo Log中保存了多份歷史版本來實現MVCC，當某個歷史版本已經確認不會被任何現有的和未來的事務看到的時候，就應該被清理掉。因此就需要有辦法判斷哪些Undo Log不會再被看到。InnoDB中每個寫事務結束時都會拿一個遞增的編號trx_no作為事務的提交序號，而每個讀事務會在自己的ReadView中記錄自己開始的時候看到的最大的trx_no為m_low_limit_no。那么，如果一個事務的trx_no小于當前所有活躍的讀事務Readview中的這個m_low_limit_no，說明這個事務在所有的讀開始之前已經提交了，其修改的新版本是可見的， 因此不再需要通過undo構建之前的版本，這個事務的Undo Log也就可以被清理了。如下圖所所以，由于ReadView List中最老的ReadView在獲取時，Transaction J就已經Commit，因此所有的讀事務都一定能被Index中的版本或者第一個Undo歷史版本滿足，不需要更老的Undo，因此整個Transaction J的Undo Log都可以清理了。

Undo的清理工作是由專門的后臺線程srv_purge_coordinator_thread進行掃描和分發， 并由多個srv_worker_thread真正清理的。coordinator會首先在函數trx_purge_attach_undo_recs中掃描innodb_purge_batch_size配置個Undo Records，作為一輪清理的任務分發給worker。

1.掃描一批要清理Undo Records

事務結束的時候，對于需要Purge的Update類型的Undo Log，會按照事務提交的順序trx_no，掛載到Rollback Segment Header的History List上。Undo Log回收的基本思路，就是按照trx_no從小到大，依次遍歷所有Undo Log進行清理操作。前面介紹了，InnoDB中有多個Rollback Segment，那么就會有多個History List，每個History List內部事務有序，但還需要從多個History List上找一個trx_no全局有序的序列，如下圖所示：

圖中的事務編號是按照InnoDB這里引入了一個堆結構purge_queue，用來依次從所有History List中找到下一個擁有最小trx_no的事務。purge_queue中記錄了所有等待Purge的Rollback Segment和其History中trx_no最小的事務，trx_purge_choose_next_log依次從purge_queue中pop出擁有全局最小trx_no的Undo Log。調用trx_purge_get_next_rec遍歷對應的Undo Log，處理每一條Undo Record。之后繼續調用trx_purge_rseg_get_next_history_log從purge_queue中獲取下一條trx_no最小的Undo Log，并且將當前Rollback Segment上的下一條Undo Log繼續push進purge_queue，等待后續的順序處理。對應上圖的處理過程和對應的函數調用，如下圖所示：

1. [trx_purge_choose_next_log]PopT1frompurge_queue;
2. [trx_purge_get_next_rec]IteratorT1;
3. [trx_purge_rseg_get_next_history_log]GetT1next:T5;
4. [trx_purge_choose_next_log]PushT5intopurge_queue;
6. [trx_purge_choose_next_log]PopT4frompurge_queue;
7. [trx_purge_get_next_rec]IteratorT4;
8. [trx_purge_rseg_get_next_history_log]GetT4next:...;
9. [trx_purge_choose_next_log]Push...intopurge_queue;
11. [trx_purge_choose_next_log]PopT5frompurge_queue;
12. [trx_purge_get_next_rec]IteratorT5;
13. [trx_purge_rseg_get_next_history_log]GetT5next:T6;
14. [trx_purge_choose_next_log]PushT6intopurge_queue;
15. ......

其中，trx_purge_get_next_rec會從上到下遍歷一個Undo Log中的所有Undo Record，這個跟前面講過的Rollback時候從下到上的遍歷方向是相反的，還是以同樣的場景為例，要Purge的Undo Log橫跨兩個Undo Page，Undo Record 1在Page 1中，而Undo Record 2，3在Page 2中。如下圖所示，首先會從當前的Undo Log Header中找到第一個Undo Record的位置Log Start Offset，處理完Undo Record1之后沿著Next Record Offset去找下一個Undo Record，當找到Page末尾時，要通過Page List Node找下一個Page，找到Page內的第一個Undo Record，重復上面的過程直到找出所有的Undo Record。

對每個要Purge的Undo Record，在真正刪除它本身之前，可能還需要處理一些索引上的信息，這是由于正常運行過程中，當需要刪除某個Record時，為了保證其之前的歷史版本還可以通過Rollptr找到，Record是沒有真正刪除的，只是打了Delete Mark的標記，并作為一種特殊的Update操作記錄了Undo Record。那么在對應的TRX_UNDO_DEL_MARK_REC類型的Undo Record被清理之前，需要先從索引上真正地刪除這個Delete Mark的記錄。因此Undo Record的清理工作會分為兩個過程：

• TRX_UNDO_DEL_MARK_REC類型Undo Record對應的Record的真正刪除，稱為Undo Purge;
• 以及Undo Record本身從舊到新的刪除，稱為Undo Truncate。

除此之外，當配置的獨立Undo Tablespace大于兩個的時候，InnoDB支持通過重建來縮小超過配置大小的Undo Tablespace：

• Undo Tablespace的重建縮小，稱為Undo Tablespace Truncate

2.Undo Purge

這一步主要針對的是TRX_UNDO_DEL_MARK_REC類型的Undo Record，用來真正的刪除索引上被標記為Delete Mark的Record。worker線程會在row_purge函數中，循環處理coordinator分配來的每一個Undo Records，先通過row_purge_parse_undo_rec，依次從Undo Record中解析出type、table_id、rollptr、對應記錄的主鍵信息以及update vector。之后，針對TRX_UNDO_DEL_MARK_REC類型，調用row_purge_remove_sec_if_poss將需要刪除的記錄從所有的二級索引上刪除，調用row_purge_remove_clust_if_poss從主索引上刪除。另外，TRX_UNDO_UPD_EXIST_REC類型的Undo雖然不涉及主索引的刪除，但可能需要做二級索引的刪除，也是在這里處理的。

3.Undo Truncate

coordinator線程會等待所有的worker完成一批Undo Records的Purge工作，之后嘗試清理不再需要的Undo Log，trx_purge_truncate函數中會遍歷所有的Rollback Segment中的所有Undo Segment，如果其狀態是TRX_UNDO_TO_PURGE，調用trx_purge_free_segment釋放占用的磁盤空間并從History List中刪除。否則，說明該Undo Segment正在被使用或者還在被cache(TRX_UNDO_CACHED類型)，那么只通過trx_purge_remove_log_hd將其從History List中刪除。

需要注意的是，Undo Truncate的動作并不是每次都會進行的，它的頻次是由參數innodb_rseg_truncate_frequency控制的，也就是說要攢innodb_rseg_truncate_frequency個batch才進行一次，前面提到每一個batch中會處理innodb_purge_batch_size個Undo Records，這也就是為什么我們從show engine innodb status中看到的Undo History List的縮短是跳變的。

4.Undo Tablespace Truncate

如果innodb_trx_purge_truncate配置打開，在函數trx_purge_truncate中還會去嘗試重建Undo Tablespaces以縮小文件空間占用。Undo Truncate之后，會在函數trx_purge_mark_undo_for_truncate中掃描所有的Undo Tablespace，文件大小大于配置的innodb_max_undo_log_size的Tablespace會被標記為inactive，每一時刻最多有一個Tablespace處于inactive，inactive的Undo Tablespace上的所有Rollback Segment都不參與給新事物的分配，等該文件上所有的活躍事務退出，并且所有的Undo Log都完成Purge之后，這個Tablespace就會被通過trx_purge_initiate_truncate重建，包括重建Undo Tablespace中的文件結構和內存結構，之后被重新標記為active，參與分配給新的事務使用。

十、總結

本文首先概括地介紹了Undo Log的角色，之后介紹了一個Undo Record中的內容，緊接著介紹它的邏輯組織方式、物理組織方式、文件組織方式以及內存組織方式，詳細描述了Undo Tablespace、Rollback Segment、Undo Segment、Undo Log和Undo Record的之間的關系和層級。這些組織方式都是為了更好的使用和維護Undo信息。最后在此基礎上，介紹了Undo在各個重要的DB功能中的作用和實現方式，包括事務回滾、MVCC、Crash Recovery、Purge等。

參考：

[1] MySQL 8.0.11Source Code Documentation: Format of redo log

https://dev.mysql.com/doc/dev/mysql-server/8.0.11/PAGE_INNODB_REDO_LOG_FORMAT.html

[2] MySQL Source Code

https://github.com/mysql/mysql-server

[3] The basics of the InnoDB undo logging and history system

https://blog.jcole.us/2014/04/16/the-basics-of-the-innodb-undo-logging-and-history-system/#:~:text=InnoDB%20keeps%20a%20copy%20of%20everything%20that%20is%20changed&text=It's%20called%20an%20undo%20log,record%20to%20its%20previous%20version.

[4] MySQL · 引擎特性 · InnoDB undo log 漫游

http://mysql.taobao.org/monthly/2015/04/01/

[5] 數據庫故障恢復機制的前世今生

http://catkang.github.io/2019/01/16/crash-recovery.html

[6] 淺析數據庫并發控制機制

http://catkang.github.io/2018/09/19/concurrency-control.html

[7] 庖丁解InnoDB之REDO LOG

原文鏈接：https://zhuanlan.51cto.com/art/202111/689329.htm