搜索引擎的缓存机制-以淘宝为例 ip
在淘宝搜索系统中中，搜索结果页的缓存(Cache)是对搜索“效率”贡献最大的设计。由于缓存中的搜索结果页都是前人查询的结果，因此用户的查询请求如果在缓存中命中(和前人的查询相同)，则查询系统直接把缓存中存放的搜索结果页返回给用户。 用户在使用淘宝搜索引擎进行检索时，查询词可能千差万别。但是如果从大量用户的查询统计上看，总会有一些词汇经常被查询，有些词汇却很少被查询。 (1)前20%的查询词的查询次数约占了总查询次数的80%。 (2)查询具有稳定性，查过的词很可能在不久的将来还会被查询。 搜索结果缓存的实现方法和操作系统中提到的LRU算法基本一致，我们大致回顾一下LRU缓存置换算法。 熟悉网页库设计的读者都应该知道，对搜索结果页的缓存库必须能够支持随机访问，这一点很重要。如何支持这种随机访问其内部原理和数据库设计很相似，这里不再展开，有兴趣的读者可以参考B+树等这类能够支持随机访问的索引方式。 有了搜索结果页缓存的设计，淘宝搜索引擎查询层就能够大大降低重复的计算量，提高同时响应用户检索请求的能力。具有搜索结果页缓存功能支持的查询系统如图1所示。
增加了缓存功能后，淘宝查询系统可以较少执行实际的查询计算，而采用重用缓存中保存的历史相同的查询结果网页的方法来大大提高查询效率。目前的技术能够达到在缓存中命中99%的查询，因此用户实际的查询绝大多数情况都是取自缓存的搜索结果页，这就是搜索引擎为什么能够如此快速地返回查询结果的一个重要原因。 也许是由于搜索结果页缓存的出色设计，在“效率”和“效果”之间的竞争上，“效率”占据了优势。因此近年来，淘宝查询系统的研究方向主要在“效果”上，而“效果”的追求还需要推测用户的查询意图。如果能正确地推测出用户的查询意图，那么对效果的改善可以说是非常有利的。接下来我们就详细讲解淘宝搜索引擎的缓存机制和原理。 缓存(Cache)是目前所有搜索引擎都会采用的技术。所谓缓存，就是在高速内存硬件设备内开辟一块数据存储区，用来容纳常见的用户查询及搜索结果(或者索引数据及搜索的中间结果)，同时采取一定的管理策略来维护存储区内的数据。当搜索引擎接收到用户查询请求时，首先在缓存系统里查找，如果能够找到则直接返回搜索结果，否则采取正常的搜索流程来返回搜索结果。为何搜索引擎要引入缓存机制?一则使用缓存系统能够加快用户查询响应的速度;另外还可以有效地减少搜索引擎后台计算量，节省计算资源。 对于一个正常的搜索流程，比如用户输入查询请求“夏季 连衣裙”，淘宝搜索引擎需要分别将存储在磁盘上的两个单词的倒排索引读入内存，之后进行解压缩，然后求两个单词对应倒排列表的交集，找到所有包含两个单词的文档集合，根据排序算法来对每个文档的相关性进行打分，按照相关度输出相关度最高的搜索结果。 以上这个流程涉及了磁盘读/写、内存运算等一系列操作，相对比较耗费时间和计算资源。如果将本次搜索结果存储在缓存中，下次遇到相同的查询请求，则可以直接将搜索结果返回，不需要经过上述的复杂流程进行计算。缓存一般用最快的内存设备进行存储，所以响应速度非常快，同时也省略了相当多的磁盘读取和计算步骤，有效地节省了计算资源。 以上搜索加速行为能够成立，其实隐含了一个假设，即：相同的用户查询会反复出现。只有这个假设成立，才能够利用以上措施来加快搜索速度，但是问题是这个假设成立吗? 这涉及用户查询分布本身具有的特点。我们先看下用户搜索请求行为有哪些特点。目前有很多研究集中在分析用户搜索行为，通过对搜索日志的分析，可以得出如下结论。 1、至少63.5%的搜索引擎用户只看搜索结果第1页的内容；大约11.7%的搜索引擎用户会翻看搜索结果第2页内容；至少79%的搜索引擎用户只查看搜索结果前3页的内容。 2、用户发出的查询请求分布符合逆Power-Law规则，即少数查询占了查询总数的相当比例，而大多数查询出现次数非常少。在十亿规模的搜索日志记录中，63.7%的用户查询只出现过一次，而热门查询占搜索请求总数的比例非常高，最热门的25个用户搜索请求占了用户查询请求总数的1.2%一1.5%；同时，用户查询有很大比例的重复性，大约有30%-40%的用户查询是重复查询。 3、用户查询请求具备时间局部性，即大多数重复的用户查询会在较短的间隔时间被再次重复访问。 通过上面的调查结论，可以看出在一定的时间间隔内，发送到搜索引擎的用户查询有相当比例的重复性，而缓存机制之所以能够运用在搜索引擎里来加快系统响应速度，与这一点是密不可分的。
一、淘宝搜索引擎缓存系统架构 图2是淘宝搜索引擎缓存系统架构示意图，当淘宝搜索引擎接收到用户查询的时候，会首先在缓存系统查找，看缓存内是否包含用户查询的搜索结果，如果发现缓存已经存储了相同查询的搜索结果，则从缓存内读出结果展现给用户；如果缓存内没有找到相同的用户查询，则将用户查询按照常规处理方式交由淘宝搜索引擎返回结果，并将这条用户查询的搜索结果及中间数据根据一定策略调入缓存中，这样下次遇到同样的查询可以直接在缓存中读取，以加快用户响应速度并减少淘宝搜索引擎系统的计算负载。 淘宝缓存系统包含两个部分，即缓存存储区及缓存管理策略。缓存存储区是高速内存中的一种数据结构，可以存放某个查询对应的搜索结果，也可以存放搜索中间结果，比如一个查询单词的倒排列表。 缓存管理策略又包含两个子系统，即缓存淘汰策略和缓存更新策略。 之所以需要缓存淘汰策略，是因为不论给缓存分配多大空间，当系统运行到一定程度，很可能缓存已经满了，当有新的需要缓存的内容要进入缓存时，需要根据一定的策略，从缓存中剔除一部分优先级别较低的缓存内容，以腾出空间供后续内容放入缓存存储区，如何选择替换项目是缓存淘汰策略需要考虑的问题。 另外，使用缓存系统是有一定风险存在的，即缓存内容和索引内容不一致问题。如果淘宝搜索引擎索引的文档集合是静态文档，这个问题是不存在的，因为既然文档集合没有发生任何变化，只要搜索引擎的排序算法不更改，那么针对固定的用户查询，其对应的搜索结果是固定不变的，所以缓存里面的内容永不过期。
但是在一般应用场景中，搜索引擎要处理的文档集合是动态变化的，可能会面临新加入的文档，也可能会删除旧的文档或者旧的文档内容发生了变化。当索引己经反映了这种变化，而缓存数据没有随着索引做出相应的变化，那么就会发生缓存内容和索引内容不一致的问题。缓存更新策略就是用来维持两者一致性的。 对淘宝搜索引缓存系统来说，一个优秀的缓存系统，希望能够在以下儿个方面表现出色。 1、最大化缓存命中率 所谓缓存的命中率，就是说一段时间内所有用户发出的查询中，有多大比例的查询对应的搜索结果是从缓存中获得的。这个比例越高，说明缓存管理策略越成功，就有效地节省了淘宝搜索引擎的计算成本。具体而言，不同的缓存淘汰策略就是采用不同算法来获得尽可能高的命中率。 2、缓存内容与索引内容保持一致性 好的缓存管理策略应该避免出现缓存内容与索引内容不一致的状况，因为这种不一致会影响用户的搜索体验，所以缓存系统需要有优秀的缓存更新策略来达到这个目的。
二、缓存对象 对于搜索引擎缓存，在存储区内存放的数据对象并不是唯一的，可以是搜索结果，也可以是某个查询词汇对应的倒排列表，或者是一些搜索的中间结果。 最常见的缓存对象类型是用户查询请求所对应的搜索结果信息，比如宝贝的标题、宝贝URL等。图3给出了将搜索结果作为缓存内容的示例，缓存里保存了“连衣裙" ,“运动鞋”等用户查询，以及其对应的搜索结果。如果此时有另外一个用户愉入“连衣裙”作为查询，则淘宝搜索引擎首先在缓存里面查找，发现己经存在这个用户查询项，则直接提取原先的搜索结果作为输出返回给用户。
另外一种比较常见的存储对象类型是查询词汇对应的倒排列表(Posting List)。图4是以单词倒排列表作为缓存内容的一个示例图，从图中可以看出，以搜索结果作为缓存内容的情况下，用户查询即使包含多个单词，也是作为一个整体存储在缓存槽里的；而以单词倒排列表作为缓存内容的方式，其存储粒度相对会小些，是以用户查询的分词结果存储在缓存槽里的。比如“夏季 连衣裙”这个用户查询，在搜索结果作为缓存内容情形下占用一项缓存槽，而在缓存倒排列表方式下会占用两个缓存槽,“夏季”和“连衣裙”各自占用一个存储位置。
这两种不同的缓存存储内容各自有其优缺点，对于搜索结果型缓存来说，其用户查询响应速度非常快，因为只需要进行查找运算即可返回结果，但是其粒度比较粗，比如在如图3所示的例子中，如果此时用户输入查询“连衣裙 韩版”，则淘宝搜索引擎会发现缓存里面并不存在这个查询，只能按照正常搜索流程，去调用索引数据并进行网页排序等运算。但是倒排列表型缓存因为粒度较小，会发现“连衣裙”这个查询词汇已经在缓存中了，此时只需要从存储在硬盘的倒排索引中读取“韩版”这个词汇的倒排列表数据，然后进行排序运算即可返回结果。由这个例子可以看出，倒排列表型缓存粒度小，所以命中率高，但是因为保存的只是倒排列表这种中间数据，所以仍然需要进行后续的计算才能返回最终结果，在用户响应效率方面慢于搜索结果型缓存。而搜索结果型缓存粒度大，如果在缓存内命中用户查询，则很快给出最终结果，但是命中率要低于倒排列表型缓存。 另外，搜索结果型缓存因为征个搜索结果的大小是可以预估的(一般取前列的K个搜索结果)，所以管理起来比较简单，而倒排列表型缓存需要缓存某个单词的倒排列表，而不同单词的倒排列表大小差异很大，如果遇到一个非常大的倒排列表，可能会对目前的缓存空间造成较大影响，甚至被迫移出经常使用的用户查询缓存项，所以如何管理倒排列表型缓存存储区相对而言比较复杂。 以上两种缓存对象是比较常见的缓存类型，还有一种不太经常使用的方式，即保留两个经常搭配出现单词的倒排列表的交集，以这种中间结果形式作为缓存内容。因为用户查询有很大比例是由2个或者3个单词组成的，对于多词构成的用户查询，搜索引擎在从硬盘读出每个词汇的倒排列表后，需要进行文档队列的交集运算。而如果能够事先将这些交集运算的计算结果缓存起来，则可以避免后续的交集运算，提高搜索系统返回结果的速度。但是这种词汇组合的数据量非常大，都放置到内存中往往很困难，所以一般这种中间结果会存储在磁盘上。这种类型的缓存不能单独使用，但是可以作为多级缓存中的一个缓存级别存在，对其他类型的缓存起到补充作用。
三、缓存结构 搜索引擎缓存的结构设计可以有多种选择，最常见的是单级缓存，也可以设计为二级甚至是三级缓存结构。 单级缓存是一种最常见也最简单直接的缓存结构，缓存系统中只包含一个单一缓存，配以缓存管理策略构成了整个缓存系统。图5左方和右方分别是搜索结果型和倒排列表型单级缓存示意图。 尽管单级缓存只包含一级缓存，但是对于不同缓存对象类型来说，其内部处理流程有一定差异。搜索结果型缓存首先在缓存中查找是否包含用户查询，如果存在则直接将搜索结果返回，否则对用户查询进行处理，由搜索系统返回搜索结果并加入缓存中，之后将搜索结果返回给用户。对于倒排列表型缓存，其处理步骤正好相反，查询处理阶段首先将用户查询分词，之后在缓存中查找这些单词对应的倒排列表，如果所有单词的倒排列表都在缓存中，则由查询处理模块根据单词倒排列表对搜索结果进行排序，并将搜索结果返回给用户。如果发现某些单词的倒排列表不在缓存中，会首先从磁盘读入单词对应的倒排列表，将其放入缓存，之后讲行查询处理步骤。 二级缓存结构由两级缓存串联构成，第1级缓存是搜索结果型缓存，第2级缓存是倒排列表型缓存，图6是二级缓存示意图。当系统接收到用户查询时，首先在一级缓存查找，如果找到相同查询请求，则返回搜索结果；如果在一级缓存没有找到完全相同的查询，则转向二级缓存查找构成查询的各个单词的倒排列表，如果某些单词的倒排列表没有在二级缓存中找到，则从磁盘读取对应的倒排列表，进入二级缓存；之后，对所有单词的倒排列表进行求交集运算并根据排序算法排序输出最相关的搜索结果，将相应的用户查询和搜索结果放入一级缓存进行存储，并返回最终结果给用户。采用两级缓存结构的出发点在于能够融合搜索结果型缓存的用户快速响应速度和倒排列表型缓存的命中率高这两个优点。
四、缓存淘汰策略(Evict Policy) 缓存淘汰策略是任何缓存必须配备的管理策略。因为缓存的大小总是有限的，当缓存已满的时候，如果有新的缓存项需要加入，那么必须从已有的缓存项中剔除相对最不重要的项目，而不同的缓存淘汰策略就是根据不同的算法来衡量项目的重要性，并剔除掉最不重要项目占用的内存空间。缓存淘汰策略方法众多，从宏观角度，可以将其分为动态策略和静态动态混合策略。
4.1 动态策略 动态策略的缓存数据完全来自于在线用户查询请求，这种缓存策略的基本思路是：对缓存项保留一个权重值，这个权重值根据查询命中情况动态调整，当缓存已满的情况出现时，优先淘汰权重值最低的那个缓存项，通过这种方式来腾出空间。比较常见的动态策略包括：LRU策略、LandLord策略及SLRU等改进策略。
LRU策略：最近最少使用策略(Least Recently Used) LRU淘汰策略是计算机领域使用非常广泛的缓存替换算法，在操作系统内存管理和Web页面缓存等领域也发挥着重要作用。LRU策略的基本思想是：当缓存已满时，将在设定的时间范围内使用次数最少的项目剔除出缓存，也就是将在设定时间段范围内最少访问的用户查询剔除掉。 在实际系统中，往往为每个缓存项设置一个计数器，将命中查询的计数器清零，与此同时，其他查询计数器加1。如果缓存己满，则将计数器数值最大的项目剔除出缓存。
LandLord策略 LandLord策略是一种加权缓存策略(Weighted Cache)。其基本计算流程如下：当一个缓存项插入缓存的时候，会根据缓存项能够获得收益和缓存项所占内存大小的比率设定一个过期值(Deadline)，可以将这个比率理解为系统缓存这个项目的性价比。如果缓存已满，需要剔除项目的时候，选择过期值最小的项目进行淘汰，即淘汰性价比最低的项目。同时，其他未被淘汰的项目对应的过期值都减去被淘汰项目的过期值，如果一个查询请求在缓存中命中时，会相应地将其过期值根据一定策略调大。
SLRU策略：大小自适应LRU (Size-adjusted LRU) SLRU策略是对LRU方法的改进。缓存被分为两个部分：非保护区域和保护区域。每个区域的缓存项都按照最近使用频度由高到低排序，频率高端叫做MRU，低端的叫做LRU。如果某个查询没有在缓存中找到，那么将这个查询放入非保护区域的MRU端；如果某个查询在缓存中命中，则把这个查询记录放到保护区的MRU端；如果保护区已满，则把记录从保护区放入非保护区的MRU，这样保护区的记录最少要被访问两次。淘汰机制是将非保护区的LRU端缓存项淘汰。
4.2 混合策略 动态策略的缓存数据完全来自于在线用户查询请求，混合策略与此不同，其缓存数据一方面来自于在线用户查询，一方面来自于搜索日志等历史数据。目前效果较好的混合策略包括SDC策略和AC策略。图7是这种策略的示意图。
SDC策略：静态动态混合缓存策略(Static and Dynamic Caching) SDC策略是一种混合缓存策略，SDC将缓存切割为两个部分，一个静态缓存与一个动态缓存。所谓静态缓存，即缓存内容是事先根据搜索日志统计出的最高频的那部分查询请求，在一定时间范围里是相对不变的；而动态缓存则可以配合使用LRU等其他缓存管理策略，根据用户查询请求不断更换内容。通过同时使用静态缓存和动态缓存，可以有效增加缓存请求命中率。SDC是目前效果最好的缓存策略之一。
AC策略：准入策略(Admission Control) 准入策略是类似于SDC策略的一种方法。该方法也将缓存分为两个部分，分别存储高频出现的历史用户查询和动态出现的用户查询及其对应的搜索结果。与SDC不同之处在于：SDC的静态缓存所存储的高频用户查询是完全从过去的搜索日志统计得来的静态内容，而AC策略则综合了搜索日志的统计数据、查询长度等多个判断因素，以此来预测某个查询是否会在未来被多次访问，如果判断是，则放入高频用户查询缓存。
五、缓存更新策略(Refresh Policy) 如果搜索引擎的索引内容不发生变化，缓存的内容就总是和索引系统保持一致。但是淘宝搜索引擎索引经常更新，如果索引内容发生变化，而缓存内容不随着索引变动，会导致缓存内容和索引内容的不一致，这种不一致对于用户的搜索体验会造成负面影响。缓存更新策略就是通过一定的技术手段尽可能保持缓存内容和索引内容的一致性。 目前很多搜索引擎使用简单的更新策略，即在搜索引擎比较繁忙的时候不考虑缓存更新问题，而等到搜索引擎请求很少的时候，比如午夜等时间段，将缓存内的内容批量进行更新，使缓存内容保持和索引内容的一致。这种简单策略适合索引更新不是非常频繁的应用场景，对于索引更新频繁的场景，需要相对复杂些的缓存更新策略。 根据缓存内容和索引内容联系的密切程度，目前的缓存更新策略可以分为两种：缓存——索引密切耦合策略和缓存——索引非耦合策略。 缓存——索引密切耦合策略在索引和缓存之间增加一种直接的变化通知机制，一旦索引内容发生变化则通知缓存系统，缓存系统根据一定的方法判断哪些缓存的内容发生了改变，然后将改变的缓存内容进行更新，或者设定缓存项为过期，这样就可以紧密跟踪并反映索引变化内容。这种密切耦合策略在实际实现时是非常复杂的，因为频繁的索引更新导致频繁的缓存更新，对系统效率及缓存命中率都会有直接影响。图8是一个缓存——索引密切耦合策略的示意图。当有新的索引文档进入淘宝搜索引擎时，系统会对文档内容进行分析，抽取出文档中得分较高的索引词汇，并将这些词汇及其得分传递给失效通知模块，因为如果缓存中的查询包含这些索引词汇的话，很可能该文档将会使得缓存内容失效，失效通知模块会评估哪些缓存项需要进行内容更新，如果某项缓存项需要更新，则提取最新的缓存内容更新旧缓存项。
缓存——索引非耦合策略则使用相对简单的策略，当索引变化时并不随时通知缓存系统进行内容更新，而是给每个缓存项设定一个过期值(Time To Live)，随着时间流逝，项会逐步过期。通过这种方式可以将缓存项和索引的不一致尽可能减小。淘宝搜索引擎就是采用了用了缓存——索引非祸合策略来维护缓存内容的更新，这就是淘宝搜索系统中下架时间的最根本的来源。总结 1、使用搜索引引擎缓存技术可以加快用户响应速度并节省计算资源。 2、缓存系统的目标是最大化缓存命中率和保持缓存内容与索引内容的一致性。 3、缓存存储对象主要包括网页搜索结果及查询词对应的倒排列表。 4、缓存系统可以有多层级结构。 5、缓存淘汰策略方法众多，从宏观角度，可以将其分为动态策略和静态动态混合策略。
