緩存設(shè)計(jì)相關(guān)問題

申請(qǐng)免費(fèi)試用、咨詢電話：400-8352-114

　　LRU交換算法

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

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

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

　　緩存鎖

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

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

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

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

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

　　LIRS思維

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

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

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

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

　　SSD與緩存

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

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

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

　　當(dāng)然，跟著SSD的使用，我想削減緩存鎖粒度的主要性會(huì)越來越凸起。

　　總結(jié)&引薦材料

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