介绍：
很多人听说过"缓存“这个词，当你问他们什么是缓存的时候，他们能给你一个完美的答案，但是他们并不知道”缓存"是怎么构建的，也不知道应该以哪种标准去进行缓存框架的选择。在这篇文章里，我们要说说缓存，缓存算法和缓存框架，并且比较一下哪个更好一点。
面试：
“缓存是一个临时存放数据的地方(这些数据我经常用到)，因为获取原始的数据代价很高，所以缓存起来可以更快的获取数据。
这是面试中某程序员的回答。（一个月之前，他发了一封简历给一家公司，这家公司需要一个有丰富缓存、缓存框架、大规模数据处理经验的java程序员）
这个程序员以前用hashtable实现了一个缓存，hashtable是他唯一知道的缓存的知识，而他的hashtable存放着150条数据，这被他认为是大规模的数据:）
（caching == hashtable,把要查询的数据放在hashtable里面，这样就万无一失了）。下面来看看这个面试时怎么进行的。
面试官:很好，你依据什么标准来选择缓存系统。
某程序员:哈，(想了5分钟)，嗯。。依据，依据数据吧。（咳嗽。。。）
面试官：什么！你刚才说什么？
某程序员：数据？！
面试官：哦，明白了。好吧，列出几个缓存算法，然后告诉我都是什么原理。
某程序员：无辜的望着面试官，脸上露出一些奇怪的表情，一些没人知道的非人类的表情。
面试官：好吧。我换种方式问。如果达到缓存容量上限，那么缓存系统该怎么做？
某程序员：上限？嗯。（想。。。hashtable对容量没有限制啊，我可以往里面随意添加数据，hashtable会自动扩展容量的）（我想这应该是那个程序员的没说出来的想法）
面试官对那个程序员说了声谢谢(这次面试持续了仅10分钟)，然后一个女人过来说，哦，谢谢您大老远跑来，您回去等消息吧，我们会再联系您。慢走。
这是那个程序员最糟糕的一场面试。（他没有看到那个职位要求描述，要求上写着：要求求职者必须要用很强的缓存知识背景，而实际上他仅仅看到了那段“待遇优厚”的描述：））
说到做到：
当那个程序员离开后，他想去了解面试者到底说写啥，那些问题该怎么回到。所以他去上网。那程序员根本就知道啥缓存知识，想着：当我要缓存的时候，我用hashtable。
当用最喜欢的搜索引擎搜索后，他找到了一篇非常好的解释缓存的文章，开始读了起来。
为什么我们需要缓存？
在没缓存概念之前的很长一段时间，用户去请求一个对象，这个对象从存储系统里取出来。随着对象越来越大（多），用户需要花费越来越多的时间。
这使存储系统负担加重，因为他必须满负荷运转。而用户和数据库都相当的恼火，有两种可能的结果：
1--用户受不了了，抱怨甚至不再使用这个软件（很常见的情况）
2--存储系统受不了。down了。这是一个相当大的问题（没地方存数据了）（发生几率比较小）
缓存系统是上帝的馈赠：
在60年代，IBM的研究者经过多年的研究，引入了一个新的概念，命名为"Cache"
什么是缓存？
缓存命中率：
当客户端调用一个请求（我们假设他想看看产品信息），我们的程序响应了这个请求，程序需要访问存储系统（数据库）中的产品信息，首先它会去缓存检查
如果找到了一条与标签(比如说产品id)与所请求的数据匹配的记录，这条数据将被使用。这就是所说的缓存命中（缓存命中是衡量一个缓存系统有效性的主要指标，稍后我们会再谈谈）
缓存命中数占全部缓存请求的百分比，我们称之为命中率或者命中比。
缓存未命中：
相反，如果标签在缓存中没有找到（没有匹配的数据），这被叫做缓存没命中。这时候将向后端存储系统发送请求，取到数据后，它将被放在缓存中，将来的缓存请求可以找到,,并可以命中。
如果我们遇到一次缓存没命中，那么将可能出现以下两种情景：
情景1：缓存中有多余空间(缓存没有达到它的上限有多余空间)，这种情况下，没有命中缓存的那个对象将从存储系统的取回来，并插入到缓存中。
情景2：缓存已经没有剩余空间了（缓存已经达到容量上限了），这种情况下，没有命中缓存的那个对象将从存储系统的取回来，然后我们将决定缓存中哪一个记录需要被删掉，以便有空间容纳我们刚创建的那个对象（就是我们刚获取的），这个是由替换策略（缓存算法）来做的，它决定哪个记录被删掉以便腾出空间来。下面我们还会谈谈这个。
存储成本
当缓存没有命中时，从后端存储系统中获取的数据将被加载放入缓存中。但是这些我们刚获取的数据在缓存中需要多大空间呢？这就是所谓的存储成本了。
检索成本:
当我们需要去加载数据的时候，我们必须知道取这些数据要多长时间。这就是所谓的检索成本。
失效:
当缓存中的对象被更新了，比如说在后端存储系统中。那么这个对象需要被更新，让缓存保持最新就是所谓的失效。
缓存中的数据失效后，再次从后端存储系统从获取，这样就可以得到一个更新了的版本了。
替换策略:
当缓存没命中时，缓存排除一些对象以便为之前没有缓存的数据腾出空间（当没有足够空间的情况下），用来选择去除记录的启发式方法我们称之为替换策略。
最佳替换策略:
理论上的最佳页面替换策略（也叫做OPT或者比雷迪最佳替换策略）是一个算法，它试图达到以下目标：当一个可缓存的对象需要放到缓存中，缓存算法应该替换那个
将在最长时间之后才会被用到的缓存记录。
举个例子：一个10秒钟内不会被用到缓存记录将被一个在2秒内会用到的记录所替代。想想，对于最佳替换策略，我们可以说是不可能达到的，但是一些算法依据启发，能够做到接近最优化策略，那么所有的算法都基于启发式知识，那么是什么让一种算法优于另一种算法呢？他们又是怎么利用他们的启发式知识的呢？
java街上的噩梦:
当程序员1读这篇文章的时候，他睡着了，并且做了个噩梦（从来没有过的噩梦）
程序员1：哇哈哈，我要让你失效。（发疯似的说）
缓存对象：不，请不要让我离开，他们还需要我，我还有孩子。
程序员1：所有的缓存记录在他们要被失效的时候都这么说哦，那你什么时候有的孩子？不管了，现在就给我永远的消失吧。
霍哈哈，程序员1狂笑着，沉默了几分钟后，一个警察突然打破了平静，警察逮住了程序员1，他被逮捕了，因为他让一个还在被客户端使用的缓存记录失效了。他被送进了监狱。
程序员1醒了，他非常害怕，他看看周围，意识到这不过是一场梦，他继续读着“缓存”，试图排除恐惧。
缓存算法:
没人能说自己的缓存算法比别人的都好。
最不常使用 (LFU):
我是“最不常使用”；我通过增加一个计数器来统计缓存记录的使用频率。
我把用的最少的记录删掉，首先我不是很快，在自适应行为（意思是使用模型或者换句话说请求模型来保留那些真正需要的记录，而抛弃那些最久之后才用到的记录）中表现也不是很好。
最近最少使用 (LRU):
我是“最近最少使用”。
我是最近最少使用缓存算法；我会首先把那些最近用得最少的数据抛弃掉，也就是那个最长时间里没用到的记录。
我需要记录下什么缓存项什么时候被用到了，这个代价很高，如果它想确保我总是抛弃那些最近最少使用的缓存项。
浏览器把我用来做缓存。新记录被放到缓存最上面。当缓存到达它的上限时，我将被那些最下面抛弃掉。方法就是：只有是一个缓存项被访问了，我就把它放在最上面。
所以呢，最常用到的那些缓存项始终放在缓存里。有两种方式可以实现我，数组或者链表（这个把最少使用的放在尾，最常用的放在了头。）
我很快，而且我能自适应，换句话说我能针对根据数据访问模型进行调整，我有一个很大的家族，他们跟我竞争，他们甚至比我表现更好（有时候我很嫉妒，但是还好），他们中包括（LRU2和2Q）（他们都是用来改进LRU缓存算法的）
最近最少使用2(LRU2):
我是最近最少使用2，一些人叫我两次最近最少使用,我更喜欢这个叫法，在对象被第二次访问的时候，我会把它放到缓存中（对象需要被请求两次以便把它放到缓存中）；当缓存满了的时候，我移除那些两次最近最少使用的记录。因为需要记录2次最近访问，访问的开销随着缓存的大小而增长。如果我被用在一个大容量的缓存中，这将会是一个问题，也会成为缺点。此外，我还必须记录那些没在缓存中的记录（他们还没被访问两次）。我比最近最少使用要好，我也能适用访问模型。
-Two Queues:
I
am Two Queues; I add entries to an LRU cache as they are accessed. If
an entry is accessed again, I move them to second, larger, LRU cache.
I
remove entries a so as to keep the first cache at about 1/3 the size of
the second. I provide the advantages of LRU2 while keeping cache access
overhead constant, rather than having it increase with cache size.
Which makes me better than LRU2 and I am also like my family, am
adaptive to access patterns.
Adaptive Replacement Cache (ARC):
I
am Adaptive Replacement Cache; some people say that I balance between
LRU and LFU, to improve combined result, well that’s not 100% true
actually I am made from 2 LRU lists, One list, say L1, contains entries
that have been seen only once “recently”, while the other list, say L2,
contains entries that have been seen at least twice “recently”.
The
items that have been seen twice within a short time have a low
inter-arrival rate, and, hence, are thought of as “high-frequency”.
Hence, we think of L1as capturing “recency” while L2 as capturing
“frequency” so most of people think I am a balance between LRU and LFU
but that is ok I am not angry form that.
I am considered one of
the best performance replacement algorithms, Self tuning algorithm and
low overhead replacement cache I also keep history of entries equal to
the size of the cache location; this is to remember the entries that
were removed and it allows me to see if a removed entry should have
stayed and we should have chosen another one to remove.(I really have
bad memory)And yes I am fast and adaptive.
Most Recently Used (MRU):
I
am most recently used, in contrast to LRU; I remove the most recently
used items first. You will ask me why for sure, well let me tell you
something when access is unpredictable, and determining the least most
recently used entry in the cache system is a high time complexity
operation, I am the best choice that’s why.
I am so common in
the database memory caches, whenever a cached record is used; I replace
it to the top of stack. And when there is no room the entry on the top
of the stack, guess what? I will replace the top most entry with the
new entry.
First in First out (FIFO):
I
am first in first out; I am a low-overhead algorithm I require little
effort for managing the cache entries. The idea is that I keep track of
all the cache entries in a queue, with the most recent entry at the
back, and the earliest entry in the front. When there e is no place and
an entry needs to be replaced, I will remove the entry at the front of
the queue (the oldest entry) and replaced with the current fetched
entry. I am fast but I am not adaptive
先进先出 (FIFO):
我是先进先出，我是个低消耗算法，只需要做一点点工作就管理好缓存记录。想法就是把缓存记录存在一个队列中。把最近使用的放在后面，把最久未使用的放在前面，当缓存没空间，记录需要被替换的时候，我就把队列前面的(最老的那个记录)删掉，并用刚获取的数据替换，我很快，但是不能自适应。
译者注：下面几种算法用的比较少，不翻译了。
-Second Chance:
Hello
I am second change I am a modified form of the FIFO replacement
algorithm, known as the Second chance replacement algorithm, I am
better than FIFO at little cost for the improvement. I work by looking
at the front of the queue as FIFO does, but instead of immediately
replacing the cache entry (the oldest one), i check to see if its
referenced bit is set(I use a bit that is used to tell me if this entry
is being used or requested before or no). If it is not set, I will
replace this entry. Otherwise, I will clear the referenced bit, and
then insert this entry at the back of the queue (as if it were a new
entry) I keep repeating this process. You can think of this as a
circular queue. Second time I encounter the same entry I cleared its
bit before, I will replace it as it now has its referenced bit cleared.
am better than FIFO in speed
-Clock:
I am
Clock and I am a more efficient version of FIFO than Second chance
because I don’t push the cached entries to the back of the list like
Second change do, but I perform the same general function as
Second-Chance.
I keep a circular list of the cached entries in
memory, with the "hand" (something like iterator) pointing to the
oldest entry in the list. When cache miss occurs and no empty place
exists, then I consult the R (referenced) bit at the hand's location to
know what I should do. If R is 0, then I will place the new entry at
the "hand" position, otherwise I will clear the R bit. Then, I will
increment the hand (iterator) and repeat the process until an entry is
replaced.I am faster even than second chance.
Simple time-based:
I
am simple time-based caching; I invalidate entries in the cache based
on absolute time periods. I add Items to the cache, and they remain in
the cache for a specific amount of time. I am fast but not adaptive for
access patterns
Extended time-based expiration:
I
am extended time based expiration cache, I invalidate the items in the
cache is based on relative time periods. I add Items the cache and they
remain in the cache until I invalidate them at certain points in time,
such as every five minutes, each day at 12.00.
Sliding time-based expiration:
I
am Sliding time-base expiration, I invalidate entries a in the cache by
specifying the amount of time the item is allowed to be idle in the
cache after last access time. after that time I will invalidate it . I
am fast but not adaptive for access patterns
Ok after we listened
to some replacement algorithms (famous ones) talking about themselves,
some other replacement algorithms take into consideration some other
criteria like:
Cost: if items have different costs, keep those items that are expensive to obtain, e.g. those that take a long time to get.
Size: If items have different sizes, the cache may want to discard a large item to store several smaller ones.
Time:
Some caches keep information that expires (e.g. a news cache, a DNS
cache, or a web browser cache). The computer may discard items because
they are expired. Depending on the size of the cache no further caching
algorithm to discard items may be necessary.
The E-mail!
After
programmer 1 did read the article he thought for a while and decided to
send a mail to the author of this caching article, he felt like he
heard the author name before but he couldn’t remember who this person
was but anyway he sent him mail asking him about what if he has a
distributed environment? How will the cache behave?
The author of
the caching article got his mail and ironically it was the man who
interviewed programmer 1 :D, The author replied and said :
分布式缓存系统:
*缓存的数据能存放在一个独立的缓存空间里，跟缓存目录（用来处理缓存记录。。）分开，能通过网络访问。.比如说磁盘。
*缓存分布允许增加缓存的大小。.
*这种情况下（译者注：增加缓存大小）获取数据的成本会增加，网络请求时间也会增加获取数据的成本。.
*这样也会使缓存命中率增加，因为有了更大的缓存。
但是分布式缓存怎么工作的呢？
假设我们有3台服务器，其中的两台被用来处理分布式缓存，第三台处理所有的请求（访问缓存的请求）。
Step
1:程序请求关键字entry1,entry2,entry3。在分析这些记录的hash值依据这些hash值，将决定把请求发往合适的缓存服务器。
Step 2: 主节点发送并行请求给所有相关的服务器（他们有我们要找的缓存记录）
Step 3: 缓存服务器返回结果给主节点（在第一个地方发送缓存请求的那个）
Step 4: 主节点发送响应给应用程序（缓存客户端）。
*如果缓存没有找到 (记录的hash值将被重定向发给服务器1或者2。这种情况下，我们要的记录在服务器1上找不到，那么它将从数据库中获取，然后加到服务器1的缓存列表中。
大部分的缓存依据命中率和与理论上的最佳算法来评价，这个通常通过产生一个没有真实数据的缓存关键字列表来做到。但是这里命中率的评价都假设所有的记录都有相同的检索成本，这往往不是实际情况，比如在Web缓存中，缓存能缓存的数据量比缓存命中率重要（比如，我能用10个小的记录来替换一个大的记录，在Web上，这往往更有效率）
