国产13区,一区二区第亚洲

緩存和 Map 之間的一個根本區(qū)別在于緩存可以回收存儲的 item。
回收策略為在指定時間刪除哪些對象。此策略直接影響緩存的命中率 —— 緩存庫的一個重要特性。Caffeine 因使用了 Window TinyLfu 回收策略，提供了一個近乎最佳的命中率。

依賴

我們需要在 pom.xml 中添加 caffeine 依賴：

<dependency>
    <groupId>com.github.ben-manes.caffeine</groupId>
    <artifactId>caffeine</artifactId>
    <version>2.5.5</version>
</dependency>

填充緩存

讓我們來了解一下 Caffeine 的三種緩存填充策略：手動、同步加載和異步加載。

首先，我們?yōu)橐彺嬷写鎯Φ闹殿愋蛯懸粋€類：

class DataObject {
    private final String data;
 
    private static int objectCounter = 0;
    // standard constructors/getters
     
    public static DataObject get(String data) {
        objectCounter++;
        return new DataObject(data);
    }
}

手動填充

在此策略中，我們手動將值放入緩存后再檢索。

Cache<String, DataObject> cache = Caffeine.newBuilder()
  .expireAfterWrite(1, TimeUnit.MINUTES)
  .maximumSize(100)
  .build();

現(xiàn)在，我們可以使用 getIfPresent 方法從緩存中獲取值。如果緩存中不存指定的值，則方法將返回 null：

String key = "A";
DataObject dataObject = cache.getIfPresent(key);
 
assertNull(dataObject);

我們可以使用 put 方法手動填充緩存：

cache.put(key, dataObject);
dataObject = cache.getIfPresent(key);
 
assertNotNull(dataObject);

我們可以使用 put 方法手動填充緩存：

cache.put(key, dataObject);
dataObject = cache.getIfPresent(key);

assertNotNull(dataObject);

我們也可以使用 get 方法獲取值，該方法將一個參數(shù)為 key 的 Function 作為參數(shù)傳入。如果緩存中不存在該 key，則該函數(shù)將用于提供默認值，該值在計算后插入緩存中：

dataObject = cache
  .get(key, k -> DataObject.get("Data for A"));
 
assertNotNull(dataObject);
assertEquals("Data for A", dataObject.getData());

get 方法可以以原子方式執(zhí)行計算。這意味著你只進行一次計算 —— 即使有多個線程同時請求該值.

有時我們需要手動觸發(fā)一些緩存的值失效：

cache.invalidate(key);
dataObject = cache.getIfPresent(key);
 
assertNull(dataObject);

同步加載

這種加載緩存的方式使用了與用于初始化值的 Function 的手動策略類似的 get 方法。讓我們看看如何使用它。

首先，我們需要初始化緩存：

LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
  .maximumSize(100)
  .expireAfterWrite(1, TimeUnit.MINUTES)
  .build(k -> DataObject.get("Data for " + k));

現(xiàn)在我們可以使用 get 方法來檢索值：

DataObject dataObject = cache.get(key);
 
assertNotNull(dataObject);
assertEquals("Data for " + key, dataObject.getData());

當然，也可以使用 getAll 方法獲取一組值：

Map<String, DataObject> dataObjectMap 
  = cache.getAll(Arrays.asList("A", "B", "C"));
 
assertEquals(3, dataObjectMap.size());

從傳給 build 方法的初始化函數(shù)檢索值，這使得可以使用緩存作為訪問值的主要門面（Facade）。

異步加載

此策略的作用與之前相同，但是以異步方式執(zhí)行操作，并返回一個包含值的 CompletableFuture：

AsyncLoadingCache<String, DataObject> cache = Caffeine.newBuilder()
  .maximumSize(100)
  .expireAfterWrite(1, TimeUnit.MINUTES)
  .buildAsync(k -> DataObject.get("Data for " + k));

我們可以以相同的方式使用 get 和 getAll 方法，同時考慮到他們返回的是 CompletableFuture：

String key = "A";
 
cache.get(key).thenAccept(dataObject -> {
    assertNotNull(dataObject);
    assertEquals("Data for " + key, dataObject.getData());
});
 
cache.getAll(Arrays.asList("A", "B", "C"))
  .thenAccept(dataObjectMap -> assertEquals(3, dataObjectMap.size()));

值回收

Caffeine 有三個值回收策略：基于大小，基于時間和基于引用。

基于大小回收:
這種回收方式假定當緩存大小超過配置的大小限制時會發(fā)生回收。獲取大小有兩種方法：緩存中計數(shù)對象，或獲取權重。

LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
  .maximumSize(1)
  .build(k -> DataObject.get("Data for " + k));
 
assertEquals(0, cache.estimatedSize());

當我們添加一個值時，大小明顯增加：

cache.get("A");
 
assertEquals(1, cache.estimatedSize());

我們可以將第二個值添加到緩存中，這將導致第一個值被刪除：

cache.get("B");
cache.cleanUp();
 
assertEquals(1, cache.estimatedSize());

值得一提的是，在獲取緩存大小之前，我們調(diào)用了 cleanUp 方法。這是因為緩存回收被異步執(zhí)行，這種方式有助于等待回收工作完成。

我們還可以傳遞一個 weigher Function 來獲取緩存的大?。?/p>

LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
  .maximumWeight(10)
  .weigher((k,v) -> 5)
  .build(k -> DataObject.get("Data for " + k));
 
assertEquals(0, cache.estimatedSize());
 
cache.get("A");
assertEquals(1, cache.estimatedSize());
 
cache.get("B");
assertEquals(2, cache.estimatedSize());

當 weight 超過 10 時，值將從緩存中刪除：

cache.get("C");
cache.cleanUp();
 
assertEquals(2, cache.estimatedSize());

基于時間回收
這種回收策略是基于條目的到期時間，有三種類型：

訪問后到期 — 從上次讀或?qū)懓l(fā)生后，條目即過期。
寫入后到期 — 從上次寫入發(fā)生之后，條目即過期。
自定義策略 — 到期時間由 Expiry 實現(xiàn)獨自計算。

訪問后過期

@Test
public void expireAfterAccessTest() throws InterruptedException {
    LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
            .expireAfterAccess(2, TimeUnit.SECONDS)
            .build(k -> DataObject.get("Data for " + k));
            
    final String key = "A";
    cache.get(key);
    TimeUnit.SECONDS.sleep(2);
    assertNull(cache.getIfPresent(key));
}

寫入后到期

@Test
public void expireAfterWriteTest() throws InterruptedException {
    LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
            .expireAfterWrite(2, TimeUnit.SECONDS)
            .build(k -> DataObject.get("Data for " + k));

    final String key = "A";
    cache.get(key);

    TimeUnit.SECONDS.sleep(2);
    assertNull(cache.getIfPresent(key));
}

自定義過期策略

@Test
public void defineExpireTest() {
    LoadingCache<String, DataObject> cache = Caffeine.newBuilder().expireAfter(new Expiry<String, DataObject>() {
        @Override
        public long expireAfterCreate(
                String key, DataObject value, long currentTime) {
            return value.getData().length() * 1000;
        }
        @Override
        public long expireAfterUpdate(
                String key, DataObject value, long currentTime, long currentDuration) {
            return currentDuration;
        }
        @Override
        public long expireAfterRead(
                String key, DataObject value, long currentTime, long currentDuration) {
            return currentDuration;
        }
    }).build(k -> DataObject.get("Data for " + k));
}

基于引用回收
我們可以將緩存配置為啟用緩存鍵值的垃圾回收。為此，我們將 key 和 value 配置為弱引用，并且我們可以僅配置軟引用以進行垃圾回收。

當沒有任何對對象的強引用時，使用 WeakRefence 可以啟用對象的垃圾收回收。SoftReference 允許對象根據(jù) JVM 的全局最近最少使用（Least-Recently-Used）的策略進行垃圾回收。

弱引用

@Test
public void weakTest() {
    LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
            .expireAfterWrite(10, TimeUnit.SECONDS)
            .weakKeys()
            .weakValues()
            .build(k -> DataObject.get("Data for " + k));
}

軟引用

@Test
public void softTest() {
    LoadingCache<String, DataObject> cache = Caffeine.newBuilder()
            .expireAfterWrite(10, TimeUnit.SECONDS)
            .softValues()
            .build(k -> DataObject.get("Data for " + k));
}

原理

淘汰策略

LRU

LRU的全稱是Least Recently Used，最近最少使用。如果緩存滿了，把最近沒有被使用到的數(shù)據(jù)移出。它的思想是：如果數(shù)據(jù)最近被訪問過，將來被訪問的概率也更高。

最簡單的方式就是使用LinkedHashMap，幾行代碼就能實現(xiàn)。

public class LruCacheLinkedHashMapLazy<K, V> implements LruCache<K,V> {
    private LinkedHashMap<K, V> map;
    private final int CAPACITY;

    public LruCacheLinkedHashMapLazy(int capacity) {
        CAPACITY = capacity;
        map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CAPACITY;
            }
        };
    }
    @Override
    public V get(K key) {
        return map.getOrDefault(key, null);
    }
    @Override
    public void put(K key, V value) {
        map.put(key, value);
    }
}

LinkedHashMap通過hash表和雙向鏈表維護數(shù)據(jù)，如果初始化時accessOrder=true，新加入或者訪問的數(shù)據(jù)都會放到鏈表頭部，這樣，一直沒被訪問的node就會被頂?shù)轿膊?，如果超出緩存大小，把鏈表尾部的?shù)據(jù)刪除即可。

也可以通過HashMap和Doubley-Linked實現(xiàn)，這樣更清晰看出怎么通過雙向鏈表實現(xiàn)：

public class LRUCacheHashMapAndDoublyLinked<K, V> implements LruCache<K, V> {
    private class Node {
        K key;
        V value;
        Node prev, next;

        Node(K k, V v) {
            this.key = k;
            this.value = v;
        }
    }

    private int capacity, count;
    private Map<K, Node> map;
    private Node head, tail;

    public LRUCacheHashMapAndDoublyLinked(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    private void update(Node node) {
        remove(node);
        add(node);
    }

    private void add(Node node) {
        Node after = head.next;
        head.next = node;
        node.prev = head;
        node.next = after;
        after.prev = node;
    }

    private void remove(Node node) {
        Node before = node.prev, after = node.next;
        before.next = after;
        after.prev = before;
    }

    @Override
    public V get(K k) {
        Node n = map.get(k);
        if (null == n) {
            return null;
        }
        update(n);
        return n.value;
    }

    @Override
    public void put(K key, V value) {
        Node n = map.get(key);
        if (null == n) {
            n = new Node(key, value);
            map.put(key, n);
            add(n);
            ++count;
        } else {
            n.value = value;
            update(n);
        }
        if (count > capacity) {
            Node toDel = tail.prev;
            remove(toDel);
            map.remove(toDel.key);
            --count;
        }
    }
}

image.png

但是，上面兩個示例都不是并發(fā)安全的，需要加鎖.

LFU

LFU（Least Frequently Used）算法根據(jù)數(shù)據(jù)的歷史訪問頻率來淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)過去被訪問多次，那么將來被訪問的頻率也更高”。

LFU的每個數(shù)據(jù)塊都有一個引用計數(shù)，所有數(shù)據(jù)塊按照引用計數(shù)排序，具有相同引用計數(shù)的數(shù)據(jù)塊則按照時間排序。

image.png

新加入數(shù)據(jù)插入到隊列尾部（因為引用計數(shù)為1）；
隊列中的數(shù)據(jù)被訪問后，引用計數(shù)增加，隊列重新排序；
當需要淘汰數(shù)據(jù)時，將已經(jīng)排序的列表最后的數(shù)據(jù)塊刪除。

一般情況下，LFU效率要優(yōu)于LRU，且能夠避免周期性或者偶發(fā)性的操作導致緩存命中率下降的問題。但LFU需要記錄數(shù)據(jù)的歷史訪問記錄，一旦數(shù)據(jù)訪問模式改變，LFU需要更長時間來適用新的訪問模式，即：LFU存在歷史數(shù)據(jù)影響將來數(shù)據(jù)的“緩存污染”效用。
需要維護一個隊列記錄所有數(shù)據(jù)的訪問記錄，每個數(shù)據(jù)都需要維護引用計數(shù)。需要記錄所有數(shù)據(jù)的訪問記錄，內(nèi)存消耗較高；需要基于引用計數(shù)排序，性能消耗較高。

Guava cache 實現(xiàn)SLRU

對上面的示例，要并發(fā)安全，只能加鎖。為了改善加鎖后開銷，可以像ConcurrentHashMap一樣，把table分到一個個segment下，每個segment對應一個鎖，來分散全局鎖帶來的性能損失，GuavaCache就是這樣的實現(xiàn)，如下圖

image.png

guava cache還維護兩個隊列，accesQueue和writeQueue，用來實現(xiàn)segement的局部LRU和過期時間。另外還有一個recencyQueue，它用來提高accessQueue更新鎖消耗。如果每次訪問都加鎖更新accessQueue，影響性能，guava把訪問的數(shù)據(jù)更新到recencyQueue，recencyQueue通過ConcurrentLinkedQueue實現(xiàn)，并發(fā)安全。等寫入數(shù)據(jù)時，再加鎖從recencyQueue更新到accesQueue。

另外，對于過期數(shù)據(jù)的清理，guava并不是另起一個線程，而是每次有訪問的時候才清理。

W-TinyLFU

不管是LFU還是LRU，都是希望在緩存填滿后，淘汰掉那些在短期內(nèi)可能不會使用的數(shù)據(jù)，從而提升緩存的命中率。LRU和LFU都有他的局限性。LRU是一個比較流行的算法，它什么問題？它不是抗掃描的。比如cache的大小是N，緩存N+1個item(第一個會被淘汰)，如果順序發(fā)起N個請求。將導致沒有一個命中緩存。

而TinyLFU有一個缺點，在應對突發(fā)流量的時候，可能由于沒有及時構(gòu)建足夠的頻率數(shù)據(jù)來保證自己駐留在緩存中，從而導致緩存的命中率下降，為了解決這個問題，產(chǎn)生了W-TinyLFU算法。
W-TinyLFU由兩部分組成，主緩存使用SLRU回收策略和TinyLFU回收策略，而窗口緩存使用沒有任何回收策略的LRU回收策略，增加的窗口緩存用于應對突發(fā)流量的問題。

W-TinyLFU 是一個綜合LRU和LFU優(yōu)點的實現(xiàn)方式：

image.png

其中TinyLFU維護了近期訪問記錄的頻率信息，作為一個過濾器，當新記錄來時，只有滿足TinyLFU要求的記錄才可以被插入緩存。其中實現(xiàn)算法采用ount-Min Sketch算法。以LRU作為淘汰方式，TinyLFU作為許入過濾器。

CountMin Sketch 通過矩陣和多個hash函數(shù)實現(xiàn)：

image.png

一個key，通過不同的hash定位到數(shù)組index，值加1，最后取min(8,6,7,6)=6作為此key的訪問次數(shù)記錄。因為hash沖突的原因，值不一定準確，但對于LFU的實現(xiàn)，這個誤差可以忽略。下面我們看它是怎么解決LFU缺點的。

因為使用矩陣，跟數(shù)據(jù)量大小沒關系，很好地解決了LFU的內(nèi)存開銷問題。對于數(shù)據(jù)年齡，可以添加一個計數(shù)上限，一旦到達上限，所有記錄的Sketch數(shù)據(jù)都除2，從而實現(xiàn)衰減效果，對于短暫熱點數(shù)據(jù)，如果之后一直沒有訪問，count/2不斷衰減，直至淘汰。

下圖是另一種表達方式： sketch 作為過濾器（filter）。當新來的數(shù)據(jù)比要驅(qū)逐的數(shù)據(jù)高頻時，這個數(shù)據(jù)才會被緩存接納。

image.png

窗口緩存占用總大小的1%左右，主緩存占用99%。Caffeine可以根據(jù)工作負載特性動態(tài)調(diào)整窗口和主空間的大小，如果新增數(shù)據(jù)頻率比較高，大窗口更受歡迎;如果新增數(shù)據(jù)頻率偏小，小窗口更受歡迎。主緩存內(nèi)部包含兩個部分，一部分為Protected，用于存比較熱的數(shù)據(jù)，它占用主緩存80%空間；另一部分是Probation，用于存相對比較冷的數(shù)據(jù)，占用主緩存20%空間，數(shù)據(jù)可以在這兩部分空間里面互相轉(zhuǎn)移。

緩存淘汰的過程：新添加的數(shù)據(jù)首先放入窗口緩存中，如果窗口緩存滿了，則把窗口緩存淘汰的數(shù)據(jù)轉(zhuǎn)移到主緩存Probation區(qū)域中。如果這時主緩存也滿了，則從主緩存的Probation區(qū)域淘汰數(shù)據(jù)，把這條數(shù)據(jù)稱為受害者，從窗口緩存淘汰的數(shù)據(jù)稱為候選人。接下來候選人和受害者進行一次pk，來決定去留。pk的方式是通過TinyFLU記錄的訪問頻率來進行判斷

首先獲取候選人和受害者的頻率
1.如果候選人大于受害者，則淘汰受害者

如果候選人頻率小于等于5，則淘汰候選人
其余情況隨機處理。

Caffeine中的pk代碼：

 boolean admit(K candidateKey, K victimKey) {

 int victimFreq = frequencySketch().frequency(victimKey);

 int candidateFreq = frequencySketch().frequency(candidateKey);

 if (candidateFreq > victimFreq) {

 return true;

 } else if (candidateFreq <= 5) {

 return false;

 }

 int random = ThreadLocalRandom.current().nextInt();

 return ((random & 127) == 0);

 }

讀寫優(yōu)化

Caffeine的底層數(shù)據(jù)存儲采用ConcurrentHashMap。因為Caffeine面向JDK8，在jdk8中ConcurrentHashMap增加了紅黑樹，在hash沖突嚴重時也能有良好的讀性能。
Caffeine的緩存清除動作是觸發(fā)式的，它可能發(fā)生在讀、寫請求后。這個動作在Caffeine中是異步執(zhí)行的，默認執(zhí)行的線程池是ForkJoinPool.commonPool()。相比較Guava cache的同步執(zhí)行清除操作，Caffeine的異步執(zhí)行能夠提高讀寫請求的效率。針對讀寫請求后的異步操作（清除緩存、調(diào)整LRU隊列順序等操作），Caffeine分別使用了ReadBuffer和WriterBuffer。使用Buffer一方面能夠合并操作，另一方面可以避免鎖爭用的問題。

在時間的過期策略中，Caffeine針對不同的過期策略采用不同的實現(xiàn)：針對寫后過期，維護了一個寫入順序隊列；針對讀后過期，維護了一個讀取順序隊列；針對expireAfter指定的多種時間組合過期策略中，采用了二維時間輪來實現(xiàn)。Caffeine使用上述這些策略，來提高其在緩存過期清除時的效率。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Caffeine使用及原理

Caffeine使用及原理

依賴

填充緩存

手動填充

同步加載

異步加載

值回收

原理

LRU

LFU

Guava cache 實現(xiàn)SLRU

W-TinyLFU

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Caffeine使用及原理

依賴

填充緩存

手動填充

同步加載

異步加載

值回收

原理

LRU

LFU

Guava cache 實現(xiàn)SLRU

W-TinyLFU

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av