背景介绍

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 论文链接 和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），它是全局唯一的。

  1. struct ftnode {
  2.     MSN max_msn_applied_to_node_on_disk;  // applied最大的msn
  3.     unsigned int flags; // 创建标志，等于ft->h->flags
  4.     BLOCKNUM blocknum; // 节点对应的块号
  5.     int    height; // 高度：0表示leaf节点，>0表示中间节点
  6.     int    dirty; // 脏页标记，用于cachetable脏页回刷
  7.     uint32_t fullhash; // 在cachetable的哪个bucket上
  8.     int n_children; // partition个数
  9.     ftnode_pivot_keys pivotkeys; // 每个partition的key值区间
  10.     TXNID oldest_referenced_xid_known; // 最近一次push_into_root操作时系统可能的最老事务id
  11. struct ftnode_partition *bp; // internal节点：子节点的msg_buffer; leaf节点：有序数据结构
  12.     struct ctpair *ct_pair; // 对应cachetable的pair（cache entry）
  13. };

Fractal Tree layout

screenshot

上图中蓝色圆圈表示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信息

  1. struct ftnode_partition {
  2. BLOCKNUM  blocknum; // internal节点：子节点块号;  leaf节点：unused
  3. uint64_t     workdone; // internal节点：applied message字节数; leaf节点：unused
  4. struct ftnode_child_pointer ptr; // internal节点：子节点msg_buffer信息; leaf节点：basement节点
  5. enum pt_state state; // internal节点：子节点状态; leaf节点：basement节点状态
  6.     uint8_t clock_count; // evictor线程根据此变量判断是否可以partial evict
  7. };
  8. enum pt_state {
  9.     PT_INVALID = 0, // 无效
  10.     PT_ON_DISK = 1, // 在磁盘上
  11.     PT_COMPRESSED = 2, // 已读入内存，压缩格式
  12.     PT_AVAIL = 3 // 已读入内存，解压缩格式
  13. };
  14. typedef struct ftnode_child_pointer {
  15.     union {
  16.         struct sub_block *subblock;  //压缩后的buffer
  17.         struct ftnode_nonleaf_childinfo *nonleaf;  // internal节点：msg_buffer
  18.         struct ftnode_leaf_basement_node *leaf; // leaf节点：basement节点
  19.     } u;
  20.  } FTNODE_CHILD_POINTER;

Internal节点存储的msg_buffer

  1. struct ftnode_nonleaf_childinfo {
  2.     message_buffer msg_buffer; // 缓存的message
  3.     off_omt_t broadcast_list; // 用于支持on-line add index, on-line add column
  4.     marked_off_omt_t fresh_message_tree; // 未apply的message在msg_buffer 里的offset，按（key，msn）顺序排序
  5.     off_omt_t stale_message_tree; // 已经applied过的message在msg_buffer里的offset，按（key，msn）顺序排序
  6.     uint64_t flow[2]; // 流控
  7. };

Leaf节点的basement节点

  1. struct ftnode_leaf_basement_node {
  2.     bn_data data_buffer; // 有序序列，弱平衡树形结构（或者数组）
  3.     unsigned int seqinsert; // 判断顺序 insert的hint
  4.     MSN max_msn_applied; // applied最大的msn
  5. };

维护Fractal Tree的基本操作

创建新的Fractal Tree的索引

每个Fractal Tree由FT来表示。下面是列举了FT中比较重要的域。

  1. struct ft {
  2.     FT_HEADER h; // header
  3.     FT_HEADER checkpoint_header; // checkpoint开始时刻header的克隆
  4.     CACHEFILE cf; // 描述了FT对应的磁盘文件和数据节点信息。
  5.     toku::comparator cmp; // DBT compare函数
  6.     block_table blocktable; // FT逻辑块号到文件offset的映射表
  7.     struct toku_list live_ft_handles; // 打开此FT的handle列表
  8.     uint32_t num_txns;  // 访问此FT的事务个数
  9.     bool pinned_by_checkpoint; // 表示checkpoint正在进行
  10.     BLOCKNUM rightmost_blocknum; // 最右leaf节点块号，用于顺序insert优化
  11. } ;
  12. typedef struct ft *FT;
  13. struct ft_header {
  14.     enum ft_type type; // header类型
  15.     int dirty; // 脏标记
  16.     uint64_t checkpoint_count; // checkpoint计数
  17.     LSN checkpoint_lsn; // checkpoint开始时刻的lsn
  18.     const uint64_t time_of_creation; // FT创建时间
  19.     TXNID root_xid_that_created; //创建FT的事务ID
  20.     uint64_t time_of_last_modification; // 最近一次更新时间
  21.     BLOCKNUM root_blocknum; // root节点块号
  22.     const unsigned int flags; // 创建标志
  23.     unsigned int nodesize; // 节点大小，缺省值4M字节
  24.     unsigned int basementnodesize; // basement节点大小，缺省值128K字节
  25.     enum toku_compression_method compression_method; // 压缩算法
  26.     unsigned int fanout; // internal节点的fanout
  27.     MSN max_msn_in_ft; // FT最大的msn
  28. };
  29. enum ft_type {
  30.     FT_CURRENT = 1, // FT header
  31.     FT_CHECKPOINT_INPROGRESS // checkpoint开始时刻FT header的克隆
  32. };

创建新的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节点上的。伪代码如下：
  1. void toku_ft_root_put_msg(FT ft, const ft_msg &msg, txn_gc_info *gc_info) {
  2.     ftnode_fetch_extra bfe;
  3.     bfe.create_for_full_read(ft); // fetch整个node
  4.     pair_lock_type lock_type = PL_READ; // 初始状态：申请读锁
  5. change_lock_type:
  6.     toku_pin_ftnode(ft, root_key, fullhash, &bfe, lock_type, &node, true);
  7.     enum reactivity re = toku_ftnode_get_reactivity(ft, node);
  8.     switch (re) {
  9.     case RE_STABLE:
  10. case RE_FUSIBLE:
  11.         // root节点不支持merge操作
  12.         if (lock_type != PL_READ) {
  13.             // 其他thread抢先做了split
  14.             toku_unpin_ftnode_read_only(ft, node);
  15.             lock_type = PL_READ;
  16.             goto change_lock_type;
  17.         }
  18.         break;
  19.     case RE_FISSIBLE:
  20.         if (lock_type == PL_READ) {
  21.             // 需要split，升级为写锁
  22.             toku_unpin_ftnode_read_only(ft, node);
  23.             lock_type = PL_WRITE_CHEAP;
  24.             goto change_lock_type;
  25.         } else {
  26.             // root节点split
  27.             ft_init_new_root(ft, node, &node);
  28.             // split完成，降级为读锁
  29.             toku_unpin_ftnode(ft, node);
  30.             lock_type = PL_READ;
  31.             goto change_lock_type;
  32.         }
  33.         break;
  34.     }
  35.     if (root ->height == 0 || ft_msg_type_is_broadcast(msg.type())) {
  36.         // root是leaf节点或者messsage是广播消息，把message放到root节点上
  37.         // 这里释放锁的原因是：inject_message_at_this_blocknum里面会重新拿锁
  38.         toku_unpin_ftnode_read_only(ft, root);
  39.         inject_message_at_this_blocknum(ft, root_key, fullhash, msg, flow_deltas, gc_info);
  40.     } else if (root->height > 1) {
  41.         // root高度大于1时，把message加到root节点的某个子树上
  42.         push_something_in_subtree(ft, node, -1, msg, flow_deltas, gc_info, 0, LEFT_EXTREME |  RIGHT_EXTREME, false);
  43.     } else {
  44.         // root高度等于1时，确定message应该放到哪个leaf节点上
  45.         int childnum = toku_ftnode_which_child(node, msg.kdbt(), ft->cmp);
  46.         // 目标leaf节点是root的最左或最右子节点时，把message放到相应的leaf节点上
  47.         if (childnum == 0 || childnum == node->n_children - 1) {
  48.             push_something_in_subtree(ft, node, childnum, msg, flow_deltas, gc_info, 0, LEFT_EXTREME | RIGHT_EXTREME, false);
  49.         } else {
  50.             // 把message放到root节点上
  51.             // 这里释放锁的原因是：inject_message_at_this_blocknum里面会重新拿锁
  52.             toku_unpin_ftnode_read_only(ft, node);
  53.             inject_message_at_this_blocknum(ft, root_key, fullhash, msg, flow_deltas, gc_info);
  54.         }
  55.     }
  56. }
  57. toku_ftnode_get_reactivity返回的reactivity定义如下：
  58. enum reactivity {
  59.     RE_STABLE,    // 正常状态
  60.     RE_FUSIBLE,   // 需要merge
  61.     RE_FISSIBLE    // 需要split
  62. };

下面我们一起看一下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节点上。伪代码如下：

  1. 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) {
  2.     // 生成全局（FT内）唯一的msn
  3.     MSN msg_msn = { .msn = toku_sync_add_and_fetch(&ft->h->max_msn_in_ft.msn, 1) };
  4. ft_msg msg_with_msn(msg.kdbt(), msg.vdbt(), msg.type(), msg_msn, msg.xids());
  5.     toku_ftnode_put_msg(ft->cmp, ft->update_fun, node, childnum, msg_with_msn, true, gc_info, flow_deltas, &stats_delta);
  6. if (node->height > 0 && toku_ftnode_nonleaf_is_gorged(node, ft->h->nodesize)) {
  7.     // 如果node节点是internal节点，msg_buffer非空并且node节点所需的磁盘空间 + 各个子节点的workdone（query过程中同步flush的message大小的总和）大于nodesize（缺省4M），trigger client线程池的工作线程异步flush这个节点。
  8.     // msg_buffer非空并且node节点所需的磁盘空间 + 各个子节点的workdone: 表示node节点逻辑上的size
  9.    toku_ft_flush_node_on_background_thread(ft, node);
  10.     } else {
  11.         toku_unpin_ftnode(ft, node);
  12. }
  13. }

函数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伪代码如下：

  1. toku_le_apply_msg(const ft_msg &msg,
  2.                  LEAFENTRY old_leafentry,    // 老的LEAFENTRY
  3.                  bn_data* data_buffer,       // basement节点的bn，如果是basement节点上第一个message，这个值NULL
  4.                  uint32_t idx,               // old_leafentry在bn上的index
  5.                  uint32_t old_keylen, txn_gc_info *gc_info,
  6.                  LEAFENTRY *new_leafentry_p,  //新的LEAFENTRY
  7.                  int64_t * numbytes_delta_p) {
  8.     if (old_leafentry == NULL) {
  9.         msg_init_empty_ule(&ule);
  10.     } else {
  11.         le_unpack(&ule, old_leafentry); // 把LEAFENTRY转成ULE
  12.     }
  13.     msg_modify_ule(&ule, msg);          // 把message加到ULE的MVCC
  14.     // 把ULE转成LEAFENTRY
  15.     // 若data_buffer == NULL，le_pack分配basement节点的bn
  16.     int r = le_pack(&ule, data_buffer, idx, msg.kdbt()->data, keylen, old_keylen, oldmemsize, new_leafentry_p, &maybe_free);
  17. }

如果是FT_INSERT_NO_OVERWRITE，需要检查key是否已存在。若存在，直接退出。否则在ULE的MVCC结构添加一个类型为XR_INSERT的provisional txn。

  1. msg_modify_ule(ULE ule, const ft_msg &msg) {
  2.     switch (type) {
  3.     case FT_INSERT_NO_OVERWRITE: {
  4.         UXR old_innermost_uxr = ule_get_innermost_uxr(ule);
  5.         // key已存在，保留老值
  6.         if (uxr_is_insert(old_innermost_uxr)) break;
  7.     }
  8.     case FT_INSERT: {
  9.         uint32_t vallen = msg.vdbt()->size;
  10.         void * valp = msg.vdbt()->data;
  11.         ule_apply_insert(ule, xids, vallen, valp);
  12.         break;
  13. }

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。

  1. msg_modify_ule(ULE ule, const ft_msg &msg) {
  2.     switch (type) {
  3.     case FT_DELETE_ANY:
  4.         ule_apply_delete(ule, xids);
  5.         break;
  6.     }
  7. }

LEAFENTRY的隐式提交

之前有篇月报《MySQL·TokuDB·事务子系统和 MVCC 实现》讨论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节点（或者其下面的某个子节点）就返回。

  1. static void
  2. msg_modify_ule(ULE ule, const ft_msg &msg) {
  3.     XIDS xids = msg.xids();
  4.     enum ft_msg_type type = msg.type();
  5.     if (type != FT_OPTIMIZE && type != FT_OPTIMIZE_FOR_UPGRADE) {
  6.         ule_do_implicit_promotions(ule, xids);
  7.     }
  8. }
  9. static void
  10. ule_do_implicit_promotions(ULE ule, XIDS xids) {
  11.     if (ule->num_puxrs > 0) {
  12.         int num_xids = toku_xids_get_num_xids(xids);
  13.         uint32_t max_index = ule->num_cuxrs + min_i32(ule->num_puxrs, num_xids) - 1;
  14.         uint32_t ica_index = max_index;
  15.         uint32_t index;
  16.         for (index = ule->num_cuxrs; index <= max_index; index++) {
  17.             TXNID current_msg_xid = toku_xids_get_xid(xids, index - ule->num_cuxrs);
  18.             TXNID current_ule_xid = ule_get_xid(ule, index);
  19.             if (current_msg_xid != current_ule_xid) {
  20.                 //ICA表示innermost common ancestor
  21.                 ica_index = index - 1;
  22.                 break;
  23.             }
  24.         }
  25.         if (ica_index < ule->num_cuxrs) {
  26.             // 隐式提交上一次对这个LEAFENTRY的修改
  27.             invariant(ica_index == ule->num_cuxrs - 1);
  28.             ule_promote_provisional_innermost_to_committed(ule);
  29.         }
  30.         else if (ica_index < ule->num_cuxrs + ule->num_puxrs - 1) {
  31.             ule_promote_provisional_innermost_to_index(ule, ica_index);
  32.         }
  33.     }
  34. }

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类型：

  1. enum split_mode {
  2.     SPLIT_EVENLY,
  3.     SPLIT_LEFT_HEAVY,
  4.     SPLIT_RIGHT_HEAVY
  5. };

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节点没有双向链表

screenshot screenshot

上面的图是FT的树形结构，下面的图是B+Tree的树形结构

FT查询每次都是从root节点开始的，在internal节点中的查找是由pivotkeys路由到相应的子节点上，在leaf节点上是由pivotkeys路由到basement节点，然后在basement节点进行binary search寻找search key所在的位置。当要进行一个range查询的时候，首先使用set_range方法找到满足查询range区间的第一个key，然后把上一次得到的key作为参数调用get_next方法。

screenshot

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节点的有序结构都会读到内存来。伪代码如下：

  1. 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)
  2. {
  3. try_again:
  4.     trycount++;
  5.     ftnode_fetch_extra bfe;
  6.     // 只读取包含search key的那个子节点
  7.     bfe.create_for_subset_read(ft, search, &ftcursor->range_lock_left_key,
  8.                            &ftcursor->range_lock_right_key, ftcursor->left_is_neg_infty,
  9.                            Ftcursor->right_is_pos_infty,ftcursor->disable_prefetching, true);
  10.     FTNODE node = NULL;
  11.     {
  12.         //读取root节点，并设置bfe.child_to_read为包含search key的子节点
  13.         toku_pin_ftnode(ft, root_key, fullhash, &bfe, PL_READ, &node, true);
  14.     }
  15.     struct unlock_ftnode_extra unlock_extra   = {ft_handle,node,false};
  16.     struct unlockers  unlockers      = {true, unlock_ftnode_fun, (void*)&unlock_extra,          (UNLOCKERS)NULL};
  17.     {
  18.         bool doprefetch = false; bfe.child_to_read
  19.         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);
  20.         if (r==TOKUDB_TRY_AGAIN) {
  21.             // 获取锁时需要等待或者需要partial fetch
  22.             if (unlockers.locked) {
  23.                 toku_unpin_ftnode_read_only(ft_handle->ft, node);
  24.             }
  25.             goto try_again;
  26.         } else {
  27.             assert(unlockers.locked);
  28.         }
  29.     }
  30.     assert(unlockers.locked);
  31.     toku_unpin_ftnode_read_only(ft_handle->ft, node);
  32. }

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节点上进行搜索。