文档章节

缓存算法简单介绍

robertchao
 robertchao
发布于 2016/05/20 13:21
字数 1019
阅读 7
收藏 0
  1. Least-Recently-Used(LRU) - 最近最少使用
    替换掉最近被请求最少的文档。这一传统策略在实际中应用最广。在CPU缓存淘汰和虚拟内存系统中效果很好。然而直接应用与代理缓存效果欠佳,因为Web访问的时间局部性常常变化很大。
  2. FIFO(First in First out)
    在FIFO Cache设计中,核心原则就是:如果一个数据最先进入缓存中,则应该最早淘汰掉。也就是说,当缓存满的时候,应当把最先进入缓存的数据给淘汰掉。这个原则简单、且符合人们的惯性思维,具备公平性,并且实现起来简单,直接使用数据结构中的队列即可实现。
  3. Least-Frequently-Used(LFU) - 最不经常使用
    替换掉访问次数最少的。这一策略意图保留最常用的、最流行的对象,替换掉很少使用的那些。然而,有的文档可能有很高的使用频率,但之后再也不会用到。传统 的LFU策略没有提供任何移除这类文件的机制,因此会导致“缓存污染(Cache Pollution)”,即一个先前流行的缓存对象会在缓存中驻留很长时间,这样,就阻碍了新进来可能会流行的对象对它的替代。
  4. SIZE
    替换size最大的对象。这一策略通过淘汰一个大对象而不是多个小对象来提高命中率。不过,可能有些进入缓存的小对象永远不会再被访问。SIZE策略没有提供淘汰这类对象的机制,也会导致“缓存污染”。
  5. LRU-Threshold
    不缓存超过某一size的对象,其它与LRU相同。
  6. Log(Size) + LRU
    替换size最大的对象,当size相同时,按LRU进行替换
  7. Hyper-G
    LFU的改进版,同时考虑上次访问时间和对象size
  8. Pitkow/Recker
    替换最近最少使用的对象,除非所有对象都是今天访问过的。如果是这样,则替换掉最大的对象。这一策略试图符合每日访问web网页的特定模式。这一策略也被建议在每天结束是运行,以释放被“旧的”,最近最少使用的对象占用的空间。
  9. Lowest-Latency-First
    替换下载时间最少的文档。显然它的目标是最小化平均延迟。
  10. Hybrid
    Hybrid有另外一个目标,减少平均延迟。对缓存中的每个文档都会计算一个保留效用(utility of retaining)。保留效用最低的对象会被替换掉。位于服务器s的文档f的效用函数定义如下:
    Cs: 与服务器s的连接时间
    bs: 服务器s的带宽
    frf: f的使用频率
    sizef: f的size,单位字节

    K1和K2是常量,Cs和bs是根据最近从服务器s获取文档的时间进行估计的。
  11. Lowest Relative Value(LRV)
    LRV也是基于计算缓存中文档的保留效用。然后替换保留效用最低的文档。有点复杂,实际应用价值不大,就不详述了。
  12. 随机算法,即RAND算法(Random algorithm)
    利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单,而且容易实现。但是,这种算法完全没有利用主存储器中页面调度情况的历史信息,也没有反映程序的局部性,所以命中率比较低。
  13. 最优替换算法,即OPT算法(OPTimal replacement algorithm)
    它假设将来主存储器中的页面调度情况与过去一段时间内主存储器的页面调度情况是相同的。显然,这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面,这种替换算法的命中率一定是最高的,它就是最 优替换算法。




本文转载自:http://blog.csdn.net/robertcpp/article/details/51408243

共有 人打赏支持
robertchao
粉丝 3
博文 55
码字总数 30285
作品 0
海淀
Android工程师
Android公共库(缓存 下拉ListView 下载管理Pro 静默安装 root运行 Java公共类)

最新内容建议直接访问原文:Android公共库(缓存 下拉ListView 下载管理Pro 静默安装 root运行 Java公共类) 介绍总结的一些android公共库,包含缓存(图片缓存、预取缓存)、公共View(下拉及底部...

Trinea
2013/07/28
839
1
总结的一些android公共库

最新最准确内容建议直接访问原文:Android公共库(缓存 下拉ListView 下载管理Pro 静默安装 root运行 Java公共类) 介绍总结的一些android公共库,包含缓存(图片缓存、预取缓存)、公共View(下拉...

Trinea
2012/07/16
0
1
memcached全面剖析–4. memcached的分布式算法

版权声明:可以任意转载,但转载时必须标明原作者charlee、原始链接http://tech.idv2.com/2008/07/24/memcached-004/以及本声明. 之前介绍了memcached的内部情况。本次不再介绍memcached的内...

flynewton
2010/10/15
0
0
《大型网站技术架构》读书笔记之六:永无止境之网站的伸缩性架构

http://www.cnblogs.com/edisonchou/ 《大型网站技术架构》读书笔记之六:永无止境之网站的伸缩性架构 此篇已收录至《大型网站技术架构》读书笔记系列目录贴,点击访问该目录可获取更多内容。...

swearyd457
2015/08/17
0
2
教你密码缓存

Advanced Office Password Recovery是一款专业针对Office系列文档的密码破解工具,AOPR会将工作中涉及到的所有密码保存在密码缓存中,因此密码缓存就是一个专门用来存储密码的区域。   什么...

neluzyy1
2015/12/25
74
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

jquery创建类似于java的map

var map = {}; // Map map = new HashMap(); map[key] = value; // map.put(key, value); var value = map[key]; // Object value = map.get(key); var has = key in map; // boolean has = ......

SuperDabai
31分钟前
0
0
java大数据转换16进制转10进制

public static void main(String[] args) {String hex = "0xdbf3accc683297cf0000";BigInteger amount = new BigInteger(hex.substring(2), 16);System.out.println(amount);......

任梁荣
昨天
1
0
OSChina 周六乱弹 —— 目测我们程序员丁克的几率不大

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @真Skr小机灵鬼儿:8.13分享Jocelyn Pook/Russian Red的单曲《Loving Strangers》 《Loving Strangers》- Jocelyn Pook/Russian Red 手机党少...

小小编辑
昨天
9
3
TypeScript基础入门 - 函数 - 剩余参数

转载 TypeScript基础入门 - 函数 - 剩余参数 项目实践仓库 https://github.com/durban89/typescript_demo.gittag: 1.2.1 为了保证后面的学习演示需要安装下ts-node,这样后面的每个操作都能...

durban
昨天
1
0
OpenCV边缘检测算子原理总结及实现

1. 拉普拉斯算子 原理:是一种基于图像导数运算的高通线性滤波器。它通过二阶导数来度量图像函数的曲率。 拉普拉斯算子是最简单的各向同性微分算子,它具有旋转不变性。一个二维图像函数的拉...

漫步当下
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部