Facebook MySQL: 索引在线碎片整理特性

背景

我们知道Innodb使用BTREE来进行数据组织存储，当发生INSERT/UPDATE/DELETE时，有可能会产生数据s碎片，不能有效的利用page空间。而这些空洞在未来甚至有可能不再被使用到。即使是顺序的Insert，也可能产生空间浪费：为了保证以后对相同page的更新不会产生page分裂，Innodb总是为其保留一部分的剩余空间。

本文是对之前写的这篇博客的整理和补充（http://mysqllover.com/?p=1014）

DML操作的空间影响

INSERT操作

对于INSERT也分两种情况，直接INSERT 以及通过更改已有记录的方式来INSERT；第一种方式大家可能比较理解；

对于第一种方式，在插入记录时，对于page 内数据大小是有个硬限制的：

从btr_cur_optimistic_insert函数截取的代码：

1399         /* If there have been many consecutive inserts to the

1400         clustered index leaf page of an uncompressed table, check if

1401         we have to split the page to reserve enough free space for

1402         future updates of records. */

1403

1404         if (leaf && !zip_size && dict_index_is_clust(index)

1405             && page_get_n_recs(page) >= 2

1406             && dict_index_get_space_reserve() + rec_size > max_size

1407             && (btr_page_get_split_rec_to_right(cursor, &dummy)

1408                 || btr_page_get_split_rec_to_left(cursor, &dummy))) {

1409                 goto fail;

1410         }

dict_index_get_space_reserve函数的返回值是十六分之一的page size，也就是说插入新记录后，留余的空闲空间不能小于这个1/16 *page size，默认16k配置下，就是1K。

说到INSERT，就不得不提一个bug#67718，以主键逆序的方式插入记录可能导致索引分裂非常频繁。感兴趣的可以看看 bug传送门： http://bugs.mysql.com/bug.php?id=67718：

假定page最多插入6条记录

子节点p1有数据(1,2,3,4,5,6)

插入记录（10），产生分裂新子节点p2(10)

插入记录（8），寻址到p1，PAGE_LAST_INSERT是6，满足顺序插入条件，但p1已满，产生新子节点p3(8)。

这个Bug已经在最新版本中被fix掉了（5.6.21 及5.7.5）。

对于第二种插入方式，假设这种场景：

CREATE TABLE t1 (a int, b int, c int, primary key(a,b));

INSERT INTO t1 (1,2,3);

DELETE FROM t1;

INSERT INTO t1 (1,2,6);

MySQL使用标记删除的方式来删除记录，如果DELETE和再次INSERT中间的间隔足够小，Purge线程还没来得及清理该记录时，新插入的(1,2,6)就会沿用之前的记录，因为他们主键是相同的。

参考函数：row_ins_must_modify_rec、row_ins_clust_index_entry_by_modify

INSERT BY MODIFY的方式是，先将原记录的delete标记清楚，然后再对该记录做update。

UPDATE操作

对于更新操作，有两种方式，一种是IN-PLACE更新，另一种是先标记删除再插入新记录的方式。更新的顺序是总是先更新聚集索引，再更新二级索引。

对于二级索引记录更新，总是先标记删除再插入新记录。对于聚集索引，这两种情况都存在。例如如果没有改变记录大小（row_upd_changes_field_size_or_external），就直接In-place更新了（btr_cur_update_in_place），否则在代码逻辑上，总是先删除（page_cur_delete_rec）再插入记录（btr_cur_insert_if_possible），如果主键未变，则沿用其之前的聚集索引记录所在的位置，注意尽管主键不变，但如果记录长度变小了，依然会在page内产生碎片

如果更新的是聚集索引记录，引起索引顺序发生变化，则采用标记删除+插入（row_upd_clust_rec_by_insert）

很显然频繁的Update可能会导致空间膨胀，尤其是当二级索引比较多的时候。当然purge线程可以去回收被标记删除的空间，但page空间利用率依然会有所降低。

DELETE操作

实际上删除操作和update操作走类似的接口函数row_update_for_mysql，只是将prebuilt->upd_node->is_delete设置为TRUE来进行区分。使用标记删除的方式。

Innodb自我调节

合并Page

Innodb在特定情况下会主动去尝试合并Page，主要包含以下几个调用栈

btr_compress

btr_node_ptr_delete

btr_cur_pessimistic_update

btr_cur_pessimistic_delete

            |—->btr_cur_compress_if_useful

                       |—->btr_compress

上述调用栈，都是在做完悲观DELETE或UPDATE后尝试合并Page。在满足如下条件时会去尝试合并(函数btr_cur_compress_recommendation)：

# 非root page

# Page内的数据小于PAGE SIZE的二分之一（BTR_CUR_PAGE_COMPRESS_LIMIT）；

# 如果是当前level唯一的一个page，需要上提到父节点(btr_lift_page_up)

早期有个bug#68501，innodb在确定合并的page是左节点还是右节点时，总是先尝试左节点，如果左节点是可用的，但是合并失败时，没有去再次尝试右节点页。在做逆序删除操作时，可能导致大量btr_compress失败，引起ibd空间无法有效收缩。

Oracle mysql 在5.6.13版本fix了这个问题，当合并左节点失败时，会再次尝试右节点，具体可以浏览补丁Rev:4384

Page内自调整

当page内的最大可用空间不满足记录插入时，可能会触发page内的数据重组（btr_page_reorganize）。即使空闲空间满足插入记录，还有一个硬限制来进行重组，即page大小的32分之一(BTR_CUR_PAGE_REORGANIZE_LIMIT)。

相关堆栈：

btr_can_merge_with_page

|—->btr_page_reorganize_block

         |—->btr_page_reorganize_low

btr_page_split_and_insert

btr_cur_insert_if_possible

btr_cur_optimistic_insert

btr_cur_update_alloc_zip_func

ibuf_insert_to_index_page_low

|—->btr_page_reorganize

         |—->btr_page_reorganize_low

page_cur_insert_rec_zip

|—–>btr_page_reorganize_low

页内重组的流程大概如下：

1. 从bufferpool重分配一个新的block，并将page内的数据都拷贝进去。
2. 重新初始化页面 （page整个frame被写redo了，因此可以崩溃恢复)
3. 从step 1产生的临时block中将记录一个个拷贝到重初始化过后的page
4. 对于压缩表，会做一次重压缩

从代码来看，拷贝过程中并没有去移除标记删除的记录。因此这个重组织做的并不彻底。

传统方案

optimize table、alter table tbname engine=innodb (MySQL 5.6.17及之后已经开始支持ONLINE)

dump/restore 数据集

Facebook MySQL的defragment特性

Fb的实现中，引入了一个独立的线程(btr_defragment_thread)来专门做碎片整理，每次从叶子节点开始，持有索引X锁，每整理N个page后释放锁，然后再继续执行。可以指定做defragement操作的索引是聚集索引还是二级索引。一次处理最多不超过32个page，以降低持有索引X锁的时间。

以下基于webscalesql-5.6.21.55分析

语法解析

defragment:

          DEFRAGMENT_SYM index_defragmentation opt_async_commit

          {

            THD *thd= YYTHD;

            Lex->m_sql_cmd= new (thd->mem_root)

              Sql_cmd_defragment_table();

            if (Lex->m_sql_cmd == NULL)

              MYSQL_YYABORT;

          }

从语法可以看到，支持对特定索引做defragement操作，支持异步/同步返回

Sql_cmd_defragment_table类：

class Sql_cmd_defragment_table : public Sql_cmd_common_alter_table

{

public:

  Sql_cmd_defragment_table()

  {}

  ~Sql_cmd_defragment_table()

  {}

  bool execute(THD *thd);

};

执行用户请求

bool Sql_cmd_defragment_table::execute(THD *thd)

:

436   int ret = handler->ha_defragment_table(path, index.str,

437                                          thd->lex->async_commit);

在完成必要的MDL加锁后，调用存储引擎接口，也就是ha_innobase::defragment_table

根据要做defragment的表名和索引名，首先检查是否已经在工作队列(btr_defragment_wq)中（btr_defragment_find_index(index)），如果不在，则返回错误，否则加入工作队列中（btr_defragment_add_index(index, async)）

如果SQL指定的async操作，则直接返回，否则需要等待defragment操作完成。如果在等待的过程中线程被kill了，就将这个任务标记为removed，然后返回。

将item加入工作队列时，初始化一个cursor，定位在B-TREE 叶子节点的第一个page的第一个记录:

        btr_pcur_t* pcur = btr_pcur_create_for_mysql();

        os_event_t event = NULL;

        if (!async) {

                event = os_event_create();

        }

        btr_pcur_open_at_index_side(true, index, BTR_SEARCH_LEAF, pcur,

                                    true, 0, &mtr);

        btr_pcur_move_to_next(pcur, &mtr);

        btr_pcur_store_position(pcur, &mtr);

        mtr_commit(&mtr);

独立后台defragment线程

后台开启一个线程，专门做defragment操作，入口函数为btr_defragment_thread.

defragement 线程的设计大概如下：

1. defragment线程负责清理工作队列中被标记为removed的item，或者在item工作完成时移除，用户线程只负责插入。

2. 可配置做defragment的操作频度，避免给系统带来太大的负载

3. 因为每次defragment操作都需要锁索引锁，因此为了平衡负载，对每个item（对应一个索引）的操作也不是一次完成的，而是一次完成srv_defragment_n_pages（可配置）个page后，记录下当前的cursor ,下一轮继续，但一轮最多不超过32个page：

      保存cursor

                        page_t* last_page = buf_block_get_frame(last_block);

                        rec_t* rec = page_rec_get_prev(

                                page_get_supremum_rec(last_page));

                        ut_a(page_rec_is_user_rec(rec));

                        page_cur_position(rec, last_block,

                                          btr_cur_get_page_cur(cursor));

                        btr_pcur_store_position(pcur, &mtr);

                       mtr_commit(&mtr);

主函数btr_defragment_n_pages：对N个Page进行defragment处理

大概流程如下：

1. 读入这N个page；并计算这些page中存储的总的数据长度(total_data_size)和记录数(total_n_recs)

如果当前Level只有一个page的话，上提到父节点(btr_lift_page_up(index, block, mtr))

2. 计算可缩减的空间量

data_size_per_rec = total_data_size / total_n_recs;

optimal_page_size = page_get_free_space_of_empty(page_is_comp(first_page));

（对于压缩表，optimal_page_size是根据压缩失败时的page利用率来估算，索引对象上维持了一个stat_defrag_data_size_sample数组，用于记录采样值）

reserved_space = min((ulint)(optimal_page_size

                              * (1 – srv_defragment_fill_factor)),

                             (data_size_per_rec

                              * srv_defragment_fill_factor_n_recs));  //每个page的保留空间

有两个factor可以用于控制保留空间数，按照记录数保留或按照page百分比保留；srv_defragment_fill_factor默认为20；srv_defragment_fill_factor_n_recs默认为20;

optimal_page_size -= reserved_space;

n_new_slots = (total_data_size + optimal_page_size – 1)

                      / optimal_page_size;  //优化后需要的page数

如果计算后的n_new_slots 比目前的page数还多，则无需整理，直接返回。

从第二个page开始，向前面的page中开始merge记录。

        for (uint i = 1; i < n_pages; i ++) {

                buf_block_t* new_block = btr_defragment_merge_pages(

                        index, blocks[i], current_block, zip_size,

                        reserved_space, &max_data_size, heap, mtr);

                if (new_block != current_block) {

                        n_defragmented ++;

                        current_block = new_block;

                }

        }

btr_defragment_merge_pages函数处理page间的记录合并:

a. 计算能装载的空间大小，并据此记录可移动的记录数；

b. 如果可用空间可能不足，会尝试做一次页面重组(btr_page_reorganize_block)；

c. 然后开始一个记录，一个记录的转移 （page_copy_rec_list_start）

d. 如果整个page都搬空了，则释放该page，加入到空闲链表中：

470                 lock_update_merge_left(to_block, orig_pred,

471                                        from_block);

472                 btr_search_drop_page_hash_index(from_block);

473                 btr_level_list_remove(space, zip_size, from_page,

474                                       index, mtr);

475                 btr_node_ptr_delete(index, from_block, mtr);

476                 btr_blob_dbg_remove(from_page, index,

477                                     “btr_defragment_n_pages”);

478                 btr_page_free(index, from_block, mtr);

e. 否则，删除page中已被merge到目标page的记录，更新行锁，ibuf，父节点指针。同时当前page作为下一轮merge的目标块。

这中间也有很多特殊处理，比如对压缩表的处理，感兴趣的自行翻代码。

结论

该特性的好处是：能够实现在线defragment，提升Innodb索引的利用率，被释放出来的空间将会被重用，从而降低碎片化，提升空间利用率，最终达到节约存储空间的目的。