[發明專利]基于SSD的大容量緩存中的LRU策略實現方法

有效

• 申請號: 201310097306.9
• 申請日: 2013-03-25
• 公開（公告）號: CN103150136A
• 公開（公告）日: 2013-06-12
• 發明（設計）人: 肖儂;盧宇彤;陳志廣;周恩強;劉芳;所光;謝旻;董勇;張偉
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F5/16
• 分類號: G06F5/16
• 代理公司: 湖南兆弘專利事務所 43008
• 代理人: 趙洪;譚武藝

技術領域

本發明涉及計算機存儲領域，具體涉及一種基于SSD的大容量緩存中的低開銷LRU策略實現方法。

背景技術

緩存是一種根據局部性原理，利用小容量的高速存儲設備保存近期頻繁使用的數據，從而提高整個存儲系統性能的機制。它因為簡單有效、性價比高、對上層應用透明而被廣泛的應用于計算機系統中。緩存只保存近期頻繁訪問的數據，不再頻繁訪問的數據將被替換出緩存，識別不頻繁訪問數據的機制被稱為緩存替換策略。LRU(Least?Recently?Used，最久未使用)是一種基本的緩存替換策略。它因為準確地反映了局部性原理而被廣泛地采用，成為大部分復雜緩存替換策略的基礎。LRU替換策略維護一條LRU隊列。近期訪問的數據被放到LRU隊列的頭部，近期未訪問的數據逐步淘汰到LRU隊列的底部。發生緩存替換時，僅需將LRU隊列底部的數據替換出緩存即可。

本發明針對基于SSD(Solid?State?Drive，固態盤)的緩存，提出一種低開銷的LRU緩存替換策略實現方法。基于本發明提出的方法，可以實現更復雜的緩存替換策略。SSD是一種新型的存儲設備。它讀寫延遲較低，能夠提供很高的帶寬。但是，相比于磁盤，SSD價格較貴，容量較小。所以，SSD適合當作磁盤的緩存。相對基于DRAM(Dynamic?Random?Access?Memory，內存)的緩存，基于SSD的緩存容量很大。這種大容量緩存采用的替換策略需要維護很長的LRU隊列。目前，LRU替換策略的實現方法通常有以下兩種：

1、LRU隊列以雙向鏈表的方式實現，鏈表中的每個節點索引一頁數據。當一頁數據被訪問時，相應的節點被移動到鏈表的頭部。很久不被訪問的數據逐步淘汰到鏈表的尾部，緩存替換時只需將鏈表尾部的數據淘汰出緩存即可。這種方法只能將鏈表實現在內存中，因為操作系統發出的每個讀寫請求都會觸發雙向鏈表中節點的移動，頻繁的鏈表操作只能在內存中進行。對于基于SSD的大容量緩存，這種實現方式占用過多的內存。另外，基于雙向鏈表的實現方式需要為鏈表維護一個互斥鎖，頻繁地加鎖和解鎖也會占用很多計算資源。

2、以Clock(時鐘)隊列替代LRU隊列。LRU隊列以雙向鏈表的方式實現時，互斥鎖消耗較多的計算資源，Clock隊列則用來減少加鎖和解鎖操作的頻率。Clock隊列也維護一個雙向鏈表，鏈表的每個節點索引一頁數據，同時還為這頁數據設置一個標志位，標志位初始化為0。如果一頁數據被訪問，只需將標志位置為1，而不需將整個節點移動到雙向鏈表的頭部，所以避免了加鎖和解鎖。緩存替換時，檢查Clock隊列尾部的節點，如果節點的標志位為1，則將該節點移動到隊列頭部，并將標志位置為0；否則，將該節點刪除，該節點索引的數據被替換出緩存。Clock隊列避免了頻繁地加鎖和解鎖，但必須實現在內存中，因為需要頻繁地重置標志位。對于基于SSD的大容量緩存，這種方法仍然不適用。

發明內容

本發明要解決的技術問題是提供一種實現簡單、操作快捷、存儲占用空間低、內存開銷低的基于SSD的大容量緩存中的LRU策略實現方法。

為了解決上述技術問題，本發明采用的技術方案為：

一種基于SSD的大容量緩存中的LRU策略實現方法，其實施步驟如下：

1)在SSD上分配一塊連續的地址空間初始化FIFO隊列；在內存中建立用于記錄只訪問過一次的磁盤邏輯地址的第一計數型布隆選擇器和用于記錄訪問過兩次以上的磁盤邏輯地址的第二計數型布隆選擇器的數據結構，在內存中分別申請兩塊地址空間作為待寫入磁盤邏輯地址緩沖區和待替換磁盤邏輯地址緩沖區，跳轉執行下一步；

2)接收操作系統對磁盤邏輯地址的讀寫請求，跳轉執行下一步；

3)檢查讀寫請求的磁盤邏輯地址是否記錄在第二計數型布隆選擇器中，若在第二計數型布隆選擇器中存在，等待在新的讀寫請求到來時跳轉執行步驟2)；否則跳轉執行步驟4)；

4)檢查讀寫請求的磁盤邏輯地址是否記錄在第一計數型布隆選擇器中，若在第一計數型布隆選擇器中存在，跳轉執行步驟5)；否則，跳轉執行步驟6)；

5)將讀寫請求的磁盤邏輯地址從第一計數型布隆選擇器中刪除，同時將讀寫請求的磁盤邏輯地址添加到第二計數型布隆選擇器中，等待在新的讀寫請求到來時跳轉執行步驟2)；

6)判定第一計數型布隆選擇器和第二計數型布隆選擇器的數據結構中均不包含讀寫請求的磁盤邏輯地址，將讀寫請求的磁盤邏輯地址添加至第一計數型布隆選擇器中，跳轉執行下一步；