混合映射方式下NAND閃存垃圾回收算法

張靖君，王 玲

(湖南師范大學 信息科學與工程學院，長沙 410006)E-mail：417583212@qq.com

1 引 言

如今，NAND 閃存已廣泛應用于各種嵌入式設備中[1]，例如手機、U盤、固態硬盤等.它具有體積小、速度快、功耗低、抗震等優點.與磁盤、軟盤這些磁介質存儲器相比，NAND閃存具有以下特點：

1)NAND閃存的物理結構主要分為物理塊和物理頁，整個閃存設備由多個物理塊組成，每一個物理塊又是由一定數目的物理頁組成.每一頁由兩部分組成分別是數據段(Data Field)和附加段(Spare Field)，數據段用于存儲數據，附加段用于保存閃存的管理數據，包括：ECC碼、映射表信息和壞塊信息[2].

2)NAND閃存讀寫數據是以物理頁為單位，擦除操作則以物理塊為單位[3].讀取一個物理頁的速度較快，寫入一頁數據的時間則較慢，而擦除一個物理塊的時間遠遠大于寫的時間.

3)不能直接對物理塊保存的數據進行修改，必須先進行擦除操作才能寫入新的數據[4].

4)物理塊的擦除次數有限SLC(Single-Level Cell 單層單元)通常在10萬次左右，MLC(Multi-Level Cell多層單元)通常在1萬次左右[5].

由于這些特性，傳統的文件系統無法在閃存設備上正常工作.為了將閃存設備模擬成標準的磁盤設備以兼容傳統的文件系統，通常使用閃存轉換層FTL (Flash Translation Layer)作為中間層管理閃存設備[6].FTL的主要功能包括：地址映射、垃圾回收、磨損均衡和壞塊管理[7].其中地址映射是FTL中最重要的一個功能，不同的地址映射方式必須要有與之相匹配的垃圾回收、磨損均衡算法，才能發揮其性能.

目前NAND 閃存的垃圾回收算法主要是針對頁級地址映射設計的，如GR(GReedy)算法[8]，GR算法為了減少有效頁拷貝造成的性能損失，會選擇有效頁最少的物理塊進行垃圾回收.目標是用最少的性能損失來獲得更多的空閑空間，但是，GR算法未考慮到各塊的擦除情況，因此磨損均衡度較差.CAT(Cost-Age-Time)算法[9]，考慮了擦除次數對均衡度的影響，選擇更新頻率最低、無效頁最多且擦除次數最少的物理塊進行回收.由于考慮到了物理塊的更新頻率和擦除次數，所以磨損均衡效果優于GR算法.SACATA (Swap-Aware Cost-Age-Time Age-sort)算法[10]在linux交換系統技術上考慮了所有塊的最大和最小擦除次數，因此磨損均衡度較好.以上三種算法在頁級地址映射上能夠取得較好的效果，但在混合映射上效果并不理想，造成這種結果的原因主要是物理塊之間關聯程度不同.頁級地址映射上物理塊之間都是獨立的，而混合映射上物理塊被分為數據塊和日志塊，數據塊和日志塊之間的數據存在關聯.單獨考慮日志塊中有效頁數量在混合映射上并不能獲得最好的回收性能.FAST轉換層[11]是基于混合映射的轉換層，轉換層將日志塊共享給多個數據塊，提高了日志塊的利用率[12]，但冷熱數據混合在一個日志塊中，垃圾回收將頻繁觸發全合并這將會占用極大的資源[13].垃圾回收作為FTL一個重要部分，不僅要考慮閃存的壽命也要考慮其性能[14].

通過對基于混合映射的FAST算法的深入研究，針對其算法存在的不足，考慮邏輯塊的冷熱度、日志塊無效頁占比和數據塊的擦除次數，設計基于循壞隊列的邏輯塊熱度計算方法和數據塊選擇策略，并提出一種基于混合映射的垃圾回收算法即：HMSGC(Hybrid Mapping Scheme With Garbage Collection)算法.

2 算法描述

2.1 閃存設備基本結構

在Linux系統下基于NAND 閃存存儲結構可以分為：操作系統API、文件系統層、閃存轉換層和FLASH設備.系統結構如圖1所示.

圖1 NAND FLASH 存儲系統結構Fig.1 NAND FLASH storage system structure

操作系統層會提供給應用程序讀寫數據的程序接口，文件系統提供管理數據的方法.FTL(Flash Translation Layer)層是一種軟件中間層，它把NAND FLASH設備虛擬成傳統的硬盤設備，使得NTFS、EXT2等針對傳統硬盤設計的文件系統可以在不經過修改的情況下正常使用[4].FTL層主要包含了壞塊管理、地址映射、磨損均衡、垃圾回收等幾個方面[5,6].

2.2 FAST算法垃圾回收方式

在基于混合映射的FAST算法中數據塊使用塊級映射而日志塊使用頁級映射，當日志塊的空閑頁都被耗盡后，由于日志塊中還包含有效頁，所以并不能像頁級映射那樣，簡單的把當前的日志塊標記為無效塊，之后再申請一個新的日志塊來接收數據.此時我們必須進行回收操作，把日志塊和數據塊的有效數據合并到一個新的數據塊中才能繼續申請新的日志塊并接收數據.在FAST算法中存在三種合并方式：全合并、交換合并、部分合并[7].

全合并，當數據塊和日志塊中的有效數據頁分布分散難以整理成有序的數據塊存儲使用，此時必須另外尋找一個新的物理塊，依次讀入日志塊和數據塊中的有效數據成為新的數據塊，并回收舊的數據塊和日志塊.這種合并方式要拷貝所有的有效數據，因此開銷最大.

交換合并，當只存在順序數據更新，數據塊中的數據全部順序更新到日志塊中，數據塊中無有效數據，此時只需要把日志塊轉換成數據塊，將數據塊擦除即可.

部分合并，當只存在順序數據更新，數據塊中有部分數更新到日志塊中.此時需要將數據塊中未被更新的有效數據順序拷貝到日志塊中，再把日志塊轉換成數據塊即可.

2.3 基于循環隊列的熱塊識別算法

CAT算法中冷熱塊的識別主要集中在數據的寫訪問次數方面[8]，當通過長時間的積累使地址A被訪問到了100次和在短時間內地址B被訪問到了100次，此時根據CAT的計算公式A、B將計算出同樣的熱度值.但由于B是在短時間的頻繁訪問，地址B的熱度值應該更高.

為了有效的反應邏輯地址的被訪問的次數隨著時間的變化關系，可以在閃存設備接收到寫命令時使用循環隊列統計該塊地址的熱度值，并利用隊列的先入先出特性刪除過時的數據.具體方法如下：

建立固定長度的循環隊列，長度為len，從隊頭到隊尾為每一個位置分配一個遞增的熱度權值，當一個寫命令來時，將LBA入隊，此時LBA的熱度為len，原隊列各元素向隊頭移動一個位置，對頭元素出列.由于是循環隊列，元素入隊、出隊、移位只需要修改隊頭和隊尾指針，提高了運算速度.隊列狀態如圖2所示.

圖2 熱度循環隊列狀態圖Fig.2 Heat queue state diagram

當計算某個邏輯塊地址的熱度值Hoti時，通過對隊列中該地址的熱度權值求和，便得到該邏輯塊地址的熱度值.

2.4 磨損均衡策略

在混合映射中日志塊采用的是頁級映射方式，一個日志塊可以接收多個數據塊的更新數據.當冷熱數據混合在一個日志塊的時候，由于熱數據頻繁的更新，日志塊中的空閑頁很快就被耗盡，合并操作會同時拷貝熱數據和冷數據.為了避免冷數據和熱數據混合在一塊日志塊導致冷數據過多沒必要的拷貝，需要根據數據的冷熱值將相似熱度的有效頁分配在同一日志塊上，以達到減少塊合并操作的目的.

本文采用一種基于邏輯塊熱度的冷熱分離，通過有效頁所對應的邏輯塊熱度來決定寫入的日志頁的狀態.具體步驟如下：

1) 設定冷熱塊的閾值HotTh，通過累加循環隊列中目標邏輯塊的權值，計算出當前邏輯塊的熱度值.

2)若寫入數據對應邏輯塊的熱度≥HotTh，該數據寫入的邏輯塊被定義為熱塊，這時將分配空閑塊中擦寫次數最小的兩個物理塊作為其數據塊和日志塊，此時該日志塊不共享給其他數據塊.

3)若寫入數據對應邏輯塊的熱度< HotTh，該數據對應邏輯塊被定義為冷塊，這時將分配空閑塊中擦寫次數最大的兩個物理塊作為其數據塊和日志塊，此時該日志塊共享給其他數據塊.

2.5 回收塊的選擇

系統在進行垃圾回收時，首先需要考慮垃圾回收的效率，應盡量選擇能夠交換合并和部分合并的數據塊進行回收避免性能最差的全合并[9,10].由于NAND 閃存設備擦除次數有限，無效頁回收還要考慮閃存塊的磨損均衡度和資源的合理利用.所以回收策略結合了擦除次數、有效頁比例和熱度值.具體公式如公式(1)所示：

(1)

其中：v表示順序日志塊中有效頁比例；εmin表示FLASH設備中塊的最小擦除次數；εmax表示FLASH設備中塊的最大擦除次數；εi表示該物理塊被擦除的次數；HotTh表示判定冷熱塊的閾值；Hoti表示該塊的熱度值.對于混合映射來說由于垃圾回收必然會執行數據塊合并操作，當順序日志塊上有效頁越多執行部分合并時效率就越高，同時冷熱程度也作為資源合理利用的依據，冷數據塊所對應的日志塊會被長期占用，由于冷數據塊可能在接下來很長一段時間無數據寫入，因此也無法通過數據寫滿日志塊觸發合并回收日志塊，此時日志塊將被一直無法被其他塊使用，這對空間的利用和磨損均衡都是不利的[10]，所以應該優先回收冷數據塊的日志塊.回收機制會選擇數據塊的順序日志塊有效頁最多、擦除次數最少且熱度值最低的數據塊進行回收.

3 實驗與分析

3.1 實驗環境及實驗參數

在linux 2.6下使用disksim磁盤仿真平臺模擬NAND閃存.測試數據使用同等大小的RAM虛擬磁盤設備在實際運行下的讀寫記錄生成tarce文件.通過在disksim中添加測試算法并使用生成的tarce測試數據進行測試獲得性能數據.其中RAM虛擬磁盤格式化為FAT32文件系統，在文件系統中創建1KB～2MB文件，所有文件大小總和占RAM虛擬磁盤設備85%.文件創建完后對文件進行更新.測試數據通過記錄系統對虛擬磁盤的I/O生成可用于Flashsim 的trace測試數據[11-13].模擬出來的NAND 閃存和RAM磁盤大小都為64M，NAND 閃存頁大小為8KB，塊大小為1MB，總容量為64MB.實驗與同樣使用混合映射的CAT、SACATA算法進行性能比較.HMSGC算法中參數HotTh設為128，熱度鏈表長度為128.

3.2 算法性能比較

論文在FAST轉換層的基礎上實現了CAT、SACATA、HMSGC三種垃圾回收算法并進行了實驗比較.性能比較采用的指標包括：所有物理塊的擦除總數、全合并總數、擦除次數的標準差曲線、擦除次數最大差值比和響應時間.

由圖3、圖4可知，隨寫入數據的增加，使用HMSGC算法的總擦除次數始終比CAT、SACATA算法少50%以上，全合并次數要少84%.這主要是因為HMSGC對冷熱數據塊進行了識別，并且將冷熱塊的更新數據分開存儲到不同擦除次數的日志塊中，減少了垃圾回收觸發頻率以及全合并次數.

圖3 擦除總次數對比圖Fig.3 Totalnumberoferaseoperation圖4 全合并次數對比圖Fig.4 Totalnumberofmergers

由圖5可知，HMSGC算法的塊最大擦除次數和最小擦除次數差值要比CAT和SACATA算法少70%.這是因為回收代價函數中引入了塊的熱度值，回收了更新數據較慢的冷數據塊，改善了磨損均衡度，提高了塊空間了利用.

圖5 擦除次數最大差值對比Fig.5 Maximumdifferentoferasecycles圖6 擦除次數的標準差對比Fig.6 Standdeviationofblockerasecycles

由圖6可知，隨著擦除次數的增加，CAT和SACATA算法的標準差逐漸增加且增速變快，而HMSGC算法的標準差雖然隨著擦除次數的增加也在增加，但其增速卻比CAT和SACATA算法要慢，并且標準差更趨近于穩定.這是由于HMSGC算法選擇合適的物理塊進行回收，同時以邏輯塊的熱度對日志塊數據進行冷熱分離.把擦除次數最少的物理塊作為熱邏輯塊的數據塊和日志塊，把擦除次數最多的物理塊作為冷邏輯塊的數據塊和日志塊.這種策略有助于平衡各物理塊的擦除次數，從而改善了塊的磨損均衡度.

表1 算法讀寫性能Table 1 Algorithm read and write performance

由表1可知，I/O的平均響應時間和最大響應時間HMSGC算法要明顯小于SACATA和CAT算法.這是由于HMSGC算法使用冷熱數據分離大量減少了全合并的次數，同時為熱數據塊分配單獨的日志塊避免熱數據塊頻繁觸發合并操作，縮短了響應時間.

4 結 語

針對NAND閃存的硬件特性，改進FAST轉換層提出了一種基于混合映射的垃圾回收算法.首先，提出一種基于循環隊列的熱塊識別算法計算邏輯塊熱度，其次選擇對應順序日志塊有效頁最多、擦除次數最少且熱度值最低的數據塊進行回收.最后將熱數據存入擦除次數最少的數據塊或日志塊中，冷數據存入擦除次數最大的數據塊或日志塊中.實現在日志塊中冷熱數據的分開存儲.實驗結果表明，與CAT和SACATA算法比較，磨損均衡度方面取得了較好的性能，同時全合并觸發次數和擦除總次數減少了50%以上.在I/O性能上也有較大的提升.該算法能夠延長NAND 閃存的壽命，并優化其性能.