Java Cache系列之Cache概述和Simple Cache

前記：最近公司在做的項目完全基于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) {

        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) {

            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;

    public boolean ispresent(k key) {

            return cache.containskey(key);

    public void put(k key, v value) {

        writelock.lock();

            cache.put(key, value);

            writelock.unlock();

    public void putall(map<? extends k, ? extends v> entries) {

            cache.putall(entries);

    public void invalidate(k key) {

            if(!ispresent(key)) {

                throw new cacheentrynotexistsexception(this, key);

            cache.remove(key);

    public void invalidateall(iterator<? extends k> keys) {

                if(!ispresent(key)) {

                invalidate(key);

    public void invalidateall() {

            cache.clear();

    public int size() {

            return cache.size();

    public void clear() {

    public map<? extends k, ? extends v> asmap() {

            return new concurrenthashmap<k, v>(cache);

    public boolean isempty() {

            return cache.isempty();

其簡單的使用用例如下： 

    @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);