[[332941]]

jvm內(nèi)部緩存有哪些

原生Java

簡(jiǎn)單的在HashMap的鏈?zhǔn)椒ㄔ黾有碌囊眯纬梢粋€(gè)鏈表，即是一個(gè)HashMap又是一個(gè)鏈表，這樣輸出即有序，也可以根據(jù)訪問(wèn)來(lái)動(dòng)態(tài)調(diào)整順序，達(dá)到FIFO或者LRU的特點(diǎn)。

使用ConcurrentHashMap作為緩存，沒(méi)有淘汰功能或者手動(dòng)淘汰。但是尋找效率較高，而且線程安全

可以明顯看出這個(gè)存在的問(wèn)題，線程不安全，需要額外加鎖，功能結(jié)構(gòu)單一，沒(méi)有過(guò)期時(shí)間容易存在內(nèi)存泄露

Guava

因?yàn)長(zhǎng)inkedHashMap存在的問(wèn)題，所以大神們?cè)诖嘶A(chǔ)上造出了Guava

既然HashMap線程不安全，那么就使用CurrentHashMap(類似不完全是)，為了實(shí)現(xiàn)過(guò)期那么就給數(shù)據(jù)加上時(shí)間戳標(biāo)志，為了實(shí)現(xiàn)寫(xiě)后過(guò)期，讀后過(guò)期，這兩種配置，就使用了多條隊(duì)列分別代表讀和寫(xiě)

EHCHCHED

• Ehcache支持持久化到本地磁盤(pán)，Guava不可以;
• Ehcache有現(xiàn)成的集群解決方案，Guava沒(méi)有。不過(guò)個(gè)人感覺(jué)比較雞肋，對(duì)JVM級(jí)別的緩存來(lái)講太重了
• Ehcache jar包龐大，Guava Cache只是Guava jar包中的工具之一，而且后者遠(yuǎn)遠(yuǎn)小于Ehcache;
• 兩種緩存當(dāng)緩存過(guò)期或者沒(méi)有命中的時(shí)候都可以通過(guò)load接口重載數(shù)據(jù)，調(diào)用方式略有不同。兩者的主要區(qū)別是Ehcache的緩存load的時(shí)候，允許用戶返回null，而Guava Cache則不允許返回為null，因?yàn)镚uava Cache是根據(jù)value的值是否為null來(lái)判斷是否需要load，所以不允許返回為null，但是使用的時(shí)候可以使用空對(duì)象替換。不允許返回null是一個(gè)很好的考慮;
• Ehcache有內(nèi)存占用大小統(tǒng)計(jì)，Guava Cache沒(méi)有，需要自己開(kāi)發(fā);
• Ehcache在put緩存的時(shí)候，對(duì)K、V都做了包裝，對(duì)GC有一定影響。

Caffeine

Caffeine是Spring 5默認(rèn)支持的Cache，可見(jiàn)Spring對(duì)它的看重，那么Spring為什么喜新厭舊的拋棄Guava而追求Caffeine呢?

緩存的淘汰策略是為了預(yù)測(cè)哪些數(shù)據(jù)在短期內(nèi)最可能被再次用到，從而提升緩存的命中率。LRU由于實(shí)現(xiàn)簡(jiǎn)單、高效的運(yùn)行時(shí)表現(xiàn)以及在常規(guī)的使用場(chǎng)景下有不錯(cuò)的命中率，或許是目前最佳的實(shí)現(xiàn)途徑。但 LRU 通過(guò)歷史數(shù)據(jù)來(lái)預(yù)測(cè)未來(lái)是局限的，它會(huì)認(rèn)為最后到來(lái)的數(shù)據(jù)是最可能被再次訪問(wèn)的，從而給與它最高的優(yōu)先級(jí)。這樣就意味著淘汰真正熱點(diǎn)數(shù)據(jù)，為了解決這個(gè)問(wèn)題業(yè)界運(yùn)用一些數(shù)據(jù)結(jié)構(gòu)上的改進(jìn)巧妙的解決這個(gè)問(wèn)題。

下面的內(nèi)容是轉(zhuǎn)載的一篇譯文，如果需要查看譯文原文，請(qǐng)點(diǎn)擊這里,英語(yǔ)好的同學(xué)也可以直接查看英文原作。

緩存是提升性能的通用方法，現(xiàn)在大多數(shù)的緩存實(shí)現(xiàn)都使用了經(jīng)典的技術(shù)。這篇文章中，我們會(huì)發(fā)掘Caffeine中的現(xiàn)代的實(shí)現(xiàn)方法。Caffeine是一個(gè)開(kāi)源的Java緩存庫(kù)，它能提供高命中率和出色的并發(fā)能力。期望讀者們能被這些想法激發(fā)，進(jìn)而將它們應(yīng)用到任何你喜歡的編程語(yǔ)言中。

驅(qū)逐策略

緩存的驅(qū)逐策略是為了預(yù)測(cè)哪些數(shù)據(jù)在短期內(nèi)最可能被再次用到，從而提升緩存的命中率。由于簡(jiǎn)潔的實(shí)現(xiàn)、高效的運(yùn)行時(shí)表現(xiàn)以及在常規(guī)的使用場(chǎng)景下有不錯(cuò)的命中率，LRU(Least Recently Used)策略或許是最流行的驅(qū)逐策略。但LRU通過(guò)歷史數(shù)據(jù)來(lái)預(yù)測(cè)未來(lái)是局限的，它會(huì)認(rèn)為最后到來(lái)的數(shù)據(jù)是最可能被再次訪問(wèn)的，從而給與它最高的優(yōu)先級(jí)。

現(xiàn)代緩存擴(kuò)展了對(duì)歷史數(shù)據(jù)的使用，結(jié)合就近程度(recency)和訪問(wèn)頻次(frequency)來(lái)更好的預(yù)測(cè)數(shù)據(jù)。其中一種保留歷史信息的方式是使用popularity sketch(一種壓縮、概率性的數(shù)據(jù)結(jié)構(gòu))來(lái)從一大堆訪問(wèn)事件中定位頻繁的訪問(wèn)者?？梢詤⒖糃ountMin Sketch算法，它由計(jì)數(shù)矩陣和多個(gè)哈希方法實(shí)現(xiàn)。發(fā)生一次讀取時(shí)，矩陣中每行對(duì)應(yīng)的計(jì)數(shù)器增加計(jì)數(shù)，估算頻率時(shí)，取數(shù)據(jù)對(duì)應(yīng)是所有行中計(jì)數(shù)的最小值。這個(gè)方法讓我們從空間、效率、以及適配矩陣的長(zhǎng)寬引起的哈希碰撞的錯(cuò)誤率上做權(quán)衡。

Window TinyLFU(W-TinyLFU)算法將sketch作為過(guò)濾器，當(dāng)新來(lái)的數(shù)據(jù)比要驅(qū)逐的數(shù)據(jù)高頻時(shí)，這個(gè)數(shù)據(jù)才會(huì)被緩存接納。這個(gè)許可窗口給予每個(gè)數(shù)據(jù)項(xiàng)積累熱度的機(jī)會(huì)，而不是立即過(guò)濾掉。這避免了持續(xù)的未命中，特別是在突然流量暴漲的的場(chǎng)景中，一些短暫的重復(fù)流量就不會(huì)被長(zhǎng)期保留。為了刷新歷史數(shù)據(jù)，一個(gè)時(shí)間衰減進(jìn)程被周期性或增量的執(zhí)行，給所有計(jì)數(shù)器減半。

對(duì)于長(zhǎng)期保留的數(shù)據(jù)，W-TinyLFU使用了分段LRU(Segmented LRU，縮寫(xiě)SLRU)策略。起初，一個(gè)數(shù)據(jù)項(xiàng)存儲(chǔ)被存儲(chǔ)在試用段(probationary segment)中，在后續(xù)被訪問(wèn)到時(shí)，它會(huì)被提升到保護(hù)段(protected segment)中(保護(hù)段占總?cè)萘康?0%)。保護(hù)段滿后，有的數(shù)據(jù)會(huì)被淘汰回試用段，這也可能級(jí)聯(lián)的觸發(fā)試用段的淘汰。這套機(jī)制確保了訪問(wèn)間隔小的熱數(shù)據(jù)被保存下來(lái)，而被重復(fù)訪問(wèn)少的冷數(shù)據(jù)則被回收。

如圖中數(shù)據(jù)庫(kù)和搜索場(chǎng)景的結(jié)果展示，通過(guò)考慮就近程度和頻率能大大提升LRU的表現(xiàn)。一些高級(jí)的策略，像ARC，LIRS和W-TinyLFU都提供了接近最理想的命中率。想看更多的場(chǎng)景測(cè)試，請(qǐng)查看相應(yīng)的論文，也可以在使用simulator來(lái)測(cè)試自己的場(chǎng)景。

過(guò)期策略

過(guò)期的實(shí)現(xiàn)里，往往每個(gè)數(shù)據(jù)項(xiàng)擁有不同的過(guò)期時(shí)間。因?yàn)槿萘康南拗?，過(guò)期后數(shù)據(jù)需要被懶淘汰，否則這些已過(guò)期的臟數(shù)據(jù)會(huì)污染到整個(gè)緩存。一般緩存中會(huì)啟用專有的清掃線程周期性的遍歷清理緩存。這個(gè)策略相比在每次讀寫(xiě)操作時(shí)按照過(guò)期時(shí)間排序的優(yōu)先隊(duì)列來(lái)清理過(guò)期緩存要好，因?yàn)楹笈_(tái)線程隱藏了的過(guò)期數(shù)據(jù)清除的時(shí)間開(kāi)銷。

鑒于大多數(shù)場(chǎng)景里不同數(shù)據(jù)項(xiàng)使用的都是固定的過(guò)期時(shí)長(zhǎng)，Caffien采用了統(tǒng)一過(guò)期時(shí)間的方式。這個(gè)限制讓用O(1)的有序隊(duì)列組織數(shù)據(jù)成為可能。針對(duì)數(shù)據(jù)的寫(xiě)后過(guò)期，維護(hù)了一個(gè)寫(xiě)入順序隊(duì)列，針對(duì)讀后過(guò)期，維護(hù)了一個(gè)讀取順序隊(duì)列。緩存能復(fù)用驅(qū)逐策略下的隊(duì)列以及下面將要介紹的并發(fā)機(jī)制，讓過(guò)期的數(shù)據(jù)項(xiàng)在緩存的維護(hù)階段被拋棄掉。

并發(fā)

由于在大多數(shù)的緩存策略中，數(shù)據(jù)的讀取都會(huì)伴隨對(duì)緩存狀態(tài)的寫(xiě)操作，并發(fā)的緩存讀取被視為一個(gè)難點(diǎn)問(wèn)題。傳統(tǒng)的解決方式是用同步鎖。這可以通過(guò)將緩存的數(shù)據(jù)劃成多個(gè)分區(qū)來(lái)進(jìn)行鎖拆分優(yōu)化。不幸的是熱點(diǎn)數(shù)據(jù)所持有的鎖會(huì)比其他數(shù)據(jù)更常的被占有，在這種場(chǎng)景下鎖拆分的性能提升也就沒(méi)那么好了。當(dāng)單個(gè)鎖的競(jìng)爭(zhēng)成為瓶頸后，接下來(lái)的經(jīng)典的優(yōu)化方式是只更新單個(gè)數(shù)據(jù)的元數(shù)據(jù)信息，以及使用隨機(jī)采樣、基于FIFO的驅(qū)逐策略來(lái)減少數(shù)據(jù)操作。這些策略會(huì)帶來(lái)高性能的讀和低性能的寫(xiě)，同時(shí)在選擇驅(qū)逐對(duì)象時(shí)也比較困難。

另一種可行方案來(lái)自于數(shù)據(jù)庫(kù)理論，通過(guò)提交日志的方式來(lái)擴(kuò)展寫(xiě)的性能。寫(xiě)入操作先記入日志中，隨后異步的批量執(zhí)行，而不是立即寫(xiě)入到數(shù)據(jù)結(jié)構(gòu)中。這種思想可以應(yīng)用到緩存中，執(zhí)行哈希表的操作，將操作記錄到緩沖區(qū)，然后在合適的時(shí)機(jī)執(zhí)行緩沖區(qū)中的內(nèi)容。這個(gè)策略依然需要同步鎖或者tryLock，不同的是把對(duì)鎖的競(jìng)爭(zhēng)轉(zhuǎn)移到對(duì)緩沖區(qū)的追加寫(xiě)上。

在Caffeine中，有一組緩沖區(qū)被用來(lái)記錄讀寫(xiě)。一次訪問(wèn)首先會(huì)被因線程而異的哈希到stripped ring buffer上，當(dāng)檢測(cè)到競(jìng)爭(zhēng)時(shí)，緩沖區(qū)會(huì)自動(dòng)擴(kuò)容。一個(gè)ring buffer容量滿載后，會(huì)觸發(fā)異步的執(zhí)行操作，而后續(xù)的對(duì)該ring buffer的寫(xiě)入會(huì)被丟棄，直到這個(gè)ring buffer可被使用。雖然因?yàn)閞ing buffer容量滿而無(wú)法被記錄該訪問(wèn)，但緩存值依然會(huì)返回給調(diào)用方。這種策略信息的丟失不會(huì)帶來(lái)大的影響，因?yàn)閃-TinyLFU能識(shí)別出我們希望保存的熱點(diǎn)數(shù)據(jù)。通過(guò)使用因線程而異的哈希算法替代在數(shù)據(jù)項(xiàng)的鍵上做哈希，緩存避免了瞬時(shí)的熱點(diǎn)key的競(jìng)爭(zhēng)問(wèn)題。

寫(xiě)數(shù)據(jù)時(shí)，采用更傳統(tǒng)的并發(fā)隊(duì)列，每次變更會(huì)引起一次立即的執(zhí)行。雖然數(shù)據(jù)的損失是不可接受的，但我們?nèi)匀挥泻芏喾椒梢詠?lái)優(yōu)化寫(xiě)緩沖區(qū)。所有類型的緩沖區(qū)都被多個(gè)的線程寫(xiě)入，但卻通過(guò)單個(gè)線程來(lái)執(zhí)行。這種多生產(chǎn)者/單個(gè)消費(fèi)者的模式允許了更簡(jiǎn)單、高效的算法來(lái)實(shí)現(xiàn)。

緩沖區(qū)和細(xì)粒度的寫(xiě)帶來(lái)了單個(gè)數(shù)據(jù)項(xiàng)的操作亂序的競(jìng)態(tài)條件。插入、讀取、更新、刪除都可能被各種順序的重放，如果這個(gè)策略控制的不合適，則可能引起懸垂索引。解決方案是通過(guò)狀態(tài)機(jī)來(lái)定義單個(gè)數(shù)據(jù)項(xiàng)的生命周期。

在基準(zhǔn)測(cè)試中，緩沖區(qū)隨著哈希表的增長(zhǎng)而增長(zhǎng)，它的的使用相對(duì)更節(jié)省資源。讀的性能隨著CPU的核數(shù)線性增長(zhǎng)，是哈希表吞吐量的33%。寫(xiě)入有10%的性能損耗，這是因?yàn)楦鹿１頃r(shí)的競(jìng)爭(zhēng)是最主要的開(kāi)銷。

Caffeine

舉個(gè)例子

Mysql的緩存池，內(nèi)部實(shí)現(xiàn)是一個(gè)LRU，但是其內(nèi)部有個(gè)中間點(diǎn),指向倒數(shù)3/8，一半是old區(qū)，另一半是young區(qū)，新數(shù)據(jù)插入是直接插入young區(qū)，這樣就保護(hù)了真正的老數(shù)據(jù)不會(huì)被沖刷掉。

多級(jí)隊(duì)列的形式

LFU結(jié)合頻率這一屬性給予更好的預(yù)測(cè)緩存數(shù)據(jù)是否在未來(lái)被使用。

但是傳統(tǒng)LFU有其局限性：

LFU實(shí)現(xiàn)需要維護(hù)大而復(fù)雜的元數(shù)據(jù)(頻次統(tǒng)計(jì)數(shù)據(jù)等)

大多數(shù)實(shí)際工作負(fù)載中，訪問(wèn)頻率隨著時(shí)間的推移而發(fā)生根本變化，而傳統(tǒng)LFU無(wú)法周期衰減頻率

傳統(tǒng)LFU的實(shí)現(xiàn)通過(guò)外接一個(gè)HashMap統(tǒng)計(jì)頻率，但是HashMap存在Hash沖突，這會(huì)導(dǎo)致頻率統(tǒng)計(jì)的不準(zhǔn)確。

為了解決這些問(wèn)題，Caffeine提出一種新的算法W-TinyLFU，它可以解決頻率統(tǒng)計(jì)不準(zhǔn)確以及訪問(wèn)頻率衰減問(wèn)題。這個(gè)方法讓我們從空間、效率、以及適配矩陣的長(zhǎng)寬引起的哈希碰撞的錯(cuò)誤率上做權(quán)衡。

傳統(tǒng)Hash存在Hash沖突的問(wèn)題，使用LFU算法時(shí)候記錄頻率的話一旦發(fā)生hash沖突可能造成頻率的統(tǒng)計(jì)錯(cuò)誤。

W-TinyLFU算法使用一種Count-Min Sketch解決維護(hù)空間大的問(wèn)題，類似布隆過(guò)濾器，降低沖突可能性，原理是多次hash分散開(kāi)來(lái)，取最小值作為頻率，一次Hash沖突的幾率是1%的話，4次Hash的幾率就是1%的4次方，大大降低的沖突可能性。

在Caffeine中為了實(shí)現(xiàn)Count-Min Sketch它在其中村政府，存放四個(gè)算法

其中randomSeed是一個(gè)隨機(jī)數(shù)，sampleSize=開(kāi)始設(shè)置的緩存最大樹(shù)*10;table= 最大緩存數(shù)最接近的2的次方數(shù)(100的話是128，50是64);tableMask = table.length-1;size=0

在向緩存put數(shù)據(jù)的時(shí)候會(huì)調(diào)用

這個(gè)AddTask是一個(gè)Runnable，其中run方法會(huì)調(diào)用increment方法。

Caffeine比guava好在哪

W-TinyLFU

傳統(tǒng)的LFU受時(shí)間周期的影響比較大。所以各種LFU的變種出現(xiàn)了，基于時(shí)間周期進(jìn)行衰減，或者在最近某個(gè)時(shí)間段內(nèi)的頻率。同樣的LFU也會(huì)使用額外空間記錄每一個(gè)數(shù)據(jù)訪問(wèn)的頻率，即使數(shù)據(jù)沒(méi)有在緩存中也需要記錄，所以需要維護(hù)的額外空間很大。

可以試想我們對(duì)這個(gè)維護(hù)空間建立一個(gè)hashMap，每個(gè)數(shù)據(jù)項(xiàng)都會(huì)存在這個(gè)hashMap中，當(dāng)數(shù)據(jù)量特別大的時(shí)候，這個(gè)hashMap也會(huì)特別大。

再回到LRU，我們的LRU也不是那么一無(wú)是處，LRU可以很好的應(yīng)對(duì)突發(fā)流量的情況，因?yàn)樗恍枰塾?jì)數(shù)據(jù)頻率。

所以W-TinyLFU結(jié)合了LRU和LFU，以及其他的算法的一些特點(diǎn)。

頻率記錄

首先要說(shuō)到的就是頻率記錄的問(wèn)題，我們要實(shí)現(xiàn)的目標(biāo)是利用有限的空間可以記錄隨時(shí)間變化的訪問(wèn)頻率。在W-TinyLFU中使用Count-Min Sketch記錄我們的訪問(wèn)頻率，而這個(gè)也是布隆過(guò)濾器的一種變種。

如果需要記錄一個(gè)值，那我們需要通過(guò)多種Hash算法對(duì)其進(jìn)行處理hash，然后在對(duì)應(yīng)的hash算法的記錄中+1，為什么需要多種hash算法呢?由于這是一個(gè)壓縮算法必定會(huì)出現(xiàn)沖突，比如我們建立一個(gè)Long的數(shù)組，通過(guò)計(jì)算出每個(gè)數(shù)據(jù)的hash的位置。比如張三和李四，他們兩有可能hash值都是相同，比如都是1那Long[1]這個(gè)位置就會(huì)增加相應(yīng)的頻率，張三訪問(wèn)1萬(wàn)次，李四訪問(wèn)1次那Long[1]這個(gè)位置就是1萬(wàn)零1，如果取李四的訪問(wèn)評(píng)率的時(shí)候就會(huì)取出是1萬(wàn)零1，但是李四命名只訪問(wèn)了1次啊，為了解決這個(gè)問(wèn)題，所以用了多個(gè)hash算法可以理解為long[][]二維數(shù)組的一個(gè)概念，比如在第一個(gè)算法張三和李四沖突了，但是在第二個(gè)，第三個(gè)中很大的概率不沖突，比如一個(gè)算法大概有1%的概率沖突，那四個(gè)算法一起沖突的概率是1%的四次方。通過(guò)這個(gè)模式我們?nèi)±钏牡脑L問(wèn)率的時(shí)候取所有算法中，李四訪問(wèn)最低頻率的次數(shù)。所以他的名字叫Count-Min Sketch。

這里和以前的做個(gè)對(duì)比，簡(jiǎn)單的舉個(gè)例子:如果一個(gè)hashMap來(lái)記錄這個(gè)頻率，如果我有100個(gè)數(shù)據(jù)，那這個(gè)HashMap就得存儲(chǔ)100個(gè)這個(gè)數(shù)據(jù)的訪問(wèn)頻率。哪怕我這個(gè)緩存的容量是1，因?yàn)長(zhǎng)fu的規(guī)則我必須全部記錄這個(gè)100個(gè)數(shù)據(jù)的訪問(wèn)頻率。如果有更多的數(shù)據(jù)我就有記錄更多的。

在Count-Min Sketch中，我這里直接說(shuō)caffeine中的實(shí)現(xiàn)吧(在FrequencySketch這個(gè)類中),如果你的緩存大小是100，他會(huì)生成一個(gè)long數(shù)組大小是和100最接近的2的冪的數(shù)，也就是128。而這個(gè)數(shù)組將會(huì)記錄我們的訪問(wèn)頻率。在caffeine中規(guī)定頻率最大為15，15的二進(jìn)制位1111，總共是4位，而Long型是64位。所以每個(gè)Long型可以放16種算法，但是caffeine并沒(méi)有這么做，只用了四種hash算法，每個(gè)Long型被分為四段，每段里面保存的是四個(gè)算法的頻率。這樣做的好處是可以進(jìn)一步減少Hash沖突，原先128大小的hash，就變成了128X4。

一個(gè)Long的結(jié)構(gòu)如下:

我們的4個(gè)段分為A,B,C,D，在后面我也會(huì)這么叫它們。而每個(gè)段里面的四個(gè)算法我叫他s1,s2,s3,s4。下面舉個(gè)例子如果要添加一個(gè)訪問(wèn)50的數(shù)字頻率應(yīng)該怎么做?我們這里用size=100來(lái)舉例。

1. 首先確定50這個(gè)hash是在哪個(gè)段里面，通過(guò)hash & 3(3的二進(jìn)制是11)必定能獲得小于4的數(shù)字，假設(shè)hash & 3=0，那就在A段。
2. 對(duì)50的hash再用其他hash算法再做一次hash，得到long數(shù)組的位置，也就是在長(zhǎng)度128數(shù)組中的位置。假設(shè)用s1算法得到1，s2算法得到3，s3算法得到4，s4算法得到0。
3. 因?yàn)镾1算法得到的是1，所以在long[1]的A段里面的s1位置進(jìn)行+1,簡(jiǎn)稱1As1加1，然后在3As2加1，在4As3加1，在0As4加1。

這個(gè)時(shí)候有人會(huì)質(zhì)疑頻率最大為15的這個(gè)是否太小?沒(méi)關(guān)系在這個(gè)算法中，比如size等于100，如果他全局提升了size*10也就是1000次就會(huì)全局除以2衰減，衰減之后也可以繼續(xù)增加，這個(gè)算法再W-TinyLFU的論文中證明了其可以較好的適應(yīng)時(shí)間段的訪問(wèn)頻率。

讀寫(xiě)性能

在guava cache中我們說(shuō)過(guò)其讀寫(xiě)操作中夾雜著過(guò)期時(shí)間的處理，也就是你在一次Put操作中有可能還會(huì)做淘汰操作，所以其讀寫(xiě)性能會(huì)受到一定影響，可以看上面的圖中，caffeine的確在讀寫(xiě)操作上面完爆guava cache。主要是因?yàn)樵赾affeine，對(duì)這些事件的操作是通過(guò)異步操作，他將事件提交至隊(duì)列，這里的隊(duì)列的數(shù)據(jù)結(jié)構(gòu)是RingBuffer,不清楚的可以看看這篇文章,你應(yīng)該知道的高性能無(wú)鎖隊(duì)列Disruptor。然后會(huì)通過(guò)默認(rèn)的ForkJoinPool.commonPool()，或者自己配置線程池，進(jìn)行取隊(duì)列操作，然后在進(jìn)行后續(xù)的淘汰，過(guò)期操作。

當(dāng)然讀寫(xiě)也是有不同的隊(duì)列，在caffeine中認(rèn)為緩存讀比寫(xiě)多很多，所以對(duì)于寫(xiě)操作是所有線程共享一個(gè)Ringbuffer。

對(duì)于讀操作比寫(xiě)操作更加頻繁，進(jìn)一步減少競(jìng)爭(zhēng)，其為每個(gè)線程配備了一個(gè)RingBuffer：

數(shù)據(jù)淘汰策略

在caffeine所有的數(shù)據(jù)都在ConcurrentHashMap中，這個(gè)和guava cache不同，guava cache是自己實(shí)現(xiàn)了個(gè)類似ConcurrentHashMap的結(jié)構(gòu)。在caffeine中有三個(gè)記錄引用的LRU隊(duì)列:

• Eden隊(duì)列:在caffeine中規(guī)定只能為緩存容量的%1,如果size=100,那這個(gè)隊(duì)列的有效大小就等于1。這個(gè)隊(duì)列中記錄的是新到的數(shù)據(jù)，防止突發(fā)流量由于之前沒(méi)有訪問(wèn)頻率，而導(dǎo)致被淘汰。比如有一部新劇上線，在最開(kāi)始其實(shí)是沒(méi)有訪問(wèn)頻率的，防止上線之后被其他緩存淘汰出去，而加入這個(gè)區(qū)域。伊甸區(qū)，最舒服最安逸的區(qū)域，在這里很難被其他數(shù)據(jù)淘汰。
• Probation隊(duì)列:叫做緩刑隊(duì)列，在這個(gè)隊(duì)列就代表你的數(shù)據(jù)相對(duì)比較冷，馬上就要被淘汰了。這個(gè)有效大小為size減去eden減去protected。
• Protected隊(duì)列:在這個(gè)隊(duì)列中，可以稍微放心一下了，你暫時(shí)不會(huì)被淘汰，但是別急，如果Probation隊(duì)列沒(méi)有數(shù)據(jù)了或者Protected數(shù)據(jù)滿了，你也將會(huì)被面臨淘汰的尷尬局面。當(dāng)然想要變成這個(gè)隊(duì)列，需要把Probation訪問(wèn)一次之后，就會(huì)提升為Protected隊(duì)列。這個(gè)有效大小為(size減去eden) X 80% 如果size =100，就會(huì)是79。

這三個(gè)隊(duì)列關(guān)系如下:

1. 所有的新數(shù)據(jù)都會(huì)進(jìn)入Eden。
2. Eden滿了，淘汰進(jìn)入Probation。
3. 如果在Probation中訪問(wèn)了其中某個(gè)數(shù)據(jù)，則這個(gè)數(shù)據(jù)升級(jí)為Protected。
4. 如果Protected滿了又會(huì)繼續(xù)降級(jí)為Probation。

對(duì)于發(fā)生數(shù)據(jù)淘汰的時(shí)候，會(huì)從Probation中進(jìn)行淘汰。會(huì)把這個(gè)隊(duì)列中的數(shù)據(jù)隊(duì)頭稱為受害者，這個(gè)隊(duì)頭肯定是最早進(jìn)入的，按照LRU隊(duì)列的算法的話那他其實(shí)他就應(yīng)該被淘汰，但是在這里只能叫他受害者，這個(gè)隊(duì)列是緩刑隊(duì)列，代表馬上要給他行刑了。這里會(huì)取出隊(duì)尾叫候選者，也叫攻擊者。這里受害者會(huì)和攻擊者皇城PK決出我們應(yīng)該被淘汰的。

通過(guò)我們的Count-Min Sketch中的記錄的頻率數(shù)據(jù)有以下幾個(gè)判斷:

• 如果攻擊者大于受害者，那么受害者就直接被淘汰。
• 如果攻擊者<=5，那么直接淘汰攻擊者。這個(gè)邏輯在他的注釋中有解釋:

他認(rèn)為設(shè)置一個(gè)預(yù)熱的門(mén)檻會(huì)讓整體命中率更高。

其他情況，隨機(jī)淘汰。