不合理的需求，如何轻松应对？文章较长，建议提前收藏。可能99%的同学没有做搜索引擎，但99%的同学一定实现过搜索功能。搜索、检索，这里面包括哪些技术，希望这篇文章能给大家一些启发。需求一：想做一个全网搜索引擎，不复杂，类似百度，两个月能上线吗？全网搜索引擎的结构和流程是怎样的？全网搜索引擎的宏观架构如上图所示。核心子系统主要分为三部分（粉色部分）：（1）蜘蛛爬虫系统；(2)search&index索引和query索引系统。本系统主要分为两部分：一部分用于生成索引数据build_index，另一部分用于查询索引数据search_index(3)排名评分排序系统；核心数据主要分为两部分（紫色部分）：网页库；索引索引数据；由整个网络搜索引擎的业务特点决定的是的，这是一个“写”和“取”的独立系统。写作是如何实现的？系统组成：由spider和search&index两个系统完成。输入：网站管理员生成的互联网页面。输出：正向和反向索引数据。流程：如架构图中的1、2、3、4：蜘蛛抓取互联网网页；spider将Internet网页存储在网页库中（这对存储要求很高，几乎要存储整个“万维网”图片）；build_index从web库中读取数据，完成分词；build_index生成倒排索引；检索是如何实现的？系统组成：由search&index和rank两个系统完成。输入：用户的搜索词。输出：搜索结果的第一页排序。流程：如架构图中的a、b、c、d：search_index获取用户的搜索词，完成分词；search_index查询倒排索引得到“字符匹配”网页，即初筛结果；rank是对初筛结果进行打分排序；rank返回排序后的第一页结果；站点搜索引擎的结构和流程是怎样的？毕竟做在线搜索的公司只是少数，大多数公司想要实现的只是站内搜索。以搜索同城100亿帖为例，整体结构如下：与互联网搜索引擎的宏观架构相比，区别仅在于写的地方：全网搜索需要蜘蛛被动地获取数据；站内搜索是内部系统生成的数据，比如“发布系统”会主动将生成的帖子推送到build_data系统；画外音：看似“小”的差异，架构实现难度却差了很多。全网搜索很难“实时”找到“全量”的网页，但通过站内搜索，实时获取所有数据却很容易。对于spider、search&index、rank这三个系统：(1)spider和search&index是工程系统；(2)rank是一个与业务和策略、算法密切相关的系统。搜索体验的差异主要在于此，而业务和策略的优化需要时间积累，这里的启示是：谷歌的体验优于百度。原因是前者的等级很强。国内的互联网公司（比如360）很难在短时间内打造出体验超越百度的搜索引擎。真的需要时间去积累。前面的内容太宏观了。为了照顾大部分没做过搜索引擎的同学，数据结构和算法部分从正向索引和倒排索引开始。什么是远期指数？简而言之，通过键查询实体的过程使用正索引。比如user表：t_user(uid,name,passwd,age,sex)通过uid查询整行的过程就是正向索引查询。再比如网页库：t_web_page(url,page_content)就是通过url查询整个网页的过程，也属于正向索引查询。网页内容分词后，page_content会对应一个分词集合list- 。简单的，正向索引可以理解为：Map>是一种数据结构，可以从网页url快速查找内容。画外音：时间复杂度可以考虑O(1)。什么是倒排索引？与正向索引相反，按项查询键的过程使用倒排索引。对于网页搜索，倒排索引可以理解为：Map>可以从查询词中快速找到包含查询词的网页的数据结构。画外音：时间复杂度也是O(1)。比如假设有3个网页：url1->“我爱北京”url2->“我爱道家”url3->“道家很美”这是一个正向索引：Map经过分词后：url1->{我，爱，北京}url2->{我，爱，家}url3->{到家，美丽}这是分词后的正向索引：Map>倒排后分词分割指数：我->{url1,url2}爱情->{url1,url2}北京->{url1}首页->{url2,url3}美丽->{url3}使用搜索词项快速找到网页包含查询词的Map>是倒排索引。画外音：明白了，word到url的过程就是一个倒排索引。正向索引和倒排索引是spider和build_index系统预先建立的数据结构。之所以使用这两种数据结构，是因为它们可以快速实现“用户网页检索”的需求。画外音中，业务需求决定了架构的实现，查询速度非常快。检索过程是怎样的？假设搜索词是“我爱”：(1)分词，将“我爱”分词为{我，爱}，时间复杂度为O(1)；(2)每次分词后的item，从倒排索引中查询包含该item的网页list，时间复杂度也是O(1)：I->{url1,url2}Love->{url1,url2}(3)查找list的交集，即满足所有查询词的结果页面。对于这个例子，{url1,url2}是最终的查询结果；画外音：检索过程也很简单：分词，查找倒排索引，找到结果集的交集。结束了吗？事实上，分词和倒排查询的时间复杂度都是O(1)。整个搜索的时间复杂度取决于“求list的交集”，问题转化为求两个集合的交集。字符类型的url不利于存储和计算。一般来说，每个url将由一个数字url_id标识。为了后面描述方便，list统一替换为list。如何找到list1和list2的交集？方案一：for*for，native方法，时间复杂度O(n*n)每个搜索词命中的网页很多，O(n*n)的复杂度显然不能接受。倒排索引可以在创建之初进行排序和预处理。将问题转化为两个有序列表来寻找交集就方便多了。画外音：更笨的方式。解法二：求有序列表的交集，zipper方法有序集1{1,3,5,7,8,9}有序集2{2,3,4,5,6,7}两个指针指向第一个元素，比较元素的大小：如果相同，则放入结果集中，随意移动一个指针；否则，移动一个值较小的指针，直到队列结束；这种方法的优点是：集合中的元素最多比较一次，时间复杂度为O(n)；可同时进行多个有序集合，适用于多个分词项查找url_id的交集；这种方法好比拉链的两个齿轮，一对一比较好比拉链，所以称为拉链法；画外音：倒排索引提前初始化，可以使用“有序”特性。方案三：bucket并行优化当数据量很大时，url_idbucket水平切分+并行操作是一种常见的优化方式。如果list1和list2可以分成几个bucket区间，每个区间使用多线程并行相交，将每个线程的结果集并集，作为最终的结果集，可以大大减少执行时间。示例：有序集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}求交集，先把桶分成split：桶1的范围是[1,9]桶2的范围是[10,100]桶3的范围是[101,max_int]因此，set1被拆分为：seta{1,3,5,7,8,9}setb{10,30,50,70,80,90}setc{}set2被拆分为：setd{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}桶3中集合c与集合d的交集为z{}最后集合1与集合2的交集为x,y,z的并集，即集合{3,5,7,30,50,70}。画外音：多线程和水平切分是常用的优化方式。方案四：Bitmap再次优化数据。经过水平分桶和拆分后，每个桶中的数据必须在一定范围内。如果集合满足这个特性，就可以用位图来表示集合：如上图所示，假设set1{1,3,5,7,8,9}和set2{2,3,4的所有元素，5,6,7}都在bucket值[1,16]的范围内，可以用16位来描述这两个集合，原集合中的元素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)。每次比较都能“跳过一些元素”吗？跳表出现：集合1{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)正向索引(forwardindex)是通过网页url_id快速找到分词后的网页内容列表
- 的过程；(5)倒排索引(invertedindex)是通过分词项快速找到包含该词的网页列表的过程；(6)用户检索的过程是先分词，然后找到每个item对应的list，最后进行集合交集的过程；(7)有序集交集的方法有：双for循环法，时间复杂度O(n*n)拉链法，时间复杂度O(n)水平分桶，多线程并行位图，大大提高了运算的并行性，时间复杂度O(n)跳表，时间复杂度O(log(n))需求2：想做一个内容检索功能，不复杂，100亿条数据，每秒只有10万条查询，两周能上线吗？大部分工程师可能没有接触过“搜索核心”，但互联网业务基本都会涉及到“检索”功能。以同城发帖业务场景为例，发帖标题和发帖内容都有很强的用户检索需求。在业务、流量、并发量增长的各个阶段，检索需求应该如何实现？在原始阶段-LIKE创业阶段，往往采用这种方式来实现快速落地。数据在数据库中可能是这样存储的：t_tiezi(tid,title,content)满足标题和内容检索需求可以通过LIKE实现：selecttidfromt_tieziwherecontentlike'%Tiantongyuan%'这个方法确实可以很快满足业务需求，存在的问题也很明显：效率低，每次都需要全表扫描，计算量大，并发高时cpu容易100%；不支持分词；初级阶段——如何快速提高全文索引效率，支持分词，对系统架构的影响尽可能小。首先想到的是建立全文索引：altertablet_tieziaddfulltext(title,content)使用match和against实现对索引字段的查询需求。全文索引可以快速实现业务的分词需求，快速提升性能（分词后倒转，至少不用全表扫描），但也存在一些问题：只适用于MyISAM；由于全文索引利用了数据库的特性，搜索需求和普通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万的吞吐量；而当业务个性逐渐增加时，就需要一个自研的搜索引擎了，搜索内核已经定制化了。定制自研搜索引擎阶段，设计侧重于大数据量、高并发。为了满足“无限容量、无限并发”的需求，架构设计需要关注“可扩展性”，力求：增加可扩展的机器数量（数据量+并发）。同城自研搜索引擎易搜初步架构图如下：（1）上层代理（粉色）接入集群，作为对外入口，接受搜索请求。它的无状态性保证了代理集群的性能可以通过增加机器来扩展；(2)中层合并（淡蓝色）是一个逻辑簇，主要用于查找合并，打分排序。业务相关的行列在这一层实现，其无状态性也可以保证合并集群可以通过增加机器来扩展性能；(3)底层搜索器（深红色大框）是一个检索集群。服务和索引数据部署在同一台机器上。服务启动时，可以将索引数据加载到内存中，请求访问时从内存中加载数据。访问速度非常快。快速：为了满足数据容量的扩展性，索引数据被水平拆分，通过增加拆分次数可以无限扩展性能。如上图所示，搜索者分为4组。进行冗余。理论上，增加更多的机器可以无限扩展性能。如上图所示，每组搜索器都有2个冗余副本。这种设计可以真正实现更多的数据量和更高的响应更多的机器。并发。小结：为了满足搜索业务的需求，随着数据量和并发量的增长，搜索架构一般会经历几个阶段：原始阶段——LIKE；初级阶段——全文索引；中间阶段——开源外部索引；高级阶段——自主研发的搜索引擎；需求三：检索的时效性对用户体验非常重要。需要检索5分钟前的新闻和1秒前发布的帖子。是不是很复杂？最后一个进阶话题是关于搜索的实时性：百度为什么能实时检索到5分钟前的新闻？为什么同城可以实时检索1秒前发布的帖子？实时搜索引擎系统架构的要点有哪些？为了保证搜索引擎在大数据量、高并发情况下的实时性，架构设计的两个关键点：索引分类；转储&合并；首先，在数据量非常大的情况下，为了保证倒排索引高效的检索效率，对数据的任何更新都不会实时修改索引。画外音：因为，一旦产生碎片，检索效率就会大大降低。既然索引数据不能实时修改，那么如何保证能索引到最新的网页呢？指标分类，分为全库、日增库、时增库。如上图所示：全索引库有300亿条数据；一天内修改的1000万条数据在当天数据库中；一小时内修改的50万条数据在小时库中；当修改请求发生时，只操作最低级别的索引，例如小时库。当一个查询请求发生时，会同时查询各级索引，合并结果得到最新的数据：全库是紧凑存储的索引，没有碎片，速度快；天空数据库存储严密，速度快；每小时数据库数据量小，速度快；层次索引可以保证实时性，那么新的问题又来了，时库的数据什么时候反映到天库，天库的数据什么时候反映到全库？dump&merge，索引导出和合并，是由这两个异步工具完成的：dumper：导出在线数据。合并：将离线数据合并到更高级别的索引中。计时库，每小时一次，并入日库；日库，每天一次，并入全库；这样可以保证时库和日库的数据量不会特别大；如果数据量和并发量较大，可以加入周库和月库进行缓冲。简单总结：超大数据量，超高并发，一个实时搜索引擎的两个架构点：索引分类；转储&合并；能否满足“搜索”和“检索”的需求？
