可能99%的同学没有做搜索引擎，但99%的同学一定实现过搜索功能。搜索，检索，这里面包括哪些技术性的东西，希望这篇文章能给大家一些启发。全网搜索引擎的结构和流程是怎样的？整个网络搜索引擎的宏观结构如上图所示。核心子系统主要分为三部分（粉色部分）：（1）蜘蛛爬虫系统；(2)search&index索引和查询索引系统，该系统主要分为两部分：一部分用于生成索引数据build_index，另一部分用于查询索引数据search_index(3)排名评分和排序系统；核心数据主要分为两部分（紫色部分）：网页库；index索引数据；全网搜索引擎的业务特点决定了这是一个“写”和“取”分离的系统。写作是如何实现的？系统组成：由spider和search&index两个系统完成。输入：网站管理员生成的互联网页面。输出：正向和反向索引数据。过程：如架构图中的1、2、3、4：（1）蜘蛛抓取互联网网页；（2）蜘蛛将互联网网页存储在网页库中（这对存储要求很高，几乎是“万维网”的整个镜像）；(3)build_index从web库中读取数据，完成分词；(4)build_index生成倒排索引；检索是如何实现的？系统组成：由search&index和rank两个系统完成。输入：用户的搜索词。输出：搜索结果的第一页排序。流程：如架构图中的a、b、c、d：(a)search_index获取用户的搜索词，完成分词；(b)search_index查询倒排索引，得到“字符匹配”网页，这是初步筛选的结果；(c)对初选结果进行排名和排序；站点搜索引擎的结构和流程是怎样的？以搜索一亿帖为例，其整体结构如下：本站搜索引擎的宏观架构如上图所示，对比搜索引擎整体的宏观架构network，区别只在写的地方：全网搜索需要蜘蛛被动抓取数据；站内搜索是内部系统生成的数据。比如“发布系统”会主动将生成的帖子推送到build_data系统；画外音：看似差别“不大”，但架构实现难度却大相径庭。全网搜索怎么样”实时找到“全量”的网页是非常困难的，但是通过站内搜索很容易实时得到所有的数据。对于蜘蛛的三个系统，search&index和rank：spider和search&index是相对工程化的系统；rank是与业务和策略、算法密切相关的系统，搜索体验的主要区别在于业务和策略的优化，需要时间去积累是的，这里的启示是：谷歌的体验比百度好，原因是前者的排名太强了，国内的互联网公司（比如360）很难在短时间内打造出超越百度体验的搜索引擎的时间，真的很费时间，积累前面的内容太宏观了，为了照顾大部分没做过搜索引擎的同学，数据结构和算法部分从正向索引开始和倒排索引。什么是远期指数？简而言之，通过键查询实体的过程使用正向索引。比如user表：t_user(uid,name,passwd,age,sex)就是按uid查询整行的过程，马上就在进行索引查询。再比如网页库：t_web_page(url,page_content)就是通过url查询整个网页的过程，也属于正向索引查询。网页内容切分后，page_content会对应一个分词列表。简单的，正向索引可以理解为：Map>是一种数据结构，可以从网页url快速查找内容。画外音：时间复杂度可以考虑O(1)。什么是倒排索引？与正向索引相反，按项查询键的过程使用倒排索引。对于网页搜索，倒排索引可以理解为：Map>可以从查询词中快速找到包含查询词的网页的数据结构。画外音：时间复杂度也是O(1)。例如假设有3个网页：url1->“我爱北京”url2->“我爱道家”url3->“道家很美”这是一个正向索引：Map分词后：url1->{我，爱，北京}url2->{我，爱，家}url3->{家，美丽}这是分词后的正向索引：Map>分词后倒排索引：我->{url1,url2}爱情->{url1,url2}北京->{url1}首页->{url2,url3}美丽->{url3}通过搜索快速找到包含查询词的网页worditemMap>是倒排索引。画外音：明白了，word到url的过程就是一个倒排索引。正向索引和倒排索引是spider和build_index系统预先建立的数据结构。之所以使用这两种数据结构，是因为它们可以快速实现“用户网页检索”的需求。画外音中，业务需求决定了架构的实现，查询速度非常快。检索过程是怎样的？假设搜索词是“我爱”：分词，“我爱”会被分词成{我，爱}，时间复杂度为O(1)；对包含此项的网页列表进行索引时，时间复杂度也是O(1)：找到列表的交集就是匹配所有查询词的结果网页。对于这个例子，{url1,url2}是最终的查询结果；I->{url1,url2}love->{url1,url2}画外音：搜索过程也很简单：分词，查找倒排索引，找到结果集的交集。结束了吗？其实不然，分词和倒排查询的时间复杂度是O(1)。整个查找的时间复杂度取决于“求列表的交集”，问题转化为求两个集合的交集。字符类型的url不利于存储和计算。一般来说，每个url将由一个数字url_id标识。为了描述方便，将列表替换为列表。如何找到list1和list2的交集？（1）方案一：for*for，native方法，时间复杂度O(n*n)每个搜索词命中的页面很多，O(n*n)的复杂度显然不能接受。倒排索引可以在创建之初进行排序和预处理。将问题转化为两个有序列表来寻找交集就方便多了。画外音：更笨的方式。(2)方案二：求有序列表的交集，zipper方法有序集1{1,3,5,7,8,9}有序集2{2,3,4,5,6,7}两个指针指向第一个元素，比较元素的大小：如果相同，则放入结果集中，随意移动一个指针；否则，移动一个值较小的指针，直到队列结束；这种方法的优点是：集合中的元素最多比较一次，时间复杂度为O(n)；可同时进行多个有序集合，适用于多个分词项查找url_id的交集；这种方法好比拉链的两个齿轮，一对一比较好比拉链，所以称为拉链法；画外音：倒排索引提前初始化，可以使用“有序”特性。(3)方案三：桶并行优化当数据量较大时，url_id桶水平切分+并行操作是常用的优化方式。如果list1和list2可以分成几个桶区间，每个区间使用多线程并行交集，将每个线程的结果集并集，作为最终的结果集，可以大大减少执行时间。示例：有序集1{1,3,5,7,8,9,10,30,50,70,80,90}有序集2{2,3,4,5,6,7,20,30,40,50,60,70}求交集，先进行分桶：分桶1的范围为[1,9]分桶2的范围为[10,100]分桶3的范围为[101,max_int]然后:集合1被拆分为集合a{1,3,5,7,8,9}集合b{10,30,50,70,80,90}集合c{}集合2被拆分为集合d{2,3,4,5,6,7}sete{20,30,40,50,60,70}sete{}每个桶中的数据量大大减少，每个桶中没有重复的元素，可以使用多线程并行计算：桶1中集合a和集合d的交集在x{3,5,7}桶2中集合b和集合e的交集在y{30,50,70}bucket3集合c与集合d的交集为z{}最后，集合1与集合2的交集为x,y,z的并集，即集合{3,5,7,30,50,70}。画外音：多线程和水平切分是常用的优化方式。(4)方案四：再次优化Bitmap。数据横向分桶后，每个桶中的数据必须在一定范围内。如果集合满足这个特性，就可以用位图来表示集合：如上图所示，假设set1{1,3,5,7,8,9}和set2{2,3,4的所有元素，5,6,7}都在bucket取值范围内[1,16]，16可以用bit来描述这两个集合，原集合中的元素x，这个16bitmap中的第x位为1，在这次对两个位图进行交集，只需要对两个位图进行“与”运算，结果集位图的第3、5、7位为1，表示原集的交集为{3,5,7}。经过水平分桶和位图优化后，交集的效率可以大大提高，但时间复杂度仍然是O(n)。位图需要大量的连续空间，占用大量内存。画外音：位图可以表示一个集合，用它来求集合的交集非常快。(5)方案五：跳表skiplist是最常用的一种数据结构，用于查找有序链表集合的交集。它可以降低从O(n)到接近O(log(n))找到有序集的交集的复杂性。Set1{1,2,3,4,20,21,22,23,50,60,70}Set2{50,70}需要交集，如果用zipper方法，会发现1,2,3,4,20,21,22,23都要遍历一次，每个元素都要比较，时间复杂度为O(n)。每次比较都能“跳过一些元素”吗？出现跳表A：set1{1,2,3,4,20,21,22,23,50,60,70}创建跳表时，只有三个元素{1,20,50}在第一层，第二层和普通链表一样。Collection2{50,70}由于元素较少，只有一级普通链表。这样，在实现“拉链”找交集的过程中，set1的指针可以从1跳到20再跳到50，中间可以跳过很多元素，不需要比较逐个。跳表找交点的时间比较复杂。度数约为O(log(n))，这是搜索引擎中常用的算法。小结：(1)整个网络搜索引擎系统由三个子系统组成：spider、search&index、rank；(2)全站搜索引擎与全网搜索引擎的区别在于少了一个蜘蛛子系统；(3)蜘蛛和搜索索引系统是两个工程系统，但是排名系统的优化需要长时间的调优和积累；(4)正向索引是通过网页的url_id分词后快速找到网页内容列表的过程；(5)反向倒排索引是通过分词项快速找到包含该分词的网页列表的过程；(6)用户检索的过程是先分词，然后找到每一项对应的list，最后设置求交集的过程；(7)求有序集合交集的方法有：双for循环法，时间复杂度O(n*n)拉链法，时间复杂度O(n)水平分桶，多线程并行位图，大大提高并行度，时间复杂度O(n)跳表，时间复杂度O(log(n))画外音：面试应该够了。大部分工程师可能没有接触过“搜索核心”，但互联网业务基本都会涉及到“检索”功能。还是以58同城的邮政业务场景为例。帖子的标题和帖子的内容有很强的用户检索需求。在业务、流量、并发量逐渐增加的各个阶段，检索需求应该如何实现？原始阶段-LIKE在创业阶段，经常使用这种方法来快速变现。数据在数据库中可能是这样存储的：t_tiezi(tid,title,content)满足标题和内容检索需求可以通过LIKE:selecttidfromt_tieziwherecontentlike'%Tiantongyuan%'这种方式确实可以快速满足业务需求，现有的问题也很明显：效率低，每次都需要全表扫描，计算量大，并发高的时候容易100%cpu；不支持分词；起步阶段——如何快速提高全文索引效率，支持分词，尽可能影响原有系统架构小，我第一个想到的是建立全文索引：altertablet_tieziaddfulltext(title,content）使用match和against实现对索引字段的查询需求。全文索引可以快速实现业务的分词需求，快速提升性能（分词后倒转，至少不用全表扫描），但也存在一些问题：只适用于MyISAM；由于全文索引利用了数据库的特性，检索需求和普通CURD需求在数据库中耦合在一起：当检索需求较大时，可能会影响CURD请求；当CURD并发量大时，检索会很慢；如果数据量达到百万级，性能还是会明显下降，查询返回时间会非常快。漫长的、不可接受的业务；横向扩展相对困难；中间阶段——开源外部索引为了解决全文索引的局限性，当数据量增加到几百万或几千万时，就必须考虑外部索引。外部索引的核心思想是：索引数据与原始数据分离。前者满足搜索要求，后者满足CURD要求。通过一定的机制（双写、通知、周期重构）来保证数据的一致性。原来的数据可以继续使用Mysql存储。如何实现外部索引？Solr、Lucene、ES都是常见的开源解决方案。其中ES（ElasticSearch）是目前最流行的。Lucene虽然好，但潜在的缺点是：Lucene只是一个库，需要自己做服务，实现高可用/可扩展性/负载均衡等复杂特性；Lucene只支持Java，如果要支持其他语言，就得自己做服务了；Lucene并不友好，很致命，也很复杂。用户往往需要深入了解搜索知识才能理解其工作原理。为了屏蔽它的复杂性，他们还是要做自己的服务；为了改进Lucene的各种不足，解决的方案都是“用友好的接口封装一个服务，屏蔽底层的复杂性”，于是就有了ES：ES是一个以Lucene为核心的服务，实现搜索功能，提供一个REStful接口；ES可以支持大量数据的信息存储，支持极高并发的搜索请求；ES支持集群，为用户屏蔽高可用/可扩展/负载均衡等复杂特性；目前，快狗打车以ES为核心搜索服务，满足业务中的各种搜索需求，其中：数据量最大的是“接口耗时数据采集”，数据量约10亿条；最大并发“经纬度地理位置搜索”需求，平均在线并发量2000左右，压测数据并发8000左右；因此，ES完全可以满足常见的10亿数据量、5k吞吐量的搜索业务需求。高级阶段——自主研发搜索引擎当数据量进一步增加，达到10亿或100亿时；并发量也进一步提升，达到每秒10万的吞吐量；而当业务个性逐渐增加时，就需要一个自研的搜索引擎了，搜索内核已经定制化了。定制自研搜索引擎阶段，设计侧重于大数据量、高并发。为了满足“无限容量、无限并发”的需求，架构设计需要关注“可扩展性”，力求：增加可扩展的机器数量（数据量+并发）。58同城自研搜索引擎易搜的初步架构图如下：(1)上层代理（粉色）接入集群，作为对外入口，接受搜索请求。它的无状态性保证了代理集群的性能可以通过增加机器来扩展；（2）中层合并（淡蓝色）是一个逻辑集群，主要用于搜索合并，打分排序。业务相关的rank在这一层实现，其无状态性也可以保证合并后可以通过增加机器来扩展Cluster的性能；(3)底层搜索器（深红色大框）是一个检索集群。服务和索引数据部署在同一台机器上。服务启动时，可以将索引数据加载到内存中，请求访问时从内存中加载数据。访问速度很快：为了满足数据容量的可扩展性，对索引数据进行水平切分，通过增加切分次数可以无限扩展性能。如上图所示，搜索者分为4组。数据是冗余的。理论上，增加更多的机器可以无限扩展性能。如上图所示，每组搜索者都有2个冗余副本。这种设计可以真正做到通过加机器实现更大的数据量和更高的响应。并发性。小结：为了满足搜索业务的需求，随着数据量和并发量的增长，搜索架构一般会经历几个阶段：原始阶段-LIKE；初级全文索引；中间阶段——开源外部索引；高级阶段——自主研发的搜索引擎；最后一个进阶话题，关于搜索的实时性：百度为什么能实时检索到15分钟前发布的新消息？为什么58同城可以实时检索1秒前发布的帖子？实时搜索引擎系统架构有哪些要点？为了保证搜索引擎在大数据量、高并发情况下的实时性，在架构设计上有两个关键点：索引分类；转储&合并；首先，在数据量非常大的情况下，为了保证倒排索引高效的检索效率，任何对数据的更新都不会实时修改索引。画外音：因为，一旦产生碎片，检索效率就会大大降低。既然索引数据不能实时修改，那么如何保证能索引到最新的网页呢？索引分为全库、日增量库、小时增量库。如上图：300亿条数据在全索引库中；1天内修改的1000万条数据在天库；1小时内修改的50万条数据在小时库中；当修改请求发生时，只操作最低级别的索引，例如小时库。当一个查询请求发生时，会同时查询各级索引，合并结果得到最新的数据：全库是紧密存储的索引，没有碎片，速度快；天空数据库存储严密，速度快；小时数据库数据量小，速度快；分层索引可以保证实时性。那么，一个新的问题就出现了，时库的数据什么时候才能体现到天库，天库的数据什么时候才能体现到全库呢？dump&merge,index导出和合并是通过这两个异步工具完成的：dumper：导出在线数据。合并：将离线数据合并到更高级别的索引中。计时库，每小时一次，并入日库；日库，每天一次，并入全库；这样可以保证时库和日库的数据量不会特别大；如果数据量和并发量较大，可以加入周库和月库进行缓冲。小结：超大数据量，超高并发，一个实时搜索引擎的两个架构点：索引分类；转储&合并；关于“搜索”和“检索”，GET是否获得了新技能？【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此查看该作者更多好文
