精华内容
下载资源
问答
  • 缓存算法

    2016-01-12 15:26:28
    命中(如果在缓存中,一个条目通过get被找到了,我们就称之为缓存命中)缓存Miss存储成本(数据放入缓存所需要的时间和空间)索引成本失效(当存在缓存中的数据需要更新时,就意味着该数据失效了)缓存算法(当缓存...

    缓存就是临时存储数据(通常是使用频繁的数据)的地方,以避免额外的开销较大的计算,并且使得获取结果的速度更快。


    缓存相关的术语:

    • 命中(如果在缓存中,一个条目通过get被找到了,我们就称之为缓存命中)
    • 缓存Miss
    • 存储成本(数据放入缓存所需要的时间和空间)
    • 索引成本
    • 失效(当存在缓存中的数据需要更新时,就意味着该数据失效了)
    • 缓存算法(当缓存未命中时,且缓存容量已满,就需要从缓存中置换出一个旧的条目,添加一条新的条目)


    常见的缓存算法

    • Least FrequentlyUsed(LFU,通过为每个被缓存的数据元素计算它们被使用的频率,然后把最不常用的元素置换出去
    • Least Recently User(LRU,把最近最少使用的缓存数据元素置换出去,实现中会把最新访问的元素放在缓存池的顶部,当缓存容量到达limit时,就从缓存池顶部开始将元素置换出去
    • Least Recently User 2(LRU2,又称最近最少使用twice。把两次被访问过的元素放入缓存池中,当缓存池满了,再把有两次最少使用的缓存元素置换出去。因为需要跟踪元素2次,访问负载就会随着缓存池的增加而增加,这样当在大容量的缓存池中,就会产生问题。此外还需要跟踪那些不在缓存中的元素,因为它们还没有被第二次读取。其是adoptive to access
    • Two Queues(2Q,把被访问的数据元素放到LRU的缓存中,如果这个元素再次被访问,就把它转移到第二个、更大的LRU缓存中,置换出缓存元素是为了保持第一个缓存池是第二个缓存池的1/3,缓存的访问负载是固定的时候,把LRU换成 LRU2,就比增加缓存的容量更好,其是 adoptive to access
    • Adaptive Replacement Cache(ARC,是由2个LRU组成,第一个L1包含的是最近只被使用过一次的元素,第二个L2包含的是最近被使用过两次的元素,因此L1放的是新对象,而L2放的是常用对象。所以其被认为是介于LRU和LFU之间的。被认为是性能最好的缓存算法之一,能够自调,并且是低负载的,同时也保存着历史对象,这样就可以记住那些被移除的对象,记忆力很差
    • Most Recently Used(MRU,和LRU相对应。会移除最近最多被使用的对象——当请求访问的时候,因为有些事情是无法预测的,并且在缓存系统中找出最少最近使用的元素是一项时间复杂度非常高的运算,此时就可以考虑使用MRU。在数据库内存缓存中比较常见
    • First in First out(FIFO,是先进先出,我是一个低负载的算法,并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。我很快,但是我并不适用
    • Second Chance(基于FIFO,并改善了FIFO的成本。和FIFO一样也是观察队列的前端,但是和FIFO的立刻置换不同,会检查即将要被置换出去的元素有没有之前被使用过——通过一个bit标识来表示,没有被使用过的元素就把它置换出去,否则将该标志位清除,然后再把这个缓存元素当做新增缓存元素加入队列——可以想象这就是一个环形队列。当再次在队头碰到该元素时,由于它已经没有标志位了,所以可以立即将它置换出去,其速度比FIFO快
    • CLock比second chance更好,因为它不会像second chance那样把有标志的缓存元素放到队列的尾部,同时也可以达到second chance的效果。CLock持有一个装有缓存元素的环形列表,头指针指向列表中最老的缓存元素,当缓存miss发生并且没有新的缓存空间时,会查看指针指向的缓存元素的标志位以决定如何去做:如果标志位是0,直接用新的缓存元素替代这个缓存元素;  如果标志位是1,则把头指针递增,然后重复这个过程,直到新的缓存元素能够被放入
    • Simple time-based通过绝对的时间周期去失效那些缓存元素,对于新增元素会保存特定的时间。不太适用
    • Extended time-based expiration通过相对时间去失效缓存对象的,对于新增元素会保存特定的时间,比如是每5分钟,每天的12点等
    • Sliding time-based expiration与前面不同的是,缓存元素的生命周期是从这个缓存的最后被访问时间开始算起,不太适用

    Random Cache:随机缓存,随意的替换缓存实体。通过这些行为,可以随意的去处理缓存实体。比FIFO机制更好,在某些情况下,甚至比LRU好,但是通常LRU更好


    展开全文
  • 缓存、缓存算法和缓存框架简介
  • 为提升数据检索读的性能,基于老化算法采取Cache方法,通过设计合理的缓存结构,给出一种新的分布式文件缓存算法.该算法在缓存实现部分,使用了LRU算法中常用的老化算法,并将其由一个页面置换算法改进为一个文件缓存替换...
  • LRU缓存算法也叫LRU页面置换算法,是一种经典常用的页面置换算法,下面这篇文章主要介绍了c++实现的常见缓存算法和LRU,需要的朋友可以参考借鉴,下面来一起看看吧。
  • 缓存、缓存算法和缓存框架简介 - 文章 - 伯乐在线.pdf 来自http://blog.jobbole.com/30940/
  • 内容分发网络中基于内容名的缓存算法会导致路由表规模随网络增长而膨胀,将严重影响网络路由效率和性能。针对该问题,提出一种基于相关内容吸引的节点缓存算法。利用本地缓存算法,通过节点已缓存内容对其他内容的吸引...
  • 在这边文章,我们会去讨论缓存,缓存算法,缓存框架以及哪个缓存框架会更好。面试“缓存就是存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。”这就是 programmer one ...

    引言

    我们都听过 cache,当你问他们是什么是缓存的时候,他们会给你一个完美的答案,可是他们不知道缓存是怎么构建的,或者没有告诉你应该采用什么标准去选择缓存框架。在这边文章,我们会去讨论缓存,缓存算法,缓存框架以及哪个缓存框架会更好。

    面试

    “缓存就是存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。”

    这就是 programmer one (programmer one 是一个面试者)在面试中的回答(一个月前,他向公司提交了简历,想要应聘要求在缓存,缓存框架,大规模数据操作有着丰富经验的 Java 开发职位)。

    programmer one 通过 hash table 实现了他自己的缓存,但是他知道的只是他的缓存和他那存储着150条记录的 hash table,这就是他认为的大规模数据(缓存 = hashtable,只需要在 hash table 查找就好了),所以,让我们来看看面试的过程吧。

    面试官:你选择的缓存方案,是基于什么标准的?

    programmer one:呃,(想了5分钟)嗯,基于,基于,基于数据(咳嗽……)

    面试官:excese me ! 能不能重复一下?

    programmer one:数据?!

    面试官:好的。说说几种缓存算法以及它们的作用

    programmer one:(凝视着面试官,脸上露出了很奇怪的表情,没有人知道原来人类可以做出这种表情 )

    面试官:好吧,那我换个说法,当缓存达到容量时,会怎么做?

    programmer one:容量?嗯(思考……hash table 的容量时没有限制的,我能任意增加条目,它会自动扩充容量的)(这是 programmer one 的想法,但是他没有说出来)

    面试官对 programmer one 表示感谢(面试过程持续了10分钟),之后一个女士走过来说:谢谢你的时间,我们会给你打电话的,祝你好心情。这是 programmer one 最糟糕的面试(他没有看到招聘对求职者有丰富的缓存经验背景要求,实际上,他只看到了丰厚的报酬 )。

    说到做到

    programmer one 离开之后,他想要知道这个面试者说的问题和答案,所以他上网去查,programmer one 对缓存一无所知,除了:当我需要缓存的时候,我就会用 hash table。

    在他使用了他最爱的搜索引擎搜索之后,他找到了一篇很不错的关于缓存文章,并且开始去阅读……

    为什么我们需要缓存?

    很久很久以前,在还没有缓存的时候……用户经常是去请求一个对象,而这个对象是从数据库去取,然后,这个对象变得越来越大,这个用户每次的请求时间也越来越长了,这也把数据库弄得很痛苦,他无时不刻不在工作。所以,这个事情就把用户和数据库弄得很生气,接着就有可能发生下面两件事情:

    1.用户很烦,在抱怨,甚至不去用这个应用了(这是大多数情况下都会发生的)

    2.数据库为打包回家,离开这个应用,然后,就出现了大麻烦(没地方去存储数据了)(发生在极少数情况下)

    上帝派来了缓存

    在几年之后,IBM(60年代)的研究人员引进了一个新概念,它叫“缓存”。

    什么是缓存?

    正如开篇所讲,缓存是“存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。”

    缓存可以认为是数据的池,这些数据是从数据库里的真实数据复制出来的,并且为了能别取回,被标上了标签(键 ID)。太棒了

    programmer one 已经知道这点了,但是他还不知道下面的缓存术语。

    缓存、缓存算法和缓存框架简介

    命中:

    当客户发起一个请求(我们说他想要查看一个产品信息),我们的应用接受这个请求,并且如果是在第一次检查缓存的时候,需要去数据库读取产品信息。

    如果在缓存中,一个条目通过一个标记被找到了,这个条目就会被使用、我们就叫它缓存命中。所以,命中率也就不难理解了。

    Cache Miss:

    但是这里需要注意两点:

    1. 如果还有缓存的空间,那么,没有命中的对象会被存储到缓存中来。

    2. 如果缓存慢了,而又没有命中缓存,那么就会按照某一种策略,把缓存中的旧对象踢出,而把新的对象加入缓存池。而这些策略统称为替代策略(缓存算法),这些策略会决定到底应该提出哪些对象。

    存储成本:

    当没有命中时,我们会从数据库取出数据,然后放入缓存。而把这个数据放入缓存所需要的时间和空间,就是存储成本。

    索引成本:

    和存储成本相仿。

    失效:

    当存在缓存中的数据需要更新时,就意味着缓存中的这个数据失效了。

    替代策略:

    当缓存没有命中时,并且缓存容量已经满了,就需要在缓存中踢出一个老的条目,加入一条新的条目,而到底应该踢出什么条目,就由替代策略决定。

    最优替代策略:

    最优的替代策略就是想把缓存中最没用的条目给踢出去,但是未来是不能够被预知的,所以这种策略是不可能实现的。但是有很多策略,都是朝着这个目前去努力。

    Java 街恶梦:

    当 programmer one 在读这篇文章的时候,他睡着了,并且做了个恶梦(每个人都有做恶梦的时候)。

    programmer one:nihahha,我要把你弄失效!(疯狂的状态)

    缓存对象:别别,让我活着,他们还需要我,我还有孩子。

    programmer one:每个缓存对象在失效之前都会那样说。你从什么时候开始有孩子的?不用担心,现在就永远消失吧!

    哈哈哈哈哈……programmer one 恐怖的笑着,但是警笛打破了沉静,警察把 programmer one 抓了起来,并且控告他杀死了(失效)一个仍需被使用的缓存对象,他被押到了监狱。

    programmer one 突然醒了,他被吓到了,浑身是汗,他开始环顾四周,发现这确实是个梦,然后赶紧继续阅读这篇文章,努力的消除自己的恐慌。

    在programmer one 醒来之后,他又开始阅读文章了。

    缓存算法

    没有人能说清哪种缓存算法优于其他的缓存算法

    Least Frequently Used(LFU):

    大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

    Least Recently User(LRU):

    我是 LRU 缓存算法,我把最近最少使用的缓存对象给踢走。

    我总是需要去了解在什么时候,用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉,是非常困难的。

    浏览器就是使用了我(LRU)作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,我会把底部的对象踢走,而技巧就是:我会把最新被访问的缓存对象,放到缓存池的顶部。

    所以,经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我,array 或者是 linked list。

    我的速度很快,我也可以被数据访问模式适配。我有一个大家庭,他们都可以完善我,甚至做的比我更好(我确实有时会嫉妒,但是没关系)。我家庭的一些成员包括 LRU2 和 2Q,他们就是为了完善 LRU 而存在的。

    Least Recently Used 2(LRU2):

    我是 Least Recently Used 2,有人叫我最近最少使用 twice,我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池,当缓存池满了之后,我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中,就会有问题。另外,我还需要跟踪那么不在缓存的对象,因为他们还没有被第二次读取。我比LRU好,而且是 adoptive to access 模式 。

    Two Queues(2Q):

    我是 Two Queues;我把被访问的数据放到 LRU 的缓存中,如果这个对象再一次被访问,我就把他转移到第二个、更大的 LRU 缓存。

    我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把 LRU 换成 LRU2,就比增加缓存的容量更好。这种机制使得我比 LRU2 更好,我也是 LRU 家族中的一员,而且是 adoptive to access 模式 。

    Adaptive Replacement Cache(ARC):

    我是 ARC,有人说我是介于 LRU 和 LFU 之间,为了提高效果,我是由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。所以,别人才会认为我是介于 LRU 和 LFU 之间的,不过没关系,我不介意。

    我被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。我也保存着历史对象,这样,我就可以记住那些被移除的对象,同时,也让我可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。我的记忆力很差,但是我很快,适用性也强。

    Most Recently Used(MRU):

    我是 MRU,和 LRU 是对应的。我会移除最近最多被使用的对象,你一定会问我为什么。好吧,让我告诉你,当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这就是为什么我是最好的选择。

    我是数据库内存缓存中是多么的常见!每当一次缓存记录的使用,我会把它放到栈的顶端。当栈满了的时候,你猜怎么着?我会把栈顶的对象给换成新进来的对象!

    First in First out(FIFO):

    我是先进先出,我是一个低负载的算法,并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。我很快,但是我并不适用。

    Second Chance:

    大家好,我是 second chance,我是通过 FIFO 修改而来的,被大家叫做 second chance 缓存算法,我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端,但是很FIFO的立刻踢出不同,我会检查即将要被踢出的对象有没有之前被使用过的标志(1一个 bit 表示),没有没有被使用过,我就把他踢出;否则,我会把这个标志位清除,然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时,由于他已经没有这个标志位了,所以我立刻就把他踢开了。我在速度上比 FIFO 快。

    CLock:

    我是 Clock,一个更好的 FIFO,也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部,但是也可以达到 second chance 的效果。

    我持有一个装有缓存对象的环形列表,头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时,我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0,我会直接用新的缓存对象替代这个缓存对象;如果标志位是1,我会把头指针递增,然后重复这个过程,知道新的缓存对象能够被放入。我比 second chance 更快。

    Simple time-based:

    我是 simple time-based 缓存算法,我通过绝对的时间周期去失效那些缓存对象。对于新增的对象,我会保存特定的时间。我很快,但是我并不适用。

    Extended time-based expiration:

    我是 extended time-based expiration 缓存算法,我是通过相对时间去失效缓存对象的;对于新增的缓存对象,我会保存特定的时间,比如是每5分钟,每天的12点。

    Sliding time-based expiration:

    我是 sliding time-based expiration,与前面不同的是,被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快,但是我也不太适用。

    其他的缓存算法还考虑到了下面几点:

    成本:如果缓存对象有不同的成本,应该把那些难以获得的对象保存下来。

    容量:如果缓存对象有不同的大小,应该把那些大的缓存对象清除,这样就可以让更多的小缓存对象进来了。

    时间:一些缓存还保存着缓存的过期时间。电脑会失效他们,因为他们已经过期了。

    根据缓存对象的大小而不管其他的缓存算法可能是有必要的。

    电子邮件!

    在读完这篇文章之后,programmer one 想了一会儿,然后决定给作者发封邮件,他感觉作者的名字在哪听过,但是已经想不起来了。不管怎样,他还是把邮件发送出来了,他询问了作者在分布式环境中,缓存是怎么样工作的。

    文章的作者收到了邮件,具有讽刺意味的是,这个作者就是面试 programmer one 的人 ,作者回复了……

    在这一部分中,我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的,如果你想自己实现缓存算法,可能自己还得加上一些额外的工作。

    LeftOver 机制

    在 programmer one 阅读了文章之后,他接着看了文章的评论,其中有一篇评论提到了 leftover 机制——random cache。

    Random Cache

    我是随机缓存,我随意的替换缓存实体,没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为,我随意的去处缓存实体。我比 FIFO 机制好,在某些情况下,我甚至比 LRU 好,但是,通常LRU都会比我好。

    现在是评论时间

    当 programmer one 继续阅读评论的时候,他发现有个评论非常有趣,这个评论实现了一些缓存算法,应该说这个评论做了一个链向评论者网站的链接,programmer one顺着链接到了那个网站,接着阅读。

    看看缓存元素(缓存实体)

    public class CacheElement
    {
         private Object objectValue;
         private Object objectKey;
         private int index;
         private int hitCount; // getters and setters
    }

    这个缓存实体拥有缓存的key和value,这个实体的数据结构会被以下所有缓存算法用到。

    缓存算法的公用代码

    public final synchronized void addElement(Object key, Object value)
    {
        int index;
        Object obj;
        // get the entry from the table
        obj = table.get(key);
        // If we have the entry already in our table
        // then get it and replace only its value.
        obj = table.get(key);
        if (obj != null)
        {
            CacheElement element;
            element = (CacheElement) obj;
            element.setObjectValue(value);
            element.setObjectKey(key);
            return;
        }
    }

    上面的代码会被所有的缓存算法实现用到。这段代码是用来检查缓存元素是否在缓存中了,如果是,我们就替换它,但是如果我们找不到这个 key 对应的缓存,我们会怎么做呢?那我们就来深入的看看会发生什么吧!

    现场访问

    今天的专题很特殊,因为我们有特殊的客人,事实上他们是我们想要听的与会者,但是首先,先介绍一下我们的客人:Random Cache,FIFO Cache。让我们从 Random Cache开始。

    看看随机缓存的实现

    public final synchronized void addElement(Object key, Object value)
    {
        int index;
        Object obj;
        obj = table.get(key);
        if (obj != null)
        {
            CacheElement element;// Just replace the value.
            element = (CacheElement) obj;
            element.setObjectValue(value);
            element.setObjectKey(key);
            return;
        }// If we haven't filled the cache yet, put it at the end.
        if (!isFull())
        {
            index = numEntries;
            ++numEntries;
        }
        else { // Otherwise, replace a random entry.
            index = (int) (cache.length * random.nextFloat());
            table.remove(cache[index].getObjectKey());
        }
        cache[index].setObjectValue(value);
        cache[index].setObjectKey(key);
        table.put(key, cache[index]);
    }

    看看FIFO缓算法的实现

    public final synchronized void addElement(Objectkey, Object value)
    {
        int index;
        Object obj;
        obj = table.get(key);
        if (obj != null)
        {
            CacheElement element; // Just replace the value.
            element = (CacheElement) obj;
            element.setObjectValue(value);
            element.setObjectKey(key);
            return;
        }
        // If we haven't filled the cache yet, put it at the end.
        if (!isFull())
        {
            index = numEntries;
            ++numEntries;
        }
        else { // Otherwise, replace the current pointer,
               // entry with the new one.
            index = current;
            // in order to make Circular FIFO
            if (++current >= cache.length)
                current = 0;
            table.remove(cache[index].getObjectKey());
        }
        cache[index].setObjectValue(value);
        cache[index].setObjectKey(key);
        table.put(key, cache[index]);
    }

    看看LFU缓存算法的实现

    public synchronized Object getElement(Object key)
    {
        Object obj;
        obj = table.get(key);
        if (obj != null)
        {
            CacheElement element = (CacheElement) obj;
            element.setHitCount(element.getHitCount() + 1);
            return element.getObjectValue();
        }
        return null;
    }
    public final synchronized void addElement(Object key, Object value)
    {
        Object obj;
        obj = table.get(key);
        if (obj != null)
        {
            CacheElement element; // Just replace the value.
            element = (CacheElement) obj;
            element.setObjectValue(value);
            element.setObjectKey(key);
            return;
        }
        if (!isFull())
        {
            index = numEntries;
            ++numEntries;
        }
        else
        {
            CacheElement element = removeLfuElement();
            index = element.getIndex();
            table.remove(element.getObjectKey());
        }
        cache[index].setObjectValue(value);
        cache[index].setObjectKey(key);
        cache[index].setIndex(index);
        table.put(key, cache[index]);
    }
    public CacheElement removeLfuElement()
    {
        CacheElement[] elements = getElementsFromTable();
        CacheElement leastElement = leastHit(elements);
        return leastElement;
    }
    public static CacheElement leastHit(CacheElement[] elements)
    {
        CacheElement lowestElement = null;
        for (int i = 0; i < elements.length; i++)
        {
            CacheElement element = elements[i];
            if (lowestElement == null)
            {
                lowestElement = element;
            }
            else {
                if (element.getHitCount() < lowestElement.getHitCount())
                {
                    lowestElement = element;
                }
            }
        }
        return lowestElement;
    }

    今天的专题很特殊,因为我们有特殊的客人,事实上他们是我们想要听的与会者,但是首先,先介绍一下我们的客人:Random Cache, FIFO Cache。让我们从 Random Cache开始。

    最重点的代码,就应该是 leastHit 这个方法,这段代码就是把
    hitCount 最低的元素找出来,然后删除,给新进的缓存元素留位置。

    看看LRU缓存算法实现

    private void moveToFront(int index)
    {
        int nextIndex, prevIndex;
        if(head != index)
        {
            nextIndex = next[index];
            prevIndex = prev[index];
            // Only the head has a prev entry that is an invalid index
            // so we don't check.
            next[prevIndex] = nextIndex;
            // Make sure index is valid. If it isn't, we're at the tail
            // and don't set prev[next].
            if(nextIndex >= 0)
                prev[nextIndex] = prevIndex;
            else
                tail = prevIndex;
            prev[index] = -1;
            next[index] = head;
            prev[head] = index;
            head = index;
        }
    }
    public final synchronized void addElement(Object key, Object value)
    {
        int index;Object obj;
        obj = table.get(key);
        if(obj != null)
        {
            CacheElement entry;
            // Just replace the value, but move it to the front.
            entry = (CacheElement)obj;
            entry.setObjectValue(value);
            entry.setObjectKey(key);
            moveToFront(entry.getIndex());
            return;
        }
        // If we haven't filled the cache yet, place in next available
        // spot and move to front.
        if(!isFull())
        {
            if(_numEntries > 0)
            {
                prev[_numEntries] = tail;
                next[_numEntries] = -1;
                moveToFront(numEntries);
            }
            ++numEntries;
        }
        else { // We replace the tail of the list.
            table.remove(cache[tail].getObjectKey());
            moveToFront(tail);
        }
        cache[head].setObjectValue(value);
        cache[head].setObjectKey(key);
        table.put(key, cache[head]);
    }

    这段代码的逻辑如 LRU算法 的描述一样,把再次用到的缓存提取到最前面,而每次删除的都是最后面的元素。

    结论

    我们已经看到 LFU缓存算法 和 LRU缓存算法的实现方式,至于如何实现,采用数组还是 LinkedHashMap,都由你决定,不够我一般是小的缓存容量用数组,大的用 LinkedHashMap。

    转载自:http://blog.jobbole.com/30940/

    展开全文
  • 我们都听过 cache,当你问他们是什么是缓存的时候,他们会给你一个完美的答案,可是他们不知道缓存是怎么构建的,或者没有告诉你应该采用...在这篇文章,我们会去讨论缓存,缓存算法,缓存框架以及哪个缓存框架会更好。

    来自:lixiang(http://www.leexiang.com/cache-algorithm)(点击尾部阅读原文前往)
    翻译:http://www.zavakid.com
    原文:http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html

    这里写图片描述

    1.引言

    我们都听过 cache,当你问他们是什么是缓存的时候,他们会给你一个完美的答案,可是他们不知道缓存是怎么构建的,或者没有告诉你应该采用什么标准去选择缓存框架。在这篇文章,我们会去讨论缓存,缓存算法,缓存框架以及哪个缓存框架会更好。

    2.面试

    “缓存就是存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。”

    这就是 programmer one (programmer one 是一个面试者)在面试中的回答(一个月前,他向公司提交了简历,想要应聘要求在缓存,缓存框架,大规模数据操作有着丰富经验的 java 开发职位)。

    programmer one 通过 hash table 实现了他自己的缓存,但是他知道的只是他的缓存和他那存储着150条记录的 hash table,这就是他认为的大规模数据(缓存 = hashtable,只需要在 hash table 查找就好了),所以,让我们来看看面试的过程吧。

    面试官:你选择的缓存方案,是基于什么标准的?
    programmer one:呃,(想了5分钟)嗯,基于,基于,基于数据(咳嗽……)
    面试官:excese me ! 能不能重复一下?
    programmer one:数据?!
    面试官:好的。说说几种缓存算法以及它们的作用
    programmer one:(凝视着面试官,脸上露出了很奇怪的表情,没有人知道原来人类可以做出这种表情 )
    面试官:好吧,那我换个说法,当缓存达到容量时,会怎么做?
    programmer one:容量?嗯(思考……hash table 的容量时没有限制的,我能任意增加条目,它会自动扩充容量的)(这是 programmer one 的想法,但是他没有说出来)

    面试官对 programmer one 表示感谢(面试过程持续了10分钟),之后一个女士走过来说:谢谢你的时间,我们会给你打电话的,祝你好心情。这是 programmer one 最糟糕的面试(他没有看到招聘对求职者有丰富的缓存经验背景要求,实际上,他只看到了丰厚的报酬 )。

    3.说到做到

    programmer one 离开之后,他想要知道这个面试者说的问题和答案,所以他上网去查,programmer one 对缓存一无所知,除了:当我需要缓存的时候,我就会用 hash table。

    在他使用了他最爱的搜索引擎搜索之后,他找到了一篇很不错的关于缓存文章,并且开始去阅读……

    4.为什么我们需要缓存?

    很久很久以前,在还没有缓存的时候……用户经常是去请求一个对象,而这个对象是从数据库去取,然后,这个对象变得越来越大,这个用户每次的请求时间也越来越长了,这也把数据库弄得很痛苦,他无时不刻不在工作。所以,这个事情就把用户和数据库弄得很生气,接着就有可能发生下面两件事情:

    1、用户很烦,在抱怨,甚至不去用这个应用了(这是大多数情况下都会发生的)

    2、数据库为打包回家,离开这个应用,然后,就出现了大麻烦(没地方去存储数据了)(发生在极少数情况下)

    5.上帝派来了缓存

    在几年之后,IBM(60年代)的研究人员引进了一个新概念,它叫“缓存”。

    6.什么是缓存?

    正如开篇所讲,缓存是“存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些。”

    缓存可以认为是数据的池,这些数据是从数据库里的真实数据复制出来的,并且为了能别取回,被标上了标签(键 ID)。太棒了

    programmer one 已经知道这点了,但是他还不知道下面的缓存术语。

    命中:

    当客户发起一个请求(我们说他想要查看一个产品信息),我们的应用接受这个请求,并且如果是在第一次检查缓存的时候,需要去数据库读取产品信息。

    如果在缓存中,一个条目通过一个标记被找到了,这个条目就会被使用、我们就叫它缓存命中。所以,命中率也就不难理解了。

    Cache Miss:

    但是这里需要注意两点:

    1、如果还有缓存的空间,那么,没有命中的对象会被存储到缓存中来。

    2、如果缓存满了,而又没有命中缓存,那么就会按照某一种策略,把缓存中的旧对象踢出,而把新的对象加入缓存池。而这些策略统称为替代策略(缓存算法),这些策略会决定到底应该提出哪些对象。

    存储成本:

    当没有命中时,我们会从数据库取出数据,然后放入缓存。而把这个数据放入缓存所需要的时间和空间,就是存储成本。

    索引成本:

    和存储成本相仿。从缓存中取数据所需要的时间和空间,就是索引成本。

    失效:

    当存在缓存中的数据需要更新时,就意味着缓存中的这个数据失效了。

    替代策略:

    当缓存没有命中时,并且缓存容量已经满了,就需要在缓存中踢出一个老的条目,加入一条新的条目,而到底应该踢出什么条目,就由替代策略决定。

    最优替代策略:

    最优的替代策略就是想把缓存中最没用的条目给踢出去,但是未来是不能够被预知的,所以这种策略是不可能实现的。但是有很多策略,都是朝着这个目前去努力。

    Java 街恶梦:

    当 programmer one 在读这篇文章的时候,他睡着了,并且做了个恶梦(每个人都有做恶梦的时候)。

    programmer one:nihahha,我要把你弄失效!(疯狂的状态)
    缓存对象:别别,让我活着,他们还需要我,我还有孩子。

    programmer one:每个缓存对象在失效之前都会那样说。你从什么时候开始有孩子的?不用担心,现在就永远消失吧!

    哈哈哈哈哈……programmer one 恐怖的笑着,但是警笛打破了沉静,警察把 programmer one 抓了起来,并且控告他杀死了(失效)一个仍需被使用的缓存对象,他被押到了监狱。

    programmer one 突然醒了,他被吓到了,浑身是汗,他开始环顾四周,发现这确实是个梦,然后赶紧继续阅读这篇文章,努力的消除自己的恐慌。

    在programmer one 醒来之后,他又开始阅读文章了。

    7.缓存算法

    没有人能说清哪种缓存算法优于其他的缓存算法

    Least Frequently Used(LFU):

    大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

    Least Recently User(LRU):

    我是 LRU 缓存算法,我把最近最少使用的缓存对象给踢走。

    我总是需要去了解在什么时候,用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉,是非常困难的。

    浏览器就是使用了我(LRU)作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,我会把底部的对象踢走,而技巧就是:我会把最新被访问的缓存对象,放到缓存池的顶部。

    所以,经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我,array 或者是 linked list。

    我的速度很快,我也可以被数据访问模式适配。我有一个大家庭,他们都可以完善我,甚至做的比我更好(我确实有时会嫉妒,但是没关系)。我家庭的一些成员包括 LRU2 和 2Q,他们就是为了完善 LRU 而存在的。

    Least Recently Used 2(LRU2):

    我是 Least Recently Used 2,有人叫我最近最少使用 twice,我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池,当缓存池满了之后,我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中,就会有问题。另外,我还需要跟踪那么不在缓存的对象,因为他们还没有被第二次读取。我比LRU好,而且是 adoptive to access 模式 。

    Two Queues(2Q):

    我是 Two Queues;我把被访问的数据放到 LRU 的缓存中,如果这个对象再一次被访问,我就把他转移到第二个、更大的 LRU 缓存。

    我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把 LRU 换成 LRU2,就比增加缓存的容量更好。这种机制使得我比 LRU2 更好,我也是 LRU 家族中的一员,而且是 adoptive to access 模式 。

    Adaptive Replacement Cache(ARC):

    我是 ARC,有人说我是介于 LRU 和 LFU 之间,为了提高效果,我是由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。所以,别人才会认为我是介于 LRU 和 LFU 之间的,不过没关系,我不介意。

    我被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。我也保存着历史对象,这样,我就可以记住那些被移除的对象,同时,也让我可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。我的记忆力很差,但是我很快,适用性也强。

    Most Recently Used(MRU):

    我是 MRU,和 LRU 是对应的。我会移除最近最多被使用的对象,你一定会问我为什么。好吧,让我告诉你,当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这就是为什么我是最好的选择。

    我是数据库内存缓存中是多么的常见!每当一次缓存记录的使用,我会把它放到栈的顶端。当栈满了的时候,你猜怎么着?我会把栈顶的对象给换成新进来的对象!

    First in First out(FIFO):

    我是先进先出,我是一个低负载的算法,并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。我很快,但是我并不适用。

    Second Chance:

    大家好,我是 second chance,我是通过 FIFO 修改而来的,被大家叫做 second chance 缓存算法,我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端,但是很FIFO的立刻踢出不同,我会检查即将要被踢出的对象有没有之前被使用过的标志(1一个 bit 表示),没有没有被使用过,我就把他踢出;否则,我会把这个标志位清除,然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时,由于他已经没有这个标志位了,所以我立刻就把他踢开了。我在速度上比 FIFO 快。

    CLock:

    我是 Clock,一个更好的 FIFO,也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部,但是也可以达到 second chance 的效果。

    我持有一个装有缓存对象的环形列表,头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时,我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0,我会直接用新的缓存对象替代这个缓存对象;如果标志位是1,我会把头指针递增,然后重复这个过程,知道新的缓存对象能够被放入。我比 second chance 更快。

    Simple time-based:

    我是 simple time-based 缓存算法,我通过绝对的时间周期去失效那些缓存对象。对于新增的对象,我会保存特定的时间。我很快,但是我并不适用。

    Extended time-based expiration:

    我是 extended time-based expiration 缓存算法,我是通过相对时间去失效缓存对象的;对于新增的缓存对象,我会保存特定的时间,比如是每5分钟,每天的12点。

    Sliding time-based expiration:

    我是 sliding time-based expiration,与前面不同的是,被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快,但是我也不太适用。

    其他的缓存算法还考虑到了下面几点:

    成本:如果缓存对象有不同的成本,应该把那些难以获得的对象保存下来。

    容量:如果缓存对象有不同的大小,应该把那些大的缓存对象清除,这样就可以让更多的小缓存对象进来了。

    时间:一些缓存还保存着缓存的过期时间。电脑会失效他们,因为他们已经过期了。

    根据缓存对象的大小而不管其他的缓存算法可能是有必要的。

    8.电子邮件!

    在读完这篇文章之后,programmer one 想了一会儿,然后决定给作者发封邮件,他感觉作者的名字在哪听过,但是已经想不起来了。不管怎样,他还是把邮件发送出来了,他询问了作者在分布式环境中,缓存是怎么样工作的。

    文章的作者收到了邮件,具有讽刺意味的是,这个作者就是面试 programmer one 的人 ,作者回复了……

    在这一部分中,我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的,如果你想自己实现缓存算法,可能自己还得加上一些额外的工作。

    9.LeftOver机制

    在 programmer one 阅读了文章之后,他接着看了文章的评论,其中有一篇评论提到了 leftover 机制——random cache。

    10.Random Cache

    我是随机缓存,我随意的替换缓存实体,没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为,我随意的去处缓存实体。我比 FIFO 机制好,在某些情况下,我甚至比 LRU 好,但是,通常LRU都会比我好。

    11.现在是评论时间

    当 programmer one 继续阅读评论的时候,他发现有个评论非常有趣,这个评论实现了一些缓存算法,应该说这个评论做了一个链向评论者网站的链接,programmer one顺着链接到了那个网站,接着阅读。

    看看缓存元素(缓存实体)

    public class CacheElement
    {
    private Object objectValue;
    private Object objectKey;
    private int index;
    private int hitCount; // getters and setters
    }

    这个缓存实体拥有缓存的key和value,这个实体的数据结构会被以下所有缓存算法用到。

    12.缓存算法的公用代码

    展开全文
  • 视频点播环境下的缓存算法研究
  • OpenGL深度缓存算法

    千次阅读 2016-03-15 20:23:31
    OpenGL深度缓存算法
            在OpenGL渲染过程中,深度测试对于多个物体之间的显示至关重要,如果不做适当处理,显示的结果将会与预期截然不容。所以深度缓存算法(depth buffer method)是一个比较常用的判别对象表面可见性的空间算法。它在投影面上的每一个像素位置比较场景中所有面的深度。该算法对场景各个对象表面单独进行处理,且在表面的逐点进行。该算法通常应用于只包含多边形面的场景,因为这些场景适合于很快地计算出深度值且算法易于实现,当然,该算法也可以应用于非平面的对象表面。由于通常沿着观察系统的z轴来计算对各对象距离观察平面的深度,因此该算法也成为z缓存(z-buffer)算法。但是,深度缓存算法通常会计算出沿着z轴从投影面到达对象表面点的距离来代替原场景中点的真实z坐标。
    展开全文
  • 如何用LinkedHashMap实现LRU缓存算法.pdf
  • 基于深度学习的视频缓存算法.pdf
  • 针对该场景, 在无线mesh网络架构下, 提出地空异构网络中无人机辅助的文件协作缓存算法. 其中, mesh路由器为主要缓存设备, 将缓存文件块作为缓存策略的基因, 采用遗传算法实现文件协作缓存, 减少用户请求文件的响应...
  • 最简单的一种缓存算法,设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 k-v 。 使用了一个对象作为缓存,一个数组配合着记录添加进对象时的顺序,判断是否到达上限,若到达上限取...
  • LTE移动网络的EPC和RAN协作缓存算法
  • 缓存算法和缓存策略的介绍

    万次阅读 2010-03-04 10:55:00
    缓存算法:缓存法通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。...
  • [转]缓存、缓存算法和缓存框架简介

    千次阅读 2016-03-09 12:44:58
    我们都听过 cache,当你问他们是什么是缓存的时候,他们会给你一个完美的答案,可是他们不知道缓存是怎么构建的,或者没有告诉你应该采用...在这边文章,我们会去讨论缓存,缓存算法,缓存框架以及哪个缓存框架会更好。
  • 缓存算法(页面置换算法)

    千次阅读 2017-05-30 13:22:23
    缓存算法是指令的一个明细表,用于提示计算设备的缓存信息中哪些条目应该被删去。常见类型包括LFU、LRU、ARC、FIFO、MRU。 最不经常使用算法(LFU, least frequently used):这个缓存算法使用一个计数器来...
  • LOCA:基于闪存的SSD的低开销缓存算法
  • 分布式虚拟环境中对等3D流的高效缓存算法
  • 没有人能说清哪种缓存算法由于其他的缓存算法。(以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下 ) Least Frequently Used(LFU): 大家好,我是 LFU,我会计算为每个缓存对象计算他们被...
  • 针对移动CCN中网络拓扑结构不断变化、缓存内容不断更替的特性,为了实现节点频繁移动时数据有效、可靠、较长时间缓存的目的,提出一套三模划分缓存算法。该算法基于节点位置信息,通过限定节点间通信距离阀值上限,将...
  • 自适应替换缓存 自适应替换缓存算法优于LRU
  • 常见缓存算法和缓存策略

    千次阅读 2013-01-10 11:40:28
    缓存算法:缓存法通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。...
  • 常用缓存算法简介

    2011-11-07 15:44:10
    没有人能说清哪种缓存算法优于其他的缓存算法。(以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下) Least Frequently Used(LFU): 大家好,我是 LFU,我会计算为每个缓存对象计算他们被...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 422,498
精华内容 168,999
关键字:

缓存算法