MySQL · TokuDB · 事务子系统和 MVCC 实现

前言

之前有篇月报是关于innodb事务子系统的《MySQL · 引擎特性 · InnoDB 事务子系统介绍》 里面较详细的讲述了 MySQL 如何开启一个事务，感兴趣的同学可以先阅读那篇温习一下。

TokuDB 引擎也支持事务，保证一个事务内的所有操作都执行成功或者都未被执行。TokuDB中的事务由数据结构 tokutxn 表示。当开启一个 txn 时，TokuDB会创建一个 tokutxn 实例，下面只显示比较重要的字段。

struct tokutxn {
    TXNID_PAIR txnid;                             // 事务ID
    uint64_t snapshot_txnid64;                    // 快照ID
    const TXN_SNAPSHOT_TYPE snapshot_type;        // 快照类型
    const bool for_recovery;                      // 是否处于recovery过程
    struct tokulogger* const logger;              // logger子系统handle
    struct tokutxn* const parent;                 // parent事务
    struct tokutxn* child;                        // child事务
    txn_child_manager* child_manager;             // child事务的txn manager
    xid_omt_t* live_root_txn_list;                // 活跃读写事务列表，记录这个txn开始时刻系统所有活跃读写事务。按txnID（事务开启时间）从小到大排列
    struct XIDS_S* xids;                          // 对于nested txn，记录这个txn和他所有祖先txn。xids[0]是最老的祖先事务
    struct tokutxn* snapshot_next;                // 链到txn_manager的snapshot list双向链表的连接件
    struct tokutxn* snapshot_prev;                // 链到txn_manager的snapshot list双向链表的连接件
    toku_mutex_t txn_lock;                        // txn的互斥锁
    struct txn_roll_info roll_info;               // rollback段的管理结构
};

开启txn

TokuDB开启txn会调用toku_txn_begin_with_xid 函数创建tokutxn实例并进行初始化。每个TokuDB txn都有一个唯一的txnid，如果是snapshot读还有一个唯一的snapshot_txnid64。toku_txn_begin_with_xid 根据 parent 是否为NULL和for_recovery是否为TRUE调用相应的函数来设置：

• 设置txnid；
• 如果是snapshot操作，设置snapshot_txnid64；
• 如果是snapshot操作，创建live_root_txn_list：表示这个txn能看到的view，在下面的isolation level一节会展开讨论；
• 如果是snapshot操作，需要把这个txn加到txn_manager的snapshot list双向链表尾部；
• 创建xids数组：nested txn数组，xids[0]表示最老的祖先txn；
• 如果是读写事务，这个txn也在它的live_root_txn_list上。

代码片段：

int
toku_txn_begin_with_xid (TOKUTXN parent, TOKUTXN *txnp, TOKULOGGER logger, TXNID_PAIR xid, TXN_SNAPSHOT_TYPE snapshot_type, DB_TXN *container_db_txn, bool for_recovery, bool read_only)
{
    int r = 0;
    TOKUTXN txn;
    //创建并初始化tokutxn
    toku_txn_create_txn(&txn, parent, logger, snapshot_type, container_db_txn, for_recovery, read_only);
    if (for_recovery) {
        if (parent == NULL) {
            assert(xid.child_id64 == TXNID_NONE);
            toku_txn_manager_start_txn_for_recovery(txn, logger->txn_manager, xid.parent_id64);
        }
        else {
            parent->child_manager->start_child_txn_for_recovery(txn, parent, xid);
        }
    }
    else {
        assert(xid.parent_id64 == TXNID_NONE);
        assert(xid.child_id64 == TXNID_NONE);
        if (parent == NULL) {
            toku_txn_manager_start_txn(txn, logger->txn_manager, snapshot_type, read_only);
        }
        else {
            parent->child_manager->start_child_txn(txn, parent);
            toku_txn_manager_handle_snapshot_create_for_child_txn(txn, logger->txn_manager, snapshot_type);
        }
    }
    if (!read_only) {
        txn_create_xids(txn, parent);
    }
    *txnp = txn;
exit:
    return r;
}

这里不考略recovery（即for_recovery为TRUE）的情况。对于一般的事务，caller传过来的xid参数为{TXNID_NONE，TXNID_NONE}，txn->txnid 在这个函数里生成。parent==NULL，表示是root txn 的情况；否则是nested child txn的情况。细心的朋友可能会发现传入参数xid和struct tokutxn的txnid域的类型是TXNID_PAIR，定义如下：
typedef struct txnid_pair_s { TXNID parent_id64; TXNID child_id64; } TXNID_PAIR;

parent_id64 表示root txn的txnid，child_id64只对nested child txn有意义，表示child的txnid。

提交txn

TokuDB 提交 txn 最终会调到toku_rollback_commit。如果是root txn调用apply_txn对rollback log的每一个item进行commit操作。如果是nested child txn把child txn的rollback log挂到parent的rollback log尾部，等到root txn 提交的时候对所有rollback log的item进行commit。apply_txn的最后一个参数是一个回调函数，txn->commit时，传给apply_txn的回调函数是toku_rollback_commit。需要注意的是，对于大部分DML操作rollback log item->commit都是noop。

回滚txn

如果txn中发生错误或者上层显示调用rollback命令，TokuDB最终调用toku_rollback_abort回滚这个txn的所有操作。toku_rollback_abort也是调用apply_txn来对rollback log的每一个item进行abort操作。txn->txn_abort时，传给apply_txn的回调函数是toku_rollback_abort。它对每个rollback log item记录的key发FT_ABORT_ANY消息进行回滚。

Rollback log

这里我们一起来看看rollback log吧。TokuDB txn的rollback log的信息记录在tokutxn->roll_info域里面。

struct txn_roll_info {
    uint64_t num_rollback_nodes;              // rollback node个数
    uint64_t num_rollentries;                  // rollback entry总个数
    uint64_t num_rollentries_processed;         //已经处理过得rollback entry个数
    uint64_t rollentry_raw_count;               // rollback entry的总字节数
    BLOCKNUM spilled_rollback_head;           // spilled rollback双向链表头
    BLOCKNUM spilled_rollback_tail;             // spilled rollback双向链表尾
    BLOCKNUM current_rollback;                // 当前rollback node
};

txn修改数据的动作会记录在tokutxn->roll_info。current_rollback指向的数据节点里面，这些节点被称为rollback node也是缓存在catchetable里面，请参阅之前月报 《MySQL · TokuDB · Cachetable 的工作线程和线程池》 对cachetable的描述。如果一个txn修改了大量数据，一个rollback node存不下怎么办呢？TokuDB的处理方式是在每次往current_rollback里面添加新的undo信息时调用函数toku_maybe_spill_rollbacks判断current_rollback是否已满，若是则把current_rollback挂到spilled_rollback_head所指向的双向链表的末尾，此后有新的undo要写的时候，需要再申请一个新的rollback node作为current_rollback。提交nested child txn时，如果child txn有spilled rollback log，需要先调用toku_logger_save_rollback_rollinclude在parent的current rollback里新加一个rollback log entry把child txn的spilled rollback信息记录在里面。

Isolation level

前面描述了TokuDB中一个txn是如何开始和如何结束的，描述的都是单独一个txn是怎么工作的。当有多个txn并发执行对同一个数据的修改时，用户看到的行为又将如何呢？
数据库有四种isolation level，定义可以参考 wiki。

• Read uncommitted：读最新数据，缺点：可能读到脏数据
• Read committed：读最近一次commit数据，缺点：在一个txn内多次重复执行同一条query结果集可能不同
• Repeatable read：读txn开始时刻commit数据，缺点：可能出现幻读
• Serializable：行为上类似串行执行，缺点：性能开销大

一般的应用场景使用read committed或者repeatable read隔离级别。简单的说，Read committed读到的是stmt开始时刻committed的数据；repeatable read读到的是txn开始时刻committed的数据。

下面我们一起来看看TokuDB是如何实现这两种isolation level的。

TokuDB在txn->txn_begin把sql的isolation level (repeatable read在MySQL里映射成snapshot) 映射成TokuDB的isolation level，映射如下表所示：

TokuDB隔离级别

最后一列是snapshot type，在txn->begin的时候会根据snapshot type 建立live_root_txn_list。对于TXN_SNAPSHOT_CHILD（也就是read committed），每个txn （即使是nested child txn）都会新创建一个snapshot, 生成全局唯一的snapshot_txnid64，txn->live_root_txn_list是当前这个tokutxn开始时刻的活跃读写事务列表。对于TXN_SNAPSHOT_ROOT（也就是Repeatable read），root txn在txn->txn_begin的时候会创建一个新的snapshot，生成全局唯一的snapshot_txnid64，root txn的 live_root_txn_list 是这个root tokutxn开始时刻的活跃读写事务列表；对于nested child txn在txn->txn_begin的时候不会创建新的snapshot，而是继承root tokutxn的live_root_txn_list。
判断是否要创建新的snapshot的函数如下：

inline bool txn_needs_snapshot(TXN_SNAPSHOT_TYPE snapshot_type, struct tokutxn *parent) {
    // we need a snapshot if the snapshot type is a child or if the snapshot type is root and we have no parent.
    // Cases that we don't need a snapshot: when snapshot type is NONE or when it is ROOT and we have a parent
    return (snapshot_type != TXN_SNAPSHOT_NONE && (parent==NULL || snapshot_type == TXN_SNAPSHOT_CHILD));
}

顺便说一下，Serializable 隔离级别是在row lock层实现的，请参阅之前月报《MySQL · TokuDB · TokuDB 中的行锁》。在c_set_bounds函数，如果是Serializable隔离级别需要获取row lock的读锁，其他的隔离级别在读的时候不需要拿row lock。需要提一点的是，TokuDB在实现row lock的模块里，隐式地将读锁升级为写锁。所以，Serializable隔离级别下，并发访问同一行的多个txn是串行执行的。代码片段如下：

static int
c_set_bounds(DBC *dbc, const DBT *left_key, const DBT *right_key, bool pre_acquire, int out_of_range_error) {
    //READ_UNCOMMITTED and READ_COMMITTED transactions do not need read locks.
    if (!dbc_struct_i(dbc)->rmw && dbc_struct_i(dbc)->iso != TOKU_ISO_SERIALIZABLE)
        return 0;
    toku::lock_request::type lock_type = dbc_struct_i(dbc)->rmw ? toku::lock_request::type::WRITE : toku::lock_request::type::READ;
    int r = toku_db_get_range_lock(db, txn, left_key, right_key, lock_type);
    return r;
}

MVCC

前面谈了这么多主要是为这一节做铺垫，MVCC的全称是Multi-Version Concurrency Control。此技术最初是 Oracle 实现的用以控制并发事务读取数据的技术。除了MVCC以外，还有基于lock并发访问技术，InnoDB、DB2、SQL Server都有基于锁的并发访问技术。MVCC在OLTP领域的性能方面有一定的优势，现在主流数据库版本都实现了MVCC技术。

TokuDB实现MVCC的方法和Oracle、InnoDB都不一样，不是通过undo segment来构造snapshot读的数据，而是把多个版本的数据都存放在leaf node的entry里面。所以，TokuDB实现的MVCC，读和写之间是可能产生等待（等的锁是pair->lock, 其实是cachetable的hashtable的bucket锁，这块比较隐晦，读者仔细看看代码便知）。

下面我们一起来看一下MVCC的数据在内存中展开的样子：

typedef struct uxr {
    uint8_t   type;     // delete/insert/placeholder
    uint32_t  vallen;    // 长度
    void *    valp;     // 指向数据的buffer
    TXNID     xid;     // txnid
} UXR_S, *UXR;
typedef struct ule {
    uint32_t  num_puxrs;   // provisional txn的个数
    uint32_t  num_cuxrs;   // committed txn的个数
UXR_S   uxrs_static[MAX_TRANSACTION_RECORDS*2];    // 静态分配的空间
UXR     uxrs;                                      // txns
} ULE_S, *ULE;

多个版本的数据是存放在uxrs域里面，它的每一项对应一个txn的版本。从uxrs[0]开始到uxrs[num_cuxrs - 1]存放的是committed数据，uxrs[num_cuxrs]到uxrs[num_cuxrs + num_puxr-1]存放的是provisional的数据。
假设一个leaf entry，有2份committed数据，3份provisional数据，uxrs如下所示(红色表示committed txn，绿色表示provisional txn):

ULE_S只是MVCC数据的逻辑表示，真正存在leaf node的entry是以序列化形式存放的，相应的数据结构叫做leafentry：

struct leafentry {
    struct leafentry_clean {
        uint32_t vallen;
        uint8_t  val[0];
    };
    struct __attribute__ ((__packed__)) leafentry_mvcc {
        uint32_t num_cxrs; // number of committed transaction records
        uint8_t  num_pxrs; // number of provisional transaction records
        uint8_t xrs[0];
    };
    uint8_t  type;    // type is LE_CLEAN or LE_MVCC
    union __attribute__ ((__packed__)) {
        struct leafentry_clean clean;
        struct leafentry_mvcc mvcc;
    } u;
};

Leaf node的每一个entry可以处在两种形式其中的一种：

• Clean：只有一个版本，和一般数据库leaf node里的数据类似；
• MVCC：每个数据有多个版本，每个版本对应一个txn的数据。多个txn的数据保存在xrs里面，是一段连续的内存。num_cxrs表示committed txn的个数，num_pxrs表示in-progress txn的个数。

Leafentry->u.mvcc.xrs表示的连续内存空间的layout如下：从offset 0 开始，每项占1个 (txnid, 长度&类型)字节或多个(数据)字节

• 最外的provisional txn的txnid；
• 除最外的committed txn以外，所有的committed txn的 txnid形成的txnid列表，顺序从最里的committed txn直到次最外的committed txn；最外的committed txn的txn id是TXNID_NONE；
• 最里的provisional txn的长度和类型；
• Commited txn的（长度，类型）二元组的列表，顺序从最里的committed txn到最外的committed txn；
• 最里的provisional txn数据；
• 所有commited txn数据列表，顺序从最里的committed txn到最外的committed txn；
• 最外的provisional txn长度和类型；
• 最外的provisional txn数据；
• provisional txn的（txnid，长度&类型，数据）三元组列表，顺序从次最外的provisional txn到次最里的provisional txn；
• 最里的provisionl txn的txnid；

当修改leaf node数据的时候，需要先把 leafentry 表示的 MVCC 数据转成 ULE 表示的数据，然后进行修改，insert/delete 就是新加一个provisional txn，最后在把ULE表示的MVCC数据转成leafentry表示保存在leaf node里面。

读leaf node的数据过程比较复杂，涉及到MVCC的核心部分。首先用binary search定位在FT的哪个leaf node的哪个basement node的data_buffer的哪个leaf entry。调用le_extract_val来读leaf entry上的数据，一般来说ftcursor->is_snapshot_read都为TRUE，它会调用 le_iterate_val 根据type判断读clean的数据还是MVCC的数据。如果是clean的就直接读出返回；如果是 MVCC 就要解析Leafentry->u.mvcc.xrs的序列化的结构。在这个layout里，最前面的num_cuxrs+1（如果有provisional txn）个字节保存的是一些txnid：

• Provisional txn的txnid（如有provisional txn）；
• 最里的committed txn的txnid到次最外的committed txn的txnid列表；

也就是从ULE.uxrs[num_cuxrs]开始往ULE.uxrs[0]的方向找到当前txn可以读的txnid最大的（也即最新的事务）committed txnid。函数toku_txn_reads_txnid判读一个txn是否可以读某个特定的txnid的数据。代码如下所示：

int toku_txn_reads_txnid(TXNID txnid, TOKUTXN txn) {
    int r = 0;
    TXNID oldest_live_in_snapshot = toku_get_oldest_in_live_root_txn_list(txn);
    if (oldest_live_in_snapshot == TXNID_NONE && txnid < txn->snapshot_txnid64) {
        r = TOKUDB_ACCEPT;
    } else if (txnid < oldest_live_in_snapshot || txnid == txn->txnid.parent_id64) {
        r = TOKUDB_ACCEPT;
    } else if (txnid > txn->snapshot_txnid64 || toku_is_txn_in_live_root_txn_list(*txn->live_root_txn_list, txnid)) {
        r = 0;
    } else {
        r = TOKUDB_ACCEPT;
    }
    return r;
}

txn可以读txnid数据的条件：

• 如果txn的live_root_txn_list为空（创建snapshot的时候没有活跃的读写事务），并且txnid对应事务比txn还要早，并且txn是snapshot读；
• 如果txnid对应事务比txn的live_root_txn_list里的所有活跃的读写事务都要早，或者txnid对应事务就是txn（非snapshot读），或者txnid对应的事务是txn的root txn(snapshot读)；
• txnid对应事务比txn早，并且txnid不在txn->live_root_txn_list。

le_iterate_val代码片段如下：

int
le_iterate_val(LEAFENTRY le, LE_ITERATE_CALLBACK f, void** valpp, uint32_t *vallenp, TOKUTXN context) {
    uint8_t type = le->type;
    switch (type) {
        case LE_CLEAN: {
            vallen = toku_dtoh32(le->u.clean.vallen);
            valp   = le->u.clean.val;
            r = 0;
            break;
        }
        case LE_MVCC:;
            uint32_t num_cuxrs = toku_dtoh32(le->u.mvcc.num_cxrs);
            uint32_t num_puxrs = le->u.mvcc.num_pxrs;
            uint8_t *p = le->u.mvcc.xrs;
            uint32_t index, num_interesting;
            num_interesting = num_cuxrs + (num_puxrs != 0);
            TXNID *xids = (TXNID*)p;
            r = le_iterate_get_accepted_index(xids, &index, num_interesting, f, context);
}

Garbage Collection

从前面的分析可以看出，TokuDB引擎运行一定时间后leaf entry里面的历史txn信息越来越大，自然而然地要考虑内存空间回收的问题，即MVCC的GC问题。

Txn manager

TokuDB维护一个全局唯一的txn_manager数据结构管理系统中所有读写事务（live_root_ids有序数据结构），snapshot（snapshot head/snapshot tail双向链表）和可能正在被引用的committed读写事务（referenced_xids有序数据结构）。

struct txn_manager {
    toku_mutex_t txn_manager_lock;             // 互斥锁
    txn_omt_t live_root_txns;                   // 系统中活跃的读写事务
    xid_omt_t live_root_ids;                    // 系统中活跃的读写事务ID
    TOKUTXN snapshot_head，snapshot_tail;      // 系统中所有snapshot构成的双向链表
    uint32_t num_snapshots;                    // 系统中snapshot的个数
    rx_omt_t referenced_xids;                   // 三元组（committed txnid，系统中最大的可能的txnid，可能访问committed txnid的snapshot个数）的有序数据结构，按committed txnid字段排序。
    TXNID last_xid;                            // 系统中最大的可能的txnid
    TXNID last_xid_seen_for_recover;             // recovery过程中最大的txnid
    TXNID last_calculated_oldest_referenced_xid;   // 所有live list（包括live root list，snapshot list，referencelist）中最小的（最老的）txnid
};

一个txn的生命周期是由txn_manager的live_root_ids，snapshot双向链表，referenced_xids这三个数据结构来跟踪的，TokuDB MVCC 的 GC 也是根据这三个数据结构来判断一个committed txn是否可以被清理掉了。下面我们一起去看看txn是在什么时候加入和离开这三个数据结构的。

• live_root_ids：如果是读写事务，在txn->txn_begin加入live_root_ids (live_root_txns)；txn->txn_commit或者txn->txn_abort的时候离开live_root_ids (live_root_txns)。如果是只读事务，它不会加入到live_root_ids (live_root_txns)。在TokuDB中，autocommit=1情况下query是只读事务，insert/update/delete是读写事务；autocommit=0的情况下，query也是读写事务；
• snapshot_head和snapshot_tail构成的双向链表：在txn->txn_begin，如果是创建新的snapshot，这个txn会被加到snapshot链表尾部（snapshot list尾部表示最新的snapshot，头部表示最老的snapshot）；在txn->txn_commit/txn->txn_abort时，如果是snapshot操作，并且这个txn有对应的snapshot，它会被从snapshot list里删除；
• referenced_xids：在txn->txn_commit/txn->txn_abort时，如果是读写事务，会扫描snapshot list找到可能引用这个txn的所有snapshot（也就是在这个txn之后创建的所有snapshot），这些snapshot被记做这个txn的reference snapshot set。在TokuDB的代码里reference_xids记录的是（这个committed 读写事务txnid，系统当前最大的txnid，可能引用这个读写事务的snapshot的个数）构成的三元组。如果是只读事务，不会加入到referenced_xids。当snapshot对应的txn执行txn->txn_commit/txn->txn_abort时，会查找referenced_xids把这个snapshot引用的所有读写事务的ref_count减1，若ref_count减为0则把引用的读写事务对应的三元组从referenced_xids删除。回顾前面讲的，snapshot对应的txn创建的时候，被引用的读写事务一定处在已创建&未提交&未回滚的状态，所以被引用的读写事务一定是在snapshot对应的txn的live_root_txn_list，那么只需要扫描snapshot对应txn的live_root_txn_list上的每一个读写事务txn1，看看是否有（txn1, txn2, count）构成的三元组存在即可。程序里有个优化，当txn的live_root_txn_list的大小远远大于 txn_manger 的 referenced_xids，可以扫描referenced_xids，对每一个三元组（txn1, end_txnid, ref_count）判断txn1是否在txn的live_root_txn_list上面，若是则对ref_count减1。当ref_count减为0则把这个三元组从referenced_xids删除。

TokuDB leaf entry 的 GC

• 隐式提交provisional txn：如果leaf entry里最老的（最外的）provisional txn，比系统可能存在的最老的txn还要老，把那个provisional txn promote成最新的（最内的）committed txn，所有的provisional txn都将被丢弃。Promote最老的provisional txn时，txnid选择最老的provisional txn的txnid，value选择最新的provisional txn的value，这样做是考虑到nested txn的情况；
• 简单GC：如果leaf entry里面存在某些committted txn，它们比所有活跃的读写事务、所有的snapshot、所有被引用的已committed的读写事务都要早，简而言之是那些已经不被任何后继事务访问的已提交事务。找到leaf entry里面满足如上条件最新的（txnid最大的）committed txn，它之前的所有committed txn都可以被清理掉；
• 深度GC：如果leaf entry里面存在某些committed txn，它们不在任何txn的活跃读写事务列表里面，并且它的数据对所有的snapshot都没有意义（没有snapshot可能读它的数据）。那么这些committed txn可以被丢弃。

调用GC的时机

• Leaf node在被从cachetable写回到磁盘之前会尝试对整个leaf node做GC；
• 往leaf node上的某个entry上apply msg的时候，如果leaf entry size大于某个阈值会对这个leaf entry做GC。

为了支持 nested txn 的额外工作

为了支持nested txn，MVCC的实现变得较为复杂，在这里顺便提一下，大家有时间仔细看看代码。在对leaf node entry做commit操作时（ule_apply_commit）会考虑provisional txn的个数，等于1表示非nested txn，直接调用ule_promote_provisional_innermost_to_committed把最新的（最里的）provisional txn提交；如果大于1，表示有nested txn存在，会调用ule_promote_provisional_innermost_to_index把最新的（最里的）provisional txn提交到它的parent（上一个provisional txn）。在nested txn中，可能存在一些没有直接修改这个ULE的事务，这些事务是在第一个直接修改这个ULE的txn执行msg_modify_ule的时候调用ule_do_implicit_promotions把它们补上去的。