Undo Log

MySQL版本: 8.0.13

InnoDB 使用 MVCC 来解决事务的并发控制,而其中 Undo Log 是 MVCC 的重要组成部分。一条 Undo Log 对应一个事务中的一条读写语句,Undo Log 记录了被修改的 Record 的旧版本数据,当其他的事务需要读取该记录的旧版本时,通过 Undo Log 可以回溯到对应的版本的数据. 另外当事务需要回滚时,也可以根据 Undo Log 进行数据的回滚.

这里我们介绍 Undo Log 的相关数据结构和设计,InnoDB事务分析-MVCC 介绍了 MVCC 和 InnoDB 其他事务细节.

Undo Log

事务中的四种操作会产生Undo Log:

  1. INSERT operations on user-defined tables
  2. UPDATE and DELETE operations on user-defined tables
  3. INSERT operations on user-defined temporary tables
  4. UPDATE and DELETE operations on user-defined temporary tables

Undo Log 相关数据结构

Undo Tablespace

在MySQL中, Undo tablespace 使用独立的表空间, Undo tablespace 定义了回滚段innodb_rollback_segments用来存放 Undo Log,Undo tablespace 默认的最小数量是2个,在MySQL初始化时创建: srv_undo_tablespaces_init() -> srv_undo_tablespaces_create() -> srv_undo_tablespace_create().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 -------------
| srv_start() |
-------------
|
| /* 初始化Undo Tablespace */
| -----------------------------
--> | srv_undo_tablespaces_init() |
-----------------------------
|
| /* 创建默认数量的Undo Tablespace, 并创建文件undo_xxx */
| -------------------------------
--> | srv_undo_tablespaces_create() |
| -------------------------------
|
| /* 初始化Undo Tablespace文件结构 */
| --------------------------------------
--> | srv_undo_tablespaces_construct() |
--------------------------------------
|
|
| /* 初始化Undo Tablespce的文件结构Header */
| -------------------
--> | fsp_header_init() |
| -------------------
|
| /* 创建回滚段目录Page */
| -------------------------
--> | trx_rseg_array_create() |
-------------------------
1
2
3
4
5
6
7
8
9
10
11
12
13
/* storage/innobase/include/trx0purge.h */

/* Undo Tablespace */
struct Tablespace {
/* ... */
private:
space_id_t m_id; /* Undo Tablespace的ID. */

space_id_t m_num; /* Undo Tablespace的Number, 从1至127. */

/* ... */
Rsegs *m_rsegs; /* 回滚段 */
};

下图为Undo Tablespace的逻辑示意图:

undo_tablespace

初始化Undo Tablespace

Undo Tablespace的起始space id是4294967154, 支持最大的Undo Tablespace个数为127个, 所以终止space id为4294967280.

  • Undo Tablespace通过srv_undo_tablespace_create()创建,并默认分配 SRV_UNDO_TABLESPACE_SIZE_IN_PAGES(10MB) 大小的空间.

创建回滚段

每个Undo Tablespace中有128个回滚段. 每个回滚段用来管理Undo Log, 每个回滚段维护了一个回滚段Header Page, 在默认16KB的情况下,回滚段Header Page划分了1024个Undo Slots, 一个Undo Slot对应一个Undo Log对象, 即事务启动时分配的Undo Log空间. 回滚段的内存数据结构是trx_rseg_t,Undo Tablespace中的Rsegstrx_rseg_tstd::vector封装. 在DB init阶段初始化 Undo Tablespace 后依次为每个 Undo Tablespace 创建128个回滚段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 /* DB init */
-------------
| srv_start() |
-------------
|
| /* 添加回滚段 */
| -------------------------------------
--> | trx_rseg_adjust_rollback_segments() |
-------------------------------------
|
|
| /* 创建回滚段 */
| ----------------------------------
--> | trx_rseg_add_rollback_segments() |
----------------------------------
|
| /* 创建回滚段文件结构 */
| -------------------------
--> | trx_rseg_create() |
| -------------------------
| |
| |
| | /* 创建回滚段Header */
| | ---------------------------
| --> | trx_rseg_header_create() |
| ---------------------------
|
| /* 创建并初始化trx_rseg_t */
| -----------------------------
--> | trx_rseg_mem_create() |
-----------------------------
  • 为指定的Undo Tablespace创建Segment, 这里的Segment对应文件组织结构的Segment, 具体细节参考InnoDB的文件组织结构, 所以可以理解为一个回滚段Roll Segment对应一个文件形式的Segment.

  • 每个Undo Tablespace默认创建128个回滚段, 文件形式的Segment创建成功后返回的Segment Header Page作为回滚段的Header Page, 并初始化回滚段Header Page中的TRX_RSEG_MAX_SIZE, TRX_RSEG_HISTORY_SIZE 和 文件链表TRX_RSEG_HISTORY. 初始化回滚段Roll Segment Header的Undo Slots字段为FIL_NULL, 一个回滚段默认1024个 Undo Log Slot.

  • 获取 Undo Tablespace 的回滚段目录的Page, 回滚段目录Header固定在 Undo Tablspace 的第3 (FSP_RSEG_ARRAY_PAGE_NO) 个Page, 页内偏移为 RSEG_ARRAY_HEADER. 将创建的回滚段的Header Page No插入Undo Tablespace中的回滚段目录(trx_rsegsf_set_page_no()).

  • 创建回滚段内存结构trx_rsegs_t并插入 Undo Tablespace 的Rsegs.

事务流程

为了保证事务并发操作时,在写各自的 Undo Log 时不产生冲突,InnoDB 采用回滚段的方式来维护 Undo Log 的并发写入和持久化.

分配回滚段

当开启一个读写事务时,我们需要为其分配一个回滚段,回滚流程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
     /* 分配回滚段 */
----------------------------
| trx_assign_rseg_durable() |
----------------------------
|
|
| ----------------------
-> | get_next_redo_rseg() |
----------------------
|
|
| -----------------------------------
-> | get_next_redo_rseg_from_trx_sys() |
| -----------------------------------
|
| ---------------------------------------
-> | get_next_redo_rseg_from_undo_spaces() |
---------------------------------------

分配方式:

  • 通过判断trx_sys->rsegs是否为空,假如不为空则直接从trx_sys->rsegs获取(从trx_sys->rsegs中取模迭代获取),否则从 Undo Tablespace 中获取.

get_next_redo_rseg_from_undo_spaces()

  1. 采用轮询的方式获取回滚段
1
2
3
4
5
6
7
8
迭代方式如下:  (space, rseg_id)
(0,0), (1,0), ... (n,0), (0,1), (1,1), ... (n,1), ... */
static ulint rseg_counter = 0;
ulint current = rseg_counter;
ulint window =
current % (target_rollback_segments * target_undo_tablespaces);
ulint spaces_slot = window % target_undo_tablespaces;
ulint rseg_slot = window / target_undo_tablespaces;
  1. 分配回滚段成功后, 递增rseg->trx_ref_count, 并由trx->rsegs.m_redo.rseg指向分配的回滚段递增rseg->trx_ref_count

使用回滚段

我们以insert操作举例, insert一条Record的流程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 ----------------
| ha_write_row() |
----------------
|
| --------------------------
-> | ha_innobase::write_row() |
--------------------------
|
| ------------------------
-> | row_insert_for_mysql() |
------------------------
|
| ----------------------------------------
-> | row_insert_for_mysql_using_ins_graph() |
----------------------------------------
|
| ----------------
-> | row_ins_step() |
----------------
|
| -----------
-> | row_ins() |
-----------
|
| ----------------------------
-> | row_ins_index_entry_step() |
----------------------------
|
| -----------------------
-> | row_ins_index_entry() |
-----------------------
|
| /* 假如插入的Record为聚簇索引. */
| -----------------------------
---> | row_ins_clust_index_entry() |
| -----------------------------
|
| /* 假如插入的Record非聚簇索引,但为多个value. */
| ---------------------------------------
---> | row_ins_sec_index_multi_value_entry() |
| ---------------------------------------
|
| /* 假如插入的Record为二级索引的单个value. */
| ---------------------------
---> | row_ins_sec_index_entry() |
---------------------------

我们以插入一条聚簇索引的Record为例,row_ins_clust_index_entry()调用row_ins_clust_index_entry_low()实现具体的Record插入操作,下面是代码流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 ---------------------------------
| row_ins_clust_index_entry_low() |
---------------------------------
|
| -----------------------------
-> | btr_cur_optimistic_insert() |
-----------------------------
|
| -----------------------------
-> | btr_cur_ins_lock_and_undo() |
-----------------------------
|
| /* 对DML操作记录Undo Log */
| ---------------------------------
-> | trx_undo_report_row_operation() |
---------------------------------

btr_cur_ins_lock_and_undo() 检查相关的 lock 并根据事务决定是否记录 Undo Log, 假如需要记录 Undo Log 而 trx_undo_report_row_operation()根据DML类型例如update, insert或者delete进行写 Undo Log 的操作.

写入Undo Log

在事务启动时,我们为其分配了回滚段, 在trx_undo_report_row_operation()即真正写入 Undo Log 的操作中,我们需要为事务申请 Undo Log (trx_undo_assign_undo()), 对于临时表记录 Undo Log 不需要写 Redo Log.

申请 Undo Log 的流程如下:

  • 首先尝试从回滚段上的 reuse list 获取 Undo Log

  • 假如从回滚段的 reuse list 申请失败则需要基于事务启动时分配的回滚段申请 Undo Log 空间(trx_undo_create()):

    • 首先获取回滚段 Header(trx_rsegf_get()).

    • 从回滚段 Header 获取空闲的 Slot (trx_rsegf_undo_find_free()), 每一个 Undo slot 对应一个File Segment. (Segment的结构见InnoDB的文件组织结构)

    • 初始化Undo Log Segment的Header Page并更新回滚段的TRX_RSEG_UNDO_SLOTS

    • 根据事务的DML类型TRX_UNDO_INSERTTRX_UNDO_UPDATE分别创建的trx_undo_t加入对应的list:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      if (type == TRX_UNDO_INSERT) {
      UT_LIST_ADD_FIRST(rseg->insert_undo_list, undo);
      ut_ad(undo_ptr->insert_undo == NULL);
      undo_ptr->insert_undo = undo;
      } else {
      UT_LIST_ADD_FIRST(rseg->update_undo_list, undo);
      ut_ad(undo_ptr->update_undo == NULL);
      undo_ptr->update_undo = undo;
      }

当我们完成Undo Log写入空间的申请分配之后,就可以开始进行真正的Undo Log写入:

  • 对于TRX_UNDO_INSERT_OP即事务中的Record写入操作, 具体的函数为trx_undo_page_report_insert().

Insert操作的Undo Record格式

undo_insert_record

  • 对于TRX_UNDO_INSERT_OP即事务中的Record修改操作, 具体的函数为trx_undo_page_report_modify().

Update操作的Undo Record格式

undo_update_record

Undo Log写入成功后,需要构建roll ptr (trx_undo_build_roll_ptr()), 并更新聚簇索引Record的roll_ptr字段.

事务Commit

入口函数: trx_commit() --> trx_commit_low()

在事务Commit阶段,我们需要对 Undo Log 做一些处理.

对于Insert Record操作,我们可以直接清理Undo Log, 因为insert操作的记录只是对于本事务可见,所以它们不再需要被访问. 首先判断Insert Record操作产生的Undo Log是否可以被重用,并设置状态为TRX_UNDO_CACHED或者TRX_UNDO_TO_FREE. 是否能被复用的逻辑是该Undo Log所使用的Page数量为1,并且所占Page的空间不足3/4即可被重用.

对于Update Record操作,为了保证MVCC的正确性,我们需要选择合适的时机才能够将Undo Log清理.

  • 将Undo Log对应的rseg插入purge_sys->purge_queue, 并更新undo->state状态为TRX_UNDO_TO_PURGE.

  • 获取对应回滚段的Header,并将已经Commit的Undo Log Header插入回滚段Header的TRX_RSEG_HISTORY链表. 同时记录该回滚段rseg上第一个需要Purge的Undo Log信息, 防止rseg再次被添加到Purge队列.

Undo Log的Purge

相关数据结构

purge_sys是Purge操作控制数据结构, 为了方便理解, 我们对其部分重要的数据成员作介绍:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

trx_purge_t *purge_sys = NULL;

/** The control structure used in the purge operation */
struct trx_purge_t {
/* ... */
que_t *query; /*!< 执行Purge操作的SQL */

ReadView view; /*!< 当前事务系统中最旧的Read View, 大于这个
Read View的Undo Log都不能被Purge */

purge_iter_t iter; /* 当前正在做Purge的回滚段 */
purge_iter_t limit; /* 限制history list的Truncate */

/* ... */
trx_rseg_t *rseg; /*!< 下一个Purge的回滚段 */

page_no_t page_no; /*!< 下一个Purge的Undo Log Record的Page Number */

ulint offset; /*!< 下一个Purge的Undo Log Record的页内Offset */

page_no_t hdr_page_no; /*!< 下一个Purge的Undo Log Segment的Header Page Number */

ulint hdr_offset; /*!< 下一个Purge的Undo Log Sement的Header Page的Offset */


/* ... */
purge_pq_t *purge_queue; /*!< Purge队列,包含所有待Purge的回滚段 */

/* ... */
};

Undo Log在不需要再被回溯访问到时需要进行清理, 另外对于删除和更新操作, InnoDB并不是真正的删除旧的记录,而是设置record的del_marks为1, 所以数据页上数据也要进行对应的处理. Undo Log的清理和数据Page的Purge工作交由专门的Purge线程处理, Purge线程的数量为1+N, 即1个协作线程和N个工作线程处理.

入口函数: srv_do_purge() --> trx_purge()

  • 判断可见性: 当Purge线程进行清理工作时,需要确保MVCC的正确性,即清理不会再被访问的Undo Log, 所以会选择当前活跃的Read View链表中最旧的一个MVCC::get_oldest_view(), 所有小于当前最旧的Read View的trx_no的Undo Log都可以被清理.

  • 选择被Purge的Undo Record: 调用trx_purge_attach_undo_recs()向Purge工作线程分发待Purge的Undo Record, 一次Purge操作允许最大多少个Undo Log页被Purge由参数innodb_purge_batch_size控制,默认300.

    1. 首先从purge_sys选择下一个待Purge的rseg(trx_purge_choose_next_log()), 通过purge_sys->rseg->last_page_nopurge_sys->rseg->last_offset确定Undo Log中的第一条Undo Record,并更新purge_sys:

      1
      2
      3
      4
      5
      6
      purge_sys->offset = offset;                                                                                                                                 
      purge_sys->page_no = page_no;
      purge_sys->iter.undo_no = undo_no;
      purge_sys->iter.modifier_trx_id = modifier_trx_id;
      purge_sys->iter.undo_rseg_space = undo_rseg_space;
      purge_sys->next_stored = TRUE;
    2. 根据purge_sys指向的Undo Record, 构造roll ptr(trx_undo_build_roll_ptr()).

    3. 获取下一条待Purge的Undo Record, 并以此更新purge_sys, 方法同上.

  • 将fetch的Undo Record交由Purge工作线程并处理对应的数据Record(que_run_threads()):

  • 当Undo Record对应的旧版本数据被Purge后,Undo Page上的Undo Log也可以被清理了即truncate(trx_purge_truncate()), 默认每隔128次进行一次清理, 由参数srv_purge_rseg_truncate_frequency控制:

    1. 对于Undo Log的Truncate的操作, purge_sys使用purge_sys->limitpurge_sys->view保证Truncate的回滚段不会正在做Purge操作.

    2. 迭代undo_space->rsegs()选择回滚段调用trx_purge_truncate_rseg_history().

    3. 通过回滚段的TRX_RSEG_HISTORY链表选择第一个需Truncate的Undo Log Segment, 所有事务提交的Undo Log都通过TRX_UNDO_HISTORY_NODE串联起来:

      • 对于被复用的Undo Log Segment,直接选择从history list中摘除(trx_purge_remove_log_hdr()).

      • 对于需Truncate的Undo Log Segment, 调用trx_purge_free_segment()回收空间.

总结

通过源码分析详细介绍了Undo Log的文件组织方式、分配和回收, 旨在帮助理解MySQL的事务流程. 顾名思义,一个Undo日志记录包含当前某个事务如何撤消最近的变化, 如果任何其他事务查询原始数据(行), Undo Log可以帮助回溯旧的数据. Undo Log服务于MVCC, 实现数据的多版本.