## 前言 之前有篇月报是关于innodb事务子系统的[《MySQL · 引擎特性 · InnoDB 事务子系统介绍》](http://mysql.taobao.org/monthly/2015/12/01/) 里面较详细的讲述了 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 的工作线程和线程池》](http://mysql.taobao.org/monthly/2016/01/06/) 对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](https://en.wikipedia.org/wiki/Isolation_(database_systems))。 * 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 中的行锁》](http://mysql.taobao.org/monthly/2015/11/09/)。在`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`把它们补上去的。