基于NAND Flash存儲器的頁映射Chiang算法優化?

（中國船舶重工集團公司第七一五研究所第七研究室 杭州 310023）

1 引言

Flash存儲器的非易失、高密度、高存取速度、低功耗、低價格等特性，使得它在很多領域中有著廣泛應用，而Flash又分為NAND Flash和NOR Flash。NOR Flash具有很好的讀寫性能和隨機訪問性能，但單片容量較小且寫入速度慢，主要用來執行片上程序；而NAND Flash不僅具有優秀的讀寫性能，而且具有較大的存儲容量和性價比，因此在存儲領域得到了廣泛的應用。

然而，NAND Flash存儲器不同于傳統磁盤存儲器，存在著兩個主要特點［1］：其一，重寫之前必須進行擦除；其二，讀寫操作以頁為單位，而擦除操作以塊為單位，并且塊的擦除次數是有限的，NAND Flash的物理結構如圖1所示。NAND Flash不能像磁盤存儲器一樣被傳統文件系統直接使用。因此，需要一個閃存轉換層（Flash Translation Layer，FTL）將其模擬成標準的塊設備以屏蔽其特性，使得上層文件系統在使用它時就像在使用一個普通的磁盤存儲器。FTL的主要功能是實現文件系統直接對NAND Flash進行讀、寫、擦除操作。當上層文件系統發出對某個邏輯地址進行操作的指令后，FTL分析指令通過轉譯在與該邏輯地址相對應的物理地址上進行操作，其功能的核心就在于地址映射，映射通常分為塊映射和頁映射兩種。

圖1 NANDFlash物理結構

2 Chiang算法

Chiang算法［2］將邏輯地址映射到（物理塊號，物理頁號），如圖2所示。這種算法可以通過映射表直接找到對應的物理頁，提供了比較快的映射速度，存儲空間利用率非常高，同時也支持頁的隨機讀寫，但映射表的存儲消耗了大量的系統資源，垃圾回收代價太高。比如1個Nand flash大小為128GB，每個頁大小為4KB，在Chiang算法頁映射下需要128GB/4KB=32，000，000條表項，每個表項需要4B，則映射表大小為128MB，需要占用至少128MB的內存，在嵌入式系統里面需要的內存資源代價是非常昂貴的。

圖2 Chiang算法地址映射

3 伙伴系統算法

3.1 算法模型

NAND Flash芯片中，1個物理塊的大小2N個連續的物理頁，把所有的可用物理塊劃分為N+1組，每組分別包含M0…MN個物理塊，總的可用物理塊數=M0+M2+…+MN個物理塊。邏輯地址映射到（物理塊組號，物理塊號，物理頁號），如圖3所示。物理塊組中的每個物理塊分別對應到2N，…，8，4，2，1個邏輯地址的方式建立映射表。

物理塊組0中，每個邏輯地址映射到包含1個物理頁的起始物理頁號，映射表記錄條數為M0*2N；

物理塊組1中，每個邏輯地址映射到包含2個物理頁的起始物理頁號，映射表記錄條數為M2*2N-1；

…

物理塊組N中，每個邏輯地址映射到包含連續2N個物理頁的起始物理頁號，映射表記錄條數為MN*20；

圖3 分組映射

3.2 系統資源計算

比如1個Nand flash大小為128GB，包含512K個塊，每個塊包含64=26頁，每頁大小為4KB，在伙伴系統算法下劃分7（即N=6）個物理塊組（組0～組6）。

設 定 1：M0=256K，M1=128K，M2=64K，M3=32K，M4=16K，M5=8K，M6=8K。總的映射表記錄為M0*26+M1*25+…+M6*20=22，372，352條表項，每條表項需要4B，則占用內存大小為89MB，相對于Chiang算法系統資源降低25%左右；

設定 2：M0=128K，M1=128K，M2=128K，M3=64K，M4=32K，M5=16K，M6=16K。總的映射表記錄為M0*26+M1*25+…+M6*20=15，384，576條表項，每條表項需要4B，則占用內存大小為61MB，相對于Chiang算法系統資源降低50%左右。

其中M0，M1，…，M6的值，在綜合權衡空間利用率和垃圾回收代價可以相對調整，直到設定使FTL性能最優值。

3.3 算法比較

相對于Chiang算法的頁映射，映射表體積、空間復雜度、耗費的系統資源、垃圾回收代價也大為降低，如表1所示。

表1 算法比較

4 性能分析

在實驗中，使用一系列的基準數據集仿真評估本文算法的有效性。本文將提出的方法（簡稱BS算法）和基于Chiang算法的頁級映射方法進行了實驗比較。實驗中使用4個性能度量指標：平均磨損速率、傳輸速率、系統響應時間和塊擦除次數。

4.1 實驗平臺

圖4 實驗中用的仿真框架

圖4 為性能分析實驗仿真平臺，DiskMon［5］為磁盤驅動數據跟蹤器，收集訪問磁盤的I/O數據請求；DiskSim［6］是一個廣泛用于工業界的成熟磁盤仿真框架；FlashSim作為DiskSim的一個擴展組件，用于仿真閃存芯片的管理方法和基本操作。在仿真實驗中，本文在FlashSim中實現了Chiang算法和本文的地址映射算法，配置了一個128GB的NAND閃存存儲系統，具體參數見表2。

表2 Flash配置參數

實驗采用實際I/O數據請求研究不同地址映射方法對性能的影響。I/O數據集的基本情況見表3。 其 中 ，Websearch［7］來 自 SPC（storage performance council），是一個讀為主的I/O數據集。Financial來自OLTP應用［7］，是一個連續訪問的數據集，其系統運行在商業數據中心。該數據集對應的邏輯空間較小。Systemdisk1～Systemdisk3為通過Diskmon收集的PC的磁盤訪問請求。其中，Systemdisk1數據集環境為多個文件的拷貝操作，具有較高的寫操作比例。Systemdisk2為音樂在線播放環境下收集的數據集，因此具有較高的請求數，連續寫操作較多，但是請求長度較小。Systemdisk3為多處理程序數據處理，隨機寫操作較多，但是請求長度較小。Systemdisk3為多程序數據處理，隨機寫操作較多，相鄰寫操作間的地址距離較大。因此，實驗數據集覆蓋了企業級的讀為主和寫為主的數據環境，也包括了日常數據環境下的連續寫、隨機寫、不同請求長度的各類數據集，具有一定的代表性。實驗前，通過預處理過程將數據集中的讀請求預先寫入仿真的Nand flash。

表3 仿真數據集

4.2 實驗結果

實驗比較了Chiang算法和本文提出的地址映射方法，根據4個性能度量指標——平均磨損速率、傳輸速率、系統響應時間和塊擦除次數，具體分析和討論實驗結果。

4.2.1 平均磨損速率

平均磨損速率是衡量FTL性能的重要指標，為公平比較，實驗評估了同樣的讀寫次數下，本文方法和Chiang算法的磨損速度。讀寫次數設定為1000次，1500次，2000次，3000次。實驗結果如圖5所示，本文提出的算法至少降低10%的磨損速率。

圖5 平均磨損率

4.2.2 傳輸速率

實驗分別采用了傳輸32KB、64KB、128KB、256KB、512KB、1MB、2MB、4MB、8MB、16MB、32MB的數據比較BS算法和Chiang算法的傳輸速率，如圖6所示。

圖6 傳輸速率

4.2.3 系統響應時間

系統平均響應時間是閃存存儲系統性能的重要評估指標之一，實驗比較了Chiang算法和本文方法的系統平均響應時間。影響系統平均響應時間的關鍵因素是垃圾回收機制，因此實驗主要評估了垃圾回收運行情況下對系統平均響應時間的影響。實驗結果如圖7所示，本文方法平均提高了17.14%的系統平均響應時間。

4.2.4 塊擦除次數

本文方法能夠顯著降低塊擦寫次數，而對寫為主的其他數據集，本文方法也能獲得不同程度塊擦除次數的優化，特別是對于隨機寫的數據環境，本文方法利用邏輯地址在對不同物理塊內部物理頁號映射的指數級分布，大部分相近邏輯地址的數據更容易一起更新，因此顯著降低了塊擦除的次數。

圖7 系統響應時間

圖8 塊擦除次數

5 結語

本文提出了一種基于伙伴系統算法，通過將Nand flash的可用物理塊進行分組，每個物理塊組映射的邏輯地址成2k（K取值范圍為0…N）個數指數級分布，降低了映射表占用的系統資源，也減少了映射表更新次數，均衡了空間利用率和垃圾回收代價，提升了FTL性能。