動手實現一個 localcache - 設計篇

前言

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

本篇主要介紹設計一個本地緩存都要考慮什麼點，後續爲實現文章，歡迎關注這個系列。

爲什麼要有本地緩存

隨着互聯網的普及，用戶數和訪問量越來越大，這就需要我們的應用支撐更多的併發量，比如某寶的首頁流量，大量的用戶同時進入首頁，對我們的應用服務器和數據庫服務器造成的計算也是巨大的，本身數據庫訪問就佔用數據庫連接，導致網絡開銷巨大，在面對如此高的併發量下，數據庫就會面臨瓶頸，這時就要考慮加緩存，緩存就分爲分佈式緩存和本地緩存，大多數場景我們使用分佈式緩存就可以滿足要求，分佈式緩存訪問速度也很快，但是數據需要跨網絡傳輸，在面對首頁這種高併發量級下，對性能要求是很高的，不能放過一點點的性能優化空間，這時我們就可以選擇使用本地緩存來提高性能，本地緩存不需要跨網絡傳輸，應用和 cache 都在同一個進程內部，快速請求，適用於首頁這種數據更新頻率較低的業務場景。

綜上所述，我們往往使用本地緩存後的系統架構是這樣的：

本地緩存雖然帶來性能優化，不過也是有一些弊端的，緩存與應用程序耦合，多個應用程序無法直接的共享緩存，各應用或集羣的各節點都需要維護自己的單獨緩存，對內存是一種浪費，使用緩存的是我們程序員自己，我們要根據根據數據類型、業務場景來準確判斷使用何種類型的緩存，如何使用這種緩存，以最小的成本最快的效率達到最優的目的。

思考：如何實現一個高性能本地緩存

數據結構

第一步我們就要考慮數據該怎樣存儲；數據的查找效率要高，首先我們就想到了哈希表，哈希表的查找效率高，時間複雜度爲O(1)，可以滿足我們的需求；確定是使用什麼結構來存儲，接下來我們要考慮以什麼類型進行存儲，因爲不同的業務場景使用的數據類型不同，爲了通用，在java中我們可以使用泛型，Go語言中暫時沒有泛型，我們可以使用interface類型來代替，把解析數據交給程序員自己來進行斷言，增強了可擴展性，同時也增加一些風險。

總結：

併發安全

本地緩存的應用肯定會面對併發讀寫的場景，這是就要考慮併發安全的問題。因爲我們選擇的是哈希結構，Go語言中主要提供了兩種哈希，一種是非線程安全的map，一種是線程安全的sync.map，爲了方便我們可以直接選擇sync.map，也可以考慮使用map+sync.RWMutex組合方式自己實現保證線程安全，網上有人對這兩種方式進行比較，在讀操作遠多於寫操作的時候，使用sync.map的性能是遠高於map+sync.RWMutex的組合的。在本地緩存中讀操作是遠高於寫操作的，但是我們本地緩存不僅支持進行數據存儲的時候要使用鎖，進行過期清除等操作時也需要加鎖，所以使用map+sync.RWMutex的方式更靈活，所以這裏我們選擇這種方式保證併發安全。

高性能併發訪問

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

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

對象上限

因爲本地緩存是在內存中存儲的，內存都是有限制的，我們不可能無限存儲，所以我們可以指定緩存對象的數量，根據我們具體的應用場景去預估這個上限值，默認我們選擇緩存的數量爲 1024。

淘汰策略

因爲我們會設置緩存對象的數量，當觸發上限值時，可以使用淘汰策略淘汰掉，常見的緩存淘汰算法有：

LFU

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

存在的問題：

某些數據在短時間內被高頻訪問，在之後的很長一段時間不再被訪問，因爲之前的訪問頻率急劇增加，那麼在之後不會在短時間內被淘汰，佔據着隊列前頭的位置，會導致更頻繁使用的塊更容易被清除掉，剛進入的緩存新數據也可能會很快的被刪除。

LRU

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

存在問題：

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

FIFO

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

存在的問題：

這種算法採用絕對公平的方式進行數據置換，很容易發生缺頁中斷問題。

Two Queues

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

存在問題：

這種算法和LRU-2一致，適應性差，存在LRU中的數據需要大量的訪問纔會將歷史記錄清除掉。

ARU

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

截屏 2021-12-04 下午 6.52.05

當數據被訪問時加入LRU隊列，如果該數據再次被訪問，則同時被放到 LFU 鏈表中；如果該數據在LRU隊列中淘汰了，那麼該數據進入LRU Ghost隊列，如果之後該數據在之後被再次訪問了，就增加LRU隊列的大小，同時縮減LFU隊列的大小。

存在問題：

因爲要維護四個隊列，會佔用更多的內存空間。

選擇

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

過期清除

除了使用緩存淘汰策略清除數據外，還可以添加一個過期時間做雙重保證，避免不經常訪問的數據一直佔用內存。可以有兩種做法：

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

緩存監控

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

GC 調優

對於大量使用本地緩存的應用，由於涉及到緩存淘汰，那麼 GC 問題必定是常事。如果出現 GC 較多，STW 時間較長，那麼必定會影響服務可用性；對於這個事項一般是具體 case 具體分析，本地緩存上線後記得經常查看GC監控。

緩存穿透

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

參考文章

總結

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ZtSA3J8HK4QarhrJwBQtXw

猜你喜歡