“缓存就是存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。”
这就是programmerone（programmerone是一个面试者）在面试中的回答（一个月前，他向公司提交了简历，想要应聘要求在缓存，缓存框架，大规模数据操作有着丰富经验的java开发职位）。
programmerone通过hashtable实现了他自己的缓存，但是他知道的只是他的缓存和他那存储着150条记录的hashtable，这就是他认为的大规模数据（缓存=hashtable，只需要在hashtable查找就好了），所以，让我们来看看面试的过程吧。
面试官：你选择的缓存方案，是基于什么标准的？
programmerone：呃，（想了5分钟）嗯，基于，基于，基于数据（咳嗽……）
面试官：exceseme!能不能重复一下？
programmerone：数据？！
面试官：好的。说说几种缓存算法以及它们的作用
programmerone：（凝视着面试官，脸上露出了很奇怪的表情，没有人知道原来人类可以做出这种表情）
面试官：好吧，那我换个说法，当缓存达到容量时，会怎么做？
programmerone：容量？嗯（思考……hashtable的容量时没有限制的，我能任意增加条目，它会自动扩充容量的）（这是programmerone的想法，但是他没有说出来）
说到做到
programmerone离开之后，他想要知道这个面试者说的问题和答案，所以他上网去查，programmerone对缓存一无所知，除了：当我需要缓存的时候，我就会用hashtable。
为什么我们需要缓存？
１.用户很烦，在抱怨，甚至不去用这个应用了（这是大多数情况下都会发生的）
２.数据库为打包回家，离开这个应用，然后，就出现了大麻烦（没地方去存储数据了）（发生在极少数情况下）
上帝派来了缓存
在几年之后，IBM（60年代）的研究人员引进了一个新概念，它叫“缓存”。
什么是缓存？
正如开篇所讲，缓存是“存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。”
缓存可以认为是数据的池，这些数据是从数据库里的真实数据复制出来的，并且为了能别取回，被标上了标签（键ID）。太棒了
programmerone已经知道这点了，但是他还不知道下面的缓存术语。
命中：
当客户发起一个请求（我们说他想要查看一个产品信息），我们的应用接受这个请求，并且如果是在第一次检查缓存的时候，需要去数据库读取产品信息。
如果在缓存中，一个条目通过一个标记被找到了，这个条目就会被使用、我们就叫它缓存命中。所以，命中率也就不难理解了。
CacheMiss：
但是这里需要注意两点：
１.如果还有缓存的空间，那么，没有命中的对象会被存储到缓存中来。
２.如果缓存慢了，而又没有命中缓存，那么就会按照某一种策略，把缓存中的旧对象踢出，而把新的对象加入缓存池。而这些策略统称为替代策略（缓存算法），这些策略会决定到底应该提出哪些对象。
存储成本：
索引成本：
和存储成本相仿。
失效：
当存在缓存中的数据需要更新时，就意味着缓存中的这个数据失效了。
替代策略：
当缓存没有命中时，并且缓存容量已经满了，就需要在缓存中踢出一个老的条目，加入一条新的条目，而到底应该踢出什么条目，就由替代策略决定。
最优替代策略：
最优的替代策略就是想把缓存中最没用的条目给踢出去，但是未来是不能够被预知的，所以这种策略是不可能实现的。但是有很多策略，都是朝着这个目前去努力。
Java街恶梦：
programmerone：nihahha，我要把你弄失效！（疯狂的状态）
缓存对象：别别，让我活着，他们还需要我，我还有孩子。
programmerone：每个缓存对象在失效之前都会那样说。你从什么时候开始有孩子的？不用担心，现在就永远消失吧！
哈哈哈哈哈……programmerone恐怖的笑着，但是警笛打破了沉静，警察把programmerone抓了起来，并且控告他杀死了（失效）一个仍需被使用的缓存对象，他被押到了监狱。
缓存算法
没有人能说清哪种缓存算法优于其他的缓存算法
LeastFrequentlyUsed（LFU）：
大家好，我是LFU，我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。
LeastRecentlyUser（LRU）：
我是LRU缓存算法，我把最近最少使用的缓存对象给踢走。
我总是需要去了解在什么时候，用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉，是非常困难的。
浏览器就是使用了我（LRU）作为缓存算法。新的对象会被放在缓存的顶部，当缓存达到了容量极限，我会把底部的对象踢走，而技巧就是：我会把最新被访问的缓存对象，放到缓存池的顶部。
所以，经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我，array或者是linkedlist。
我的速度很快，我也可以被数据访问模式适配。我有一个大家庭，他们都可以完善我，甚至做的比我更好（我确实有时会嫉妒，但是没关系）。我家庭的一些成员包括LRU2和2Q，他们就是为了完善LRU而存在的。
LeastRecentlyUsed2（LRU2）：
我是LeastRecentlyUsed2，有人叫我最近最少使用twice，我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池，当缓存池满了之后，我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次，访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中，就会有问题。另外，我还需要跟踪那么不在缓存的对象，因为他们还没有被第二次读取。我比LRU好，而且是adoptivetoaccess模式。
TwoQueues（2Q）：
我是TwoQueues；我把被访问的数据放到LRU的缓存中，如果这个对象再一次被访问，我就把他转移到第二个、更大的LRU缓存。
我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候，把LRU换成LRU2，就比增加缓存的容量更好。这种机制使得我比LRU2更好，我也是LRU家族中的一员，而且是adoptivetoaccess模式。
AdaptiveReplacementCache（ARC）：
我是ARC，有人说我是介于LRU和LFU之间，为了提高效果，我是由2个LRU组成，第一个，也就是L1，包含的条目是最近只被使用过一次的，而第二个LRU，也就是L2，包含的是最近被使用过两次的条目。因此，L1放的是新的对象，而L2放的是常用的对象。所以，别人才会认为我是介于LRU和LFU之间的，不过没关系，我不介意。
我被认为是性能最好的缓存算法之一，能够自调，并且是低负载的。我也保存着历史对象，这样，我就可以记住那些被移除的对象，同时，也让我可以看到被移除的对象是否可以留下，取而代之的是踢走别的对象。我的记忆力很差，但是我很快，适用性也强。
MostRecentlyUsed（MRU）：
我是数据库内存缓存中是多么的常见！每当一次缓存记录的使用，我会把它放到栈的顶端。当栈满了的时候，你猜怎么着？我会把栈顶的对象给换成新进来的对象！
FirstinFirstout（FIFO）：
我是先进先出，我是一个低负载的算法，并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象，最近最常用的缓存对象放在后面，而更早的缓存对象放在前面，当缓存容量满时，排在前面的缓存对象会被踢走，然后把新的缓存对象加进去。我很快，但是我并不适用。
SecondChance：
大家好，我是secondchance，我是通过FIFO修改而来的，被大家叫做secondchance缓存算法，我比FIFO好的地方是我改善了FIFO的成本。我是FIFO一样也是在观察队列的前端，但是很FIFO的立刻踢出不同，我会检查即将要被踢出的对象有没有之前被使用过的标志（1一个bit表示），没有没有被使用过，我就把他踢出；否则，我会把这个标志位清除，然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时，由于他已经没有这个标志位了，所以我立刻就把他踢开了。我在速度上比FIFO快。
CLock：
我是Clock，一个更好的FIFO，也比secondchance更好。因为我不会像secondchance那样把有标志的缓存对象放到队列的尾部，但是也可以达到secondchance的效果。
我持有一个装有缓存对象的环形列表，头指针指向列表中最老的缓存对象。当缓存miss发生并且没有新的缓存空间时，我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0，我会直接用新的缓存对象替代这个缓存对象；如果标志位是1，我会把头指针递增，然后重复这个过程，知道新的缓存对象能够被放入。我比secondchance更快。
Simpletime-based：
Extendedtime-basedexpiration：
Slidingtime-basedexpiration：
其他的缓存算法还考虑到了下面几点：
成本：如果缓存对象有不同的成本，应该把那些难以获得的对象保存下来。
容量：如果缓存对象有不同的大小，应该把那些大的缓存对象清除，这样就可以让更多的小缓存对象进来了。
根据缓存对象的大小而不管其他的缓存算法可能是有必要的。
电子邮件！
在这一部分中，我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的，如果你想自己实现缓存算法，可能自己还得加上一些额外的工作。
LeftOver机制
RandomCache
我是随机缓存，我随意的替换缓存实体，没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为，我随意的去处缓存实体。我比FIFO机制好，在某些情况下，我甚至比LRU好，但是，通常LRU都会比我好。
每当我们讨论缓存时，总是会对如下几个词比较熟悉，
Write-back,write-through,write-around
似乎，缓存主要是为“写”设计的，其实这是错误的理解，写从缓存中获得的好处是非常有限的，缓存主要是为“读”服务的。
之所以我们要顺带提一下，在一个缓存系统中，如何处理写的顺序，是因为，在写的过程中，需要动态的更新缓存（否则就会产生数据不一致性的问题），以及后端主存。这三个词都是用来表示如何处理写更新的。就是用什么方式来处理写。
在一个有缓存的层次结构中，如何理解缓存是为“读”服务的？这涉及到读请求的处理序列。对于每一个读请求，我们都会用如下的操作序列去处理它：
1.在缓存中查找请求对应的数据
a.如果找到，则直接返回给客户
b.如果没找到，则把请求的数据读入缓存（更新缓存），然后把数据返回给客户
那么我们来想想，在设计缓存时，我们应该从哪几方面考虑来达到这个缓存的设计目标呢？根据我们上面提到的读请求的操作序列，我们可以从如下几个方面来思考：
1.我们应该尽量多的用有用的数据填满缓存。也就是说，我们要充分利用缓存。
a.这是缓存模块和其它模块不同的地方，并不是说缓存中的数据越少越好，而是有用的数据越多越好。
b.这里有个非常好的列子，就是Windows的内存占用率总是非常高，很多人都表示过不满。其实这是一个非常好的设计。Windows总是试图尽量利用那些空闲的内存，用来缓存磁盘上的数据，以此来提高系统的整体性能。否则你那么大的内存，就为了拿来好看？
2.如何获取“有用”的数据。这里，“有用”的数据的定义就是可能在不久的将来会被client用到的数据。为了得到有用的数据，我们需要预估客户端应用的I/O模式，比如顺序读写，随机读写等等。这里就涉及到了“pre-fetch”算法。
a.Pre-fetch（预取算法）：是一种预测客户端应用下次读写的数据在哪里的算法，并且把客户要用的数据提前放入缓存中，以此来提高读的响应速度。
3.问题来了，如果缓存已经满了，那么如何存放新的需要缓存的单元呢？这就牵涉到缓存设计的另一端：淘汰算法。
a.相比于pre-fetch，淘汰算法（replacementpolicy）更加重要。因为对于随机的I/O，预取算法是无能为力的。
b.淘汰算法的关键是如何判断一个单元的数据比另一个单元的数据更加重要。但需要淘汰一个数据单元时，丢弃掉最不重要的那个数据单元，并且用它来存放新的数据。
4.缓存算法设计的另外一个重要的考虑因素是算法的复杂度。或者说是实现或运行算法带来的额外开销。我们希望算法容易实现，并且额外开销不随着缓存大小的改变而改变。包括容量的额外开销和计算的额外开销。
a.LRU（leastrecentlyused）：这种策略就是永远替换掉最近最少使用的缓存单元。它是最古老，应用最广泛的的一种淘汰算法。它的致命的缺陷就是没有考虑缓存单元的使用频率，在某些I/O模式中，会把一些有价值的缓存单元替换出去。比如，假设我们有10个缓存单元，客户端应用来了一次顺序读写，这样可能把这10个现有的缓存单元替换出去，而把这次顺序读写的数据缓存起来。但是，这种顺序读写的数据在以后都不会被再次用到。反而，那些因为顺序读而被替换出去的缓存单元却是更有价值的。为此，有了各种各样的基于LRU的优化策略被提出来。
2.频率（完全从使用频率的角度考虑）
a.LFU（leastfrequentlyused）:IRM(独立的引用模型)提供了一种用来获取频率的负载特性。它趋向于淘汰最近使用频率最少的缓存单元。这种策略的弊端是：
i.它的实现复杂度于缓存大小成对数关系（logarithmic）;
ii.对最近的缓存单元的访问情况基本没考虑；
iii.对访问模式的改变基本上没有应变的策略。
3.LRU-2（LRU-K）：一种对LRU的改进型策略（频率）
b.但是LRU-2也有一些实际的限制：
i.它需要维护一个优先级队列。也就是说它具有对数的实现复杂度；
ii.它需要一个可调参数：CIP（correlatedinformationperiod）。
c.在现实中，对数的实现复杂度是一个非常严重的overhead（负担）。所以另外一个策略2Q被提了出来。
4.2Q：对LRU-2的改进策略（频率）
a.相对于LRU-2，2Q的主要改进是用一个简单的LRUlist取代了LRU-2中的优先级队列。其它的2Q和LRU-2基本相同。
b.但是在2Q中，LRU-2的第二个不足还是存在，并且更严重了。因为它需要两个可调参数：Kin和Kout。
c.为什么可调参数一个很严重的限制？这是我们在实施一个系统时，必须确定这些参数，而且不可更改。一旦确定了一组参数，这个缓存系统往往只能对某一类workload表现很好。也就是这种缓存系统缺少了自适应性。
5.LIRS（LowInter-referenceRecencySet）（频率）
a.详细描述参考：“LIRS：Anefficientlowinter-referencerecencysetreplacementpolicytoimprovebuffercacheperformance”
b.第一个不足在于需要两个可调参数Llirs和Lhirs；
c.它的第二个缺点在于，在最坏的情况下，它需要一个“栈修剪”。这个操作需要遍历数量庞大的缓存单元。
a.FBR（Frequency-basedreplacement）:详细描述请参考“Datacachemanagementusingfrequency-basedreplacement”。这个算法的不足之处在于：
ii.Cachepollution（解决cache污染的机制）
b.LRFU（LeastRecently/FrequentlyUsed）:参考“LRFU：Aspectrumofpoliciesthatsubsumestheleastrecentlyusedandleastfrequentlyusedpolicies”
c.ALRFU(adaptiveLRFU):参考“Ontheexistenceofaspectrumofpoliciesthatsubsumestheleastrecentlyusedandleastfrequentlyusedpolicies”
7.临时距离分布（Temporaldistancedistribution）
a.MQ(multi-queuereplacementpolicyMQ):参考“Themulti-queuereplacementalgorithmforsecondlevelbuffercaches”
8.ARC:adaptivereplacementcache(IBM),adjustedreplacementcache(ZFS)
a.一种自适应，低成本的淘汰算法
b.它集合了LRU和LFU的优点，并且没有额外的使用和实现成本。