基于NAND Flash存儲器的頁映射Chiang算法優(yōu)化?

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

1 引言

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

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

圖1 NANDFlash物理結構

2 Chiang算法

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

圖2 Chiang算法地址映射

3 伙伴系統(tǒng)算法

3.1 算法模型

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

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

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

…

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

圖3 分組映射

3.2 系統(tǒng)資源計算

比如1個Nand flash大小為128GB，包含512K個塊，每個塊包含64=26頁，每頁大小為4KB，在伙伴系統(tǒng)算法下劃分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，則占用內(nèi)存大小為89MB，相對于Chiang算法系統(tǒng)資源降低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，則占用內(nèi)存大小為61MB，相對于Chiang算法系統(tǒng)資源降低50%左右。

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

3.3 算法比較

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

表1 算法比較

4 性能分析

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

4.1 實驗平臺

圖4 實驗中用的仿真框架

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

表2 Flash配置參數(shù)

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

表3 仿真數(shù)據(jù)集

4.2 實驗結果

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

4.2.1 平均磨損速率

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

圖5 平均磨損率

4.2.2 傳輸速率

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

圖6 傳輸速率

4.2.3 系統(tǒng)響應時間

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

4.2.4 塊擦除次數(shù)

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

圖7 系統(tǒng)響應時間

圖8 塊擦除次數(shù)

5 結語

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