## 前言 之前有篇月报是关于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,映射如下表所示: ![](https://oss.showapi.com/doc/2096/67/5999ae04-6dde-43d1-b7d1-6af28cde7b55.jpg) 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): ![](https://oss.showapi.com/doc/2096/67/41594e11-d30b-4def-ac24-59e3346a3a06.png) 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`把它们补上去的。