Tag Archives: 缓存

上一节中我们实现了随机缓存算法和FIFO缓存算法。现在，我们会继续实现另外两个著名的缓存算法：LFU和LRU。再一次说明，这些代码只是作为演示使用，如果你想在应用程序中使用，你还需要加上额外的工作。 看看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) … Continue reading →

在这一部分中，我们来看看如何实现这些著名的缓存算法。以下的代码只是示例用的，如果你想自己实现缓存算法，可能自己还得加上一些额外的工作。 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，这个实体的数据结构会被以下所有缓存算法用到。 … Continue reading →

接着之前的 part 2：http://www.zavakid.com/26 在programmer one 醒来之后，他又开始阅读文章了。 缓存算法 没有人能说清哪种缓存算法由于其他的缓存算法。（以下的几种缓存算法，有的我也理解不好，如果感兴趣，你可以Google一下 ） 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 … Continue reading →

接着之前的文章：有关缓存,缓存算法,缓存框架:part 1 为什么我们需要缓存？ 很久很久以前，在还没有缓存的时候……用户经常是去请求一个对象，而这个对象是从数据库去取，然后，这个对象变得越来越大，这个用户每次的请求时间也越来越长了，这也把数据库弄得很痛苦，他无时不刻不在工作。所以，这个事情就把用户和数据库弄得很生气，接着就有可能发生下面两件事情： 用户很烦，在抱怨，甚至不去用这个应用了（这是大多数情况下都会发生的） 数据库为打包回家，离开这个应用，然后，就出现了大麻烦（没地方去存储数据了）（发生在极少数情况下） 上帝派来了缓存 在几年之后，IBM（60年代）的研究人员引进了一个新概念，它叫“缓存”。 什么是缓存？ 正如 part 1 的开头，缓存是“存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。” 缓存可以认为是数据的池，这些数据是从数据库里的真实数据复制出来的，并且为了能别取回，被标上了标签（键ID）。 太棒了！programmer one已经知道这点了，但是他还不知道下面的缓存术语。 点击观看大图 命中： 当客户发起一个请求（我们说他想要查看一个产品信息），我们的应用接受这个请求，并且如果是在第一次检查缓存的时候，需要去数据库读取产品信息。 如果在缓存中，一个条目通过一个标记被找到了，这个条目就会被使用，我们就叫它缓存命中。所以，命中率也就不难理解了。 Cache Miss： （这个Cahe Miss不知道用什么词翻译合适，但是大家都知道的）。但是这里需要注意两点： 如果还有缓存的空间，那么，没有命中的对象会被存储到缓存中来。 如果缓存慢了，而又没有命中缓存，那么就会按照某一种策略，把缓存中的旧对象踢出，而把新的对象加入缓存池。而这些策略统称为替代策略（缓存算法），这些策略会决定到底应该提出哪些对象。 存储成本： 当没有命中时，我们会从数据库取出数据，然后放入缓存。而把这个数据放入缓存所需要的时间和空间，就是存储成本。 索引成本： 和存储成本想法。 失效： 当存在缓存中的数据需要更新时，就意味着缓存中的这个数据失效了。 替代策略： 当缓存没有命中时，并且缓存容量已经满了，就需要在缓存中踢出一个老的条目，加入一条新的条目，而到底应该踢出什么条目，就由替代策略决定。 最有替代策略： 最优的替代策略就是想把缓存中最没用的条目给踢出去，但是未来是不能够被预知的，所以这种策略是不可能实现的。但是有很多策略，都是朝着这个目前去努力。 Java街恶梦： 当programmer one在读这篇文章的时候，他睡着了，并且做了个恶梦（每个人都有做恶梦的时候）。 programmer … Continue reading →