XML地图 黑帽SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO优化 » 搜索引擎缓存淘汰策略(三)

搜索引擎缓存淘汰策略(三)

2018-10-14T10:37:05 | 人围观 | 关键词:搜索引擎缓存淘汰策略(三)--SEO培训


  搜索引擎缓存淘汰策略(Evict Policy)
 

  缓存淘汰策略是任何缓存必须配备的管理策略。因为缓存的大小总是有限的,当缓存已满的时候,如果有新的缓存项需要加入,那么必须从已有的缓存项中剔除相对最不重要的项目,而不同的缓存淘汰策略就是根据不同的算法来衡量项目的重要性,并剔除掉最不重要项目占用的内存空间。缓存淘汰策略方法众多,从宏观角度,可以将其分为动态策略和静态动态混合策略。
 

  11.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端缓存项淘汰。
 

  11.4.2 混合策略
 

  动态策略的缓存数据完全来自于在线的用户查询请求,混合策略与此不同,其缓存数据一方面来自于在线用户查询,一方面来自于搜索日志等历史数据。目前效果较好的混合策略包括SDC策略和AC策略。图11-6是这种策略的示意图。

 

  

 

  SDC策略:静态动态混合缓存策略(Static and Dynamic Caching)
 

  SDC策略是一种混合缓存策略,SDC将缓存切割为两个部分,一个静态缓存与一个动态缓存。所谓静态缓存,即缓存内容是事先根据搜索日志统计出的最高频的那部分查询请求,在一定时间范围里是相对不变的;而动态缓存则可以配合使用LRU等其他缓存管理策略,根据用户查询请求不断更换内容。通过同时使用静态缓存和动态缓存,可以有效增加缓存请求命中率。SDC是目前效果最好的缓存策略之一。
 

  AC策略:准入策略(Admission Control)
 

  准入策略是类似于SDC策略的一种方法。该方法也将缓存分为两个部分,分别存储高频出现的历史用户查询和动态出现的用户查询及其对应的搜索结果。与SDC不同之处在于:SDC的静态缓存所存储的高频用户查询是完全从过去的搜索日志统计得来的静态内容,而AC策略则综合了搜索日志的统计数据、查询长度等多个判断因素,以此来预测某个查询是否会在未来被多次访问,如果判断是,则放入高频用户查询缓存。
 

相关内容推荐:

Top