[[434053]]

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

一、Undo Log的作用

數(shù)據(jù)庫(kù)故障恢復(fù)機(jī)制的前世今生中提到過(guò)，Undo Log用來(lái)記錄每次修改之前的歷史值，配合Redo Log用于故障恢復(fù)。這也就是InnoDB中Undo Log的第一個(gè)作用：

1.事務(wù)回滾

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

既然已經(jīng)有了在Crash Recovery時(shí)支持事務(wù)回滾的Undo Log，自然地，在正常運(yùn)行過(guò)程中，死鎖處理或用戶請(qǐng)求的事務(wù)回滾也可以利用這部分?jǐn)?shù)據(jù)來(lái)完成。

2.MVCC(Multi-Versioin Concurrency Control)

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

二、什么樣的Undo Log

庖丁解InnoDB之REDO LOG中講過(guò)的基于Page的Redo Log可以更好的支持并發(fā)的Redo應(yīng)用，從而縮短DB的Crash Recovery時(shí)間。而對(duì)于Undo Log來(lái)說(shuō)，InnoDB用Undo Log來(lái)實(shí)現(xiàn)MVCC，DB運(yùn)行過(guò)程中是允許有歷史版本的數(shù)據(jù)存在的。因此，Crash Recovery時(shí)利用Undo Log的事務(wù)回滾完全可以在后臺(tái)，像正常運(yùn)行的事務(wù)一樣異步回滾，從而讓數(shù)據(jù)庫(kù)先恢復(fù)服務(wù)。因此，Undo Log的設(shè)計(jì)思路不同于Redo Log，Undo Log需要的是事務(wù)之間的并發(fā)，以及方便的多版本數(shù)據(jù)維護(hù)，其重放邏輯不希望因DB的物理存儲(chǔ)變化而變化。因此，InnoDB中的Undo Log采用了基于事務(wù)的Logical Logging的方式。

同時(shí)，更多的責(zé)任意味著更復(fù)雜的管理邏輯，InnoDB中其實(shí)是把Undo當(dāng)做一種數(shù)據(jù)來(lái)維護(hù)和使用的，也就是說(shuō)，Undo Log日志本身也像其他的數(shù)據(jù)庫(kù)數(shù)據(jù)一樣，會(huì)寫自己對(duì)應(yīng)的Redo Log，通過(guò)Redo Log來(lái)保證自己的原子性。因此，更合適的稱呼應(yīng)該是Undo Data。

三、Undo Record中的內(nèi)容

每當(dāng)InnoDB中需要修改某個(gè)Record時(shí)，都會(huì)將其歷史版本寫入一個(gè)Undo Log中，對(duì)應(yīng)的Undo Record是Update類型。當(dāng)插入新的Record時(shí)，還沒(méi)有一個(gè)歷史版本，但為了方便事務(wù)回滾時(shí)做逆向(Delete)操作，這里還是會(huì)寫入一個(gè)insert類型的Undo Record。

1.insert類型的Undo Record

這種Undo Record在代碼中對(duì)應(yīng)的是TRX_UNDO_insERT_REC類型。不同于Update類型的Undo Record，insert Undo Record僅僅是為了可能的事務(wù)回滾準(zhǔn)備的，并不在MVCC功能中承擔(dān)作用。因此只需要記錄對(duì)應(yīng)Record的Key，供回滾時(shí)查找Record位置即可。

其中Undo Number是Undo的一個(gè)遞增編號(hào)，Table ID用來(lái)表示是哪張表的修改。下面一組Key Fields的長(zhǎng)度不定，因?yàn)閷?duì)應(yīng)表的主鍵可能由多個(gè)field組成，這里需要記錄Record完整的主鍵信息，回滾的時(shí)候可以通過(guò)這個(gè)信息在索引中定位到對(duì)應(yīng)的Record。除此之外，在Undo Record的頭尾還各留了兩個(gè)字節(jié)用戶記錄其前序和后繼Undo Record的位置。

2.Update類型的Undo Record

由于MVCC需要保留Record的多個(gè)歷史版本，當(dāng)某個(gè)Record的歷史版本還在被使用時(shí)，這個(gè)Record是不能被真正的刪除的。因此，當(dāng)需要?jiǎng)h除時(shí)，其實(shí)只是修改對(duì)應(yīng)Record的Delete Mark標(biāo)記。對(duì)應(yīng)的，如果這時(shí)這個(gè)Record又重新插入，其實(shí)也只是修改一下Delete Mark標(biāo)記，也就是將這兩種情況的delete和insert轉(zhuǎn)變成了update操作。再加上常規(guī)的Record修改，因此這里的Update Undo Record會(huì)對(duì)應(yīng)三種Type：TRX_UNDO_UPD_EXIST_REC、TRX_UNDO_DEL_MARK_REC和TRX_UNDO_UPD_DEL_REC。他們的存儲(chǔ)內(nèi)容也類似：

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

Transaction Id記錄了產(chǎn)生這個(gè)歷史版本事務(wù)Id，用作后續(xù)MVCC中的版本可見(jiàn)性判斷

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

Update Fields中記錄的就是當(dāng)前這個(gè)Record版本相對(duì)于其之后的一次修改的Delta信息，包括所有被修改的Field的編號(hào)，長(zhǎng)度和歷史值。

四、Undo Record的組織方式

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

1.邏輯組織方式 - Undo Log

每個(gè)事務(wù)其實(shí)會(huì)修改一組的Record，對(duì)應(yīng)的也就會(huì)產(chǎn)生一組Undo Record，這些Undo Record收尾相連就組成了這個(gè)事務(wù)的Undo Log。除了一個(gè)個(gè)的Undo Record之外，還在開頭增加了一個(gè)Undo Log Header來(lái)記錄一些必要的控制信息，因此，一個(gè)Undo Log的結(jié)構(gòu)如下所示：

Undo Log Header中記錄了產(chǎn)生這個(gè)Undo Log的事務(wù)的Trx ID;Trx No是事務(wù)的提交順序，也會(huì)用這個(gè)來(lái)判斷是否能Purge，這個(gè)在后面會(huì)詳細(xì)介紹;Delete Mark標(biāo)明該Undo Log中有沒(méi)有TRX_UNDO_DEL_MARK_REC類型的Undo Record，避免Purge時(shí)不必要的掃描;Log Start Offset中記錄Undo Log Header的結(jié)束位置，方便之后Header中增加內(nèi)容時(shí)的兼容;之后是一些Flag信息;Next Undo Log及Prev Undo Log標(biāo)記前后兩個(gè)Undo Log，這個(gè)會(huì)在接下來(lái)介紹;最后通過(guò)History List Node將自己掛載到為Purge準(zhǔn)備的History List中。

索引中的同一個(gè)Record被不同事務(wù)修改，會(huì)產(chǎn)生不同的歷史版本，這些歷史版本又通過(guò)Rollptr穿成一個(gè)鏈表，供MVCC使用。如下圖所示：

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

2.物理組織格式 - Undo Segment

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

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

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

Undo Page剩余的空間都是用來(lái)存放Undo Log的，對(duì)于像上圖Undo Log 1，Undo Log 2這種較短的Undo Log，為了避免Page內(nèi)的空間浪費(fèi)，InnoDB會(huì)復(fù)用Undo Page來(lái)存放多個(gè)Undo Log，而對(duì)于像Undo Log 3這種比較長(zhǎng)的Undo Log可能會(huì)分配多個(gè)Undo Page來(lái)存放。需要注意的是Undo Page的復(fù)用只會(huì)發(fā)生在第一個(gè)Page。

3.文件組織方式 - Undo Tablespace

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

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

4.內(nèi)存組織結(jié)構(gòu)

上面介紹的都是Undo數(shù)據(jù)在磁盤上的組織結(jié)構(gòu)，除此之外，在內(nèi)存中也會(huì)維護(hù)對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)管理Undo Log，如下圖所示：

對(duì)應(yīng)每個(gè)磁盤Undo Tablespace會(huì)有一個(gè)undo::Tablespace的內(nèi)存結(jié)構(gòu)，其中最主要的就是一組trx_rseg_t的集合，trx_rseg_t對(duì)應(yīng)的就是上面介紹過(guò)的一個(gè)Rollback Segment Header，除了一些基本的元信息之外，trx_rseg_t中維護(hù)了四個(gè)trx_undo_t的鏈表，Update List中是正在被使用的用于寫入U(xiǎn)pdate類型Undo的Undo Segment;Update Cache List中是空閑空間比較多，可以被后續(xù)事務(wù)復(fù)用的Update類型Undo Segment;對(duì)應(yīng)的，insert List和insert Cache List分別是正在使用中的insert類型Undo Segment，和空間空間較多，可以被后續(xù)復(fù)用的insert類型Undo Segment。因此trx_undo_t對(duì)應(yīng)的就是上面介紹過(guò)的Undo Segment。接下來(lái)，我們就從Undo的寫入、Undo用于Rollback、MVCC、Crash Recovery以及如何清理Undo等方面來(lái)介紹InnoDB中Undo的角色和功能。

五、Undo的寫入

當(dāng)寫事務(wù)開始時(shí)，會(huì)先通過(guò)trx_assign_rseg_durable分配一個(gè)Rollback Segment，該事務(wù)的內(nèi)存結(jié)構(gòu)trx_t也會(huì)通過(guò)rsegs指針指向?qū)?yīng)的trx_rseg_t內(nèi)存結(jié)構(gòu)，這里的分配策略很簡(jiǎn)單，就是依次嘗試下一個(gè)Active的Rollback Segment。之后當(dāng)?shù)谝淮握嬲a(chǎn)生修改需要寫Undo Record的時(shí)，會(huì)調(diào)用trx_undo_assign_undo來(lái)獲得一個(gè)Undo Segment。這里會(huì)優(yōu)先復(fù)用trx_rseg_t上Cached List中的trx_undo_t，也就是已經(jīng)分配出來(lái)但沒(méi)有被正在使用的Undo Segment，如果沒(méi)有才調(diào)用trx_undo_create創(chuàng)建新的Undo Segment，trx_undo_create中會(huì)輪詢選擇當(dāng)前Rollback Segment中可用的Slot，也是就值FIL_NUL的Slot，申請(qǐng)新的Undo Page，初始化Undo Page Header，Undo Segment Header等信息，創(chuàng)建新的trx_undo_t內(nèi)存結(jié)構(gòu)并掛到trx_rseg_t的對(duì)應(yīng)List中。

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

當(dāng)一個(gè)Page寫滿后，會(huì)調(diào)用trx_undo_add_page來(lái)在當(dāng)前的Undo Segment上添加新的Page，新Page寫入U(xiǎn)ndo Page Header之后繼續(xù)供事務(wù)寫入U(xiǎn)ndo Record，為了方便維護(hù)，這里有一個(gè)限制就是單條Undo Record不跨page，如果當(dāng)前Page放不下，會(huì)將整個(gè)Undo Record寫入下一個(gè)Page。

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

六、Undo for Rollback

InnoDB中的事務(wù)可能會(huì)由用戶主動(dòng)觸發(fā)Rollback;也可能因?yàn)橛龅剿梨i異常Rollback;或者發(fā)生Crash，重啟后對(duì)未提交的事務(wù)回滾。在Undo層面來(lái)看，這些回滾的操作是一致的，基本的過(guò)程就是從該事務(wù)的Undo Log中，從后向前依次讀取Undo Record，并根據(jù)其中內(nèi)容做逆向操作，恢復(fù)索引記錄。

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

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

TRX_UNDO_insERT_REC類型的Undo回滾在row_undo_ins中進(jìn)行，insert的逆向操作當(dāng)然就是delete，根據(jù)從Undo Record中解析出來(lái)的主鍵，用row_undo_search_clust_to_pcur定位到對(duì)應(yīng)的ROW， 分別調(diào)用row_undo_ins_remove_sec_rec和row_undo_ins_remove_clust_rec在二級(jí)索引和主索引上將當(dāng)前行刪除。

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

完成回滾的Undo Log部分，會(huì)調(diào)用trx_roll_try_truncate進(jìn)行回收，對(duì)不再使用的page調(diào)用trx_undo_free_last_page將磁盤空間交還給Undo Segment，這個(gè)是寫入過(guò)程中trx_undo_add_page的逆操作。

七、Undo for MVCC

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

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

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

八、Undo for Crash Recovery

Crash Recovery時(shí)，需要利用Undo中的信息將未提交的事務(wù)的所有影響回滾，以保證數(shù)據(jù)庫(kù)的Failure Atomic。前面提到過(guò)，InnoDB中的Undo其實(shí)是像數(shù)據(jù)一樣處理的，也從上面的組織結(jié)構(gòu)中可以看出來(lái)，Undo本身有著比Redo Log復(fù)雜得多、按事務(wù)分配而不是順序?qū)懭氲慕M織結(jié)構(gòu)，其本身的Durability像InnoDB中其他的數(shù)據(jù)一樣，需要靠Redo來(lái)保證，像庖丁解InnoDB之REDO LOG中介紹的那樣。除了通用的一些MLOG_2BYTES、MLOG_4BYTES類型之外，Undo本身也有自己對(duì)應(yīng)的Redo Log類型：MLOG_UNDO_INIT類型在Undo Page舒適化的時(shí)候記錄初始化;在分配Undo Log的時(shí)候，需要重用Undo Log Header或需要?jiǎng)?chuàng)建新的Undo Log Header的時(shí)候，會(huì)分別記錄MLOG_UNDO_HDR_REUSE和MLOG_UNDO_HDR_CREATE類型的Redo Record;MLOG_UNDO_insERT是最常見(jiàn)的，在Undo Log里寫入新的Undo Record都對(duì)應(yīng)的寫這個(gè)日志記錄寫入U(xiǎn)ndo中的所有內(nèi)容;最后，MLOG_UNDO_ERASE_END 對(duì)應(yīng)Undo Log跨Undo Page時(shí)抹除最后一個(gè)不完整的Undo Record的操作。

如數(shù)據(jù)庫(kù)故障恢復(fù)機(jī)制的前世今生中講過(guò)的ARIES過(guò)程，Crash Recovery的過(guò)程中會(huì)先重放所有的Redo Log，整個(gè)Undo的磁盤組織結(jié)構(gòu)，也會(huì)作為一種數(shù)據(jù)類型也會(huì)通過(guò)上面講到的這些Redo類型的重放恢復(fù)出來(lái)。之后在trx_sys_init_at_db_start中會(huì)掃描Undo的磁盤結(jié)構(gòu)，遍歷所有的Rollback Segment和其中所有的Undo Segment，通過(guò)讀取Undo Segment Header中的State，可以知道在Crash前，最后持有這個(gè)Undo Segment的事務(wù)狀態(tài)。如果是TRX_UNDO_ACTIVE，說(shuō)明當(dāng)時(shí)事務(wù)需要回滾，否則說(shuō)明事務(wù)已經(jīng)結(jié)束，可以繼續(xù)清理Undo Segment的邏輯。之后，就可以恢復(fù)出Undo Log的內(nèi)存組織模式，包括活躍事務(wù)的內(nèi)存結(jié)構(gòu)trx_t，Rollback Segment的內(nèi)存結(jié)構(gòu)trx_rseg_t，以及其中的trx_undo_t的四個(gè)鏈表。

Crash Recovery完成之前，會(huì)啟動(dòng)在srv_dict_recover_on_restart中啟動(dòng)異步回滾線程trx_recovery_rollback_thread，其中對(duì)Crash前還活躍的事務(wù)，通過(guò)trx_rollback_active進(jìn)行回滾，這個(gè)過(guò)程跟上面提到的Undo for Rollback是一致的。

九、Undo的清理

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

Undo的清理工作是由專門的后臺(tái)線程srv_purge_coordinator_thread進(jìn)行掃描和分發(fā)， 并由多個(gè)srv_worker_thread真正清理的。coordinator會(huì)首先在函數(shù)trx_purge_attach_undo_recs中掃描innodb_purge_batch_size配置個(gè)Undo Records，作為一輪清理的任務(wù)分發(fā)給worker。

1.掃描一批要清理Undo Records

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

圖中的事務(wù)編號(hào)是按照InnoDB這里引入了一個(gè)堆結(jié)構(gòu)purge_queue，用來(lái)依次從所有History List中找到下一個(gè)擁有最小trx_no的事務(wù)。purge_queue中記錄了所有等待Purge的Rollback Segment和其History中trx_no最小的事務(wù)，trx_purge_choose_next_log依次從purge_queue中pop出擁有全局最小trx_no的Undo Log。調(diào)用trx_purge_get_next_rec遍歷對(duì)應(yīng)的Undo Log，處理每一條Undo Record。之后繼續(xù)調(diào)用trx_purge_rseg_get_next_history_log從purge_queue中獲取下一條trx_no最小的Undo Log，并且將當(dāng)前Rollback Segment上的下一條Undo Log繼續(xù)push進(jìn)purge_queue，等待后續(xù)的順序處理。對(duì)應(yīng)上圖的處理過(guò)程和對(duì)應(yīng)的函數(shù)調(diào)用，如下圖所示：

[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會(huì)從上到下遍歷一個(gè)Undo Log中的所有Undo Record，這個(gè)跟前面講過(guò)的Rollback時(shí)候從下到上的遍歷方向是相反的，還是以同樣的場(chǎng)景為例，要Purge的Undo Log橫跨兩個(gè)Undo Page，Undo Record 1在Page 1中，而Undo Record 2，3在Page 2中。如下圖所示，首先會(huì)從當(dāng)前的Undo Log Header中找到第一個(gè)Undo Record的位置Log Start Offset，處理完Undo Record1之后沿著Next Record Offset去找下一個(gè)Undo Record，當(dāng)找到Page末尾時(shí)，要通過(guò)Page List Node找下一個(gè)Page，找到Page內(nèi)的第一個(gè)Undo Record，重復(fù)上面的過(guò)程直到找出所有的Undo Record。

對(duì)每個(gè)要Purge的Undo Record，在真正刪除它本身之前，可能還需要處理一些索引上的信息，這是由于正常運(yùn)行過(guò)程中，當(dāng)需要?jiǎng)h除某個(gè)Record時(shí)，為了保證其之前的歷史版本還可以通過(guò)Rollptr找到，Record是沒(méi)有真正刪除的，只是打了Delete Mark的標(biāo)記，并作為一種特殊的Update操作記錄了Undo Record。那么在對(duì)應(yīng)的TRX_UNDO_DEL_MARK_REC類型的Undo Record被清理之前，需要先從索引上真正地刪除這個(gè)Delete Mark的記錄。因此Undo Record的清理工作會(huì)分為兩個(gè)過(guò)程：

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

除此之外，當(dāng)配置的獨(dú)立Undo Tablespace大于兩個(gè)的時(shí)候，InnoDB支持通過(guò)重建來(lái)縮小超過(guò)配置大小的Undo Tablespace：

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

2.Undo Purge

這一步主要針對(duì)的是TRX_UNDO_DEL_MARK_REC類型的Undo Record，用來(lái)真正的刪除索引上被標(biāo)記為Delete Mark的Record。worker線程會(huì)在row_purge函數(shù)中，循環(huán)處理coordinator分配來(lái)的每一個(gè)Undo Records，先通過(guò)row_purge_parse_undo_rec，依次從Undo Record中解析出type、table_id、rollptr、對(duì)應(yīng)記錄的主鍵信息以及update vector。之后，針對(duì)TRX_UNDO_DEL_MARK_REC類型，調(diào)用row_purge_remove_sec_if_poss將需要?jiǎng)h除的記錄從所有的二級(jí)索引上刪除，調(diào)用row_purge_remove_clust_if_poss從主索引上刪除。另外，TRX_UNDO_UPD_EXIST_REC類型的Undo雖然不涉及主索引的刪除，但可能需要做二級(jí)索引的刪除，也是在這里處理的。

3.Undo Truncate

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

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

4.Undo Tablespace Truncate

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

十、總結(jié)

本文首先概括地介紹了Undo Log的角色，之后介紹了一個(gè)Undo Record中的內(nèi)容，緊接著介紹它的邏輯組織方式、物理組織方式、文件組織方式以及內(nèi)存組織方式，詳細(xì)描述了Undo Tablespace、Rollback Segment、Undo Segment、Undo Log和Undo Record的之間的關(guān)系和層級(jí)。這些組織方式都是為了更好的使用和維護(hù)Undo信息。最后在此基礎(chǔ)上，介紹了Undo在各個(gè)重要的DB功能中的作用和實(shí)現(xiàn)方式，包括事務(wù)回滾、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] 數(shù)據(jù)庫(kù)故障恢復(fù)機(jī)制的前世今生

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

[6] 淺析數(shù)據(jù)庫(kù)并發(fā)控制機(jī)制

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

[7] 庖丁解InnoDB之REDO LOG