[[439213]]

本文轉(zhuǎn)載自微信公眾號「Golang夢工廠」，作者AsongGo 。轉(zhuǎn)載本文請聯(lián)系Golang夢工廠公眾號。

前言

哈嘍，大家好，我是asong。最近想動手寫一個localcache練練手，工作這么久了，也看過很多同事實現(xiàn)的本地緩存，都各有所長，自己平時也在思考如何實現(xiàn)一個高性能的本地緩存，接下來我將基于自己的理解實現(xiàn)一版本地緩存，歡迎各位大佬們提出寶貴意見，我會根據(jù)意見不斷完善的。

本篇主要介紹設(shè)計一個本地緩存都要考慮什么點，后續(xù)為實現(xiàn)文章，歡迎關(guān)注這個系列。

為什么要有本地緩存

隨著互聯(lián)網(wǎng)的普及，用戶數(shù)和訪問量越來越大，這就需要我們的應(yīng)用支撐更多的并發(fā)量，比如某寶的首頁流量，大量的用戶同時進(jìn)入首頁，對我們的應(yīng)用服務(wù)器和數(shù)據(jù)庫服務(wù)器造成的計算也是巨大的，本身數(shù)據(jù)庫訪問就占用數(shù)據(jù)庫連接，導(dǎo)致網(wǎng)絡(luò)開銷巨大，在面對如此高的并發(fā)量下，數(shù)據(jù)庫就會面臨瓶頸，這時就要考慮加緩存，緩存就分為分布式緩存和本地緩存，大多數(shù)場景我們使用分布式緩存就可以滿足要求，分布式緩存訪問速度也很快，但是數(shù)據(jù)需要跨網(wǎng)絡(luò)傳輸，在面對首頁這種高并發(fā)量級下，對性能要求是很高的，不能放過一點點的性能優(yōu)化空間，這時我們就可以選擇使用本地緩存來提高性能，本地緩存不需要跨網(wǎng)絡(luò)傳輸，應(yīng)用和cache都在同一個進(jìn)程內(nèi)部，快速請求，適用于首頁這種數(shù)據(jù)更新頻率較低的業(yè)務(wù)場景。

綜上所述，我們往往使用本地緩存后的系統(tǒng)架構(gòu)是這樣的：

本地緩存雖然帶來性能優(yōu)化，不過也是有一些弊端的，緩存與應(yīng)用程序耦合，多個應(yīng)用程序無法直接的共享緩存，各應(yīng)用或集群的各節(jié)點都需要維護(hù)自己的單獨(dú)緩存，對內(nèi)存是一種浪費(fèi)，使用緩存的是我們程序員自己，我們要根據(jù)根據(jù)數(shù)據(jù)類型、業(yè)務(wù)場景來準(zhǔn)確判斷使用何種類型的緩存，如何使用這種緩存，以最小的成本最快的效率達(dá)到最優(yōu)的目的。

思考：如何實現(xiàn)一個高性能本地緩存

數(shù)據(jù)結(jié)構(gòu)

第一步我們就要考慮數(shù)據(jù)該怎樣存儲;數(shù)據(jù)的查找效率要高，首先我們就想到了哈希表，哈希表的查找效率高，時間復(fù)雜度為O(1)，可以滿足我們的需求;確定是使用什么結(jié)構(gòu)來存儲，接下來我們要考慮以什么類型進(jìn)行存儲，因為不同的業(yè)務(wù)場景使用的數(shù)據(jù)類型不同，為了通用，在java中我們可以使用泛型，Go語言中暫時沒有泛型，我們可以使用interface類型來代替，把解析數(shù)據(jù)交給程序員自己來進(jìn)行斷言，增強(qiáng)了可擴(kuò)展性，同時也增加一些風(fēng)險。

總結(jié)：

• 數(shù)據(jù)結(jié)構(gòu)：哈希表;
• key：string類型;
• value：interface類型;

并發(fā)安全

本地緩存的應(yīng)用肯定會面對并發(fā)讀寫的場景，這是就要考慮并發(fā)安全的問題。因為我們選擇的是哈希結(jié)構(gòu)，Go語言中主要提供了兩種哈希，一種是非線程安全的map，一種是線程安全的sync.map，為了方便我們可以直接選擇sync.map，也可以考慮使用map+sync.RWMutex組合方式自己實現(xiàn)保證線程安全，網(wǎng)上有人對這兩種方式進(jìn)行比較，在讀操作遠(yuǎn)多于寫操作的時候，使用sync.map的性能是遠(yuǎn)高于map+sync.RWMutex的組合的。在本地緩存中讀操作是遠(yuǎn)高于寫操作的，但是我們本地緩存不僅支持進(jìn)行數(shù)據(jù)存儲的時候要使用鎖，進(jìn)行過期清除等操作時也需要加鎖，所以使用map+sync.RWMutex的方式更靈活，所以這里我們選擇這種方式保證并發(fā)安全。

高性能并發(fā)訪問

加鎖可以保證數(shù)據(jù)的讀寫安全性，但是會增加鎖競爭，本地緩存本來就是為了提升性能而設(shè)計出來，不能讓其成為性能瓶頸，所以我們要對鎖競爭進(jìn)行優(yōu)化。針對本地緩存的應(yīng)用場景，我們可以根據(jù)key進(jìn)行分桶處理，減少鎖競爭。

我們的key都是string類型，所以我們可以使用djb2哈希算法把key打散進(jìn)行分桶，然后在對每一個桶進(jìn)行加鎖，也就是鎖細(xì)化，減少競爭。

對象上限

因為本地緩存是在內(nèi)存中存儲的，內(nèi)存都是有限制的，我們不可能無限存儲，所以我們可以指定緩存對象的數(shù)量，根據(jù)我們具體的應(yīng)用場景去預(yù)估這個上限值，默認(rèn)我們選擇緩存的數(shù)量為1024。

淘汰策略

因為我們會設(shè)置緩存對象的數(shù)量，當(dāng)觸發(fā)上限值時，可以使用淘汰策略淘汰掉，常見的緩存淘汰算法有：

LFU

LFU(Least Frequently Used)即最近不常用算法，根據(jù)數(shù)據(jù)的歷史訪問頻率來淘汰數(shù)據(jù)，這種算法核心思想認(rèn)為最近使用頻率低的數(shù)據(jù),很大概率不會再使用，把使用頻率最小的數(shù)據(jù)置換出去。

存在的問題：

某些數(shù)據(jù)在短時間內(nèi)被高頻訪問，在之后的很長一段時間不再被訪問，因為之前的訪問頻率急劇增加，那么在之后不會在短時間內(nèi)被淘汰，占據(jù)著隊列前頭的位置，會導(dǎo)致更頻繁使用的塊更容易被清除掉，剛進(jìn)入的緩存新數(shù)據(jù)也可能會很快的被刪除。

LRU

LRU(Least Recently User)即最近最少使用算法，根據(jù)數(shù)據(jù)的歷史訪問記錄來淘汰數(shù)據(jù)，這種算法核心思想認(rèn)為最近使用的數(shù)據(jù)很大概率會再次使用，最近一段時間沒有使用的數(shù)據(jù)，很大概率不會再次使用，把最長時間未被訪問的數(shù)據(jù)置換出去

存在問題：

當(dāng)某個客戶端訪問了大量的歷史數(shù)據(jù)時，可能會使緩存中的數(shù)據(jù)被歷史數(shù)據(jù)替換，降低緩存命中率。

FIFO

FIFO(First in First out)即先進(jìn)先出算法，這種算法的核心思想是最近剛訪問的，將來訪問的可能性比較大，先進(jìn)入緩存的數(shù)據(jù)最先被淘汰掉。

存在的問題：

這種算法采用絕對公平的方式進(jìn)行數(shù)據(jù)置換，很容易發(fā)生缺頁中斷問題。

Two Queues

Two Queues是FIFO + LRU的結(jié)合，其核心思想是當(dāng)數(shù)據(jù)第一次訪問時，將數(shù)據(jù)緩存在FIFO隊列中，當(dāng)數(shù)據(jù)第二次被訪問時將數(shù)據(jù)從FIFO隊列移到LRU隊列里面，這兩個隊列按照自己的方法淘汰數(shù)據(jù)。

存在問題：

這種算法和LRU-2一致，適應(yīng)性差，存在LRU中的數(shù)據(jù)需要大量的訪問才會將歷史記錄清除掉。

ARU

ARU(Adaptive Replacement Cache)即自適應(yīng)緩存替換算法，是LFU和LRU算法的結(jié)合使用，其核心思想是根據(jù)被淘汰數(shù)據(jù)的訪問情況，而增加對應(yīng) LRU 還是 LFU鏈表的大小，ARU主要包含了四個鏈表，LRU 和 LRU Ghost ，LFU 和LFU Ghost， Ghost 鏈表為對應(yīng)淘汰的數(shù)據(jù)記錄鏈表，不記錄數(shù)據(jù)，只記錄 ID 等信息。

截屏2021-12-04 下午6.52.05

當(dāng)數(shù)據(jù)被訪問時加入LRU隊列，如果該數(shù)據(jù)再次被訪問，則同時被放到 LFU 鏈表中;如果該數(shù)據(jù)在LRU隊列中淘汰了，那么該數(shù)據(jù)進(jìn)入LRU Ghost隊列，如果之后該數(shù)據(jù)在之后被再次訪問了，就增加LRU隊列的大小，同時縮減LFU隊列的大小。

存在問題：

因為要維護(hù)四個隊列，會占用更多的內(nèi)存空間。

選擇

每一種算法都有自己特色，結(jié)合我們本地緩存使用的場景，選擇ARU算法來做緩存緩存淘汰策略是一個不錯的選擇，可以動態(tài)調(diào)整 LRU 和 LFU 的大小，以適應(yīng)當(dāng)前最佳的緩存命中。

過期清除

除了使用緩存淘汰策略清除數(shù)據(jù)外，還可以添加一個過期時間做雙重保證，避免不經(jīng)常訪問的數(shù)據(jù)一直占用內(nèi)存?？梢杂袃煞N做法：

數(shù)據(jù)過期了直接刪除

數(shù)據(jù)過期了不刪除，異步更新數(shù)據(jù)

兩種做法各有利弊，異步更新數(shù)據(jù)需要具體業(yè)務(wù)場景選擇，為了迎合大多數(shù)業(yè)務(wù)，我們采用數(shù)據(jù)過期了直接刪除這種方法更友好，這里我們采用懶加載的方式，在獲取數(shù)據(jù)的時候判斷數(shù)據(jù)是否過期，同時設(shè)置一個定時任務(wù)，每天定時刪除過期的數(shù)據(jù)。

緩存監(jiān)控

很多人對于緩存的監(jiān)控也比較忽略，基本寫完后不報錯就默認(rèn)他已經(jīng)生效了，這就無法感知這個緩存是否起作用了，所以對于緩存各種指標(biāo)的監(jiān)控，也比較重要，通過其不同的指標(biāo)數(shù)據(jù)，我們可以對緩存的參數(shù)進(jìn)行優(yōu)化，從而讓緩存達(dá)到最優(yōu)化。如果是企業(yè)應(yīng)用，我們可以使用Prometheus進(jìn)行監(jiān)控上報，我們自測可以簡單寫一個小組件，定時打印緩存數(shù)、緩存命中率等指標(biāo)。

GC調(diào)優(yōu)

對于大量使用本地緩存的應(yīng)用，由于涉及到緩存淘汰，那么GC問題必定是常事。如果出現(xiàn)GC較多，STW時間較長，那么必定會影響服務(wù)可用性;對于這個事項一般是具體case具體分析，本地緩存上線后記得經(jīng)常查看GC監(jiān)控。

緩存穿透

使用緩存就要考慮緩存穿透的問題，不過這個一般不在本地緩存中實現(xiàn)，基本交給使用者來實現(xiàn)，當(dāng)在緩存中找不到元素時,它設(shè)置對緩存鍵的鎖定;這樣其他線程將等待此元素被填充,而不是命中數(shù)據(jù)庫(外部使用singleflight封裝一下)。

參考文章

https://zhuanlan.zhihu.com/p/352910565

https://cloud.tencent.com/developer/article/1676115

https://tech.meituan.com/2017/03/17/cache-about.html

https://www.cnblogs.com/vancasola/p/9951686.html

總結(jié)

真正想設(shè)計一個高性能的本地緩存還是挺不容易的，由于我也才疏學(xué)淺，本文的設(shè)計思想也是個人實踐想法，歡迎大家提出寶貴意見，我們一起做出來一個真正的高性能本地緩存。

下篇文章我將分享自己的寫的一個本地緩存，盡請期待!!!【編輯推薦】