用Golang写一个搜索引擎 (0x01)--- 基本概念

第零部分我们已经列了一个提纲了,这一篇文章开始要详细说说了。

搜索引擎基本概念

在说搜索引擎架构分层之前,我们先确定几个搜索引擎的概念。

  • 文档,搜索引擎的基本数据单元,比如一张网页,一个商品,多个文档合在一起就是一个搜索引擎的完整数据
  • 倒排索引正排索引,存储在搜索引擎内部的数据结构,也是搜索引擎最底层的数据结构。
  • 索引器,将文档数据生成可供搜索的倒排索引正排索引的程序就是索引器。
  • 检索器,通过对倒排索引正排索引进行查找,从而查找到文档的程序。
  • 字段,每个文档可能有多个字段,比如一篇文章有标题,作者,摘要,详情,发布时间的,这些东西虽然在一个文档中,但是搜索的时候需要区别对待。
  • 索引,多个文档通过索引器生成了一堆倒排正排索引,我们把这些倒排正排索引的集合索引,如果后面提到索引就是指正排和倒排索引的集合,索引也可以理解为数据库中的表

好了,上面就是搜索引擎的最基本的概念,简单的说就是索引器吧文档变成倒排正排文件,然后检索器通过倒排正排文件还原文档的过程。

搜索引擎设计分层

数据库其实也是一个搜索引擎,只是数据库和搜索引擎的侧重点不太一样,搜索引擎追求的是简单,速度快,而数据库追求的是稳定和复杂逻辑对数据的处理,所以应用场景不太一样。

既然知道了一个搜索引擎的基本概念,应该怎么来设计这个搜索引擎呢?

按照一般的软件设计逻辑,如果不是非常复杂的系统,要设计一个系统,首先要设计数据结构,然后把数据结构封装到各个算法和类中,然后将各个类组合起来就完成了,所以,我设计这个引擎,是基于以下几个层次来的。

  • 首先需要一个底层的数据层,用来存储倒排索引正排索引,每个字段都会建立相应的倒排和正排索引,这一部分应该有一系列相关的模块来实现;
  • 所有字段的倒排索引正排索引合起来就是整个数据文件,然后需要一些模块来对这些东西进行管理;
  • 然后由于在第一篇文章中我们说了希望索引器检索器都在这里,类似ElasticSearch的实现,所以也使用了分段的方式管理文档的索引,每到一定的条件下将索引刷新到磁盘或者将索引合并起来。
  • 我们还需要一个引擎的东西来管理多个索引,引擎负责复杂的查询策略和排序策略,这个引擎是可以更换和修改了,只需要实现标准接口就行,也可以自己实现来替换默认的引擎达到更多的功能,甚至你能自己写一个引擎,实现SQL查询。
  • 最后还需要一个和外界交互的层,我实现的是一个http服务器来和外部交互,交互的数据通过json来进行,这一层也可以重写成任何你需要的样子。

按照上面这些个模块,一个搜索引擎,在整体架构上大约分成以下几个层次

  • 首先,最底层的是数据模块层,负责引擎内所有的数据描述,对于搜索引擎来说,数据分为倒排索引正排索引,也叫逆向索引正向索引,为了方便,我们这统一叫倒排索引正排索引
  • 在这一层之上是字段层,每一个字段对应了一个正排索引和一个倒排索引(可选),因为有些字段只需要展示出来而不需要进行搜索是不需要倒排的。
  • 在字段层之前有个段的层来对这些字段进行管理,段有的在内存中,有的刷新到磁盘上了。
  • 段层之上就是索引模块层了,这一层对上提供一些基本的增加,删除,修改,查找的接口。
  • 索引模块层之上是引擎层,这一层实现具体的业务查找逻辑。
  • 最上面是一个网络层,负责和外界进行交互。

在实现的时候,为了尽量简单,每个模块基本上都是一个文件来实现的,用了Golang以后,代码写起来也自由起来了,只要清晰就行,所以整个引擎下来,代码量其实不是很大。

下面这个图就是整个代码的大框架图,后面我们会一个一个的来讲这些东西。

整体分层.png

通过这一篇文章,希望能对搜索引擎有个初步的了解了,后面我会一个一个模块一个一个技术点的来拆分一下这个搜索引擎。

接下来的文章会开始介绍搜索引擎的底层技术了,倒排索引【会花比较多精力来说倒排索引,毕竟这是核心的核心】,正排索引【这个简单,就是数组】,在介绍的时候会有几篇文章介绍实现倒排索引技术需要的一些算法和数据结构。

代码托管在github上,地址是https://github.com/wyh267/FalconEngine,代码还在不断更新中,目前代码量,去掉单元测试文件,大约是6500行,因为是想到哪写到哪,有些函数也没有用,所以还有优化空间,也希望大家提交你的patch,后面讲的时候可以对照代码看看。

代码结构如下,再说一遍,代码量不大,结构也非常简单,虽然我写的代码注释不多,但是没有使用任何高级功能,闭包都没有,直接看没任何难度。

代码结构.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 193,968评论 5 459
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 81,682评论 2 371
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 141,254评论 0 319
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,074评论 1 263
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 60,964评论 4 355
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,055评论 1 272
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,484评论 3 381
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,170评论 0 253
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,433评论 1 290
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,512评论 2 308
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,296评论 1 325
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,184评论 3 312
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,545评论 3 298
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,880评论 0 17
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,150评论 1 250
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,437评论 2 341
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 40,630评论 2 335

推荐阅读更多精彩内容