此部分是关于Undolog的组织形式的一个介绍；主要分为两部分来对undolog的组织形式进行介绍：文件结构和内存结构。在介绍这两部分时，先从局部出发，最后再给出各个部分的联系。
1.文件结构
首先，在MySQL5.6之前所有的undolog全部存储在系统表空间中(ibdata1)；但是从5.6开始也可以使用独立表空间来存储undolog。
当前版本InnoDB默认有两个undotablspac，也可以使用CREATEUNDOTABLESPACE语句动态添加，最大个；每个undotablspac至多可以有TRX_SYS_N_RSEGS()个回滚段。
1.1RollbackSgmnt(回滚段)
InnoDB在undotablspac中使用回滚段来组织undolog。同时为了保证事务的并发操作，在写undolog时不产生冲突，InnoDB使用回滚段来维护undolog的并发写入和持久化；而每个回滚段又有多个undologslot。通常通过RollbackSgmntHadr来管理回滚段，RollbackSgmntHadr通常在回滚段的第一个页，具体结构如下：
MaxSiz：参数名为TRX_RSEG_MAX_SIZE，回滚段可以有用的最大pag数。HistorySiz：参数名为TRX_RSEG_HISTORY_SIZE，historylist包含的pag数。HistoryListBasNod：参数名为TRX_RSEG_HISTORY，historylist的BasNod。RollbackSgmntFSEGEntry：参数名为TRX_RSEG_FSEG_HEADER，filsgmnt的存放位置。UndoSlotsDictionary：参数名为TRX_RSEG_UNDO_SLOTS，存放活跃事务的undohadrpagno。RollbackSgmntHadr里面最重要的两部分就是historylist与undoslotdictory。
其中historylist把所有已经提交但还没有被purg事务的undolog串联起来，purg线程可以通过此list对没有事务使用的undolog进行purg。
每个事务在需要记录undolog时都会申请一个或两个slot(insrt/updat分开)，同时把事务的第一个undopag放入对应slot中；所以理论上InnoDB允许的最大事务并发数为(undotablspac)*(RollbackSgmnt)*(TRX_RSEG_UNDO_SLOTS)。下面我们进一步介绍undolog在磁盘上如何记录。
1.2UndoPag
要想知道undolog如何记录，我们先要搞清楚一个undopag具体内容，undopag一般分两种情况：hadrpag和normalpag。
hadrpag除了normalpag所包含的信息，还包含一些undosgmnt信息，后面会对undosgmnt进行详细介绍。
我们下面先介绍一下undohadrpag的详细分布。
undohadrpag是事务需要写undolog时申请的第一个undopag；一个undohadrpag他同一时刻只隶属于同一个活跃事务，但是一个undohadrpag上面的内容可能包含多个已经提交的事务和一个活跃事务。
undonormalpag是当活跃事务产生的undocord超过undohadrpag容量后，单独再为此事务分配的undopag(参考函数trx_undo_add_pag)；此pag只隶属于一个事务，只包含undopaghadr不包含undosgmnthadr。
1.3UndoPagHadr
每一个undopag都要有hadr，其中记录了当前undopag的一些状态信息，具体内容如下：
UndoPagTyp：参数名为TRX_UNDO_PAGE_TYPE，使用该pag事务的类型，包含TRX_UNDO_INSERT，TRX_UNDO_UPDATE两种。LatstLogRcordOffst：参数名为TRX_UNDO_PAGE_START，最新事务开始记录undolog起始位置。FSpacOffst：参数名为TRX_UNDO_PAGE_FREE，页内空闲空间起始地址，在此之后可记录undolog。UndoPagListNod：参数名为TRX_UNDO_PAGE_NODE，undopaglist节点，可以把同一个事务所用到的所有undopag双向串联起来。1.4UndoSgmntHadr
Stat：参数名为TRX_UNDO_STATE，undosgmnt的状态，TRX_UNDO_ACTIVE等LastLogOffst：参数名为TRX_UNDO_LAST_LOG，当前pag最后一个undologhadr的位置。UndoSgmntFSEGEntry：参数名为TRX_UNDO_FSEG_HEADER，sgmnt对应的inod的（spac_id，pag_no，offst等）UndoSgmntPagListBasNod：参数名为TRX_UNDO_PAGE_LIST，undopaglist的BasNod，对于同一个事务下的undohadrpag和undonormalpag构成双向链表。上面只是介绍了一些undolog在文件上的基本结构，下面我们继续介绍记录undolog时的文件组织。
1.5UndoLogHadr
当事务开始记录undolog时，先创建一个undologhadr，当updat/dlt事务结束后，undologhadr将会被加入到hisotrylist中；insrt事务的undolog会被立即释放。
TransactionID：参数名为TRX_UNDO_TRX_ID，事务id（事务开始的逻辑时间）TransactionNumbr：参数名为TRX_UNDO_TRX_NO，事务no（事务结束的逻辑时间）DltMarksFlags：参数名为TRX_UNDO_DEL_MARKS，如果涉及到删除记录为TRUELogStartOffst：参数名为TRX_UNDO_LOG_START，事务中第一个undocord地址。XIDFlag：参数名为TRX_UNDO_XID_EXISTS，用于XID。DDLTransactionFlag：参数名为TRX_UNDO_DICT_TRANS，是否是DDL事务TablIDifDDLTransaction：参数名为TRX_UNDO_TABLE_ID，如果是DDL事务，记录tablid。NxtUndoLogOffst：参数名为TRX_UNDO_NEXT_LOG，当前页的下一个undologhadr位置PvUndoLogOffst：参数名为TRX_UNDO_PREV_LOG，当前页的上一个undologhadr位置HistoryListNod：参数名为TRX_UNDO_HISTORY_NODE，事务结束时放入historylist的节点。有关XID的内容暂时不介绍。
有了undologhadr后，我们就可以记录undocord了。
1.6UndoRcord
PviousRcordOffst：存储上一条cord的位置。NxtRcordOffst：存储下一条cord的位置。Typ+ExtrnFlag+CompilationInfo：存undocord的typ等信息。可以从上面图中看出，undocord除了存储这里比较重要的几个信息，包含前后undocord位置，类型，undono，tablid等；而undocod中具体存储的内容我们等到《undolog的分配与记录》中去介绍。
最后，我们通过下面这幅图来了解undolog在文件组织上的一个总览。
2.主要内存数据结构
为了方便管理和记录undolog，在内存中有如下关键结构体对象：
undo::Tablspac：undotablspac内存结构体，维护undotablspac相关信息，管理此tablspac中相关回滚段。trx_rsg_t：回滚段的内存结构体，用于维护回滚段相关信息。trx_undo_t：undolog内存结构体，用于维护undologtyp等信息，便于对undopag进行维护和管理。purg_pq_t：purgquu，对已经提交事务的undolog进行维护和回收。trx_t：事务的内存结构体，对事务的信息进行管理和维护。我们重点对trx_rsg_t结构体的内容进行介绍。
trx_rsg_t主要数据成员：
last_pag_no：historylist上此rsg最后一个没有被purg的pagno。lastoffst：最后一个未被purg的undologhadr偏移。lasttrxno：最后一个未被purg的事务no。last_dl_marks：最后一个未被purg的日志需要被清理。上面四个数据可以从trx_undo_t中获取，参考trx_purg_add_updat_undo_to_history函数。
trx_f_count：被活跃事务引用的计数器；非0时，此回滚段所在的tablspac不可以被truncat。updat_undo_list：所有活跃的updat事务的trx_undo_t对象存储在此链表。updat_undo_cachd：如果updat事务提交时，此事务只使用了一个pag并且此pag剩余空间大于1/4放入此链表；新updat事务新申请undolog时优先从此链表分配。insrt_undo_list：所有活跃的insrt事务的trx_undo_t对象存储在此链表。insrt_undo_cachd：如果insrt事务提交时，此事务只使用了一个pag并且此pag剩余空间大于1/4放入此链表；新insrt事务新申请undolog时优先从此链表分配。下面我们通过一副关系图来介绍内存中各个关键结构体之间的关系；其中实线代表拥有该对象，虚线代表引用该对象。
undolog的分配与记录我们通过之前的介绍了解到；undolog在磁盘和内存中是如何组织的；从中了解到，回滚段不论在磁盘和内存中，都是一个非常关键的结构体；InnoDB存储引擎通过回滚段来对undolog进行组织和管理，所以首先我们需要弄清楚回滚段是如何分配与使用的，之后再阐述undolog具体是如何记录的。
1.分配回滚段
当开启一个事务的时候，需要预先为事务分配一个回滚段。
首先我们将事务分为两大类：只读事务与读写事务。分别从这两大类事务来探讨如何分配回滚段的。
只读事务：当事务涉及到对临时表的读写时，我们需要为其分配一个回滚段对其产生的undologcord进行记录，具体调用链路如下：
trx_assign_rsg_tmp()-gt_nxt_tmp_rsg()-(trx_sys-tmp_rsgs)
trx_sys-tmp_rsgs对应的临时文件为ibtmp1，一般来说有个回滚段。
读写事务：当一个事务被判定为读写模式时，会为其分配trx_id以及回滚段，具体调用链路如下
trx_assign_rsg_durabl()-gt_nxt_do_rsg()
-gt_nxt_do_rsg_from_trx_sys()-(trx_sys-rsgs)
-gt_nxt_do_rsg_from_undo_spacs()-(undo_spac-rsgs())
当InnoDB没有配置独立undo表空间时，从trx_sys-rsgs为读写事务分配回滚段；否则则从undo_spacs-rsgs()为其分配回滚段；InnoDB从MySQL8.0.3开始，独立表空间个数默认值从0改为2。
trx_sys-rsgs对应的文件为ibdata1，默认有个回滚段。
undo_spac-rsgs()对应的文件为undo_，undo_...，最多可有个undo文件，每个文件默认个回滚段。
具体从rsgs中分配时采用round-robin方式进行分配。
2.使用回滚段
当发生数据变更时，我们需要使用undolog记录下变更前的数据记录；因此需要从回滚段分配中来分配一个undoslot来供事务记录undo。
记录undo的入口函数为trx_undo_port_row_opration，其大致流程如下：
判断操作的表是否为临时表；如果是临时表，为其分配临时表回滚段，否则使用普通回滚段。根据事务类型，通过trx_undo_assign_undo为其分配trx_undo_t对象；之后事务产生的undo记录在此对象中。根据事务类型，通过trx_undo_pag_port_insrt/modify，来记录insrt/updat事务产生的undo。接着来看一下trx_undo_assign_undo函数流程：
首先尝试通过trx_undo_us_cachd()来获取可用的undolog对象。对于INSERT类型的undolog，我们从rsg-insrt_undo_cachd链表上获取undolog对象，并将其从链表上移除；之后通过trx_undo_insrt_hadr_us()重新初始化undopag头部信息。对于UPDATE/DELETE类型undolog，从rsg-updat_undo_cachd链表上获取undolog对象，并将其从链表上移除；然后通过trx_undo_hadr_cat()创建新的undologhadr。然后使用trx_undo_hadr_add_spac_for_xid()作用于上述undolog对象，预留XID存储空间。最后使用trx_undo_mm_init_for_us()初始化undolog对象相关信息。如果没有缓存的undolog对象，我们就需要使用trx_undo_cat()从回滚段上分配一个空闲的undoslot，并分配一个undopag，对其初始化。将已经分配好的undolog对象放入相关的链表中（rsg-insrt_undo_list或rsg-updat_undo_list）。最后，如果这个事务时DDL操作，需要将undo_hdr_pag(事务记录undolog的第一个pag)中的TRX_UNDO_DICT_TRANS置为TRUE.undohadrpag结构参考之前的《undolog的组织形式》的内容
undolog最小的并发单元为undoslot，所以undolog支持最大的并发事务为：undotablspac数*回滚段数*undoslot数。
3.undolog写入
当分配完undoslot，初始化完undolog对象后，我们就可以记录真正的undologcord；undologcord也分为一下两种，insrtundologcord与updatundocord。
当数据库需要修改某个数据记录时，都会写入一条updatundologcord；当插入一条数据记录时，会写入一条insrtundologcord。
对于insrtundolog写入的入口函数为trx_undo_pag_port_insrt()
Pvcordoffst(2)：本条cord开始的位置。Nxtcordoffst(2)：下一条cord开始的位置。Typ(1)：标记undologcord的类型，此处一般为TRX_UNDO_INSERT_REC.UndoNumbr(1-11)：trx-undo_no，事务的第几条undo。TablID(1-11)：聚集索引所对应的tablid。UniquFilds：唯一键值对于updatundolog写入的入口函数为trx_undo_pag_port_modify()
Pvcordoffst(2)：同上Nxtcordoffst(2)：同上Typ+ExtrnFlag+CompInfo(1)：Typ为undologc的类型，此处一般有三种：TRX_UNDO_DEL_MARK_REC:标记删除操作，未修改任何列值；可能由普通删除操作产生，也有可能由修改聚集索引产生，因为修改聚集索引操作被分拆为删除+插入操作。TRX_UNDO_UPD_DEL_REC:更新一个已经被删除的记录；如某个记录被删除后，在很快插入一个相同的记录；之前的记录若未被purg，就可能重用该记录所在位置。TRX_UNDO_UPD_EXIST_REC:更新一个未被标记删除的记录，也就是普通更新。ExtrnFlag：是否有外部存储列，以提示purg线程去清理外部存储。CompInfo：更新相关信息，例如更新是否导致索引序发生变化。UndoNumbr(1-11)：同上TablID(1-11)：同上InfoBits(1)：是否标记删除REC_INFO_DELETED_FLAG.DataTrxID(1-11)：修改旧记录的事务ID。DataRollPtr(1-11)：旧记录的回滚指针。UniquFilds：唯一键值UpdatGtNFilds(1-5):更新的列数。UPDOldColumns：发生更新时，旧记录的内容。DltFildsln(2):删除的列数。DELOldColumns：发生删除时，旧记录的内容；发生删除时并不总是记录旧记录，只有ord_part=1也就是说此字段为n_uniq之一的字段，才会记录旧字段。在写入过程中，可能出现undopag空间不足的情况；当出现这种情况，我们需要通过trx_undo_ras_pag_nd()来清除刚刚写入的区域，然后通过trx_undo_add_pag()申请一个新的undopag加入到undopaglist，同时将undo-last_pag_no指向新的undopag，最后重试写入。
完成undologcord的写入后，通过trx_undo_build_roll_ptr()构建新的回滚指针返回；通过回滚指针我们可以找到相关记录的undologcord，从而构建出旧版本的数据；回滚指针将会记录在聚集索引记录中。
undolog的应用我们通过之前的介绍已经了解到，undolog的组织方式与分配记录；那么后面我们继续介绍undolog主要的应用是什么。
undolog的应用主要有两方面：
事务回滚，崩溃恢复；此功能主要满足了事务的原子性，简单的说就是要么做完，要么不做。因为数据库在任何时候都可能发生宕机；包括停电，软硬件bug等。那数据库就需要保证不管发生任何情况，在重启数据库时都能恢复到一个一致性的状态；这个一致性的状态是指此时所有事务要么处于提交，要么处于未开始的状态，不应该有事务处于执行了一半的状态；所以我们可以通过undolog在数据库重启时把正在提交的事务完成提交，活跃的事务回滚，这样就保证了事务的原子性，以此来让数据库恢复到一个一致性的状态。多版本并发控制(MVCC)，此功能主要满足了事务的隔离性，简单的说就是不同活跃事务的数据互相可能是不可见的。因为如果两个活跃的事务彼此可见，那么一个事务将会看到另一个事务正在修改的数据，这样会发生数据错乱；所以我们可以借助undolog记录的历史版本数据，来恢复出对于一个事务可见的数据，来满足其读取数据的请求。我们接下来就详细介绍上面两个功能undolog是如何实现的。
1.崩溃恢复
在InnoDB因为某些原因停止运行后；重启InnoDB时，可能存在一个不一致的状态，这个时候我们就需要把MySQL恢复到一个一致的状态来保证数据库的可用性。这个恢复过程主要分下面这么几步：
把最新的undolog从dolog中恢复出来，因为undolog是受dolog保护的。根据最新的undolog构建出InnoDB崩溃前的状态。回滚那些还没有提交的事务。经过上面这三步后，InnoDB就可以恢复到一个一致的状态，并且对外提供服务。
下面我们详细的来介绍这三部分的具体过程：
1.1undolog的恢复
因为undolog受到dolog的保护，所以我们只需要根据最新的dolog就可以把undolog恢复到最新的状态；具体的调用过程如下：
cv_covry_from_chckpoint_start()//从最新的一个logchckpoint开始读取dolog并应用。
-cv_covry_bgin()//将dolog读取到logbuffr中，并将其pars到dohash中
-cv_scan_log_cs()//扫描logbuffr中的dolog，并将dohash中的dolog应用
-cv_apply_hashd_log_cs()//应用dolog到其对应的pag上。
-cv_apply_log_c()-cv_covr_pag()-cv_pars_or_apply_log_c_body()-MLOG_UNDO_INSERT…
经过上述的流程之后，undolog就可以恢复到InnoDB崩溃前的最新的状态；虽然undolog已经恢复到最新的状态，但是InnoDB还没有恢复到崩溃前的最新状态；所以下一步我们就需要根据最新的undolog把InnoDB崩溃前的内存结构都恢复出来。
1.2构建InnoDB崩溃前的状态
构建InnoDB崩溃前的状态，主要是恢复崩溃前最新事务系统的状态；通过该状态我们可以知道那些事务已经提交，那些事务还未提交，以及那些事务还未开始。
我们从前面两章的介绍，回滚段不管在内存中还是在文件中都是组织undolog的重要数据结构；所以我们首先需要把回滚段的内存结构恢复出来，然后根据内存中的回滚段，把活跃的事务恢复出来。其具体过程在函数trx_sys_init_at_db_start()中实现，其大致步骤如下：
通过trx_rsgs_init()扫描文件中的回滚段结构，来把rsg的内存结构恢复出来。通过trx_rsg_mm_cat()把last_pag_no，last_offst，last_trx_no，last_dl_marks从文件中读取上来。然后通过trx_undo_lists_init()把rsg的四个链表：insrt_undo_list，insrt_undo_cachd，updat_undo_list，updat_undo_cachd从磁盘上恢复出来。在rsg内存结构恢复好之后，我们再通过trx_lists_init_at_db_start()把活跃的事务从rsg中恢复出来。通过trx_surct_insrt()恢复活跃的插入类型的事务。通过trx_surct_updat()恢复活跃的更新类型的事务。至此，我们就已经把InnoDB崩溃前的内存和文件状态都已经恢复出来了；其实这个时候InnoDB已经可以对外提供服务了，(毕竟内存和文件状态都就绪后我们也就可以保持一致性了)；那么最后一步的事务回滚就可以交给后台线程来慢慢做事务回滚，不影响主线程对外提供服务了。
1.3事务回滚
事务需要回滚主要有两种情况：
事务发生异常：如发生在崩溃恢复时；其活跃事务虽然被恢复出来，但是无法继续，需要将其回滚。事务被显式回滚：如用户打开一个事务，执行完某些操作后需要将其回滚。那么在回滚时，我们就需要借助undolog中的旧数据来把事务恢复到之前的状态；其入口函数为row_undo_stp()；
其操作就是通过undolog来读取旧的数据记录，然后做逆向操作；主要分为下面这么几类：
对于标记删除的记录清理删除标记。对于in-plac更新，将数据更新为老版本。对于插入操作，删除聚集索引记录和二级索引记录。先通过row_undo_ins_mov_sc_c()删除二级索引记录。再通过row_undo_ins_mov_clust_c()删除聚集索引记录。2.多版本并发控制(MVCC)
多版本并发控制简单的说就是当前事务只能看见已经提交的数据记录，看不到正在修改的数据记录。所以我们只要弄清楚那些事务对于当前事务是已经提交的，那些事务对于当前事务是活跃的。
为了实现上述的功能我们先介绍几个比较关键的概念：
trx::id：事务开始的逻辑时间，也叫事务ID，在事务开始时通过trx_start_low()分配。
trx::no：事务结束的逻辑时间，在事务结束的时候通过trx_