引言

緩存是存儲(chǔ)在內(nèi)存中的KV數(shù)據(jù)結(jié)構(gòu)，分為分布式緩存和本地緩存。

分布式緩存方案中，一般應(yīng)用進(jìn)程和緩存進(jìn)程不在同一臺(tái)服務(wù)器，通過(guò)RPC或HTTP進(jìn)行通信，可以實(shí)現(xiàn)應(yīng)用服務(wù)和緩存的完全解耦，支持大量的數(shù)據(jù)存儲(chǔ)，
分布式緩存常見(jiàn)有redis，memcache等。

本地緩存方案中的應(yīng)用進(jìn)程和緩存進(jìn)程在同一個(gè)進(jìn)程，沒(méi)有網(wǎng)絡(luò)開(kāi)銷(xiāo)，訪(fǎng)問(wèn)速度快，但受限于內(nèi)存，不適合存儲(chǔ)大量數(shù)據(jù)。本地緩存主要有Guava cache，Caffeine，Encache等，還可以通過(guò)HashMap自實(shí)現(xiàn)一套本地緩存機(jī)制。

今天重點(diǎn)來(lái)聊一聊本地緩存的應(yīng)用。

Guava Cache

使用Guava Cache緩存本地?cái)?shù)據(jù)，首先需要引入對(duì)應(yīng)的工具包

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>18.0</version>
</dependency>      

本地緩存數(shù)據(jù)，并支持強(qiáng)制刷新。

@Component
public class MyGuavaCache {
    private LoadingCache<String, Field> fieldCache = CacheBuilder.newBuilder()
            .maximumSize(1000) // 設(shè)置最大容量
            .refreshAfterWrite(24, TimeUnit.HOURS) //設(shè)置過(guò)期刷新間隔
            .build(
                    new CacheLoader<String, Field>() { // 這是自動(dòng)刷新
                        @Override
                        public Field load(String key) throws Exception {
                            return getFromDb(key);
                        }
                    }
            );

    /**
    * 從db取數(shù)
    */
    private Field getFromDb(String key) {
        return dbRepositiory.getByKey(key);
    }

    /**
     * 提供給外部調(diào)用獲取結(jié)果
     */
    public Map<String, Field> get(String key) {

       try {
            return fieldCache.get(key); // 過(guò)期會(huì)自動(dòng)執(zhí)行l(wèi)oad獲取數(shù)據(jù)
        } catch (ExecutionException e) {
            throw new UncheckedExecutionException(e);
        }
    }

    /**
     * 手動(dòng)強(qiáng)制緩存失效
     * @param key
     */
    public void invalidate(String key) {
        fieldCache.invalidate(key);
    }
}

Guava cache緩存支持最大容量限制，可以指定插入時(shí)間和訪(fǎng)問(wèn)時(shí)間的過(guò)期刪除策略，且是線(xiàn)程安全，是基于LRU算法實(shí)現(xiàn)。在文章的結(jié)尾，會(huì)簡(jiǎn)單介紹一下LRU算法。

Caffeine

Caffeine內(nèi)部采用了一種結(jié)合LRU、LFU優(yōu)點(diǎn)的算法：W-TinyLFU，在性能上比Guava cache更加優(yōu)秀，Caffeine的API基本和Guava cache一樣。下面是Caffeine的三種加載方式：

/**
 * 手動(dòng)加載
 */
Cache<String, String> cache = Caffeine.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .maximumSize(1000)
    .build();
cache.get("key", k -> createData("key"));

/**
 * 同步加載
 */
LoadingCache<String, String> cache = Caffeine.newBuilder()
    .maximumSize(1000)
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .build(this::createData);

/**
 * 異步加載
 */
AsyncCache<String,String> cache = Caffeine.newBuilder()
    .expireAfterWrite(10, TimeUnit.MINUTES)
    .maximumSize(1000)
    .buildAsync();

CompletableFuture<String> data = cache.get(key , k -> createData(k));

Caffeine的過(guò)期設(shè)置也幾乎和Guava cache一致

LoadingCache<String,String> cache = Caffeine.newBuilder()
    //限制最大數(shù)量
    .maximumSize(1000)
    //基于權(quán)重
    .maximumWeight(1000)
    //指定計(jì)算權(quán)重的方式
    .weigher(this::caculateWeight)
    //緩存在寫(xiě)入多久后失效
    .expireAfterWrite(1000,TimeUnit.SECONDS)
    //緩存在訪(fǎng)問(wèn)多久后失效
    .expireAfterAccess(1000,TimeUnit.SECONDS)
    //多種時(shí)間過(guò)期策略組合使用
    .expireAfter(new Expiry<String, String>() {
                public long expireAfterCreate(Key key, Graph graph, long currentTime) {
                    long seconds = graph.creationDate().plusHours(5)
                            .minus(System.currentTimeMillis(), ChronoUnit.MILLIS).getSeconds();
                    return TimeUnit.SECONDS.toNanos(seconds);
                }
                public long expireAfterUpdate(Key key, Graph graph,long currentTime, long currentDuration) {
                    return currentDuration;
                }
                public long expireAfterRead(Key key, Graph graph,long currentTime, long currentDuration) {
                    return currentDuration;
                }
            })
    .build(this::load);

Encache

Encache是一個(gè)純Java的進(jìn)程內(nèi)緩存框架，是Hibernate中默認(rèn)de CacheProvider。同Caffeine和Guava Cache相比，Encache的功能更加豐富，擴(kuò)展性更強(qiáng)，支持多種緩存淘汰算法，包括LRU、LFU和FIFO，緩存支持堆內(nèi)存儲(chǔ)、堆外存儲(chǔ)、磁盤(pán)存儲(chǔ)（支持持久化）三種，支持多種集群方案，解決數(shù)據(jù)共享問(wèn)題。

Encache在性能上不及Caffeine和Guava Cache，其中Caffeine性能最優(yōu)，在本地緩存方案中，比較推薦Caffeine作為本地緩存工具，另外使用redis或者memcache作為分布式緩存，構(gòu)造多級(jí)緩存體系，保證性能和可靠性。

緩存算法

緩存算法有FIFO先進(jìn)先出、LRU最近最久未使用、LFU最近最少使用

FIFO

FIFO先進(jìn)先出，是最簡(jiǎn)單的一種算法，最先進(jìn)入的數(shù)據(jù)，將最先被淘汰，同隊(duì)列的機(jī)制一樣。

LRU

LRU 最近最久未使用，在很多分布式緩存系統(tǒng)（如Redis, Memcached）中都有廣泛使用。LRU（Least recently used，最近最久未使用）算法根據(jù)數(shù)據(jù)的歷史訪(fǎng)問(wèn)記錄來(lái)進(jìn)行淘汰數(shù)據(jù)，其核心思想是如果數(shù)據(jù)最近時(shí)間被訪(fǎng)問(wèn)過(guò)，那么將來(lái)被訪(fǎng)問(wèn)的幾率也更高。常用鏈表保存緩存數(shù)據(jù)，算法詳細(xì)實(shí)現(xiàn)：
1）新數(shù)據(jù)會(huì)被插入到鏈表頭部
2）緩存命中時(shí)，會(huì)將數(shù)據(jù)移到鏈表頭部
3）當(dāng)鏈表滿(mǎn)的時(shí)候，鏈表尾部數(shù)據(jù)將會(huì)被丟棄

緩存污染問(wèn)題
當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)，LRU算法很好，但偶發(fā)性的、周期性的批量操作，會(huì)導(dǎo)致LRU命中率急劇下降，緩存污染情況也比較嚴(yán)重。
實(shí)現(xiàn)較簡(jiǎn)單，命中時(shí)需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引，然后將數(shù)據(jù)移動(dòng)到頭部。

備注：【緩存污染指將不常用的數(shù)據(jù)移動(dòng)到緩存中，降低緩存效率的現(xiàn)象】

LRU-K算法

K代表最近使用的次數(shù)，為解決LRU算法中緩存污染問(wèn)題，將判斷標(biāo)準(zhǔn)改為最近使用過(guò)K次（LRU相當(dāng)于LRU-1），需要多維護(hù)一個(gè)隊(duì)列，記錄所有緩存被訪(fǎng)問(wèn)的歷史，當(dāng)訪(fǎng)問(wèn)次數(shù)達(dá)到K的時(shí)候，才將數(shù)據(jù)放到緩存；有限淘汰第K次訪(fǎng)問(wèn)時(shí)間距離當(dāng)前時(shí)間最大的數(shù)據(jù)

算法實(shí)現(xiàn)：
1）數(shù)據(jù)第一次被訪(fǎng)問(wèn)時(shí)，加入到訪(fǎng)問(wèn)歷史列表
2）數(shù)據(jù)在歷史列表里沒(méi)有達(dá)到K次訪(fǎng)問(wèn)，按一定規(guī)則淘汰，比如FIFO（先進(jìn)先出），LRU（最近最少使用）
3）當(dāng)歷史隊(duì)列數(shù)據(jù)訪(fǎng)問(wèn)達(dá)到K次后，將數(shù)據(jù)遷移到緩存隊(duì)列，并從歷史隊(duì)列移除，
4）緩存數(shù)據(jù)被再次訪(fǎng)問(wèn)后，重新排序
5）緩存隊(duì)列，優(yōu)先淘汰末尾的數(shù)據(jù)，即倒數(shù)第K次訪(fǎng)問(wèn)距離限制最久的數(shù)據(jù)，

LRU-K具有LRU的優(yōu)點(diǎn)，同時(shí)避免了LRU的缺點(diǎn)：緩存污染。
實(shí)際應(yīng)用中LRU-2是綜合各種因素后的最優(yōu)選擇，更大K值命中率雖然高，但適應(yīng)性差，需要大量數(shù)據(jù)訪(fǎng)問(wèn)才能清楚歷史訪(fǎng)問(wèn)記錄。

LRU-K 降低了緩存污染的問(wèn)題，命中率比LRU高；
LRU-K隊(duì)列是一個(gè)優(yōu)先級(jí)隊(duì)列，算法復(fù)雜度和代價(jià)比較高；
需要額外記錄被訪(fǎng)問(wèn)過(guò)還沒(méi)緩存的數(shù)據(jù)，內(nèi)存消耗要高一些，尤其數(shù)據(jù)量較大的情況；另外LRU-K需要基于時(shí)間進(jìn)行排序，CPU消耗也會(huì)更高一些。

LFU

Least Frequently Used 最近最少使用

與LRU算法相比，從時(shí)間上來(lái)說(shuō)，首先淘汰最長(zhǎng)時(shí)間未被使用的數(shù)據(jù)
LFU則是淘汰近一段時(shí)間內(nèi)被訪(fǎng)問(wèn)次數(shù)最少的數(shù)據(jù)

例如：一段時(shí)間T，主存塊為3，若數(shù)據(jù)走向?yàn)? 2 1 2 1 3 4，當(dāng)數(shù)據(jù)4過(guò)來(lái)時(shí)，主存塊滿(mǎn)觸發(fā)淘汰策略，
按LRU算法,數(shù)據(jù)2被淘汰(數(shù)據(jù)2最久未被使用)
按LFU算法應(yīng)換數(shù)據(jù)3(十分鐘內(nèi),數(shù)據(jù)3只訪(fǎng)問(wèn)了一次)

所以L(fǎng)RU關(guān)鍵是看最后一次被使用到發(fā)生調(diào)度的時(shí)間長(zhǎng)短,
而LFU關(guān)鍵是看一定時(shí)間段被使用的頻率