緩存設計相關問題

申請免費試用、咨詢電話：400-8352-114

　　LRU交換算法

　　緩存的技能點包羅內存治理和交換算法。LRU是運用最多的交換算法，每次裁減最久沒有運用的元素。LRU緩存完成分為兩個局部：Hash表和LRU鏈表，Hash表用于查找緩存中的元素，LRU鏈表用于裁減。內存常以Slab的方法治理。

　　上圖是Memcache的內存治理表示圖，Memcache以Slab方法治理內存塊，從系統(tǒng)請求1MB巨細的大塊內存并劃分為分歧巨細的 Chunk，分歧Slab的Chunk巨細順次為80字節(jié)，80 * 1.25，80 * 1.25^2, …。向Memcache中添加item時，Memcache會依據(jù)item的巨細選擇適宜的Chunk。

　　Oceanbase開始也采用LRU算法，只是內存治理有些分歧。Oceanbase向系統(tǒng)請求2MB巨細的大塊內存，刺進item時直接追加到最終一個2MB內存塊的尾部，當緩存的內存量太大需求收受接管時依據(jù)必然的戰(zhàn)略整塊收受接管2MB的內存，比方收受接管比來起碼運用的item地點的2MB內存塊。如許的做法固然不是特殊準確，然則內存治理簡略，關于系統(tǒng)初期很有益處。

　　緩存鎖

　　緩存需求操作兩個數(shù)據(jù)構造：Hash表和LRU鏈表。多線程操作cache時需求加鎖，比擬直接的做法是全體加一把大鎖后再操作Hash表和LRU鏈表。有如下的優(yōu)化思緒：

　　1, Hash表和LRU鏈表運用兩把分歧的鎖，且Hash表鎖的粒度可以降低到每個Hash桶一把鎖。這種做法的難點是需求處置兩種數(shù)據(jù)構造紛歧致招致的問題，假定操作挨次為read hash -> del hash item -> del lru item -> read lru item，最終一次read lru item時item地點的內存塊能夠曾經(jīng)被收受接管或許重用，普通需求引入援用計數(shù)并思索復雜的時序問題。

　　2, 采用多個LRU鏈表以削減LRU表鎖粒度。Hash表的鎖抵觸可以經(jīng)過添加Hash桶的個數(shù)來處理，而LRU鏈表是一個全體，難以分化。可以將緩存的數(shù)據(jù)分紅多個任務集，每個item屬于某個任務集，每個任務集一個LRU鏈表。如許做的首要問題是能夠不平衡，比方某個任務集很熱，某些從全體上看比擬熱的數(shù)據(jù)也能夠被裁減。

　　3, 犧牲LRU的準確性以削減鎖。比方Mysql中的LRU算法變形，大致如下：將LRU鏈表分紅兩局部，前半局部和后半局部，假如拜訪的item在前半局部，什么也不做，而不是像傳統(tǒng)的LRU算法那樣將item挪動到鏈表頭部;又如Linux Page Cache中的CLOCK算法。Oceanbase當前的緩存算法也是經(jīng)過犧牲準確性來削減鎖。前面提到，Oceanbase緩存以2MB的內存塊為單元進行裁減，最開端采用LRU戰(zhàn)略，每次裁減比來起碼運用的item地點的2MB內存塊，但是，如許做的問題是需求維護比來起碼運用的item，即每次讀寫緩存都需求加鎖。后續(xù)我們將裁減戰(zhàn)略修正為：每個2MB的內存塊記載一個拜訪次數(shù)和一個比來拜訪工夫，每次讀取item時，假如拜訪次數(shù)大于一切2MB內存塊拜訪次數(shù)的均勻值，更新比來拜訪工夫;不然，將拜訪次數(shù)加1。依據(jù)記載的比來拜訪工夫裁減2MB內存塊。固然，這個算法的緩存射中率不輕易評價，然則緩存讀取只需求一些原子操作，不需求加鎖，大大削減了鎖粒度。

　　4, 批量操作。緩存射中時不需求立刻更新LRU鏈表，而是可以將射中的item保管在線程Buffer中，積聚了必然數(shù)目后一次性更新LRU鏈表。

　　LIRS思維

　　Cache有兩個問題：一個是前面提到的降低鎖粒度，另一個是進步精準度，或許稱為進步射中率。LRU在大大都狀況下顯示是不錯的，然則有如下的問題：

　　1, 挨次掃描。挨次掃描的狀況下LRU沒有射中狀況，并且會裁減其它將要被拜訪的item然后污染cache。

　　2, 輪回的數(shù)據(jù)集大于緩存巨細。假如輪回拜訪且數(shù)據(jù)集大于緩存巨細，那么沒有射中狀況。

　　之所以會呈現(xiàn)上述一些比擬極端的問題，是由于LRU只思索拜訪工夫而沒有思索拜訪頻率，而LIRS在這方面做得比擬好。LIRS將數(shù)據(jù)分為兩局部：LIR(Low Inner-reference Recency)和HIR(High Inner-reference Recency)，個中，LIR中的數(shù)據(jù)是熱點，在較短的工夫內被拜訪了至少兩次。LIRS可以算作是一種分級思維：第一級是HIR，第二級是LIR，數(shù)據(jù)進步前輩入到第一級，當數(shù)據(jù)在較短的工夫內被拜訪兩次時成為熱點數(shù)據(jù)則進入LIR，HIR和LIR內部都采用LRU戰(zhàn)略。如許，LIR中的數(shù)據(jù)比擬不變，處理了LRU的上述兩個問題。LIRS論文中提出了一種完成方法，但是我們可以做一些轉變，如可以完成兩級cache，cache元素進步前輩入第一級 cache，當拜訪頻率到達必然值(比方2)時晉級到第二級，第一級和第二級均內部采用LRU進行交換。Oracle Buffer Cache中的Touch Count算法也是采用了相似的思維。

　　SSD與緩存

　　SSD開展很快，大有替代傳統(tǒng)磁盤之勢。SSD的開展能否會使得單機緩存變得毫無需要我們無從得知，當前，Memory + SSD + 磁盤的夾雜存儲方案照樣比擬靠譜的。SSD運用可以有如下分歧的形式：

　　1, write-back：數(shù)據(jù)讀寫都走SSD，內存中的數(shù)據(jù)寫入到SSD即可，別的有獨自的線程按期將SSD中的數(shù)據(jù)刷到磁盤。典型的代表如Facebook Flashcache。

　　2, write-through：數(shù)據(jù)寫操作需求先寫到磁盤，內存和SSD合在一同算作兩級緩存，即cache中相對較冷的數(shù)據(jù)在SSD，相對較熱的數(shù)據(jù)在內存。

　　當然，跟著SSD的使用，我想削減緩存鎖粒度的主要性會越來越凸起。

　　總結&引薦材料

　　到當前為止，我們在SSD，緩存相關優(yōu)化的任務照樣比擬少的。往后的一年左右工夫，我們將會投入必然的精神在系統(tǒng)優(yōu)化上，置信到時分再來總結的時分看法會愈加深入。我想，緩存相關的優(yōu)化任務起首要做的是依據(jù)需求制訂一個大致的評價規(guī)范，接著運用實踐數(shù)據(jù)做一些實行，最終能夠會還保存兩到三種完成方法或許裝備稍微有所分歧的緩存完成