翼度科技»论坛 编程开发 mysql 查看内容

MySQL全文索引源码剖析之Insert语句执行过程

7

主题

7

帖子

21

积分

新手上路

Rank: 1

积分
21
本文分享自华为云社区《MySQL全文索引源码剖析之Insert语句执行过程》 ,作者:GaussDB 数据库。

1. 背景介绍

全文索引是信息检索领域的一种常用的技术手段,用于全文搜索问题,即根据单词,搜索包含该单词的文档,比如在浏览器中输入一个关键词,搜索引擎需要找到所有相关的文档,并且按相关性排好序。
全文索引的底层实现是基于倒排索引。所谓倒排索引,描述的是单词和文档的映射关系,表现形式为(单词,(单词所在的文档,单词在文档中的偏移)),下文的示例将会展示全文索引的组织方式:
  1. mysql> CREATE TABLE opening_lines (
  2.            id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
  3.            opening_line TEXT(500),
  4.            author VARCHAR(200),
  5.            title VARCHAR(200),
  6.            FULLTEXT idx (opening_line)
  7.            ) ENGINE=InnoDB;   
  8. mysql> INSERT INTO opening_lines(opening_line,author,title) VALUES
  9.            ('Call me Ishmael.','Herman Melville','Moby-Dick'),
  10.            ('A screaming comes across the sky.','Thomas Pynchon','Gravity\'s Rainbow'),
  11.            ('I am an invisible man.','Ralph Ellison','Invisible Man'),
  12.            ('Where now? Who now? When now?','Samuel Beckett','The Unnamable');      
  13. mysql> SET GLOBAL innodb_ft_aux_table='test/opening_lines';
  14. mysql> select * from information_schema.INNODB_FT_INDEX_TABLE;
  15. +-----------+--------------+-------------+-----------+--------+----------+  
  16. | WORD      | FIRST_DOC_ID | LAST_DOC_ID | DOC_COUNT | DOC_ID | POSITION |  
  17. +-----------+--------------+-------------+-----------+--------+----------+  
  18. | across    |            4 |           4 |         1 |      4 |       18 |  
  19. | call      |            3 |           3 |         1 |      3 |        0 |  
  20. | comes     |            4 |           4 |         1 |      4 |       12 |  
  21. | invisible |            5 |           5 |         1 |      5 |        8 |  
  22. | ishmael   |            3 |           3 |         1 |      3 |        8 |  
  23. | man       |            5 |           5 |         1 |      5 |       18 |  
  24. | now       |            6 |           6 |         1 |      6 |        6 |  
  25. | now       |            6 |           6 |         1 |      6 |        9 |  
  26. | now       |            6 |           6 |         1 |      6 |       10 |  
  27. | screaming |            4 |           4 |         1 |      4 |        2 |  
  28. | sky       |            4 |           4 |         1 |      4 |       29 |  
  29. +-----------+--------------+-------------+-----------+--------+----------+
复制代码
如上,创建了一个表,并在opening_line列上建立了全文索引。以插入'Call me Ishmael.'为例,'Call me Ishmael.'也即文档,其ID为3,在构建全文索引时,该文档会被分成3个单词'call', 'me', 'ishmael',由于'me'小于设定的ft_min_word_len(4)最小单词长度被丢弃,最后全文索引中只会记录'call'和'ishmael',其中'call'起始位置在文档中的第0个字符处,偏移为0,'ishmael'起始位置在文档中的第12个字符处,偏移即为12。
关于全文索引更详细的功能介绍可以参考MySQL 8.0 Reference Manual,本文将从源码层面,简要剖析Insert语句的执行过程。
2. 全文索引Cache

全文索引表中记录的是{单词,{文档ID,出现的位置}},即插入一个文档需要将其分词成多个{单词,{文档ID,出现的位置}}这样的结构,如果每次分词完就马上刷磁盘,其性能会非常差。
为了缓解该问题,Innodb引入了全文索引cache,其作用与Change Buffer类似。每次插入一个文档时,先将分词结果缓存到cache,等到cache满了再批量刷到磁盘,从而避免频繁地刷盘。Innodb定义了fts_cache_t的结构来管理cache,如下图所示:

每张表维护一个cache,对于每个创建了全文索引的表都会在内存中创建一个fts_cache_t的对象。注意,fts_cache_t是表级别的cache, 若一个表创建了多个全文索引,内存中依旧是对应一个fts_cache_t对象。fts_cache_t的一些重要成员如下:

  • optimize_lock、deleted_lock、doc_id_lock:互斥锁,与并发操作相关。
  • deleted_doc_ids:vector类型,存储已删除的doc_id。
  • indexes:vector类型,每个元素表示一个全文索引,每次创建全文索引时,都会往该数组中添加一个元素,每个索引的分词结果以红黑树结构存储,key为word, value就是doc_id及单词的偏移。
  • total_size:cache已分配的全部内存,包含其子结构使用的内存。
3. Insert语句执行过程

以MySQL 8.0.22源码为例,Insert语句的执行主要分为三个阶段,分别为写入行记录阶段、事务提交阶段和刷脏阶段。
3.1 写入行记录阶段

写入行记录的主要工作流如下图所示:

如上图所示,这一阶段最主要是生成doc_id,并写入到Innodb的行记录中,并且将doc_id缓存,以供事务提交阶段根据doc_id获取文本内容,其函数调用栈如下:
  1.   ha_innobase::write_row
  2.         ->row_insert_for_mysql
  3.             ->row_insert_for_mysql_using_ins_graph
  4.                 ->row_mysql_convert_row_to_innobase
  5.                     ->fts_create_doc_id
  6.                         ->fts_get_next_doc_id
  7.                 ->fts_trx_add_op
  8.                     ->fts_trx_table_add_op
复制代码
fts_get_next_doc_id与fts_trx_table_add_op是比较重要的两个函数,fts_get_next_doc_id是为了获取doc_id,innodb行记录中包含了一些隐藏列,比如row_id、trx_id等,若创建了全文索引,其行记录中也会增加一个隐藏字段FTS_DOC_ID,这个值在fts_get_next_doc_id中获取的,如下:
而fts_trx_add_op则是将对全文索引的操作添加到trx中,待事务提交时进一步处理。
3.2 事务提交阶段

事务提交阶段的主要工作流如下图所示:

这一阶段是整个FTS 插入的最重要的一步,对文档进行分词,获取{单词,{文档ID,出现的位置}},插入到cache,这些都是在这一阶段完成的。其函数调用栈如下:
  1. fts_commit_table
  2.       ->fts_add
  3.           ->fts_add_doc_by_id
  4.               ->fts_cache_add_doc
  5.                     // 根据doc_id获取文档,对文档分词
  6.                   ->fts_fetch_doc_from_rec
  7.                     // 将分词结果添加到cache中
  8.                   ->fts_cache_add_doc
  9.               ->fts_optimize_request_sync_table
  10.                     // 创建FTS_MSG_SYNC_TABLE消息,通知刷脏线程刷脏
  11.                   ->fts_optimize_create_msg(FTS_MSG_SYNC_TABLE)
复制代码
其中,fts_add_doc_by_id是比较关键的一个函数,该函数主要完成了以下几件事:
1)根据doc_id找到行记录, 获取对应的文档;
2)对文档执行分词,获取{单词,(单词所在的文档,单词在文档中的偏移)}关联对,并添加到cache中;
3)判断cache->total_size是否达到阈值时,若达到阈值,则往刷脏线程的消息队列添加一个FTS_MSG_SYNC_TABLE消息, 通知该线程刷脏(fts_optimize_create_msg),具体代码如下:为方便理解,我把代码的异常处理部分以及一些查找记录的通用部分省略了,并给出了简要注释:
  1.    static ulint fts_add_doc_by_id(fts_trx_table_t *ftt, doc_id_t doc_id)
  2.     {
  3.             /* 1. 根据docid在fts_doc_id_index索引中的查找记录 */
  4.           /* btr_pcur_open_with_no_init函数中会调用btr_cur_search_to_nth_level,btr_cur_search_to_nth_level
  5.             会执行b+树搜索记录的过程,先从根节点找到docid记录所在的叶子节点,再通过二分查找找到docid记录。*/
  6.         btr_pcur_open_with_no_init(fts_id_index, tuple, PAGE_CUR_LE,
  7.                                     BTR_SEARCH_LEAF, &pcur, 0, &mtr);
  8.         if (btr_pcur_get_low_match(&pcur) == 1) { /* 如果找到了docid记录 */
  9.             if (is_id_cluster) {
  10.                  /** 1.1 如果fts_doc_id_index是聚集索引,则意味着已经找到行记录数据, 直接保存行记录 **/
  11.                 doc_pcur = &pcur;
  12.               } else {
  13.                 /** 1.2 如果fts_doc_id_index是辅助索引,则需要根据1.1找到的主键id在聚集索引上进一步搜 索行记录,找到后保存行记录**/                btr_pcur_open_with_no_init(clust_index, clust_ref, PAGE_CUR_LE,
  14.                                            BTR_SEARCH_LEAF, &clust_pcur, 0, &mtr);
  15.                doc_pcur = &clust_pcur;
  16.              }        // 遍历cache->get_docs
  17.             for (ulint i = 0; i < num_idx; ++i) {
  18.                 /***** 2. 对文档执行分词,获取{单词,(单词所在的文档,单词在文档中的偏移)}关联对,并添加到cache中 *****/
  19.                 fts_doc_t doc;
  20.                 fts_doc_init(&doc);
  21.         /** 2.1 根据doc_id获取行记录中该全文索引对应列的内容文档,解析文档,主要是为了构建               fts_doc_t结构体的tokens,tokens为一个红黑树结构,每个元素是一个               {单词,[该单词在文档中出现的位置]}的结构,解析结果存于doc中 **/
  22.                 fts_fetch_doc_from_rec(ftt->fts_trx->trx, get_doc, clust_index,doc_pcur, offsets, &doc);
  23.                 /** 2.2 将2.1步骤获得的{单词,[该单词在文档中出现的位置]}添加到index_cache中 **/
  24.                 fts_cache_add_doc(table->fts->cache, get_doc->index_cache, doc_id, doc.tokens);
  25.                /***** 3. 判断cache->total_size是否达到阈值时。  若达到阈值,则往刷脏线程的消息队列添加一个FTS_MSG_SYNC_TABLE消息, 通知该线程刷脏 *****/
  26.                 bool need_sync = false;
  27.                 if ((cache->total_size - cache->total_size_before_sync >
  28.                      fts_max_cache_size / 10 || fts_need_sync) &&!cache->sync->in_progress) {
  29.                   /** 3.1 判断是达到阈值 **/
  30.                   need_sync = true;
  31.                   cache->total_size_before_sync = cache->total_size;
  32.                 }
  33.                     if (need_sync) {
  34.                     /** 3.2 打包FTS_MSG_SYNC_TABLE消息挂载至fts_optimize_wq队列,                   通知fts_optimize_thread线程刷脏,消息的内容为table id **/                  fts_optimize_request_sync_table(table);
  35.                 }
  36.             }
  37.         }
  38.     }  
复制代码
了解了上述过程,就可以解释官网所述的全文索引事务提交的特殊现象了,参考MySQL 8.0 Reference Manual 的InnoDB Full-Text Index Transaction Handling一节,若对全文索引表插入一些行记录,如果当前事务未提交,我们在当前事务中通过全文索引是查不到已插入的行记录。其原因在于,全文索引的更新是在事务提交的时完成的,事务未提交时,fts_add_doc_by_id尚未执行,因此,不能通过全文索引查找该记录。但是,通过3.1小节可以知道,此时Innodb的行记录是已经插入了的,如果通过全文索引查询,直接执行SELECT COUNT(*) FROM opening_lines是可以查到该记录的。
3.3 刷脏阶段

刷脏阶段的主要工作流如下图所示:

InnoDB启动时,会创建一个后台线程,线程函数为fts_optimize_thread,工作队列为fts_optimize_wq。3.2节事务提交阶段,当cache满时fts_optimize_request_sync_table函数会往fts_optimize_wq队列添加一个FTS_MSG_SYNC_TABLE消息,后台线程取下该消息后将cache刷新到磁盘。其函数调用栈如下:
  1.   fts_optimize_thread
  2.         ->ib_wqueue_timedwait
  3.             ->fts_optimize_sync_table
  4.                 ->fts_sync_table
  5.                     ->fts_sync
  6.                         ->fts_sync_commit
  7.                             ->fts_cache_clear
复制代码
该线程主要执行的操作如下:

  • 从fts_optimize_wq队列取一个消息;
  • 判断消息的类型,若为FTS_MSG_SYNC_TABLE,则执行刷脏;
  • 将cache中的内容刷新到磁盘上的辅助表;
  • 清空cache, 置cache为初始状态;
  • 返回至步骤1,取下一个消息;
在3.2节中,当事务提交时,若fts cache的total_size大于了设定的内存大小阈值,则会写入一条FTS_MSG_SYNC_TABLE插入到fts_optimize_wq队列,刷脏线程会处理该消息,将fts cache中的数据刷到磁盘,随后清空cache。
值得一提的是,当fts cache的total_size大于设定的内存大小阈值时,只会写条消息到fts_optimize_wq队列,此时fts cache在未被后台刷脏线程处理之前,依然可以写入数据,内存会继续增加,这也是导致了全文索引并发插入的OOM问题的根因,问题的修复patch Bug #32831765 SERVER HITS OOM CONDITION WHEN LOADING TWO INNODB,感兴趣的读者可以自行查阅。
OOM查阅链接:https://bugs.mysql.com/bug.php?id=103523
若刷脏线程还未对某个表的fts cache刷脏,此时MySQL进程crash了,cache中的数据丢失。重启之后,第一次对该表执行insert或者select时,在fts_init_index函数中会对crash之前cache中的数据进行恢复,此时会从config表中读取已落盘的synced_doc_id, 将表中大于synced_doc_id的记录读取并分词恢复到cache中,具体实现参考fts_doc_fetch_by_doc_id, fts_init_recover_doc函数。
点击关注,第一时间了解华为云新鲜技术~
 

来源:https://www.cnblogs.com/huaweiyun/p/18201367
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?立即注册

x

举报 回复 使用道具