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 其他事务细节. 本文基于 MySQL 版本8.0.13.

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 定义了回滚段 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 Tablespace 的文件结构 Header */
                |    -------------------
                --> | fsp_header_init() |
                |    -------------------
                |
                |    /* 创建回滚段目录Page */
                |    -------------------------
                --> | trx_rseg_array_create() |
                     -------------------------

Undo Tablespace 结构体

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

  • 回滚段由 transaction system 的 header 串联.

  • 空闲 Undo Log Segment 在回滚段的 Header Page 由 TRX_RSEG_UNDO_SLOTS 存放 (TRX_RSEG_UNDO_SLOTS + n * TRX_RSEG_SLOT_SIZE).

  • Undo Log Segment 的 Undo Page 由 TRX_UNDO_PAGE_NODE 串联.

初始化 Undo Tablespace

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

  • Undo Tablespace 通过srv_undo_tablespace_create()创建，并默认分配 UNDO_INITIAL_SIZE_IN_PAGES(16MB) 大小的空间.

创建回滚段

每个 Undo Tablespace 中有128个回滚段. 每个回滚段用来管理 Undo Log, 每个回滚段维护了一个 Rollback Segment Header Page, 在默认 16KB 的情况下，回滚段 Header Page 划分了 1024 个 Undo Slots, 一个 Undo Slot 对应一个 Undo Log Segment 对象, 即事务启动时分配的 Undo Log 空间. 回滚段的内存数据结构是trx_rseg_t, Undo Tablespace 中的Rsegs是trx_rseg_t的std::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 创建 Rollback Segment, 这里的每一个 Rollback Segment 申请 File Segment, 具体细节参考InnoDB的文件组织结构, 所以可以理解为一个回滚段 Roll Segment 对应一个文件形式的 Segment.

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

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

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

事务流程

为了保证事务并发操作时, 在写各自的 Undo Log 时不产生冲突, InnoDB 采用回滚段的方式来维护 Undo Log 的并发写入和持久化. 回滚段保存 Undo Log Segment 在表空间中的位置，并将已经提交事务的 Undo Log 保存到 HISTORY 链表中, 而 Undo Log Record 是记录在 Undo Log Segment 中.

分配回滚段

当开启一个读写事务时，我们需要为其分配一个回滚段，需要注意的是一个回滚段并不是一个事务独占的, 回滚段申请流程如下:

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
    2
    3
    4
    5
    6
    7
    迭代方式如下:  (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;
    • 分配回滚段成功后, 递增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 (insert/update) 操作记录 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:

    • 对于复用的 Undo Page, 针对 Insert 类型可以直接覆写 Undo Log Header (可以通过 Read View 保证读正确性), 而对于 Update 类型需要采用 Append 方式创建 Undo Log Header (目前不能保证是否还存在读事务需要回溯 Undo Page 上的旧版本, Update 类型的 Undo Log 最后清理都是由 Purge 操作完成), 所以 Update 类型的 Undo Page 可能存在多个 Undo Log Header.

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

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

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

    • 初始化 Undo Log Segment 的 Header Page 并更新回滚段的中关于 Undo Log 的 Slots: TRX_RSEG_UNDO_SLOTS

    • 根据事务的 DML 类型 TRX_UNDO_INSERT 或 TRX_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 写入:

Insert 操作的 Undo Record 格式

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

undo_insert_record

Update 操作的 Undo Record 格式

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

undo_update_record

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

完成 Undo Log 的分析之后, 我们可以确定 Undo Tablespace 的基本结构: Undo Tablespace -> Undo Rollback Segment -> Undo Log (slot). 其中 Undo Rollback Segment 和 Undo Log 都是以文件形式的 Segment 组织在 Undo Tablespace 中.

事务 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 清理. 记录 Update 操作的 Undo Log 依然可以被重用, 判断条件与 Insert 操作一致:

  • 将 Undo Log 对应的回滚段trx_rseg_t插入purge_sys->purge_queue: trx_serialisation_number_get(), 并根据上述重用的逻辑判断更新undo->state状态为TRX_UNDO_TO_PURGE或者TRX_UNDO_CACHED: trx_undo_set_state_at_finish().

  • 获取对应 Rollback Segment Header，并将已经 commit 的 Undo Log Header 插入 Rollback Segment Header Page 的TRX_RSEG_HISTORY链表. 同时更新该回滚段trx_rseg_t上最后一个需要 Purge 的 Undo Log 信息, 防止trx_rseg_t再次被添加到Purge队列: trx_undo_update_cleanup:

1
2
3
4
5
6
7
if (rseg->last_page_no == FIL_NULL) {
  /* 更新 trx_rseg_t 信息. */
  rseg->last_page_no = undo->hdr_page_no;
  rseg->last_offset = undo->hdr_offset;
  rseg->last_trx_no = trx->no;
  rseg->last_del_marks = undo->del_marks;
}

事务回滚

事务在回滚后, 需要对修改过的 Record 做回滚处理, Record 的回滚逻辑是通过获取回滚段上 Undo Log Segment 的 Record 通过row_undo_ins()回滚 Insert 操作、row_undo_mod()回滚 Update 操作.

而对应的 Undo Log Segment 的非 Header Page 可以通过trx_undo_free_last_page()逐个回收并被复用.

Undo Log 的 Purge

在 InnoDB 的删除操作实现中通常实现为伪删除, 即仅仅标记为TRX_UNDO_DEL_MARK_REC因此并未真正的物理删除的 Record, 用户的读取需要通过 undo log 来回溯可见的版本, 在事务 commit 之后, 我们需要在 Purge 阶段对 Record 和相关索引进行清理.

相关数据结构

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
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为１, 在事务 commit 之后数据页上数据也要进行对应的处理. Undo Log 的清理和数据 Page 的 Purge 工作交由专门的 Purge 线程处理, Purge 线程的数量为 1 + N, 即 1 个协作线程和 N 个工作线程处理.

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

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

  • trx_purge_attach_undo_recs(): 首先从purge_sys->purge_queue选择回滚段, purge_sys会根据回滚段的trx_no 与purge_sys->view.low_limit_no()比较判断是否可以 Purge : trx_purge_fetch_next_rec().

    1. 从purge_sys队列选择下一个待 Purge 的回滚段trx_rseg_t: trx_purge_choose_next_log(), 通过purge_sys->rseg->last_page_no和purge_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 要求的 Undo Log, 可以根据purge_sys指向的 Undo Record, 构造 roll ptr trx_undo_build_roll_ptr().

    3. 构造完成当前的 roll ptr, purge_sys会尝试获取下一条待 Purge 的 Undo Record trx_purge_get_next_rec(), 并以此更新purge_sys元信息, 方法同上.

  • 将获取的 Undo Record 交由 Purge 工作线程并处理对应的数据 Record row_purge(), 一次 Purge 操作允许最大多少个 Undo Log 页被 Purge 由参数 innodb_purge_batch_size 控制，默认300.

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

    1. 针对 Rollback Segments 的 Truncate 的操作, purge_sys使用purge_sys->limit和purge_sys->view保证正在 Purge 的回滚段不会正在被 Truncate.

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

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

    • 对于可以被复用TRX_UNDO_CACHED的 Rollback Segment，直接选择从 history list 中摘除trx_purge_remove_log_hdr().

    • 对于需 Truncate 的 Rollback Segment, 调用trx_purge_free_segment()回收空间, 具体策略依然是 fsp 回收策略:fseg_free_step().

Undo Tablespace 的 Truncate

在完成 Undo Log 的 Purge 和 Truncate 之后会针对 Undo Tablespace 进行 Truncate, 注意这里是 Undo Tablespace 的 Truncate, 不要与 Rollback segments 的 Truncate 混淆. 具体策略是判断 Undo Tablespace 是否符合 Truncate 的条件即当前 Undo Tablespace 的 Page 数量是否超过了参数srv_max_undo_tablespace_size限制:

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 判断是否满足 Truncate 条件, 即 Undo Tablespace 的大小超过 srv_max_undo_tablespace_size. */
if (fil_space_get_size(space_id) >
    (srv_max_undo_tablespace_size / srv_page_size)) {
  
  /* Tablespace qualifies for truncate. */

  undo_trunc->increment_scan();

  /* 标记为待 Truncate */
  undo_trunc->mark(space_id);

  break;
}

Undo Tablspace 的 Truncate 操作需要确保所有的 Rollback Segment 均不包括活跃的 Undo Log, Undo Tablespace 的 Truncate 流程如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 --------------------------------
| trx_undo_truncate_tablespace() |
 --------------------------------
  |
  |     /* Undo 文件进行 Truncate */
  |    ---------------------------
  --> | fil_truncate_tablespace() |
  |    ---------------------------
  |
  |    /* 初始化 Undo Tablespace Header */
  |    -------------------
  --> | fsp_header_init() |
  |    -------------------
  |
  |    /* 创建 Rollback Segment 目录 */
  |    -------------------------
  --> | trx_rseg_array_create() |
  |    -------------------------
  |
  |    /* 依次创建回滚段 */
  |    --------------------------
  --> | trx_rseg_header_create() |
       --------------------------

总结

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