缓存算法
写在前面
来自： http://www.leexiang.com/cache-algorithm
原文： http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html
译者： http://www.zavakid.com/25
引言
我们都听过 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组成：第一个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的立刻踢出不同，我会检查即将要被踢出的对象有没有之前被使用过的标志(用一个 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，与前面不同的是，我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的(如果缓存对象X超过Y秒未被访问，则失效)。我很快，但是我也不太适用。
Random Cache
我是随机缓存，我随意的替换缓存对象，没人敢抱怨。你可以说那个被替换的对象很倒霉。通过这些行为，我随意地去除缓存对象。我比FIFO机制好，在某些情况下，我甚至比LRU好，但是，通常LRU都会比我好。
缓存算法还需要考虑到以下几点
1.成本：如果获取一个缓存对象需要不同的成本，那么应该把那些难以获得的对象缓存下来。
2.容量：如果缓存对象的大小不同，那么应该把那些大缓存对象清除，这样就可以让更多的小缓存对象进来了。
3.时间：一些缓存还保存着缓存的过期时间。应该自动失效它们，因为它们已经过期了。