## 背景介紹 TokuDB采用的是Fractal Tree作為索引的數據組織方式。它是一種面向磁盤I/O優化的數據結構，采用“分期償還”策略減少在數據插入過程中從root節點到leaf節點的搜索過程。這種搜索過程可以簡稱為locate_position，就是尋找要插入key在Tree中位置的過程。 一般B+Tree的插入過程分為兩個部分： 1. Locate_position: 從root開始使用binary search方法遞歸地尋找應該插入到哪個子節點上，直到在leaf節點找到應該插入的位置然后返回； 2. Insert_into_postion: 在locate_position返回的位置進行插入操作，如果當前leaf節點存儲的key個數超過預定義的最大值可能會引起split操作，最壞的情況是引起從leaf節點到root節點的split。 Fractal Free把每個操作都看成一個message。每個internal節點維護了一個msg_buffer按照FIFO順序緩存message；索引的有序序列是在leaf節點維護的。所謂采用“分期償還”是指：在Fractal Tree中插入時，只需要把(key, value)對插入到root節點（或者若干深度的internal節點）的msg_buffer就可以返回了，這個過程可以簡稱為`push_into_root`。中間節點msg_buffer中的message是由后臺工作線程分批地flush到子節點上，最終刷到leaf節點上的，這個過程簡稱為`push_into_child`。與Fractal Tree類似的面向磁盤I/O優化的數據結構還有Buffer Tree?[論文鏈接](http://www.cs.cmu.edu/~guyb/realworld/slidesF10/buffertree.pdf)?和Log Structured Merge Tree, 感興趣的朋友可以看一下。 下面我一起看一下Fractal Tree的數據結構定義，維護Fractal Tree的基本算法的插入，刪除，分裂，合并和查詢過程。 ## Fractal Tree數據結構 大多數情況下message不是直接插入到leaf節點上，而是被緩存在internal節點，由后臺工作線程異步flush到leaf節點上。在某個時間段，對同一個key可能存在多個未applied到leaf節點的修改，每個修改對應一個message，這些message有可能緩存被在不同的internal節點上（這些internal節點一定都在從root到leaf路徑上）。為了區分message的先后順序，在插入到root節點（`push_into_root`）時，每個message被賦予了一個有序遞增的序列號（msn），它是全局唯一的。 ~~~ struct ftnode { MSN max_msn_applied_to_node_on_disk; // applied最大的msn unsigned int flags; // 創建標志，等于ft->h->flags BLOCKNUM blocknum; // 節點對應的塊號 int height; // 高度：0表示leaf節點，>0表示中間節點 int dirty; // 臟頁標記，用于cachetable臟頁回刷 uint32_t fullhash; // 在cachetable的哪個bucket上 int n_children; // partition個數 ftnode_pivot_keys pivotkeys; // 每個partition的key值區間 TXNID oldest_referenced_xid_known; // 最近一次push_into_root操作時系統可能的最老事務id struct ftnode_partition *bp; // internal節點：子節點的msg_buffer; leaf節點：有序數據結構 struct ctpair *ct_pair; // 對應cachetable的pair（cache entry） }; ~~~ ## Fractal Tree layout  上圖中藍色圓圈表示internal節點，旁邊的白色矩形表示msg_buffer; 最下面一層藍色矩形表示leaf節點 Fractal Tree 的bp域指向partition。對于Internal節點，bp域指向每個子節點對應的msg_buffer。一個internal節點最多有16個（可配置）的子節點，每個子節點對應的子樹保存某個key值區間的數據。對于leaf節點，bp域指向leaf節點的有序數據結構。Leaf節點可以由多個有序的子結構組成，每個子結構構稱作basement節點，實際上是一個弱平衡樹形結構（或者數組）。Internal節點和leaf節點的缺省大小是4M字節，basement節點的缺省大小是128K字節。從root節點到leaf節點查詢的過程，是通過各級節點的 pivotkeys 來路由的。 Pivotkeys域表示子節點的key值范圍： * 第0個子節點的key范圍在 ( -∞, pivotkeys[0] ] * 第1個子節點的key范圍在( pivotkeys[0]，pivotkeys[1] ] * 第i個子節點的key范圍在( pivotkeys[i-1]，pivotkeys[i] ] * 最后一個子節點的key范圍在( pivotkeys[n_children-1]，+∞) Bp域表示每個partition： * 第0個partition：bp[0] * 第1個partition：bp[1] * 第i個partition：bp[i] * 最后一個partition：bp[n_children-1] ### Partition信息 ~~~ struct ftnode_partition { BLOCKNUM blocknum; // internal節點：子節點塊號; leaf節點：unused uint64_t workdone; // internal節點：applied message字節數; leaf節點：unused struct ftnode_child_pointer ptr; // internal節點：子節點msg_buffer信息; leaf節點：basement節點 enum pt_state state; // internal節點：子節點狀態; leaf節點：basement節點狀態 uint8_t clock_count; // evictor線程根據此變量判斷是否可以partial evict }; enum pt_state { PT_INVALID = 0, // 無效 PT_ON_DISK = 1, // 在磁盤上 PT_COMPRESSED = 2, // 已讀入內存，壓縮格式 PT_AVAIL = 3 // 已讀入內存，解壓縮格式 }; typedef struct ftnode_child_pointer { union { struct sub_block *subblock; //壓縮后的buffer struct ftnode_nonleaf_childinfo *nonleaf; // internal節點：msg_buffer struct ftnode_leaf_basement_node *leaf; // leaf節點：basement節點 } u; } FTNODE_CHILD_POINTER; ~~~ ### Internal節點存儲的msg_buffer ~~~ struct ftnode_nonleaf_childinfo { message_buffer msg_buffer; // 緩存的message off_omt_t broadcast_list; // 用于支持on-line add index, on-line add column marked_off_omt_t fresh_message_tree; // 未apply的message在msg_buffer 里的offset，按（key，msn）順序排序 off_omt_t stale_message_tree; // 已經applied過的message在msg_buffer里的offset，按（key，msn）順序排序 uint64_t flow[2]; // 流控 }; ~~~ ### Leaf節點的basement節點 ~~~ struct ftnode_leaf_basement_node { bn_data data_buffer; // 有序序列，弱平衡樹形結構（或者數組） unsigned int seqinsert; // 判斷順序 insert的hint MSN max_msn_applied; // applied最大的msn }; ~~~ ## 維護Fractal Tree的基本操作 ### 創建新的Fractal Tree的索引 每個Fractal Tree由FT來表示。下面是列舉了FT中比較重要的域。 ~~~ struct ft { FT_HEADER h; // header FT_HEADER checkpoint_header; // checkpoint開始時刻header的克隆 CACHEFILE cf; // 描述了FT對應的磁盤文件和數據節點信息。 toku::comparator cmp; // DBT compare函數 block_table blocktable; // FT邏輯塊號到文件offset的映射表 struct toku_list live_ft_handles; // 打開此FT的handle列表 uint32_t num_txns; // 訪問此FT的事務個數 bool pinned_by_checkpoint; // 表示checkpoint正在進行 BLOCKNUM rightmost_blocknum; // 最右leaf節點塊號，用于順序insert優化 } ; typedef struct ft *FT; struct ft_header { enum ft_type type; // header類型 int dirty; // 臟標記 uint64_t checkpoint_count; // checkpoint計數 LSN checkpoint_lsn; // checkpoint開始時刻的lsn const uint64_t time_of_creation; // FT創建時間 TXNID root_xid_that_created; //創建FT的事務ID uint64_t time_of_last_modification; // 最近一次更新時間 BLOCKNUM root_blocknum; // root節點塊號 const unsigned int flags; // 創建標志 unsigned int nodesize; // 節點大小，缺省值4M字節 unsigned int basementnodesize; // basement節點大小，缺省值128K字節 enum toku_compression_method compression_method; // 壓縮算法 unsigned int fanout; // internal節點的fanout MSN max_msn_in_ft; // FT最大的msn }; enum ft_type { FT_CURRENT = 1, // FT header FT_CHECKPOINT_INPROGRESS // checkpoint開始時刻FT header的克隆 }; ~~~ 創建新的Fractal Tree索引（簡稱FT）時候，調用函數`toku_ft_create`做一些必要的初始化工作：創建FT索引的header，創建block table（FT邏輯塊號到文件offset的映射表），以及創建FT的root節點。創建root節點的過程很簡單：初始化一個空的leaf節點（塊號為0），并把它加到cachetable中，此時的root節點只包含一個basement節點。在leaf節點被回刷到磁盤之前會把leaf節點按照128K為單位分割成多個basement節點，這樣做的好處是加速leaf節點上的查詢過程。 ### Fractal Tree insert 在第一節背景介紹里面談到的，向Fractal Tree插入（key,value）對的操作是`push_into_root`。在TokuDB代碼實現里面，insert操作是通過調用`toku_ft_root_put_msg`給FT發一個FT_INSERT/FT_INSERT_NO_OVERWRITE（出現duplicate key時保留老值）消息實現的。 向FT發送一個message的過程如下： * 調用`toku_pin_ftnode`獲取root節點（加share鎖），這個過程中可能會引起從磁盤讀取root節點的操作，在這里假設所有節點都已緩存在內存中； * 調用`toku_ftnode_get_reactivity`判斷root節點是否需要split。Leaf節點需要split的條件是：leaf節點所需的磁盤空間大于nodesize（缺省4M）；internal節點需要split的條件是：子節點個數大于fanout（缺省16）。如果需要split，root節點需要把share鎖升級為exclusive鎖，拿到exclusive鎖后調用`ft_init_new_root`進行root分裂并生成新的root節點，這個返回時root節點塊號保持不變（還是0），并持有exclusive鎖，`ft_init_new_root`返回后需要把exclusive鎖降級為share鎖。一般情況下root節點是不要split的； * 向root節點push message。 下面就是push message的過程： * 如果root是leaf節點或者message是廣播消息的話（比如on-line add index或者on-line add column）就把message放到root節點就可以返回了。這里需要解釋一下，廣播消息是需要apply到每一個leaf節點上的，所以需要從root節點向下逐級flush，不能跳過任何一個范圍； * 如果Fractal Tree的高度大于1，調用`push_something_in_subtree`把message放到root的節點的某個子樹上； * 如果Fractal Tree的高度等于1，首先調用`toku_ftnode_which_child`確定應該把message放到哪個leaf節點上。如果目標的leaf節點是最左（childnum == 0）或者最右（childnum == node->n_children - 1) 的情況，調用`push_something_in_subtree`把message放到目標leaf節點上；否則放到root節點即可返回，最左最右的情況是優化順序查詢。最后一節會看到，一般的FT search是需要把root到leaf搜索路徑上所有落在bounds區間internal節點上的message先apply到leaf節點，然后再leaf節點上進行搜索的。在TokuDB的engine層，`get_first/get_last`操作直接讀取最左/最右的leaf節點，所以最左最右插入的時候需要把message 同步apply到leaf節點上的。偽代碼如下： ~~~ void toku_ft_root_put_msg(FT ft, const ft_msg &msg, txn_gc_info *gc_info) { ftnode_fetch_extra bfe; bfe.create_for_full_read(ft); // fetch整個node pair_lock_type lock_type = PL_READ; // 初始狀態：申請讀鎖 change_lock_type: toku_pin_ftnode(ft, root_key, fullhash, &bfe, lock_type, &node, true); enum reactivity re = toku_ftnode_get_reactivity(ft, node); switch (re) { case RE_STABLE: case RE_FUSIBLE: // root節點不支持merge操作 if (lock_type != PL_READ) { // 其他thread搶先做了split toku_unpin_ftnode_read_only(ft, node); lock_type = PL_READ; goto change_lock_type; } break; case RE_FISSIBLE: if (lock_type == PL_READ) { // 需要split，升級為寫鎖 toku_unpin_ftnode_read_only(ft, node); lock_type = PL_WRITE_CHEAP; goto change_lock_type; } else { // root節點split ft_init_new_root(ft, node, &node); // split完成，降級為讀鎖 toku_unpin_ftnode(ft, node); lock_type = PL_READ; goto change_lock_type; } break; } if (root ->height == 0 || ft_msg_type_is_broadcast(msg.type())) { // root是leaf節點或者messsage是廣播消息，把message放到root節點上 // 這里釋放鎖的原因是：inject_message_at_this_blocknum里面會重新拿鎖 toku_unpin_ftnode_read_only(ft, root); inject_message_at_this_blocknum(ft, root_key, fullhash, msg, flow_deltas, gc_info); } else if (root->height > 1) { // root高度大于1時，把message加到root節點的某個子樹上 push_something_in_subtree(ft, node, -1, msg, flow_deltas, gc_info, 0, LEFT_EXTREME | RIGHT_EXTREME, false); } else { // root高度等于1時，確定message應該放到哪個leaf節點上 int childnum = toku_ftnode_which_child(node, msg.kdbt(), ft->cmp); // 目標leaf節點是root的最左或最右子節點時，把message放到相應的leaf節點上 if (childnum == 0 || childnum == node->n_children - 1) { push_something_in_subtree(ft, node, childnum, msg, flow_deltas, gc_info, 0, LEFT_EXTREME | RIGHT_EXTREME, false); } else { // 把message放到root節點上 // 這里釋放鎖的原因是：inject_message_at_this_blocknum里面會重新拿鎖 toku_unpin_ftnode_read_only(ft, node); inject_message_at_this_blocknum(ft, root_key, fullhash, msg, flow_deltas, gc_info); } } } toku_ftnode_get_reactivity返回的reactivity定義如下： enum reactivity { RE_STABLE, // 正常狀態 RE_FUSIBLE, // 需要merge RE_FISSIBLE // 需要split }; ~~~ 下面我們一起看一下`push_something_in_subtree`的處理過程。這里有個promotion的概念：message有可能不會直接放到root節點上，而是放到root的第一級子節點或者第二級子節點上（至多往下看兩級子節點）。Promotion的一般原則： * 只promote非廣播message； * 如果子節點對應的msg_buffer非空，就不會遞歸向下promote； * 為了優化順序insert，如果是最左/最右的情況一定要把message apply到leaf節點上； * 非最左/最右的情況，遇到height == 1的internal節點或者depth ==2 (已做了兩級的promotion)，promote就停止了； * 修改leaf節點是很耗時的（在后面會看到），所以一般選擇把message放到internal節點上； 函數`inject_message_in_locked_node`實現了把message push到node節點上。偽代碼如下： ~~~ static void inject_message_in_locked_node(FT ft, FTNODE node, int childnum, const ft_msg &msg, size_t flow_deltas[],txn_gc_info *gc_info) { // 生成全局（FT內）唯一的msn MSN msg_msn = { .msn = toku_sync_add_and_fetch(&ft->h->max_msn_in_ft.msn, 1) }; ft_msg msg_with_msn(msg.kdbt(), msg.vdbt(), msg.type(), msg_msn, msg.xids()); toku_ftnode_put_msg(ft->cmp, ft->update_fun, node, childnum, msg_with_msn, true, gc_info, flow_deltas, &stats_delta); if (node->height > 0 && toku_ftnode_nonleaf_is_gorged(node, ft->h->nodesize)) { // 如果node節點是internal節點，msg_buffer非空并且node節點所需的磁盤空間 + 各個子節點的workdone（query過程中同步flush的message大小的總和）大于nodesize（缺省4M），trigger client線程池的工作線程異步flush這個節點。 // msg_buffer非空并且node節點所需的磁盤空間 + 各個子節點的workdone: 表示node節點邏輯上的size toku_ft_flush_node_on_background_thread(ft, node); } else { toku_unpin_ftnode(ft, node); } } ~~~ 函數`toku_ftnode_put_msg`的作用是把message push到node節點上。如果node是internal節點，調用函數`ft_nonleaf_put_msg把message`加到msg_buffer里面。Internal節點維護了一個FIFO隊列msg_buffer，按照message到達節點的順序追加到FIFO尾部。Internal節點里面還維護了兩個有序結構：`fresh_message_tree`和`stale_message_tree`，這兩個有序結構記錄了按照（key,msn）排序的message（實際上存的是message在msg_buffer中的offset）。`fresh_message_tree`保存的是未apply的message；`stale_message_tree`保存的是在query過程中同步applied過的message。`inject_message_in_locked_node`在退出之前判斷internal節點是否緩存了大量message，如果是則會把當前這個節點放到cachetable （TokuDB的buffer pool）的client線程池，讓工作線程在后臺把這個節點上的message flush到下一級節點。其實cachetable有個后臺線程cleaner線程也在做同樣的事情，但是cleaner線程是每1秒鐘啟動一次，而且一個cleaner線程負責處理cachetable所有需要flush的internal節點，是很有可能來不及處理的。 這里重點看一下把message 放到leaf節點的過程，這里我們不考慮廣播消息。首先是調用`toku_ftnode_which_child`判斷message應放到哪個basement節點上，然后調用`toku_ft_bn_apply_msg`把message放到目標basement節點上。前面函數中都沒有考慮message的類型，直到這個函數才會根據message類型做不同的處理。對應insert操作，首先嘗試順序insert的優化（即跟basement最后一個key作比較，若大于最后一個key表示是升序順序insert情況）。如果不是順序insert的pattern，會在basement節點的有序數據結構bn里面進行binary search查找key對應的LEAFENTRY，然后調用`toku_ft_bn_apply_msg_once`在basement節點進行insert。 `toku_ft_bn_apply_msg_once`是`toku_le_apply_msg`的簡單封裝。`toku_le_apply_msg`偽代碼如下： ~~~ toku_le_apply_msg(const ft_msg &msg, LEAFENTRY old_leafentry, // 老的LEAFENTRY bn_data* data_buffer, // basement節點的bn，如果是basement節點上第一個message，這個值NULL uint32_t idx, // old_leafentry在bn上的index uint32_t old_keylen, txn_gc_info *gc_info, LEAFENTRY *new_leafentry_p, //新的LEAFENTRY int64_t * numbytes_delta_p) { if (old_leafentry == NULL) { msg_init_empty_ule(&ule); } else { le_unpack(&ule, old_leafentry); // 把LEAFENTRY轉成ULE } msg_modify_ule(&ule, msg); // 把message加到ULE的MVCC // 把ULE轉成LEAFENTRY // 若data_buffer == NULL，le_pack分配basement節點的bn int r = le_pack(&ule, data_buffer, idx, msg.kdbt()->data, keylen, old_keylen, oldmemsize, new_leafentry_p, &maybe_free); } ~~~ 如果是FT_INSERT_NO_OVERWRITE，需要檢查key是否已存在。若存在，直接退出。否則在ULE的MVCC結構添加一個類型為XR_INSERT的provisional txn。 ~~~ msg_modify_ule(ULE ule, const ft_msg &msg) { switch (type) { case FT_INSERT_NO_OVERWRITE: { UXR old_innermost_uxr = ule_get_innermost_uxr(ule); // key已存在，保留老值 if (uxr_is_insert(old_innermost_uxr)) break; } case FT_INSERT: { uint32_t vallen = msg.vdbt()->size; void * valp = msg.vdbt()->data; ule_apply_insert(ule, xids, vallen, valp); break; } ~~~ ## Fractal Tree delete 在Fractal Tree刪除一個對的方法是：調用函數?`toku_ft_root_put_msg`?給FT發送一個類型為 FT_DELETE_ANY 的message。其處理過程與insert類似，函數`msg_modify_ule`會判斷message的類型，如果是FT_DELETE_ANY，就會給ULE的MVCC添加一個 XR_DELETE 類型的provisional txn。 ~~~ msg_modify_ule(ULE ule, const ft_msg &msg) { switch (type) { case FT_DELETE_ANY: ule_apply_delete(ule, xids); break; } } ~~~ ## LEAFENTRY的隱式提交 之前有篇月報[《MySQL·TokuDB·事務子系統和 MVCC 實現》](http://mysql.taobao.org/monthly/2016/03/01/)討論TokuDB在事務提交一節里有這樣的描述： > 如果是root txn調用apply_txn對rollback log的每一個item進行commit操作。如果是nested child txn把child txn的rollback log掛到parent的rollback log尾部，等到root txn 提交的時候對所有rollback log的item進行commit。需要注意的是，對于大部分DML操作rollback log item->commit都是noop。 那么在LEAFENTRY里面provisional txn是如何提交的呢？LEAFENTRY采用LAZY的方式提交，就是說provisional txn并不會在txn commit的時候變成commit txn，而是推遲到下一次修改這個LEAFENTRY的時候隱式提交。 原因是：修改LEAFENTRY需要先轉成ULE結構，做完修改再把ULE轉成LEAFENTRY。這樣做的好處是把兩次LEAFENTRY=>ULE=>LEAFENTRY合并了。Txn rollback時候，會對DML操作的key發FT_ABORT_ANY類型的message，這種message也是采用push到root節點（或者其下面的某個子節點）就返回。 ~~~ static void msg_modify_ule(ULE ule, const ft_msg &msg) { XIDS xids = msg.xids(); enum ft_msg_type type = msg.type(); if (type != FT_OPTIMIZE && type != FT_OPTIMIZE_FOR_UPGRADE) { ule_do_implicit_promotions(ule, xids); } } static void ule_do_implicit_promotions(ULE ule, XIDS xids) { if (ule->num_puxrs > 0) { int num_xids = toku_xids_get_num_xids(xids); uint32_t max_index = ule->num_cuxrs + min_i32(ule->num_puxrs, num_xids) - 1; uint32_t ica_index = max_index; uint32_t index; for (index = ule->num_cuxrs; index <= max_index; index++) { TXNID current_msg_xid = toku_xids_get_xid(xids, index - ule->num_cuxrs); TXNID current_ule_xid = ule_get_xid(ule, index); if (current_msg_xid != current_ule_xid) { //ICA表示innermost common ancestor ica_index = index - 1; break; } } if (ica_index < ule->num_cuxrs) { // 隱式提交上一次對這個LEAFENTRY的修改 invariant(ica_index == ule->num_cuxrs - 1); ule_promote_provisional_innermost_to_committed(ule); } else if (ica_index < ule->num_cuxrs + ule->num_puxrs - 1) { ule_promote_provisional_innermost_to_index(ule, ica_index); } } } ~~~ ## Cleaner線程異步flush機制 Cleaner線程找到消耗內存最多的internal節點，調用`cleaner_callback`去做flush。在`get_write_callbacks_for_node`注冊的`cleaner_callback`是`toku_ftnode_clone_callback`。這個函數首先把node的所有partition讀到內存，然后選擇內存消耗最大的子節點，把那個節點對應的bnc緩存的message flush到相應的子節點上。 Flush bnc的過程： * 記下需要flush的bnc； * 新創建一個空的bnc記做new_bnc，并用new_bnc代替bnc來緩存新的message； * 調用`toku_bnc_flush_to_child`把bnc緩存的message flush到子節點上。 `toku_bnc_flush_to_child`會遍歷bnc的所有message，然后對每個message調用`toku_ftnode_put_msg`把message放到子節點上的。一個bnc被flush完之后，可能會引起子節點遞歸的flush，也可能引起節點的split或者merge。由于篇幅有限請大家自己分析。 ## Fractal Tree split和merge Fractal Tree節點的split和merge操作是自上而下進行的，這些操作都是在向這個節點push一個message之后觸發的。 ### Fractal Tree split Fractal Tree節點split的條件是： * leaf節點：所需磁盤空間大于nodesize（缺省4M） * Internal節點：子節點個數大于fanout（缺省16） Split的過程分為兩個部分： * 分割數據：對于leaf節點來說是把basement和其存儲的LEAFENTRY按照split類型分為兩部分；對于internal節點來說是把msg_buffer平均分成兩部分； * 分割pivotkeys：按照第一步分割數據的方式把pivotkeys分成兩部分，并把splitk加到父節點上。Split完成后這兩個節點擁有相同的`max_msn_applied_to_node_on_disk`和`oldest_referenced_xid_known`。 Fratcal Tree支持的split類型： ~~~ enum split_mode { SPLIT_EVENLY, SPLIT_LEFT_HEAVY, SPLIT_RIGHT_HEAVY }; ~~~ Split之后，internal節點可能會選擇進一步做flush message的操作。為什么split之后還需要flush呢？這部分代碼比較晦澀，筆者認為可能是因為split的條件是子節點個數大于fanout，沒有考慮到節點的邏輯大小。 ### Fractal Tree merge：把相鄰的兩個節點合并成一個節點。 Fractal Tree節點merge的條件是： * Leaf節點：所需磁盤空間小于1/4 nodesize（缺省4M） * Internal節點：子節點個數小于1/4 fanout（缺省16） 節點merge的過程也分成兩種情況： * Leaf節點：如果nodea大小+nodeb大小<3/4 nodesize才會考慮合并；否則，如果nodea大小<1/4 nodesize或者nodeb大小<1/4, 會balance這兩個節點（先合并，再平均split成兩個節點） * Internal節點：把msg_buffer合并 ## Rebalance leaf節點 Leaf節點被回刷到磁盤之前會調用`toku_ftnode_leaf_rebalance`函數把leaf節點的basement節點按照basementnodesize（缺省128K）大小平均分割成若干個basement節點。還記得嗎？root節點剛創建的時候只有1個basement節點的。 ## Fractal Tree上的查詢 Fractal Free在查詢方面是比較特殊的： * FT需要先同步flush root->leaf路徑上滿足查詢條件的所有message * FT形態與B+Tree不同：leaf節點沒有雙向鏈表   上面的圖是FT的樹形結構，下面的圖是B+Tree的樹形結構 FT查詢每次都是從root節點開始的，在internal節點中的查找是由pivotkeys路由到相應的子節點上，在leaf節點上是由pivotkeys路由到basement節點，然后在basement節點進行binary search尋找search key所在的位置。當要進行一個range查詢的時候，首先使用set_range方法找到滿足查詢range區間的第一個key，然后把上一次得到的key作為參數調用get_next方法。  FT中查找key的入口函數是`toku_ft_search`。這個函數讀取root節點，并根據search->key找到需要讀取的子節點（`bfe.child_to_read`），然后調用`ft_search_node`在root節點的相應子節點查找。讀root節點的時候，`bfe.read_all_partitions`被設置被TRUE。Root節點包含的所有paritition的信息都會從磁盤上讀上來。即當root是internal節點的時候，所有子節點的msg_buffer信息都會讀到內存來；root是leaf節點的時候，所有的basement節點的有序結構都會讀到內存來。偽代碼如下： ~~~ int toku_ft_search(FT_HANDLE ft_handle, ft_search *search, FT_GET_CALLBACK_FUNCTION getf, void *getf_v, FT_CURSOR ftcursor, bool can_bulk_fetch) { try_again: trycount++; ftnode_fetch_extra bfe; // 只讀取包含search key的那個子節點 bfe.create_for_subset_read(ft, search, &ftcursor->range_lock_left_key, &ftcursor->range_lock_right_key, ftcursor->left_is_neg_infty, Ftcursor->right_is_pos_infty,ftcursor->disable_prefetching, true); FTNODE node = NULL; { //讀取root節點，并設置bfe.child_to_read為包含search key的子節點 toku_pin_ftnode(ft, root_key, fullhash, &bfe, PL_READ, &node, true); } struct unlock_ftnode_extra unlock_extra = {ft_handle,node,false}; struct unlockers unlockers = {true, unlock_ftnode_fun, (void*)&unlock_extra, (UNLOCKERS)NULL}; { bool doprefetch = false; bfe.child_to_read r = ft_search_node(ft_handle, node, search, bfe.child_to_read, getf, getf_v, &doprefetch, ftcursor, &unlockers, (ANCESTORS)NULL, pivot_bounds::infinite_bounds(), can_bulk_fetch); if (r==TOKUDB_TRY_AGAIN) { // 獲取鎖時需要等待或者需要partial fetch if (unlockers.locked) { toku_unpin_ftnode_read_only(ft_handle->ft, node); } goto try_again; } else { assert(unlockers.locked); } } assert(unlockers.locked); toku_unpin_ftnode_read_only(ft_handle->ft, node); } ~~~ `ft_search_node`?是一個遞歸調用的函數，它根據 node->height 決定調用`ft_search_child`（internal節點）或者`ft_search_basement_node`（leaf節點）。`ft_search_basement_node`就是在（`node`，`bfe.child_to_read`）對應的basement節點的有序數據結構里面查找滿足cmp函數的key。`ft_search_child`調用`toku_pin_ftnode_for_query`讀取（`node`，`bfe.child_to_read`）表示子節點childnode。每次進入`ft_search_child`定義了一個新的bfe（記做bfe_1）表示讀取childnode節點的hint信息。讀取的時候指定了`bfe_1.read_all_partitions = (childnode->height >=1)`。當childnode是internal節點時，會把所有partition的msg_buffer都讀到內存來；childnode是leaf節點的時候，只讀search->key對應basement節點。`toku_pin_ftnode_for_query`采用non-blocking的方式獲取childnode上的鎖（這里是讀鎖）。Non-blocking的含義是說如果這個鎖可以獲取就立即返回；否則在等待之前把之前獲得的從root到父節點的鎖全部釋放掉，然后阻塞在那個鎖上。被喚醒以后立即釋放鎖返回TRY_AGAIN重新從root開始search。從父節點到root節點獲得的鎖被記錄在unlockers隊列里面，隊列尾部是root節點。 函數`toku_pin_ftnode_for_query`返回成功以后，會間接遞歸調用`ft_search_node`在childroot節點上進行搜索。`ft_search_node`還有一個副產品就是把上層傳過來的bounds映射到(`node`,`bfe.child_to_read`)的key值區間，經過幾次間接遞歸調用`ft_search_node`最終會到達leaf節點。如果是leaf節點`toku_pin_ftnode_for_query`需要檢查bounds對應的key值區間的msg是否都applied過了，如果有未apply的msg，則遍歷unlockers隊列記錄的祖先節點，把祖先節點key值在bounds范圍的message flush到leaf節點上。確保所有在bounds范圍的message都apply到leaf節點以后，在leaf節點對應的basement節點上進行搜索。