FalconEngine - 一个 Go 语言实现的简单搜索引擎
我的这个搜索引擎原始数据是MySql数据库的,大家可以根据需要进行二次开发,用来支持其他数据库或者本地文件,Detail文件是存储在 Redis数据库中,同样这部分也可以根据自己的需要二次开发,使用本地文件或者其他数据库,倒排索引和正排索引本地存储的时候使用的json格式,比较耗磁盘,第一版暂时这样了吧,后续再做优化。
性能测试
- 不好意思,还没测呢,功能已经都测完了,性能还未优化,后续会测试,这是个持续的项目,会一直优化下去。
使用方法
依赖以下几个库
- github.com/outmana/log4jzl log文件
- github.com/ewangplay/config 配置文件解析
- github.com/go-sql-driver/mysql mysql驱动
- github.com/garyburd/redigo/redis Redis驱动
- github.com/huichen/sego 分词器,作者主页非常感谢他的分析器,他主页上也有个搜索引擎,没看具体实现,大家感兴趣可以去看看。
- 直接运行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 |
所以,当我们检索数据这个词的时候能迅速知道在文档 2 和 3 有这条数据,就能进行检索了。
是不是很简单,关键问题是检索数据的时候,如何能迅速定位到第三行数据,这里就用到哈希表了,所以,一个完整的倒排包括两部分,一部分是上面的这个表,第二个是一个哈希表,通过这个哈希表能知道数据这个词的下标为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主要实现了上述步骤