（转）Java Cache系列之Cache概述和Simple Cache

该文章转自http://www.blogjava.net/DLevin/archive/2013/10/15/404770.html，仅用于学习和收藏。


前记：最近公司在做的项目完全基于Cache（Gemfire）构建了一个类数据库的系统，自己做的一个小项目里用过Guava的Cache，以前做过的项目中使用过EHCache，既然和Cache那么有缘，那就趁这个机会好好研究一下Java中的Cache库。在Java社区中已经提供了很多Cache库实现，具体可以参考http://www.open-open.com/13.htm，这里只关注自己用到的几个Cache库而且这几个库都比较具有代表性：Guava中提供的Cache是基于单JVM的简单实现；EHCache出自Hibernate，也是基于单JVM的实现，是对单JVM Cache比较完善的实现；而Gemfire则提供了对分布式Cache的完善实现。这一系列的文章主要关注在这几个Cache系统的实现上，因而步探讨关于Cache的好处、何时用Cache等问题，由于他们都是基于内存的Cache，因而也仅局限于这种类型的Cache（说实话，我不知道有没有其他的Cache系统，比如基于文件？囧）。

记得我最早接触Cache是在大学学计算机组成原理的时候，由于CPU的速度要远大于内存的读取速度，为了提高CPU的效率，CPU会在内部提供缓存区，该缓存区的读取速度和CPU的处理速度类似，CPU可以直接从缓存区中读取数据，从而解决CPU的处理速度和内存读取速度不匹配的问题。缓存之所以能解决这个问题是基于程序的局部性原理，即”程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某数据被访问，则不久之后该数据可能再次被访问。空间局部性是指一旦程序访问了某个存储单元，则不久之后。其附近的存储单元也将被访问。”在实际工作中，CPU先向缓存区读取数据，如果缓存区已存在，则读取缓存中的数据（命中），否则（失效），将内存中相应数据块载入缓存中，以提高接下来的访问速度。由于成本和CPU大小的限制，CPU只能提供有限的缓存区，因而缓存区的大小是衡量CPU性能的重要指标之一。

使用缓存，在CPU向内存更新数据时需要处理一个问题（写回策略问题），即CPU在更新数据时只更新缓存的数据（write back，写回，当缓存需要被替换时才将缓存中更新的值写回内存），还是CPU在更新数据时同时更新缓存中和内存中的数据（write through，写通）。在写回策略中，为了减少内存写操作，缓存块通常还设有一个脏位（dirty bit），用以标识该块在被载入之后是否发生过更新。如果一个缓存块在被置换回内存之前从未被写入过，则可以免去回写操作；写回的优点是节省了大量的写操作。这主要是因为，对一个数据块内不同单元的更新仅需一次写操作即可完成。这种内存带宽上的节省进一步降低了能耗，因此颇适用于嵌入式系统。写通策略由于要经常和内存交互（有些CPU设计会在中间提供写缓冲器以缓解性能），因而性能较差，但是它实现简单，而且能简单的维持数据一致性。

在软件的缓存系统中，一般是为了解决内存的访问速率和磁盘、网络、数据库（属于磁盘或网络访问，单独列出来因为它的应用比较广泛）等访问速率不匹配的问题（对于内存缓存系统来说）。但是由于内存大小和成本的限制，我们又不能把所有的数据先加载进内存来。因而如CPU中的缓存，我们只能先将一部分数据保存在缓存中。此时，对于缓存，我们一般要解决如下需求：
使用给定Key从Cache中读取Value值。CPU是通过内存地址来定位内存已获取相应内存中的值，类似的在软件Cache中，需要通过某个Key值来标识相关的值。因而可以简单的认为软件中的Cache是一个存储键值对的Map，比如Gemfire中的Region就继承自Map，只是Cache的实现更加复杂。
当给定的Key在当前Cache不存在时，程序员可以通过指定相应的逻辑从其他源（如数据库、网络等源）中加载该Key对应的Value值，同时将该值返回。在CPU中，基于程序局部性原理，一般是默认的加载接下来的一段内存块，然而在软件中，不同的需求有不同的加载逻辑，因而需要用户自己指定对应的加载逻辑，而且一般来说也很难预知接下来要读取的数据，所以只能一次只加载一条纪录（对可预知的场景下当然可以批量加载数据，只是此时需要权衡当前操作的响应时间问题）。
可以向Cache中写入Key－Value键值对（新增的纪录或对原有的键值对的更新）。就像CPU的写回策略中有写回和写通策略，有些Cache系统提供了写通接口。如果没有提供写通接口，程序员需要额外的逻辑处理写通策略。也可以如CPU中的Cache一样，只当相应的键值对移出Cache以后，再将值写回到数据源，可以提供一个标记位以决定要不要写回（不过感觉这种实现比较复杂，代码的的耦合度也比较高，如果为提升写的速度，采用异步写回即可，为防止数据丢失，可以使用Queue来存储）。
将给定Key的键值对移出Cache（或给定多个Key以批量移除，甚至清除整个Cache）。
配置Cache的最大使用率，当Cache超过该使用率时，可配置溢出策略
直接移除溢出的键值对。在移除时决定是否要写回已更新的数据到数据源。
将溢出的溢出的键值对写到磁盘中。在写磁盘时需要解决如何序列化键值对，如何存储序列化后的数据到磁盘中，如何布局磁盘存储，如何解决磁盘碎片问题，如何从磁盘中找回相应的键值对，如何读取磁盘中的数据并方序列化，如何处理磁盘溢出等问题。
在溢出策略中，除了如何处理溢出的键值对问题，还需要处理如何选择溢出的键值对问题。这有点类似内存的页面置换算法（其实内存也可以看作是对磁盘的Cache），一般使用的算法有：先进先出（FIFO）、最近最少使用（LRU）、最少使用（LFU）、Clock置换（类LRU）、工作集等算法。
对Cache中的键值对，可以配置其生存时间，以处理某些键值对在长时间不被使用，但是又没能溢出的问题（因为溢出策略的选择或者Cache没有到溢出阶段），以提前释放内存。
对某些特定的键值对，我们希望它能一直留在内存中不被溢出，有些Cache系统提供PIN配置（动态或静态），以确保该键值对不会被溢出。
提供Cache状态、命中率等统计信息，如磁盘大小、Cache大小、平均查询时间、每秒查询次数、内存命中次数、磁盘命中次数等信息。
提供注册Cache相关的事件处理器，如Cache的创建、Cache的销毁、一条键值对的添加、一条键值对的更新、键值对溢出等事件。
由于引入Cache的目的就是为了提升程序的读写性能，而且一般Cache都需要在多线程环境下工作，因而在实现时一般需要保证线程安全，以及提供高效的读写性能。
在Java中，Map是最简单的Cache，为了高效的在多线程环境中使用，可以使用ConcurrentHashMap，这也正是我之前参与的一个项目中最开始的实现（后来引入EHCache）。为了语意更加清晰、保持接口的简单，下面我实现了一个基于Map的最简单的Cache系统，用以演示Cache的基本使用方式。用户可以向它提供数据、查询数据、判断给定Key的存在性、移除给定的Key(s)、清除整个Cache等操作。以下是Cache的接口定义。

public interface Cache<K, V> {
    public String getName();
    public V get(K key);
    public Map<? extends K, ? extends V> getAll(Iterator<? extends K> keys);
    public boolean isPresent(K key);
    public void put(K key, V value);
    public void putAll(Map<? extends K, ? extends V> entries);
    public void invalidate(K key);
    public void invalidateAll(Iterator<? extends K> keys);
    public void invalidateAll();
    public boolean isEmpty();
    public int size();
    public void clear();
    public Map<? extends K, ? extends V> asMap();
}

这个简单的Cache实现只是对HashMap的封装，之所以选择HashMap而不是ConcurrentHashMap是因为在ConcurrentHashMap无法实现getAll()方法；并且这里所有的操作我都加锁了，因而也不需要ConcurrentHashMap来保证线程安全问题；为了提升性能，我使用了读写锁，以提升并发查询性能。因为代码比较简单，所以把所有代码都贴上了（懒得整理了。。。。）。

public class CacheImpl<K, V> implements Cache<K, V> {
    private final String name;
    private final HashMap<K, V> cache;
    private final ReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();
    
    public CacheImpl(String name) {
        this.name = name;
        cache = new HashMap<K, V>();
    }
    
    public CacheImpl(String name, int initialCapacity) {
        this.name = name;
        cache = new HashMap<K, V>(initialCapacity);
    }
    
    public String getName() {
        return name;
    }

    public V get(K key) {
        readLock.lock();
        try {
            return cache.get(key);
        } finally {
            readLock.unlock();
        }
    }

    public Map<? extends K, ? extends V> getAll(Iterator<? extends K> keys) {
        readLock.lock();
        try {
            Map<K, V> map = new HashMap<K, V>();
            List<K> noEntryKeys = new ArrayList<K>();
            while(keys.hasNext()) {
                K key = keys.next();
                if(isPresent(key)) {
                    map.put(key, cache.get(key));
                } else {
                    noEntryKeys.add(key);
                }
            }
            
            if(!noEntryKeys.isEmpty()) {
                throw new CacheEntriesNotExistException(this, noEntryKeys);
            }
            
            return map;
        } finally {
            readLock.unlock();
        }
    }

    public boolean isPresent(K key) {
        readLock.lock();
        try {
            return cache.containsKey(key);
        } finally {
            readLock.unlock();
        }
    }

    public void put(K key, V value) {
        writeLock.lock();
        try {
            cache.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }

    public void putAll(Map<? extends K, ? extends V> entries) {
        writeLock.lock();
        try {
            cache.putAll(entries);
        } finally {
            writeLock.unlock();
        }
    }

    public void invalidate(K key) {
        writeLock.lock();
        try {
            if(!isPresent(key)) {
                throw new CacheEntryNotExistsException(this, key);
            }
            cache.remove(key);
        } finally {
            writeLock.unlock();
        }
    }

    public void invalidateAll(Iterator<? extends K> keys) {
        writeLock.lock();
        try {
            List<K> noEntryKeys = new ArrayList<K>();
            while(keys.hasNext()) {
                K key = keys.next();
                if(!isPresent(key)) {
                    noEntryKeys.add(key);
                }
            }
            if(!noEntryKeys.isEmpty()) {
                throw new CacheEntriesNotExistException(this, noEntryKeys);
            }
            
            while(keys.hasNext()) {
                K key = keys.next();
                invalidate(key);
            }
        } finally {
            writeLock.unlock();
        }
    }

    public void invalidateAll() {
        writeLock.lock();
        try {
            cache.clear();
        } finally {
            writeLock.unlock();
        }
    }

    public int size() {
        readLock.lock();
        try {
            return cache.size();
        } finally {
            readLock.unlock();
        }
    }

    public void clear() {
        writeLock.lock();
        try {
            cache.clear();
        } finally {
            writeLock.unlock();
        }
    }

    public Map<? extends K, ? extends V> asMap() {
        readLock.lock();
        try {
            return new ConcurrentHashMap<K, V>(cache);
        } finally {
            readLock.unlock();
        }
    }

    public boolean isEmpty() {
        readLock.lock();
        try {
            return cache.isEmpty();
        } finally {
            readLock.unlock();
        }
    }

}

其简单的使用用例如下：

    @Test
    public void testCacheSimpleUsage() {
        Book uml = bookFactory.createUMLDistilled();
        Book derivatives = bookFactory.createDerivatives();
        
        String umlBookISBN = uml.getIsbn();
        String derivativesBookISBN = derivatives.getIsbn();
        
        Cache<String, Book> cache = cacheFactory.create("book-cache");
        cache.put(umlBookISBN, uml);
        cache.put(derivativesBookISBN, derivatives);
        
        Book fetchedBackUml = cache.get(umlBookISBN);
        System.out.println(fetchedBackUml);
        
        Book fetchedBackDerivatives = cache.get(derivativesBookISBN);
        System.out.println(fetchedBackDerivatives);
    }