緩存設計，LIRS，cache鎖粒度

互聯網架構中緩存無處不在，某廠牛人曾經說過：”緩存就像清涼油，哪里不舒服，抹一下就好了”。高品質的存儲容量小，價格高；低品質存儲容量大，價格低，緩存的目的就在于”擴充”高品質存儲的容量。本文探討緩存相關的一些問題。

LRU替換算法

緩存的技術點包括內存管理和替換算法。LRU是使用最多的替換算法，每次淘汰最久沒有使用的元素。LRU緩存實現分為兩個部分：Hash表和LRU鏈表，Hash表用于查找緩存中的元素，LRU鏈表用于淘汰。內存常以Slab的方式管理。

上圖是Memcache的內存管理示意圖，Memcache以Slab方式管理內存塊，從系統申請1MB大小的大塊內存并劃分為不同大小的 Chunk，不同Slab的Chunk大小依次為80字節，80 * 1.25，80 * 1.25^2, …。向Memcache中添加item時，Memcache會根據item的大小選擇合適的Chunk。

Oceanbase最初也采用LRU算法，只是內存管理有些不同。Oceanbase向系統申請2MB大小的大塊內存，插入item時直接追加到最 后一個2MB內存塊的尾部，當緩存的內存量太大需要回收時根據一定的策略整塊回收2MB的內存，比如回收最近最少使用的item所在的2MB內存塊。這樣 的做法雖然不是特別精確，但是內存管理簡單，對于系統初期很有好處。

緩存鎖

緩存需要操作兩個數據結構：Hash表和LRU鏈表。多線程操作cache時需要加鎖，比較直接的做法是整體加一把大鎖后再操作Hash表和LRU鏈表。有如下的優化思路：

1, Hash表和LRU鏈表使用兩把不同的鎖，且Hash表鎖的粒度可以降低到每個Hash桶一把鎖。這種做法的難點是需要處理兩種數據結構不一致導致的問 題，假設操作順序為read hash -> del hash item -> del lru item -> read lru item，最后一次read lru item時item所在的內存塊可能已經被回收或者重用，一般需要引入引用計數并考慮復雜的時序問題。

2, 采用多個LRU鏈表以減少LRU表鎖粒度。Hash表的鎖沖突可以通過增加Hash桶的個數來解決，而LRU鏈表是一個整體，難以分解。可以將緩存的數據 分成多個工作集，每個item屬于某個工作集，每個工作集一個LRU鏈表。這樣做的主要問題是可能不均衡，比如某個工作集很熱，某些從整體上看比較熱的數 據也可能被淘汰。

3, 犧牲LRU的精確性以減少鎖。比如Mysql中的LRU算法變形，大致如下：將LRU鏈表分成兩部分，前半部分和后半部分，如果訪問的item在前半部 分，什么也不做，而不是像傳統的LRU算法那樣將item移動到鏈表頭部；又如Linux Page Cache中的CLOCK算法。Oceanbase目前的緩存算法也是通過犧牲精確性來減少鎖。前面提到，Oceanbase緩存以2MB的內存塊為單位 進行淘汰，最開始采用LRU策略，每次淘汰最近最少使用的item所在的2MB內存塊，然而，這樣做的問題是需要維護最近最少使用的item，即每次讀寫 緩存都需要加鎖。后續我們將淘汰策略修改為：每個2MB的內存塊記錄一個訪問次數和一個最近訪問時間，每次讀取item時，如果訪問次數大于所有2MB內 存塊訪問次數的平均值，更新最近訪問時間；否則，將訪問次數加1。根據記錄的最近訪問時間淘汰2MB內存塊。雖然，這個算法的緩存命中率不容易評估，但是 緩存讀取只需要一些原子操作，不需要加鎖，大大減少了鎖粒度。

4, 批量操作。緩存命中時不需要立即更新LRU鏈表，而是可以將命中的item保存在線程Buffer中，積累了一定數量后一次性更新LRU鏈表。

LIRS思想

Cache有兩個問題：一個是前面提到的降低鎖粒度，另一個是提高精準度，或者稱為提高命中率。LRU在大多數情況下表現是不錯的，但是有如下的問題：

1, 順序掃描。順序掃描的情況下LRU沒有命中情況，而且會淘汰其它將要被訪問的item從而污染cache。

2, 循環的數據集大于緩存大小。如果循環訪問且數據集大于緩存大小，那么沒有命中情況。

之所以會出現上述一些比較極端的問題，是因為LRU只考慮訪問時間而沒有考慮訪問頻率，而LIRS在這方面做得比較好。LIRS將數據分為兩部 分：LIR（Low Inner-reference Recency）和HIR（High Inner-reference Recency），其中，LIR中的數據是熱點，在較短的時間內被訪問了至少兩次。LIRS可以看成是一種分級思想：第一級是HIR，第二級是LIR，數 據先進入到第一級，當數據在較短的時間內被訪問兩次時成為熱點數據則進入LIR，HIR和LIR內部都采用LRU策略。這樣，LIR中的數據比較穩定，解 決了LRU的上述兩個問題。LIRS論文中提出了一種實現方式，不過我們可以做一些變化，如可以實現兩級cache，cache元素先進入第一級 cache，當訪問頻率達到一定值（比如2）時升級到第二級，第一級和第二級均內部采用LRU進行替換。Oracle Buffer Cache中的Touch Count算法也是采用了類似的思想。

SSD與緩存

SSD發展很快，大有取代傳統磁盤之勢。SSD的發展是否會使得單機緩存變得毫無必要我們無從得知，目前，Memory + SSD + 磁盤的混合存儲方案還是比較靠譜的。SSD使用可以有如下不同的模式：

1, write-back：數據讀寫都走SSD，內存中的數據寫入到SSD即可，另外有單獨的線程定期將SSD中的數據刷到磁盤。典型的代表如非死book Flashcache。

2, write-through：數據寫操作需要先寫到磁盤，內存和SSD合在一起看成兩級緩存，即cache中相對較冷的數據在SSD，相對較熱的數據在內存。

當然，隨著SSD的應用，我想減少緩存鎖粒度的重要性會越來越突出。

總結&推薦資料

到目前為止，我們在SSD，緩存相關優化的工作還是比較少的。今后的一年左右時間，我們將會投入一定的精力在系統優化上，相信到時候再來總結的時候 認識會更加深刻。我想，緩存相關的優化工作首先要做的是根據需求制定一個大致的評價標準，接著使用實際數據做一些實驗，最終可能會同時保留兩到三種實現方 式或者配置略微有所不同的緩存實現。緩存相關的推薦資料如下：

[1] Touch Count Algorithm. http://youyus.com/wp-content/uploads/resource/Shallahamer%20TC4a.pdf
[2] LIRS. http://portal.acm.org/citation.cfm?id=511340

原文出處：nosqlnotes