艺多不压身 -- 常用缓存Cache机制的实现

`常用缓存Cache机制的实现`

缓存，就是将程序或系统经常要调用的对象存在内存中，以便其使用时可以快速调用，不必再去创建新的重复的实例。这样做可以减少系统开销，提高系统效率。

缓存主要可分为二大类:

　　一、通过文件缓存,顾名思义文件缓存是指把数据存储在磁盘上，不管你是以XML格式，序列化文件DAT格式还是其它文件格式

　　二、内存缓存，也就是实现一个类中静态Map,对这个Map进行常规的增删查.

Java实现cache的基本机制

　　我这里说的cache不是指CPU和RAM之间的缓存，而是Java应用中间常用的缓存。最常使用的场合就是访问数据库的时候为了提高效率而使用的 cache。一般的用法就是把数据从数据库读到内存，然后之后的数据访问都从内存来读，从而减少对数据库的读取次数来提高效率。

　　在使用cache的时候最容易犯的错误就是cache涉及了业务逻辑。使用cache的原意是只是提高程序效率，而不应该干涉程序结果。按照cahce的定义，cache应该是对数据访问端透明地工作。所以在使用cache的时候我们可以问一下自己：“我把cache拿掉后程序还能运行吗？” “cache拿掉前后程序运行的结果一直吗？”。如果答案是否，那您就得重新考虑您的cache方案。常见bug：数据库的有个表里面都是些配置信息，也就是说是些读访问远大于写访问 的数据。然后这些数据被理所应当地在程序里面做成内存 cache。问题是有个delete方法删除了一条数据，但是没有更新内存cache。所以读操作的客户代码还是能读到这条数据。问题的根本就是后台数据和cache不一致。

cache的容量一般相对后台数据量都比较有限。一旦cache满了就势必要选择最没用的数据从cache里面删除掉，为新数据腾出空间。这里就涉及 cahce算法cache algorithm或者叫替换算法。在java的cache产品中一般叫evict policy。下面我们来看一下常用的cache algorithm。

最近最少使用算法 Least Recently Used (LRU):

这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。最直观的结构应该是List，采取的算法是：每次访问一个元素后把这个元素放在 List一端，这样一来最远使用的元素自然就被放到List的另一端。每次evict的时候就把那最远使用的元素remove掉。但是现实中常采用的数据结构是HashMap + List。因为List太慢，List只能提供O(n)的算法，要使得它的add，remove和get的算法为O(1)就必须使用HashMap。最简单的实现就是利用JDK自带的LinkedHashMap，你可以把它看作普通的HashMap之外，每个元素的key都用链表连接起来从而实现顺序结构。LinkedHashMap默认的元素顺序是put的顺序，但是如果使用带参数的构造函数，那么LinkedHashMap会根据访问顺序来调整内部顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端，这样一来每次顶端的元素就是remove的元素。

First In, First Out算法

这个比较直观，就是个Queue。但是还是为了保证O(1)的效率，还是要用LinkedHashMap。但是这次使用默认的无参数的构造函数，LinkedHashMap内部使用的是put的顺序。因此每次remove顶端即可。

最近最多时用算法Most Recently Used (MRU)

这个算法和LRU是相反操作，所以没什么新鲜的东西。每次remove LinkedHashMap底端的元素就可以实现。

使用次数最小算法 Least Frequently Used (LFU)

这个算法的核心是每次访问元素的时候，这个元素的次数属性加1。所以每次remove操作就是次数属性最小的元素。这次没法用LinkedHashMap来实现了，因为LinkedHashMap没有接受comparator参数的功能。有些程序是用LinkedList + HashMap来实现。这样add和get操作还是O(1)，只是remove操作的时候先要排序然后再remove，最快也就是O(n*log n)，譬如利用快速排序。或者干脆在remove的时候只是做查找最小元素的算法来除去访问次数最小的元素。

另外还有其他的cache算法，譬如按照元素自带的过期值expiration和随机random来evict元素的算法。在真正的cache产品中数据结构和算法要比上面描述的要复杂。有些产品自己定义一些数据结构来提高效率，毕竟cache是为了提高效率而产生的。高级的cache产品还可能包括事务机制，JMX和支持cluster环境这样复杂的特性。

目前比较主流的cache产品有EHCache，OSCache，SwarmCache和JBoss Cache，很多使用Hibernate的人都对都此有些了解。关于JBoss Cache，它在将来可能被JBoss的另外一个叫infinispan 的数据网格平台项目所替代。

自己动手实现java中cache

实现思路：
创建一个静态Hashtable用于保存key和value,对于cache过期后的方法回调，在cache过期后，再访问cache的时候进行，避免了使用定时器轮询过期时间，进行cache清除的效率损耗。
使用synchronized关键字进行多线程同步。
包括二个类和一个接口：
cache类：里面都是静态方法,提供基于key,value的方法进行cache的添加，修改，访问,进行cache过期后调用callback方法。

cacheitem类：用于管理每个条目的cache内容和超时时间回调方法

ICacheMethod接口：cache到期回调方法需要实现的接口

cache类：里面都是静态方法

package limeCache;

import java.util.Date;

/**
 * 静态方法,提供基于key,value的方法进行cache的添加，修改，访问,进行cache过期后调用callback方法。
 * 
 * @author lime
 *
 */
public class Cache {

    private static java.util.Hashtable<String, Object> __cacheList = new java.util.Hashtable<String, Object>();

    public Cache() {

    }

    // 添加cache,不过期
    public synchronized static void add(String key, Object value) {
        Cache.add(key, value, -1);
    }

    // 添加cache有过期时间
    public synchronized static void add(String key, Object value, long timeOut) {
        Cache.add(key, value, timeOut, null);
    }

    // 添加cache有过期时间并且具有回调方法
    public synchronized static void add(String key, Object value, long timeOut, ICacheMethod callback) {
        if (timeOut > 0) {
            timeOut += new Date().getTime();
        }
        CacheItem item = new CacheItem(key, value, timeOut, callback);
        Cache.__cacheList.put(key, item);
    }

    // 获取cache
    public synchronized static Object get(String key) {
        Object obj = Cache.__cacheList.get(key);
        if (obj == null) {
            return null;
        }
        CacheItem item = (CacheItem) obj;
        boolean expired = Cache.cacheExpired(key);
        if (expired == true) // 已过期
        {
            if (item.getCallback() == null) {
                Cache.remove(key);
                return null;
            } else {
                ICacheMethod callback = item.getCallback();
                callback.execute(key);
                expired = Cache.cacheExpired(key);
                if (expired == true) {
                    Cache.remove(key);
                    return null;
                }
            }
        }
        return item.getValue();
    }

    // 移除cache
    public synchronized static void remove(String key) {
        Object obj = Cache.__cacheList.get(key);
        if (obj != null) {
            obj = null;
        }
        Cache.__cacheList.remove(key);
    }

    // 清理所有cache对象
    public synchronized static void clear() {

        for (String s : Cache.__cacheList.keySet()) {
            Cache.__cacheList.put(s, null);
        }
        Cache.__cacheList.clear();
    }

    // 判断是否过期
    private static boolean cacheExpired(String key) {
        CacheItem item = (CacheItem) Cache.__cacheList.get(key);
        if (item == null) {
            return false;
        }
        long milisNow = new Date().getTime();
        long milisExpire = item.getTimeOut();
        if (milisExpire <= 0) { // 不过期
            return false;
        } else if (milisNow >= milisExpire) {
            return true;
        } else {
            return false;
        }
    }
}

CacheItem 类：

package limeCache;


/**
 * 用于管理每个条目的cache内容和超时时间回调方法
 * 
 * @author lime
 *
 */
public class CacheItem {
 
    private String key;
    private Object value;
    private long timeOut;
    private ICacheMethod callback = null;
 
    public CacheItem() {
 
    }
 
    public ICacheMethod getCallback() {
        return callback;
    }
 
    public void setCallback(ICacheMethod callback) {
        this.callback = callback;
    }
 
    public CacheItem(String key, Object value) {
        this.key = key;
        this.value = value;
        this.timeOut = 0;
    }
 
    public CacheItem(String key, Object value, long timeOut) {
        this.key = key;
        this.value = value;
        this.timeOut = timeOut;
    }
 
    public CacheItem(String key, Object value, long timeOut, ICacheMethod callback) {
        this.key = key;
        this.value = value;
        this.timeOut = timeOut;
        this.callback = callback;
    }
 
    public String getKey() {
        return key;
    }
 
    public void setKey(String key) {
        this.key = key;
    }
 
    public Object getValue() {
        return value;
    }
 
    public void setValue(Object value) {
        this.value = value;
    }
 
    public long getTimeOut() {
        return timeOut;
    }
 
    public void setTimeOut(long timeOut) {
        this.timeOut = timeOut;
    }
}

ICacheMethod 接口：

package limeCache;

/**
 * cache到期回调方法需要实现的接口
 * 
 * @author lime
 *
 */
public interface ICacheMethod {
    public void execute(String key);
}

java cache过期策略两种实现，一个基于list轮询一个基于timer定时

　　最近项目要引入缓存机制，但是不想引入分布式的缓存框架，所以自己就写了一个轻量级的缓存实现，有两个版本，一个是通过timer实现其超时过期处理，另外一个是通过list轮询。
　　首先要了解下java1.6中的ConcurrentMap ，他是一个线程安全的Map实现，特别说明的是在没有特别需求的情况下可以用ConcurrentHashMap。我是想学习一下读写锁的应用，就自己实现了一个SimpleConcurrentHashMap.

　　Class ： SimpleConcurrentMap

package limeCache.self;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;  
  
public class SimpleConcurrentMap<K, V> implements Map<K, V> {  
    final ReadWriteLock lock = new ReentrantReadWriteLock();  
    final Lock r = lock.readLock();  
    final Lock w = lock.writeLock();  
    final Map<K, V> map;  
      
    public SimpleConcurrentMap(Map<K, V> map) {  
        this.map = map;  
        if (map == null) throw new NullPointerException();  
    }  
  
    public void clear() {  
        w.lock();  
        try {  
            map.clear();  
        } finally {  
            w.unlock();  
        }  
    }  
  
    public boolean containsKey(Object key) {  
        r.lock();  
        try {  
            return map.containsKey(key);  
        } finally {  
            r.unlock();  
        }  
    }  
  
    public boolean containsValue(Object value) {  
        r.lock();  
        try {  
            return map.containsValue(value);  
        } finally {  
            r.unlock();  
        }  
    }  
  
    public Set<java.util.Map.Entry<K, V>> entrySet() {  
        throw new UnsupportedOperationException();  
    }  
  
    public V get(Object key) {  
        r.lock();  
        try {  
            return map.get(key);  
        } finally {  
            r.unlock();  
        }  
    }  
  
    public boolean isEmpty() {  
        r.lock();  
        try {  
            return map.isEmpty();  
        } finally {  
            r.unlock();  
        }  
    }  
  
    public Set<K> keySet() {  
        r.lock();  
        try {  
            return new HashSet<K>(map.keySet());  
        } finally {  
            r.unlock();  
        }  
    }  
  
    public V put(K key, V value) {  
        w.lock();  
        try {  
            return map.put(key, value);  
        } finally {  
            w.unlock();  
        }  
    }  
  
    public void putAll(Map<? extends K, ? extends V> m) {  
        w.lock();  
        try {  
            map.putAll(m);  
        } finally {  
            w.unlock();  
        }  
    }  
  
    public V remove(Object key) {  
        w.lock();  
        try {  
            return map.remove(key);  
        } finally {  
            w.unlock();  
        }  
    }  
  
    public int size() {  
        r.lock();  
        try {  
            return map.size();  
        } finally {  
            r.unlock();  
        }  
    }  
  
    public Collection<V> values() {  
        r.lock();  
        try {  
            return new ArrayList<V>(map.values());  
        } finally {  
            r.unlock();  
        }  
    }  
  
}

缓存对象CacheEntity.Java为：

package limeCache.self;

import java.io.Serializable;  

public class CacheEntity implements Serializable{  
    private static final long serialVersionUID = -3971709196436977492L;  
    private final int DEFUALT_VALIDITY_TIME = 20;//默认过期时间 20秒  
      
    private String cacheKey;  
    private Object cacheContext;  
    private int validityTime;//有效期时长，单位：秒  
    private long timeoutStamp;//过期时间戳  
      
    private CacheEntity(){  
        this.timeoutStamp = System.currentTimeMillis() + DEFUALT_VALIDITY_TIME * 1000;  
        this.validityTime = DEFUALT_VALIDITY_TIME;  
    }  
      
    public CacheEntity(String cacheKey, Object cacheContext){  
        this();  
        this.cacheKey = cacheKey;  
        this.cacheContext = cacheContext;  
    }  
      
    public CacheEntity(String cacheKey, Object cacheContext, long timeoutStamp){  
        this(cacheKey, cacheContext);  
        this.timeoutStamp = timeoutStamp;  
    }  
      
    public CacheEntity(String cacheKey, Object cacheContext, int validityTime){  
        this(cacheKey, cacheContext);  
        this.validityTime = validityTime;  
        this.timeoutStamp = System.currentTimeMillis() + validityTime * 1000;  
    }  
  
    public String getCacheKey() {  
        return cacheKey;  
    }  
    public void setCacheKey(String cacheKey) {  
        this.cacheKey = cacheKey;  
    }  
    public Object getCacheContext() {  
        return cacheContext;  
    }  
    public void setCacheContext(Object cacheContext) {  
        this.cacheContext = cacheContext;  
    }  
    public long getTimeoutStamp() {  
        return timeoutStamp;  
    }  
    public void setTimeoutStamp(long timeoutStamp) {  
        this.timeoutStamp = timeoutStamp;  
    }  
    public int getValidityTime() {  
        return validityTime;  
    }  
    public void setValidityTime(int validityTime) {  
        this.validityTime = validityTime;  
    }  
}

List缓存处理对象：

package limeCache.self;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;  
  
/** 
 * @projName：WZServer 
 * @className：CacheHandler 
 * @description：缓存操作类，对缓存进行管理，采用处理队列，定时循环清理的方式 
 * @creater：Administrator  
 * @creatTime：2013年7月22日 上午9:18:54  
 * @alter：Administrator 
 * @alterTime：2013年7月22日 上午9:18:54   
 * @remark： 
 * @version  
 */  
public class CacheListHandler {  
    private static final long SECOND_TIME = 1000;  
    private static final SimpleConcurrentMap<String, CacheEntity> map;  
    private static final List<CacheEntity> tempList;  
      
    static{  
        tempList = new ArrayList<CacheEntity>();  
        map = new SimpleConcurrentMap<String, CacheEntity>(new HashMap<String, CacheEntity>(1<<18));  
        new Thread(new TimeoutTimerThread()).start();  
    }  
              
    /** 
     * 增加缓存对象 
     * @param key 
     * @param ce 
     */  
    public static void addCache(String key, CacheEntity ce){  
        addCache(key, ce, ce.getValidityTime());  
    }  
      
    /** 
     * 增加缓存对象 
     * @param key 
     * @param ce 
     * @param validityTime 有效时间 
     */  
    public static synchronized void addCache(String key, CacheEntity ce, int validityTime){  
        ce.setTimeoutStamp(System.currentTimeMillis() + validityTime * SECOND_TIME);  
        map.put(key, ce);  
        //添加到过期处理队列  
        tempList.add(ce);  
    }  
      
    /** 
     * 获取缓存对象 
     * @param key 
     * @return 
     */  
    public static synchronized CacheEntity getCache(String key){  
        return map.get(key);  
    }  
      
    /** 
     * 检查是否含有制定key的缓冲 
     * @param key 
     * @return 
     */  
    public static synchronized boolean isConcurrent(String key){  
        return map.containsKey(key);  
    }  
      
    /** 
     * 删除缓存 
     * @param key 
     */  
    public static synchronized void removeCache(String key){  
        map.remove(key);  
    }  
      
    /** 
     * 获取缓存大小 
     * @param key 
     */  
    public static int getCacheSize(){  
        return map.size();  
    }  
      
    /** 
     * 清除全部缓存 
     */  
    public static synchronized void clearCache(){  
        tempList.clear();  
        map.clear();  
        System.out.println("clear cache");  
    }  
      
    static class TimeoutTimerThread implements Runnable {  
        public void run(){  
            while(true){  
                try {  
                    checkTime();  
                } catch (Exception e) {  
                    e.printStackTrace();  
                }  
            }  
        }  
          
        /** 
         * 过期缓存的具体处理方法 
         * @throws Exception 
         */  
        private void checkTime() throws Exception{    
            //"开始处理过期 ";  
            CacheEntity tce = null;  
            long timoutTime = 1000L;  
              
            //" 过期队列大小 : "+tempList.size());  
            if(1 > tempList.size()){  
                System.out.println("过期队列空，开始轮询");  
                timoutTime = 1000L;  
                Thread.sleep(timoutTime);  
                return;  
            }  
              
            tce = tempList.get(0);  
            timoutTime = tce.getTimeoutStamp() - System.currentTimeMillis();  
            //" 过期时间 : "+timoutTime);  
            if(0 < timoutTime){  
                //设定过期时间  
                Thread.sleep(timoutTime);  
                return;  
            }  
            System.out.print(" 清除过期缓存 ： "+tce.getCacheKey());  
            //清除过期缓存和删除对应的缓存队列  
            tempList.remove(tce);  
            removeCache(tce.getCacheKey());  
        }  
    }  
}

Timer方式

package limeCache.self;

import java.util.HashMap;
import java.util.Timer;
import java.util.TimerTask;  
  
/** 
 * @projName：WZServer 
 * @className：CacheHandler 
 * @description：缓存操作类，对缓存进行管理,清除方式采用Timer定时的方式 
 * @creater：Administrator  
 * @creatTime：2013年7月22日 上午9:18:54  
 * @alter：Administrator 
 * @alterTime：2013年7月22日 上午9:18:54   
 * @remark： 
 * @version  
 */  
public class CacheTimerHandler {  
    private static final long SECOND_TIME = 1000;//默认过期时间 20秒  
    private static final int DEFUALT_VALIDITY_TIME = 20;//默认过期时间 20秒  
    private static final Timer timer ;  
    private static final SimpleConcurrentMap<String, CacheEntity> map;  
      
    static{  
        timer = new Timer();  
        map = new SimpleConcurrentMap<String, CacheEntity>(new HashMap<String, CacheEntity>(1<<18));  
    }  
              
    /** 
     * 增加缓存对象 
     * @param key 
     * @param ce 
     */  
    public static void addCache(String key, CacheEntity ce){  
        addCache(key, ce, DEFUALT_VALIDITY_TIME);  
    }  
      
    /** 
     * 增加缓存对象 
     * @param key 
     * @param ce 
     * @param validityTime 有效时间 
     */  
    public static synchronized void addCache(String key, CacheEntity ce, int validityTime){  
        map.put(key, ce);  
        //添加过期定时  
        timer.schedule(new TimeoutTimerTask(key), validityTime * SECOND_TIME);  
    }  
      
    /** 
     * 获取缓存对象 
     * @param key 
     * @return 
     */  
    public static synchronized CacheEntity getCache(String key){  
        return map.get(key);  
    }  
      
    /** 
     * 检查是否含有制定key的缓冲 
     * @param key 
     * @return 
     */  
    public static synchronized boolean isConcurrent(String key){  
        return map.containsKey(key);  
    }  
      
    /** 
     * 删除缓存 
     * @param key 
     */  
    public static synchronized void removeCache(String key){  
        map.remove(key);  
    }  
      
    /** 
     * 获取缓存大小 
     * @param key 
     */  
    public static int getCacheSize(){  
        return map.size();  
    }  
      
    /** 
     * 清除全部缓存 
     */  
    public static synchronized void clearCache(){  
        if(null != timer){  
            timer.cancel();  
        }  
        map.clear();  
        System.out.println("clear cache");  
    }  
      
    /** 
     * @projName：WZServer 
     * @className：TimeoutTimerTask 
     * @description：清除超时缓存定时服务类 
     * @creater：Administrator  
     * @creatTime：2013年7月22日 上午9:34:39  
     * @alter：Administrator 
     * @alterTime：2013年7月22日 上午9:34:39   
     * @remark： 
     * @version  
     */  
    static class TimeoutTimerTask extends TimerTask{  
        private String ceKey ;  
          
        public TimeoutTimerTask(String key){  
            this.ceKey = key;  
        }  
  
        @Override  
        public void run() {  
            CacheTimerHandler.removeCache(ceKey);  
            System.out.println("remove : "+ceKey);  
        }  
    }  
}

timer方式有点是适用性更强，因为每个缓存的过期时间都可以独立配置的；ist只能适用于缓存时间都一样的线性过期。从性能开销方面，因为timer是与缓存对象数量成正比的，在缓存量很大的时候，在缓存时间内系统开销也随之提高；而list方式只要一个线程管理过期清理就可以了。

-- -- --

对timer方式的改进，定时程序只需要一个就可以了，过期时间，通过一个对象保存，根据每个对象的过期时间判断是否移除该缓存。于是得到下面的版本：

package limeCache.self.strong;

import java.util.HashMap;
import java.util.Map;
import java.util.Timer;
import java.util.TimerTask;
/**
 * 在缓存的时候，同时记录下该key,缓存时间，失效周期
 * 在读取缓存的时候，更新该key的缓存时间，
 * 定时器每两个小时运行一次，检查每个key是否过期，如果过期，删除Jboss中的cache
 *
 */
public class CacheTimerMamager{
    private static final long SECOND_TIME = 1000;//毫秒
    private static final long DEFUALT_VALIDITY_TIME = SECOND_TIME * 60 * 60 * 2;//默认过期时间 :2小时
    private static final Timer timer ;
    private static final Map<String, CacheOutTime> map;
     
    static{
        timer = new Timer();
        map = new HashMap<String, CacheOutTime>();
        timer.schedule(new CacheTimerTask(), DEFUALT_VALIDITY_TIME, DEFUALT_VALIDITY_TIME);
    }
     
    /**
     * 增加缓存对象
     * @param key
     * @param ce
     */
    public static synchronized void  addCache(String key){
        CacheOutTime cot = map.get(key);
        long outTime = System.currentTimeMillis()+DEFUALT_VALIDITY_TIME;
        if(cot==null){
            cot = new CacheOutTime(key, outTime);
            map.put(key, cot);
        }else{
            //更新该key的过期时间
            cot.setTimeoutStamp(outTime);
        }
    }
     
    //移除cache
    /**
     * 考虑，在多线程时，当有线程已经取得缓存对象时，删掉了缓存，会产生什么情况
     */
    public static synchronized void removeCache() {
        CacheOutTime cot;
        long currentTime = System.currentTimeMillis();
        for (String key : map.keySet()) {
            cot = map.get(key);
            if(cot.getTimeoutStamp()<=currentTime){
                System.out.println("remove : "+key);
            }
        }
    }
    static class CacheTimerTask extends TimerTask{
        @Override
        public void run() {
            //移除cache
            CacheTimerMamager.removeCache();
        }
    }
     
}
 
class CacheOutTime {
    private String cacheKey;
    private long timeoutStamp;//过期时间戳，在最后一次访问该key的时候计算得到
     
    public CacheOutTime() {
        super();
    }
    public CacheOutTime(String cacheKey, long timeoutStamp) {
        super();
        this.cacheKey = cacheKey;
        this.timeoutStamp = timeoutStamp;
    }
     
    public String getCacheKey() {
        return cacheKey;
    }
    public void setCacheKey(String cacheKey) {
        this.cacheKey = cacheKey;
    }
    public long getTimeoutStamp() {
        return timeoutStamp;
    }
    public void setTimeoutStamp(long timeoutStamp) {
        this.timeoutStamp = timeoutStamp;
    }
}

啦啦啦