缓存算法:缓存法通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。
缓存策略:缓存策略主要三方面:
- 缓存什么内容
- 何时进行缓存
- 当缓存空间已满时如何进行替换,即缓存替换算法。
对于第二方面,大部分缓存算法使用预取策略来提前将部分磁盘数据放入缓存,以进一步减少磁盘I/O,加大缓存命中率。通过记录、分析以往的数据请求模式来预测将来可能被请求到的数据段,将访问可能性大的数据段放入缓存。
缓存策略的数据块分割:
首部缓存和分块缓存策略普遍应用于VoD影片文件。首部缓存将影片文件开始的一部分放入缓存以减小点播用户的启动延迟,对于影片文件其他部分的访问需要直接读取磁盘。
分块缓存通过将影片文件切分成小块,以块为单位进行缓存操作。分块缓存分为定长分块与变长分块。定长分块将文件切分为大小相同的块,变长分块,变长算法是基于影片文件越靠后的部分被访问的概率越低的推断,将文件按照首尾位置分块,各块大小按指数递增。
但以上定长与变长分块均忽略了两点:
- 影片文件会存在一些“热点片段”而这些热点片段并不均处于影片首部
- 同一影片内“热点片段”的热度会随着时间不断改变,不同影片的热度也随时间不断变化。
需设计良好的算法自适应影片热点的不同位置与变化。
缓存策略的分类:
由于不同系统的数据访问模式不尽相同,同一种缓存策难以在各种数据访问模式下均取得满意性能,研究人员提出不同缓存策略以适应不同需求。
缓存策略可分为以下几类:
- 基于访问时间:此类算法按各缓存项的被访问时间来组织缓存队列,决定替换对象。如LRU。
- 基于访问频率:此类算法用缓存项的被访问频率来组织缓存。如LFU、LRU-2、2Q、LIRS。
- 访问时间与频率兼顾:通过兼顾访问时间与频率,使得在数据访问模式变化时缓存策略仍有较好性能。如FBR、LRFU、ALRFU。多数此类算法具有一个可调或自适应参数,通过该参数的调节使缓存策略在基于访问时间与频率间取得一定平衡。
- 基于访问模式:某些应用有较明确的的数据访问特点,进而产生与其相适应的缓存策略。如专为VoD系统设计的A&L缓存策略,同时适应随机、顺序两种访问模式的SARC策略。
- 基于访问时间的缓存策略:LRU (LeastRecentlyUsed)是一种应用广泛的缓存算法。该算法维护一个缓存项队列,队列中的缓存项按每项的最后被访问时间排序。当缓存空间已满时,将处于队尾,即删除最后一次被访问时间距现在最久的项,将新的区段放入队列首部。但LRU算法仅维护了缓存块的访问时间信息,没有考虑被访问频率等因素,在某些访问模式下无法获得理想命中率。例如对于VoD系统,在没有VCR操作的情况下,数据被由前至后顺序访问,已访问过的数据不会被再次访问。所以LRU算法将最新被访问的数据最后被替换不适用于VoD系统。
-
基于访问频率的缓存策略:LFU (LeastFrequentlyUsed)按每个缓存块的被访问频率将缓存中的各块排序,当缓存空间已满时,替换掉缓存队列中访问频率最低的一项。与LRU的缺点类似, LFU仅维护各项的被访问频率信息,对于某缓存项,如果该项在过去有着极高的访问频率而最近访问频率较低,当缓存空间已满时该项很难被从缓存中替换出来,进而导致命中率下降。
LRU-2[2, 3]算法记录下每个缓存页面最后两次被访问的时间。替换页面时替换掉倒数第二次访问时间距现在最久的一项。在IRM (IndependentReferenceModel)访问模式下,LRU-2有着最好的预期命中率,由于LRU-2算法要维护一个优先级队列,所以该算法复杂度为logN(N为缓存队列中缓存项的数量)。
2Q[4](2 Queues)使用LRU队列替换了LRU-2中的优先级队列,将算法时间复杂度由logN降为常数,且维护缓存项的各信息所需空间比LRU-2小。
LIRS[5](Low Inter-ReferenceRecency Set)维护一个变长的LRU队列,该队列的LRU端为最近至少被访问过2次的第Llirs项(Llirs为算法参数)。LIRS算法在IRM访问模式下可以获得很高的命中率,但对于SDD访问模式效率明显下降。
对于VoD系统,基于访问频率的策略可以捕捉到热点影片片段,使得对热点片段的大量请求免于进行缓慢的磁盘I/O。但影片热点会随时间不断变化,且此类策略无法利用VoD的顺序访问模式,所以纯粹以访问频率为度量来进行替换操作不适合VoD系统。 -
兼顾访问时间与频率:FBR[6](Frequency Based Replacement)维护一个LRU队列,并将该队列分为New、Middle、Old三段。对队列中的每一缓存项均维护一个计数值。当缓存中的一项被命中时,被命中的缓存项被移至New段的MRU端,如果该项原本位于Old或Middle段,则其计数值加1,原位于New段则计数值不变。当进行替换操作时,删除Old段计数值最小的一项(LRU端)。
LRFU[7](LeastRecently FrequentlyUsed)为每一个缓存项维护一个权值C(x),其初始值为0, C(x)按以下公式变化。
在t时刻, C(x) =1+2-λC(x): x被访问到2-λC(x) : x未被访问进行替换操作时,C(x)值最小的一项被删除。当时, LRFU算法行为类似于LFU;而当时,该算法行为逼近LRU算法。该算法通过选用合适的λ值来获得时间与频率因素的平衡。
LRFU虽然通过一个值来兼顾访问时间与频率因素,但由于值固定,当访问模式变化时,该算法无法做出相应的调整而造成性能下降。ALRFU[8](Adaptive LRFU)在此方面对LRFU进行了改进。通过对数据访问模式的历史进行监控,ALRFU动态调整值来适应数据访问模式的改变,表现出比LRFU更好的适应性。 -
基于访问模式的缓存策略:针对VoD系统的特点提出A&L算法。该算法通过记录每个缓存项的历史访问时间与访问数量来估计该项的未来被访问频率。以该频率值为度量,在进行缓存替换时替换掉该值最小的一项。由于该算法考虑了VoD系统的数据访问特点,所以广泛应用于VoD系统。
但A&L算法通过直接计算缓存区段生成以来的总的访问数量、频率来生成缓存权值,没有考虑VoD影片的访问热点会随时间不断变化。当某些缓存区段历史访问频率较高但最近访问频率下降时,仍保持较大权值,影响新的热点片段的缓存,无法适应影片热点的动态变化。
IBM提出的SARC[10]是针对于大型服务器的缓存算法,可在随机访问与顺序访问的数据访问模式下做出动态适应。SARC通过将随机访问与顺序访问分为两个队列分别管理来实现对两种不同访问模式的适应。并通过分析缓存大小-命中率的仿真试验数据曲线,得出对随机队列与顺序队列项分别进行替换的代价函数。当进行缓存替换时,通过两队列的代价函数来对代价小的队列进行替换
http://blog.csdn.net/it_yuan/article/details/8489125
相关推荐
那么,了解常见的缓存淘汰算法的策略和原理就显得特别重要。 常见的缓存算法 LRU (Least recently used) 最近最少使用,如果数据最近被访问过,那么将来被访问的几率也更高。 LFU (Least frequently used) 最不...
以下是一些常见的大数据和算法、数据分析应用场景: 电子商务:通过收集用户消费习惯、季节和产品生命周期的数据,建立算法模型来确定下一个月、几个月甚至一年的消费者需求。这样可以提高订单转化率。在营销方面,...
缓存策略:缓存类型选择、缓存一致性、缓存更新策略 数据库优化:索引优化、查询优化、分库分表 高可用性设计:故障转移、容灾备份、自动恢复机制 异步处理:消息队列、异步任务处理、事件驱动架构 安全性设计: ...
10.Redis 常见的性能问题和解决方案 11.Redis 的数据淘汰策略有哪些 12.Redis 当中有哪些数据结构 13.假如 Redis 里面有 1 亿个 key,其中有 10w 个 key 是以某个固定的已知的前缀开头的,如果将它们全部找出来? 14...
Redis常见性能问题和解决方案? Redis官方为什么不提供Windows版本? 一个字符串类型的值能存储最大容量是多少? Redis如何做大量数据插入? 假如Redis里面有1亿个key,其中有10w个key是以某个固定的已知的前缀开头...
常见的爬取策略是什么?什么是暗网爬取?如何构建 分布式爬虫?百度的阿拉丁计划是什么? • 什么是倒排索引?如何对倒排索引进行数据压缩? . 搜索引擎如何对搜索结果排序? • 什么是向量空间模型?什么是概率模型...
5.3 经典算法和算法策略 5.3.1 排序算法 5.3.2 字符串查找 5.4 一个实际的应用程序 5.4.1 识别测量数据的趋势 5.4.2 LISLP算法的复杂度 5.4.3 用T-SQL解决最长上升子序列的长度问题 5.5 总结 第6章 子查询、...
检查与进程、线程和作业相关的数据结构和算法;观察Windows如何管理虚拟内存和物理内存;理解NTFS的操作和格式,诊断文件系统访问问题;从上往下查看Windows的网络栈,包括映射、API、名称解析和协议驱动程序;诊断...
分布式缓存memcache的使用及分布式策略,包括Hash算法的选择。 常见的分布式系统存储解决方案,包括MySQL的分布式扩展、HBase的API及使用场景、Redis的使用等。 如何使用分布式消息系统ActiveMQ来降低系统之间...
5.3 经典算法和算法策略222 5.3.1 排序算法223 5.3.2 字符串查找225 5.4 一个实际的应用程序226 5.4.1 识别测量数据的趋势226 5.4.2 LISLP算法的复杂度226 5.4.3 用T-SQL解决最长上升子序列的长度问题227 5.5 总结...
5.3 经典算法和算法策略222 5.3.1 排序算法223 5.3.2 字符串查找225 5.4 一个实际的应用程序226 5.4.1 识别测量数据的趋势226 5.4.2 LISLP算法的复杂度226 5.4.3 用T-SQL解决最长上升子序列的长度问题227 5.5...
温习计划计算机网络TCP / UDP相关内容DNS相关:过程,优化 WebSocket CDN作用及原理编程...从分类和语义的角度使用标签CSS呈现常见的几何图形CSS常见布局安全问题浏览器同源策略项目安全方案XSS CSRF页面劫持参考: :
cache.dart是不同的缓存策略及其过期策略的集合。 char_matcher.dart是字符类,它们的组成和对字符串的操作的模型。 collection.dart是集合类型的集合:双向映射,位列表,多集合,集合和列表多映射,范围和字符...
分层是企业应⽤系统中最常见的⼀种架构模式,将系统在横向维度上切分成⼏个部分,每个部分负责⼀部分相对⽐较单⼀的职责,然后 通过上层对下层的依赖和调⽤组成⼀个完整的系统。 分层在计算机世界⽆处不在,在本项...
7 数据结构和算法的运用 7.1 使用图进行数据建模和解决问题 7.1.1 模拟图 7.1.2 最短路径算法 技术点52 找出两个用户间的最短距离 7.1.3 friends-of-friends(FoF) 技术点53 计算FoF 7.1.4 ...
代理服务器在网络中应用非常广泛,它除了实现代理上网外,还可以实现缓存、日志和 警报、验证等功能。 15. 用提供的密钥交换办法的优势包括在两个用户和主机间采用公钥加密、提供了安全传输 密钥的方法、提供了强...
④二级缓存与查询缓存 3、 Struts ①MVC 模式与 Struts 体系 4、 mybatis 5、 MVC 框架 6、 各框架对比与项目优化 7、 JPA ①EJB 三、 Java web 开发核心内容 1、 web 编程基础 ①Tomcat 服务器NOWCODER.COM 牛客网...
11.2.1 加载数据技术点67 加载Apache 日志文件11.2.2 过滤和投影技术点68 通过过滤和投影减少数据处理量11.2.3 分组和聚合UDF 技术点69 IP 地址的分组和计数 11.2.4 使用UDF 进行定位技术点70 使用...
19.2.4. 策略:非严格读/写缓存(Strategy: nonstrict read/write) 19.2.5. 策略:事务缓存(transactional) 19.3. 管理缓存(Managing the caches) 19.4. 查询缓存(The Query Cache) 19.5. 理解集合性能...
二级缓存与查询缓存 3.4.5. 查询语言中的替换 3.4.6. Hibernate的统计(statistics)机制 3.5. 日志 3.6. 实现NamingStrategy 3.7. XML配置文件 3.8. J2EE应用程序服务器的集成 3.8.1. 事务策略配置 3.8.2. ...