FalconEngine - 一个 Go 语言实现的简单搜索引擎

jopen 9年前
对搜索引擎感兴趣的可以去看看 这本书 ,比较浅并且也比较完整的介绍了一个搜索引擎的全部机能。

我的这个搜索引擎原始数据是MySql数据库的,大家可以根据需要进行二次开发,用来支持其他数据库或者本地文件,Detail文件是存储在 Redis数据库中,同样这部分也可以根据自己的需要二次开发,使用本地文件或者其他数据库,倒排索引和正排索引本地存储的时候使用的json格式,比较耗磁盘,第一版暂时这样了吧,后续再做优化。

性能测试

  • 不好意思,还没测呢,功能已经都测完了,性能还未优化,后续会测试,这是个持续的项目,会一直优化下去。

使用方法

依赖以下几个库

  • 直接运行install.sh
  • github.com/huichen/sego 获取分词的字典文件
  • 运行索引器,会将索引文件生成到index目录下

bin/FalconEngine -mode=build

  • 运行搜索器

bin/FalconEngine -mode=search

基本概念

以下几个概念需要理解,如果完全不了解的话,还需要自己稍微百度一下:倒排索引,正排文件,Detail文件,全量索引,增量索引,哈希函数,DocId

基础数据结构

搜索引擎首先并不神秘,基础的数据结构就那么几个,定了以后后面就是在上面添砖加瓦了。

假如有下面五个文档需要进行搜索

文档编号 内容
1 你好,搜索引擎
2 搜索引擎有一条数据
3 你好,有一条测试数据

倒排索引

倒排索引是搜索引擎基础中的基础,主要的检索都是从倒排索引开始的,所以,首先,设计一个倒排索引的数据结构是所有搜索引擎的基础。

搜索引擎的基础是DocId,也就是文档ID,DocId是唯一的并且是连续的,而倒排索引就是一组DocId链表,每个链表对应一个关键词。

上面的文档建立号倒排索引的基础结构如下图

关键词 文档编号
你好 1,3
搜索引擎 1,2
数据 2,3
有一条 2,3
测试 3

所以,当我们检索数据这个词的时候能迅速知道在文档 23 有这条数据,就能进行检索了。

是不是很简单,关键问题是检索数据的时候,如何能迅速定位到第三行数据,这里就用到哈希表了,所以,一个完整的倒排包括两部分,一部分是上面的这个表,第二个是一个哈希表,通过这个哈希表能知道数据这个词的下标为3,从而找到2,3这两个文档。

哈希表的具体实现就不详细展开了,哈希表有很多种实现方式,并且哈希函数也有很多种实现方式,总之,对于一个关键词的定位

  • 首先,通过计算这个关键词的hash,得到它的下标
  • 然后,查找倒排索引的下标,得到文档ID的链表

在代码的InvertIndex.go中是倒排索引的数据结构,StringIndexDic.go是关键词的哈希表,这两个文件产生的数据都会序列化成json文件存储下来。

正排索引

正排索引相对倒排就简单多了,实际上就是一个字典文件,key是DocId,value是这个DocId对应的内容,主要用来做结果集的过滤,所谓倒排检索,正排过滤,什么场景需要这样的东西呢?下面的场景你肯定经历过。

你在一个某东的网站搜索运动鞋,肯定出来一堆鞋子,但是你只想看nike的鞋子,这时候你可以再运动鞋后面加上Nike,搜索nike运动鞋,但是结果不一定准,因为并不是每个nike的鞋子的标题上都会写上nike,这时候就需要用到正排了,他会把nike鞋子给你过滤出来。

正排索引就是一个数组,数组的下标就是DocId,文件中的NumberProfile.go和TextProfile.go是具体的实现文件

Detail文件

Detail文件使用的是Redis实现的,没有具体的数据结构,实际上就是以主键ID为key来实现的。

增量更新

增量更新使用的是扫描mysql中的一个last_modify_time字段,获取数据,然后和redis中的数据进行对比,如果更新了就添加到索引中,添加索引按照如下的步骤进行

  • 如果是正排字段更新,并且不是新增的数据,只是原来的数据修改

    • 直接更新DocId对应下标的数据
  • 如果是正排字段更新,但是是新增的数据

    • 新增一个DocId并添加到正排文件的后面
  • 如果是倒排字段更新

    • 将原始的DocId从BitMap中删除
    • 新增一个DocId并添加到倒排文件的后面

因为DocId是连续的,倒排字段更新的话,要修改倒排链表,而目前的倒排链表是数组的,所以直接建立一个BitMap,将对应的DocId删除,后续改成链表形式的话,可以动态的删除。

增量更新使用的一个go的协程来做的,扫描的是数据库字段,后续可以改成从kafka获取数据或者其他方式获取增量更新

数据检索

数据检索分成以下几个步骤

  • 根据关键词从倒排索引中获取DocId链,有多个关键词的时候求交集
  • 通过BitMap过滤掉已经删除的DocId
  • 最后得到的DocId按照正排文件的条件进行过滤操作,获取最终的DocId链
  • 通过DocId反查出文档的真实ID,并通过Redis获取文档的详细信息用于显示

文件中的IndexSet.go主要实现了上述步骤

项目地址是: https://github.com/wyh267/FalconEngine