从零开始,写一个搜索引擎 (0x01)
第零部分我们已经列了一个提纲了,这一篇文章开始要详细说说了。
搜索引擎基本概念
检索器
,通过对倒排索引
和正排索引
进行查找,从而查找到文档
的程序。字段
,每个文档可能有多个字段,比如一篇文章有标题,作者,摘要,详情,发布时间的,这些东西虽然在一个文档
中,但是搜索的时候需要区别对待。索引
,多个文档
通过索引器
生成了一堆倒排正排索引,我们把这些倒排正排索引的集合叫索引
,如果后面提到索引
就是指正排和倒排索引的集合,索引也可以理解为数据库中的表。
好了,上面就是搜索引擎的最基本的概念,搜索引擎简单的说分成两部分,一部分就是索引器
把文档变成倒排
和正排
文件,第二部分就是检索器
通过倒排
和正排
文件还原文档
的过程。
搜索引擎设计分层
数据库其实也是一个搜索引擎,只是数据库和搜索引擎的侧重点不太一样,搜索引擎追求的是简单,速度快,而数据库追求的是稳定和复杂逻辑对数据的处理,所以应用场景不太一样。
既然知道了一个搜索引擎的基本概念,应该怎么来设计这个搜索引擎呢?
按照一般的软件设计逻辑,如果不是非常复杂的系统,要设计一个系统,首先要设计数据结构,然后把数据结构封装到各个算法和类中,然后将各个类组合起来就完成了,所以,我设计这个引擎,是基于以下几个层次来的。
首先需要一个底层的数据层,用来存储
倒排索引
和正排索引
,每个字段都会建立相应的倒排和正排索引,这一部分应该有一系列相关的模块来实现;所有字段的
倒排索引
和正排索引
合起来就是整个数据文件,然后需要一些模块来对这些东西进行管理;然后由于在第一篇文章中我们说了希望
索引器
和检索器
都在这里,类似ElasticSearch
的实现,所以也使用了分段的方式管理文档的索引
,每到一定的条件下将索引
刷新到磁盘或者将索引合并起来。我们还需要一个引擎的东西来管理多个
索引
,引擎负责复杂的查询策略和排序策略,这个引擎是可以更换和修改了,只需要实现标准接口就行,也可以自己实现来替换默认的引擎达到更多的功能,甚至你能自己写一个引擎,实现SQL查询。最后还需要一个和外界交互的层,我实现的是一个http服务器来和外部交互,交互的数据通过
json
来进行,这一层也可以重写成任何你需要的样子。
按照上面这些个模块,一个搜索引擎,在整体架构上大约分成以下几个层次
首先,最底层的是数据模块层,负责引擎内所有的数据描述,对于搜索引擎来说,数据分为
倒排索引
和正排索引
,也叫逆向索引
和正向索引
,为了方便,我们这统一叫倒排索引
和正排索引
。在这一层之上是字段层,每一个字段对应了一个正排索引和一个倒排索引(可选),因为有些字段只需要展示出来而不需要进行搜索是不需要倒排的。
在字段层之前有个段的层来对这些字段进行管理,段有的在内存中,有的刷新到磁盘上了。
索引模块层之上是引擎层,这一层实现具体的业务查找逻辑。
最上面是一个网络层,负责和外界进行交互。
在实现的时候,为了尽量简单,每个模块基本上都是一个文件来实现的,用了Golang
以后,代码写起来也自由起来了,只要清晰就行,所以整个引擎下来,代码量其实不是很大。
下面这个图就是整个代码的大框架图,后面我们会一个一个的来讲这些东西。
通过这一篇文章,希望能对搜索引擎有个初步的了解了,后面我会一个一个模块一个一个技术点的来拆分一下这个搜索引擎。
接下来的文章会开始介绍搜索引擎的底层技术了,倒排索引【会花比较多精力来说倒排索引,毕竟这是核心的核心】,正排索引【这个简单,就是数组】,在介绍的时候会有几篇文章介绍实现倒排索引技术需要的一些算法和数据结构。
代码托管在github
上,地址是https://github.com/wyh267/FalconEngine,代码还在不断更新中,目前代码量,去掉单元测试文件,大约是6000行,因为是想到哪写到哪,有些函数也没有用,所以还有优化空间,也希望大家提交你的patch,后面讲的时候可以对照代码看看。
代码结构如下,再说一遍,代码量不大,结构也非常简单,虽然我写的代码注释不多,但是没有使用任何高级功能,闭包都没有,直接看没任何难度。