## 前言 之前有篇月報是關于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`把它們補上去的。