今天的文章講解UNDO LOG，是昨天文章《「資料庫」庖丁解InnoDB之REDO LOG》的姐妹篇。歡迎閱讀~
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.1 事務復原
在設計資料庫時，我們假設資料庫可能在任何時刻，由于如硬體故障，軟體Bug，運維操作等原因突然崩潰。這個時候尚未完成送出的事務可能已經有部分資料寫入了磁盤，如果不加處理，會違反資料庫對Atomic的保證，也就是任何事務的修改要麼全部送出，要麼全部取消。針對這個問題，直覺的想法是等到事務真正送出時，才能允許這個事務的任何修改落盤，也就是No-Steal政策。顯而易見，這種做法一方面造成很大的記憶體空間壓力，另一方面送出時的大量随機IO會極大的影響性能。是以，資料庫實作中通常會在正常事務進行中，就不斷的連續寫入Undo Log，來記錄本次修改之前的曆史值。當Crash真正發生時，可以在Recovery過程中通過回放Undo Log将未送出事務的修改抹掉。InnoDB采用的就是這種方式。
既然已經有了在Crash Recovery時支援事務復原的Undo Log，自然地，在正常運作過程中，死鎖處理或使用者請求的事務復原也可以利用這部分資料來完成。
1.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。
3.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的位置。
3.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實體塊中；然後檔案組織方式介紹整體的檔案結構；最後再介紹其在記憶體中的組織方式。
4.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的曆史值。
4.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。
4.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.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。
9.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，等待後續的順序處理。對應上圖的處理過程和對應的函數調用，如下圖所示：
[trx_purge_choose_next_log] Pop T1 from purge_queue;
[trx_purge_get_next_rec] Iterator T1;
[trx_purge_rseg_get_next_history_log] Get T1 next: T5;
[trx_purge_choose_next_log] Push T5 into purge_queue;
[trx_purge_choose_next_log] Pop T4 from purge_queue;
[trx_purge_get_next_rec] Iterator T4;
[trx_purge_rseg_get_next_history_log] Get T4 next: ...;
[trx_purge_choose_next_log] Push ... into purge_queue;
[trx_purge_choose_next_log] Pop T5 from purge_queue;
[trx_purge_get_next_rec] Iterator T5;
[trx_purge_rseg_get_next_history_log] Get T5 next: T6;
[trx_purge_choose_next_log] Push T6 into purge_queue;
...... 其中，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
9.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雖然不涉及主索引的删除，但可能需要做二級索引的删除，也是在這裡處理的。
9.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的縮短是跳變的。
9.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等。
文章來源：https://mp.weixin.qq.com/s?__biz=MzIzOTU0NTQ0MA==&mid=2247506129&idx=1&sn=53b2e4a93823ec3488e5f1a8be535110&chksm=e92ae5dede5d6cc8cb0c7e1b1769f94f1a4e7b84f94b1c9e537911a8fe5f4b5fdea14647a388&scene=178&cur_album_id=1530994292440301570#rd