用Golang写一个搜索引擎(0x08)

原创
2016/05/05 00:08
阅读数 321

我觉得这个标题应该改改了,我写下来其实是告诉大家怎么写一个搜索引擎,并没有涉及太多的Golang的东西,我觉得这样也挺好,熟悉了原理,用什么实现其实并不重要了,而且说说原理比说代码更实在。

之前已经说了底层的数据结构了,包括倒排和正排索引。今天我们上一层,来说说索引的字段和段。

字段这个上一篇已经介绍了,字段的概念实际上是搜索引擎索引中我们能看到的最底层的东西,也是对外暴露的最底层的概念,在字段之下是倒排和正排索引,这两项其实对用户是封装起来了,我们可以认为每个字段对应一个正排和一个倒排,而实际上也确实是这样的。

在字段之上就是我们这一篇主要说的了,段这个概念并不是搜索引擎特有的,也不是必须的,是我这个项目新增出来的,当然,也不是我原创,很多搜索引擎的引擎系统都有这个概念。

所谓段,就是最基本的检索系统,一个包含所有字段,包含一部分连续的文档集合,能够进行完整的检索,可以把它当成一个检索系统最基本单位。

这么说可能还是有点抽象,我们打个比方,在数据库中,一行数据是最基本的单位,对应搜索引擎中的是一个文档,而表是所有文档的集合,对应搜索引擎中是一份索引,而段就是一部分表,它包含一部分文档的内容,可以对这一部分文档进行检索,多个段合并起来就是一份完整的索引。

为什么要有段这个概念呢?

  • 如果一个搜索引擎的数据再建好索引以后并不变化,那么完全没有必要使用段,直接在建立全量索引的时候把数据都建好就行了
  • 如果有增量数据,并且增量数据是不断进入系统的话,那么段的概念就有必要了,新增的数据首先在内存中进行保存,然后周期性的生成一个段,持久化到磁盘中提供检索操作。
  • 段还有一个好处就是当系统是一个分布式的系统的时候,进行索引同步的时候,因为各个段持久化以后就不会变化了,只需要把段拷贝到各个机器,就可以提供检索服务了,不需要在各个机器上重建索引。
  • 一个段损坏了,并不影响其他段的检索,只需要从其他机器上将这个段拷贝来就能正常检索了,如果只有一个索引的话,一旦索引坏了,就无法提供检索服务了,需要等把正确索引拷贝来才行。

一个段都存一些什么信息呢?

一个段包含几个文件

  • indexname_{segementNumber}.meta 这里是段的元信息,包括段中字段的名称,类型,也包括段的文档的起始和终止编号。
  • indexname_{segementNumber}.bt 这里是段的倒排索引的字典文件
  • indexname_{segementNumber}.idx 这里是段的所有字段的倒排文件
  • indexname_{segementNumber}.pfl 这里是段的所有数字正排文件的数据,同时也包含字符串类型数据的位置信息
  • indexname_{segementNumber}.dtl 这里是段的字符串类型数据的详情数据

上面的indexname是这个索引的名称,相当于数据库中的表名,segmentNumber是段编号,这个编号是系统生成的。

多个段合在一起就是一个完整的索引,检索的时候实际上是每个段单独检索,然后把数据合并起来就是最后的结果集了。

段的构建

下面我们一个一个来说说这些个文件,看看一堆正排和一堆倒排如何构成一个段的。

一个真正意义上的段的构建由以下几个步骤来构建,我们以一个实际的例子来说明一下段的构建,比如我们现在索引结构是这样,这个索引包括三个字段,分别是姓名(字符串),年龄(数字),自我介绍(带分词的字符串),那么构建段和索引的时候步骤是这样的

1.前期准备

首先新建一个段需要先初始化一个段,在初始化段的时候我们实际上已经知道这个段包含哪些字段,每个字段的类型。

  • 初始化一个段信息,包含段所包含的字段信息和类型,在这里就是包含姓名(字符串【正排和倒排】),年龄(数字【正排】),自我介绍(带分词的字符串【正排和倒排】)。
  • 给段一个编号,比如1000。
  • 准备开始接收数据。
2.建立内存中的段

内存中的段是构建段的第一步,以上述的字段信息为例,我们会在内存中建立以下几个数据结构,在这里我都是使用语言自动的原始数据结构

  • 姓名需要建立倒排索引,所以建立一个map<string,list>,key是姓名,value是docid,姓名也要建立正排索引,所以建立一个StringArray[],保存每条数据的姓名的详情。
  • 年龄需要建立正排索引,所以建立一个IntegerArray[],保存每条数据的年龄的详情。
  • 自我介绍需要建立倒排索引,所以建立一个map<string,list>,key是自我介绍的分词的term,value是docid,自我介绍也要建立正排索引,所以建立一个StringArray[],保存每条数据的自我介绍的详情。

当新增一条数据的时候{"name":"张三","age":18,"introduce":"我喜欢跑步"},首先我们给他一个docid【假如是0】,然后我们把数据分别存放到上面的5个数据结构中,如果再来一条数据{"name":"李四","age":28,"introduce":"我喜欢唱歌"},我们给他一个docid【假如是1】,那么数据就变成了下图的样子

输入图片说明

3.将数据结构持久化到磁盘中

这样,随着数据的不停导入,内存中的数据结构不断变化,内存段的数据也越来越大,当达到一定阈值的时候(这部分策略以后会说,我把这部分策略放到了引擎层,由引擎来决定什么时候进行段的持久化),我们将把数据持久化到磁盘中。

进行持久化的guo程中

  • 如果是map的数据结构,我们将遍历整个map,首先将value追加写到.idx文件中,然后把key建立B+树,value是刚刚写入的idx文件的偏移位置。
  • 如果是IntegerArray,我们遍历整个数组,然后把数据写入到pfl文件中,每个数据占用8个字节。
  • 如果是StringArray,我们遍历整个数据,首先把value追加写入到dtl文件中,然后把文件偏移量写入到pfl文件中

完成上面的三个步骤,我们的持久化工作就完成了,完成以后数据结构就变成下面的样子了,大家可以自己脑子里实现一遍。

输入图片说明

4.段构建完成后

段构建完成后,这个段就算完全持久化磁盘中了,不会再进行更改了,相当于提交到索引系统了,可以进行检索了。这时候,我们再新建一个段,接着接收新的文档数据,然后继续把后续的段持久化到磁盘中。

当检索的时候,依次检索每个段,然后将结果集合并起来返回给前端。

段的合并

段建立好了以后,可能需要对段进行合并操作,段的合并方式也很多,最简单的就是新建一个段,然后遍历之前的所有数据,从新建立一个段即可,这比较适合于数据量少的情况,因为新建一个段是在内存中的,如果之前的数据太多的话,内存会撑不住。

还有一种方式是分别将倒排,正排依次合并,这种方式不耗费内存,但是比较耗费磁盘的IO,两种方式大家可以根据自己的业务场景进行选择,第一种的方法和之前段的构建是一样的,这里我们说说第二种方式。

合并倒排文件

我们使用的B+树对倒排索引的字典文件进行存储,B+树天然带排序,那么合并段的时候实际上就是合并多个B+树,我们只要使用归并排序的方式就能合并多个B+树了。归并排序不清楚的可以自己去查查,每个B+树的Key就是待归并的元素,一边扫描B+树一边构建一个新的B+树,然后把倒排文件合并起来形成一个新的idx文件,倒排文件就合并完了。

合并正排文件

合并正排文件更加简单,只需要按照字段依次遍历每个段的正排文件,然后一边遍历一边就形成了一个新的正排文件,遍历完正排文件也就合并完了。

合并的方法在FalconIndex/segment/segment.goMergeSegments中有详细代码,大家可以参考一下这种最简单的合并方式。

段的策略

段的策略比较自由,一般也不建议固化到索引中。一般有以下几种策略可供选择,具体需要根据自己的业务逻辑来选择一个合适的段的持久化策略。

  • 如果你的系统是一个一旦建立了索引就不怎么变化的系统,那么在做全量索引的时候建立一个段就行了,全量索引构建完了,然后把段持久化到磁盘就行了,如果全量索引量很大,怕内存扛不住,那么可以每10万条建立一个段,当全量索引完成了以后再将所有的段合并成一个段就行了,段的合并后面会说,合并段基本不占用什么内存,可以随时合并,如果有增量数据,每隔一段时间序列化一下段,然后再每隔一段时间将所有非全量数据的段合并一下,那么系统中就基本上只有一个全量的段和一个增量的段,检索起来还是非常快的。
  • 如果你的系统是一个实时变化比较大的系统,比如日志系统,那么全量索引实际就没什么意义了,由于日志系统的检索其实实时性要求没有那么高,那么段的策略可以是每新增10万条数据持久化一个段,没到10个段将所有段合并成一个段。或者按照时间戳来合并段,方便剔除老的数据。
  • 如果你的系统是一个实时性要求很高的系统,那么可以按照时间(比如10秒)持久化一次段,每当系统空闲的时候将小的段合并成一个大的段。

总之,段的策略比较自由,完全由引擎层来实现,根据自己的业务场景来选择重写一个段合并的策略都是可以的。

段是索引的一部分,也是一个微型的索引,下面一篇我们将会介绍索引层了,索引层介绍玩以后搜索引擎的数据层就完全结束了,上面就是各种引擎的策略了,有了索引层以后,其实对上你要变成一个搜索引擎还是要变成一个数据库,或者变成一个KVDB的数据库都是可以的,反正基础的东西不会有太多变化。

好了,如果你想看之前的文章,可以关注我的公众号哈:)

输入图片说明

展开阅读全文
打赏
1
8 收藏
分享
加载中
更多评论
打赏
0 评论
8 收藏
1
分享
返回顶部
顶部