cache 的设计与实现 本文整理自一下两篇博客：http://my.oschina.net/ScottYang/blog/298727 http://my.oschina.net/u/866190/blog/188712
Cache简介：
Cache(高速缓存)， 一个在计算机中几乎随时接触的概念。CPU中Cache能极大提高存取数据和指令的时间，让整个存储器(Cache+内存)既有Cache的高速度，又能有内存的大容量；操作系统中的内存page中使用的Cache能使得频繁读取的内存磁盘文件较少的被置换出内存，从而提高访问速度。Cache的算法设计常见的有FIFO(first in first out，先进先出)、LRU(least recently used，最近最少使用)和LFU（Least Frequently userd，最不经常使用)。
- LRU(Least Recently Used ，最近最少使用) ―― 删除最久没有被使用过的数据
算法根据数据的最近访问记录来淘汰数据，其原理是如果数据最近被访问过，将来被访问的几概率相对比较高，最常见的实现是使用一个链表保存缓存数据，详细具体算法如下：
1. 新数据插入到链表头部；
2. 每当缓存数据命中，则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃；
- LFU(Least Frequently Used，最不经常使用) ―― 删除使用次数最少的的数据
1. 新加入数据插入到队列尾部（因为引用计数为1）；
2. 队列中的数据被访问后，引用计数增加，队列重新排序；
3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除；
- FIFO(First In First Out ，先进先出)
1. 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；
2. 淘汰FIFO队列头部的数据；
评价一个缓存算法好坏的标准主要有两个，一是命中率要高，二是算法要容易实现。当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的"缓存污染"效用。FIFO虽然实现很简单，但是命中率很低，实际上也很少使用这种算法。
面试题：Google和百度的面试题都出现了设计一个Cache的题目，什么是Cache，如何设计简单的Cache
- 解题思路：
Cache中的存储空间往往是有限的，当Cache中的存储块被用完，而需要把新的数据Load进Cache的时候，我们就需要设计一种良好的算法来完成数据块的替换。LRU的思想是基于"最近用到的数据被重用的概率比较早用到的大的多"这个设计规则来实现的。
为了能够快速删除最久没有访问的数据项和插入最新的数据项，我们双向链表连接Cache中的数据项，并且保证链表维持数据项从最近访问到最旧访问的顺序。每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度）。这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没有被使用的内容就向链表的后面移动。当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部，当Cache满时，淘汰链表最后的位置就是了。
注： 对于双向链表的使用，基于两个考虑。首先是Cache中块的命中可能是随机的，和Load进来的顺序无关。其次，双向链表插入、删除很快，可以灵活的调整相互间的次序，时间复杂度为O(1)。
查找一个链表中元素的时间复杂度是O(n)，每次命中的时候，我们就需要花费O(n)的时间来进行查找，如果不添加其他的数据结构，这个就是我们能实现的最高效率了。目前看来，整个算法的瓶颈就是在查找这里了，怎么样才能提高查找的效率呢？Hash表，对，就是它，数据结构中之所以有它，就是因为它的查找时间复杂度是O(1)。
梳理一下思路：对于Cache的每个数据块，我们设计一个数据结构来储存Cache块的内容，并实现一个双向链表，其中属性next和prev时双向链表的两个指针，key用于存储对象的键值，value用户存储要cache块对象本身。
- Cache的接口：
查询：
- 根据键值查询hashmap，若命中，则返回节点，否则返回null。
- 从双向链表中删除命中的节点，将其重新插入到表头。
- 所有操作的复杂度均为O(1)。
插入：
- 将新的节点关联到Hashmap
- 如果Cache满了，删除双向链表的尾节点，同时删除Hashmap对应的记录
- 将新的节点插入到双向链表中头部
更新：
删除：
- 从双向链表和Hashmap中同时删除对应的记录。
- 实现方式
参考实现：Apache jcs
1）首先我们需要一个双向链表，自然地，我们需要定义双向链表的节点：DoubleLinkListNode，DoubleLinkList
// 双向链表节点 public class DoubleLinkListNode implements Serializable{ private Object value; public DoubleLinkListNode next; public DoubleLinkListNode prev; DoubleLinkListNode(Object value){ this.value = value; } public Object getValue() { return value; } }
对于 DoubleLinkList ,我们需要同步对节点的各种读写操作：
public class DoubleLinkList { private int size = 0; private DoubleLinkListNode first; private DoubleLinkListNode last; public DoubleLinkList(){ super(); } // 在链表的尾部的插入一个节点 public synchronized void addLast(DoubleLinkListNode me){ if (first == null) { first = me; }else{ last.next = me; me.prev = last; } last = me; size++; } // 在链表的头部插入一个节点 public synchronized void addFirtst(DoubleLinkListNode me){ if (last == null) { last = me; }else{ first.next = me; me.prev = first; } first = me; size++; } // 获取尾节点 public synchronized DoubleLinkListNode getLast(){ return last; } // 获取头结点 public synchronized DoubleLinkListNode getFirst(){ return first; } // 删除链表指定节点（这个节点一定在链表中） public synchronized boolean remove(DoubleLinkListNode me){ if(me.next == null){ //删除尾节点 if (me.prev == null) { // Make sure it really is the only node before setting head and // tail to null. It is possible that we will be passed a node // which has already been removed from the list, in which case // we should ignore it if ( me == first
没有评论:
发表评论