InnoDB MVCC

梳理下MVCC的具体实现。

全文基于MySQLV8.0版本。

HiddenRow

InnoDB的每一行数据都隐藏了四个字段，具体如下：

  • DB_TRX_ID：记录更新该行最后一次的事务ID。

事务ID是不断递增的，最新的事务ID永远大于原有事务ID，便于校验事务是否已经过期。

  • DB_ROLL_PTR：记录该行回滚段（Undo Log）的指针，用于查找该行的历史数据。

  • DB_ROW_ID：在没有主键的情况下生成的隐藏单调自增ID。

被物理删除的DB_ROW_ID会被重用，。

  • DELELE_BIT：用于标识该记录是否被删除。

DELELE_BIT状态位属于逻辑删除，MySQL利用后台运行purge线程来实现异步的物理删除。

其中，DB_TRX_ID与DB_ROLL_PTR是实现MVCC的关键。

UndoLog

undolog是事务回滚与可重复读的关键。

undolog属于逻辑日志，包含每行数据的所有版本的数据，用于支持事务与MVCC特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* undo结构 */
struct trx_undo_t {
    ...
    /* undo ID */
    ulint id;
    /* 类型：insert or update */
    ulint type;  
    /* 事务ID */
    trx_id_t trx_id;
    /* undo对应回滚段 */
    trx_rseg_t *rseg;
    /* undo链表 */
    UT_LIST_NODE_T(trx_undo_t) undo_list;
    ...
}

undo_list是一个链表结构，链表节点正是trx_undo_t，也就是说UndoLog在内存里是按照链表存储的。

此外，每一个trx_undo_t都绑定了对应的事务ID、操作类型以及对应的回滚段。

redolog属于物理日志，被称为重做日志，记录数据的修改，防止数据丢失，主要用于数据库重启恢复的时候被使用。

为了提高持久化效率，可用Redo Log Buffer（重做日志缓冲）来缓存变更，达到阈值大小或定期flush到Redo Log File（重做日志文件）。

为确保每次日志都能写入到事务日志文件，每次日志缓存的写入都会调用操作系统fsync操作（将OS Buffer中的日志刷到磁盘上的Log File中）。

trx_sys_t

trx_sys_t可以被称为事务管理系统，包含MVCC、事务以及回滚段的管理。

利用volatile来实现待分配事务max_trx_id的可见性。

活跃的用户事务存储在mysql_trx_list事务链表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/* trx_t类型为节点的链表 */
typedef UT_LIST_BASE_NODE_T(trx_t) trx_ut_list_t;

/* 事务管理系统 */
struct trx_sys_t {
    ...
    /* 多版本控制器 */
    MVCC *mvcc;
    /* 下一个被分配的事务ID */
    volatile trx_id_t max_trx_id;
    /* 最小的活跃事务ID */
    std::atomic<trx_id_t> min_active_id;
    /* 最大的活跃事务ID */
    trx_id_t rw_max_trx_id;
    /* 事务链表, 包含用户事务、系统事务与恢复事务 */
    trx_ut_list_t rw_trx_list;
    /* 用户事务链表 */
    trx_ut_list_t mysql_trx_list;
    /* 回滚段列表，用于存储UndoLog */
    Rsegs rsegs;
    ...
}

Rsegs回滚段是由trx_rseg_t组成的数组，也就是说事务管理系统是由多个回滚段组成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* trx_rseg_t类型为节点的数组 */
using Rsegs_Vector = std::vector<trx_rseg_t *, ut_allocator<trx_rseg_t *>>;

/* 回滚段 */
class Rsegs {
    ...
    private:
        /* 回滚段对应的事务ID */
        trx_id_t m_trx_no;
        /* 具体的回滚段数据 */
        Rsegs_Vector m_rsegs;
    ...
}

trx_rseg_t

trx_rseg_t是事务回滚段的基本结构，是组成回滚段的基本单元。

UndoLog的存储是基于Rollback Segment实现的。

从回滚段的结构中可以得到：UndoLog是被分为update与insert两种类型的。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 事务回滚段 */
struct trx_rseg_t {
    /* 回滚段id */
    ulint id;
    ...
    /* update undo日志缓存及链表 */
    UT_LIST_BASE_NODE_T(trx_undo_t) update_undo_list;
    UT_LIST_BASE_NODE_T(trx_undo_t) update_undo_cached;
    /* insert undo日志缓存及链表 */
    UT_LIST_BASE_NODE_T(trx_undo_t) insert_undo_list;
    UT_LIST_BASE_NODE_T(trx_undo_t) insert_undo_cached;
    ...
}

trx_undo_t的具体结构在上面已经介绍过了，是具体存储UndoLog的结构。

ReadView

ReadView是用来判断undolog中多版本数据的可见性。

每一个事务都包含一个ReadView。

trx_t是事务的结构体，每一个事务都包含一个read_view字段。

1
2
3
4
5
6
7
8
9
/* 事务 */
struct trx_t {
  ...
  /* 事务ID */
  trx_id_t id;
  /* 解决可见性 */
  ReadView *read_view;
  ...
};
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
/* ReadView事务可见范围 */
class ReadView {
    /* 大于该ID的事务不可见（high water mark） */
    trx_id_t m_low_limit_id;
    /* 小于该ID的事务不可见（low water mark） */
    trx_id_t m_up_limit_id;
    /* 创建ReadView的事务ID */
    trx_id_t m_creator_trx_id;
    /* 创建ReadView时活跃事务 */
    ids_t m_ids;
    /* 用于记录可被purge清理的事务 */
    trx_id_t m_low_limit_no;
    /* 状态 */
    bool m_closed;
    
    typedef UT_LIST_NODE_T(ReadView) node_t;
    
    /* 具体view链表 */
    byte pad1[64 - sizeof(node_t)];
    node_t m_view_list;
}

#define UT_LIST_NODE_T(TYPE)/
struct {/
       TYPE *   prev;       /* pointer to the previous node, NULL if start of list *//
       TYPE *   next;       /* pointer to next node, NULL if end of list *//
}/

InnoDB每次创建一个事务，都会创建一个包含当前活跃事务列表以及保证事务可见性的ReadView。

事务的可见性的判断规则如下：

① m_ids中大于m_low_limit_id的事务不可见；
② m_ids中小于m_up_limit_id的事务可见。

针对相同事务的不同隔离级别，m_low_limit_id与m_up_limit_id是不同的，

  • 对于RC来说，已提交事务的数据对当前事务来说是可见的；
  • 对于RR来说，事务启动前所有未提交事务的数据对当前事务来说都是不可见的。

Reference

innodb-multi-versioning
trx0sys_8h_source
trx0trx_8h_source
read0types_8h_source
InnoDB事务分析-undo log
InnoDB的事务分析-MVCC
InnoDB 内核阅读笔记（十二）- 事务处理