LRU的改進演算法LIRS

2022-06-23 20:29:02 字數 4574 閱讀 3979

lru(least recent used)是我們在cache替換演算法中最普遍使用的演算法,在快取塊已滿,而需要快取新的資料塊的時候,這時需要從快取中找到一個“沒有價值”的塊用新的資料塊去替換它。

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

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

2, 迴圈的資料集大於快取大小。如果迴圈訪問且資料集大於快取大小,那麼沒有命中情況。

lru的特點是簡潔高效,但是缺點是lru的缺點是不能對weak locality的資料進行快取。

a. 如果stack size有1000個塊,而一個檔案是1001個塊的大小,而且每次訪問都是從頭到尾的訪問。則lru的效能非常差,幾乎沒有任何快取。

b. 假設我們要邀請學習好的同學到一個容納10人的會議室開會。如果是lru演算法的話,會邀請90分以上或者80分以上的人,,但是如果沒有80分以上的同學則一個都不邀請,而會議室也就白白浪費了,對於lirs,邀請成績前在10名的同學到會議室。這裡會議室為我們的stack ,這樣我們的會議室也就是stack至少不會浪費。

所以我們這裡邊的問題就是如何把一些weak locality的資料也能夠快取起來,使我們的cache得到充分的使用?

2. 兩個概念

reuse: 一個塊被使用之後,再次被使用

recency:一個塊被訪問後,和上一次訪問之間的距離。

lirs的基本思想是對訪問的資料塊進行分類,一部分為hot資料塊,一部分為cold資料塊。對於hot資料塊我們可以分配90%以上的cache給它們。而對於cold資料塊給它們分配10%。

從lirs演算法的描述來看,可以理解為兩個lru佇列的組合,利用cold緩衝區來保護hot緩衝區,提高了進入hot緩衝區的門檻,阻止hot緩衝區頻繁地變化。

在lirs演算法中使用了irr(inter-reference recency)和recency這兩個引數。其中irr指一個頁面最近兩次的訪問間隔;recency指頁面最近一次訪問至當前時間內有多少頁面曾經被訪問過。在irr和recency引數中不包含重複的頁面數,因為其他頁面的重複對計算當前頁面的優先權沒有太多影響。

lirs演算法實現:

首先說明lru演算法的實現。

採用帶表頭的單連結串列來儲存資料節點,head指標指向表頭,tail指標指向連結串列最後一個節點。資料節點則記錄了每個快取塊的id,載入狀態,資料指標,next指標。另有unusedsize變數存放未分配的快取塊數量。

當使用者訪問命中時,將對應的資料節點移到佇列尾部。當使用者訪問未命中時,若能分配新資料節點,則分配,否則從表頭摘下一個資料節點,並解除安裝資料。更新得到的資料節點的資訊,並加到佇列尾部。

最後,為了避免在查詢資料節點時遍歷整個連結串列,增加了dictionary的字典,利用其hash查詢功能提高查詢效率。

再說明lirs演算法的實現。

為了簡化實現,將演算法實現為多個邏輯lru佇列(可實現多級緩衝區),在物理實現上,仍採用帶表頭的單連結串列來儲存資料節點。對於n級緩衝區的實現(原始的lirs演算法為2級),使用unusedsize[n]陣列存放每個緩衝區的未分配數量,使用head[n+1]存放緩衝區的頭尾指標。這樣head[0]、head[1]指示了第0塊緩衝區的頭尾,依次類推,head[n-1]、head[n]指示了第n-1塊緩衝區的頭尾。0號緩衝區是cold的緩衝區,n-1號則是最hot的。由於使用了多級緩衝區,資料節點也需要增加一個選擇器selector,用於指示該節點屬於哪個緩衝區。

當使用者訪問未命中,分配新節點時,先檢查n-1號緩衝區是否能分配新節點,若不能則依次向前檢查。若分配了新節點,則直接加入相應緩衝區的尾部,否則就從0級緩衝區頭部摘下一個節點來,更新節點資訊後加入0級緩衝區尾部。

當使用者訪問命中時,則將x級的節點提升到x+1級,並加到緩衝區尾部,x+1級的頭部節點,則被移到x級緩衝區的尾部

同樣的,增加了dictionary字典,提高查詢節點的效率。

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記憶體塊。雖然,這個演算法的快取命中率不容易評估,但是快取讀取只需要一些原子操作,不需要加鎖,大大減少了鎖粒度。

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中的資料刷到磁碟。典型的代表如facebook flashcache。

2, write-through:資料寫操作需要先寫到磁碟,記憶體和ssd合在一起看成兩級快取,即cache中相對較冷的資料在ssd,相對較熱的資料在記憶體。

當然,隨著ssd的應用,我想減少快取鎖粒度的重要性會越來越突出。

總結&推薦資料

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

SAR的演算法

sar的演算法 假設引數為 n 2 20 首先要確定是漲勢還是跌勢,並且得出起算點。有多種不同的確定方法,這裡略過。 一 漲勢中演算法 1...

被演算法支配的恐懼

人物雜誌的報道《外賣騎手,困在系統裡》刷屏。我想,大家在同情外賣小哥 泛稱,不準確,因為還有女性 的同時,也在為自己的命運感到深深的憂慮。 外賣小哥只是提前進入了演算法統治時代而已。 同情心不能解決問題,同情心甚至不能幫助我們理解問題的實質。抵制外賣,拯救外賣小哥?可是外賣小哥失業之後,變成無業流民,...

思維的演算法就是人生的活法

更在於他堅持用自己的人生哲學指導了這樣的成功。 他的人生哲學,充滿了精神世界的強大力量,每一個人都有條件實踐。利他。 心流理論認為,心流才能夠帶來真正的幸福感。而獲得心流更多的場景,是工作。所以工作的重要目的,是獲得心流。 我在學習肯 羅賓遜的教育創新五部曲之後,總結得出 能夠拯救生命的只有天賦和愛...