[[277692]]

原生Java

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

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

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

Guava

因?yàn)長inkedHashMap存在的問題，所以大神們在此基礎(chǔ)上造出了Guava

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

EHCHCHED

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

Caffeine

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

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

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

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

驅(qū)逐策略

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

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

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

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

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

過期策略

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

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

并發(fā)

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

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

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

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

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

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

Caffeine

舉個例子

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

多級隊(duì)列的形式

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

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

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

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

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

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

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

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

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

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

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

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

Caffeine比guava好在哪

W-TinyLFU

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

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

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

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

頻率記錄

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

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

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

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

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

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

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

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

讀寫性能

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

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

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

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

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

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

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

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

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

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

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

• 他認(rèn)為設(shè)置一個預(yù)熱的門檻會讓整體命中率更高。
• 其他情況，隨機(jī)淘汰。