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

有效

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

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

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

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

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

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

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

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

7)將讀寫請求的磁盤邏輯地址寫到待寫入磁盤邏輯地址緩沖區，跳轉執行下一步；

8)檢查待寫入磁盤邏輯地址緩沖區是否寫滿，若未寫滿則跳轉執行步驟10)，否則跳轉執行步驟9)；

9)將待寫入磁盤邏輯地址緩沖區中的磁盤邏輯地址刷新到SSD中FIFO隊列的尾部，同時將FIFO隊列的尾部指針遞增，跳轉執行下一步；

10)判定讀寫請求的請求類型，如果請求類型為寫請求，則直接將待寫入的用戶數據寫到SSD上；如果請求類型為讀請求，由于沒有在SSD上命中，先從底層存儲系統讀出數據，將數據返回給上層應用的同時，將數據寫到SSD上；跳轉執行下一步；

11)檢查SSD的空閑存儲空間占SSD總容量的比例是否小于第一預設閾值，若SSD的空閑存儲空間占SSD總容量的比例小于第一預設閾值則跳轉執行步驟12)，否則跳轉執行步驟2)等待新的讀寫請求到來；

12)讀取FIFO隊列的頭部到待替換磁盤邏輯地址緩沖區，跳轉執行下一步；

13)取出所述待替換磁盤邏輯地址緩沖區的首個磁盤邏輯地址作為當前磁盤邏輯地址，跳轉執行下一步；

14)判斷當前磁盤邏輯地址是否在第二計數型布隆選擇器中，如果在第二計數型布隆選擇器中則跳轉執行步驟15)；否則跳轉執行步驟16)；

15)將當前磁盤邏輯地址從第二計數型布隆選擇器中刪除，同時將當前磁盤邏輯地址添加到第一計數型布隆選擇器中，跳轉執行步驟17)；

16)判斷當前磁盤邏輯地址是否在第一計數型布隆選擇器中，如果在第一計數型布隆選擇器中則將當前磁盤邏輯地址從第一計數型布隆選擇器中刪除，跳轉執行步驟18)；

17)將當前磁盤邏輯地址寫入到待寫入磁盤邏輯地址緩沖區，使得當前磁盤邏輯地址對應的數據繼續保留在SSD上，跳轉執行步驟18)；

18)判斷所述待替換磁盤邏輯地址緩沖區的所有磁盤邏輯地址是否已經全部處理完畢，如果尚未處理完畢則獲取下一個磁盤邏輯地址作為當前磁盤邏輯地址，跳轉執行步驟14)；如果已經處理完畢則跳轉執行步驟19)；

19)檢查SSD的空閑存儲空間占SSD總容量的比例是否大于第二預設閾值，所述第二預設閾值比第一預設閾值大，若SSD的空閑存儲空間占SSD總容量的比例大于第二預設閾值，則等待在新的讀寫請求到來時跳轉執行步驟2)；否則跳轉執行步驟12)。