基于NAND Flash存儲器的磨損均衡DP算法優化

薛 鐳

(中國船舶重工集團公司第七一五研究所 浙江 杭州 310023)

0 引 言

用NAND Flash作為存儲媒介，具有體積小、功耗低、速度快等特點，廣泛受到青睞，在手機、平板電腦、數碼相機等電子產品中均有運用[1]。NAND Flash不能被復寫，寫之前需要做擦除操作。NAND Flash讀寫操作的基本單位是頁。其中包含最新數據的頁被稱為有效頁(新數據被稱為有效數據)，包含舊數據的頁被稱為無效頁或臟頁，臟頁經過擦除操作后成為空閑頁，才可以重新寫入數據。NAND Flash擦除操作的基本單位是塊(如1個塊包含多個頁)，塊的擦除次數是有限的(根據不同顆粒類型如TLC/MLC/SLC等，一般幾千次到100萬次之間)，如果出現塊的擦除次數達到了上限，NAND Flash的性能將大幅下降[2]。

經常使用讀寫的數據稱為熱數據,很少被讀寫到的數據稱為冷數據，冷數據和熱數據將導致存儲在NAND介質上的數據塊的讀寫擦除計數出現嚴重不平衡。為了保持NAND Flash性能的穩定，必須提出一種方法使每個塊的擦除操作盡可能均衡，這種方法就是磨損均衡算法。

Chang[3]提出的雙池算法是目前眾多磨損均衡算法中較為主流的算法。相比其他算法而言，該算法主要解決了“冷塊”幾乎不被處理和磨損控制水平較低的問題，達到了預期的磨損均衡效果。本文在雙池算法的基礎上，保留磨損控制的策略，針對其不足之處提出進一步優化的方案，并通過仿真實驗進行驗證分析，期望保留較高磨損控制水平，縮短磨損均衡過程，減少頁復制次數，使NAND Flash的使用壽命進一步提高。

1 雙池算法

1.1 算法原理

該算法首先將NAND Flash塊隨機地分配到“冷池”和“熱池”中，隨著數據的更新，算法將存放冷熱數據的NAND Flash塊分別存入“冷池”和“熱池”中。如果“熱池”中的某些塊的被擦除次數大于某個閾值，這些塊的數據將被將換到“冷池”中擦除次數最少的閃存塊中。

比如NAND Flash一共有1 024個塊，系統初始化時，給“冷池”分配序號為奇數的塊，給“熱池”分配序號為偶數的塊如圖1所示。“冷池”NAND Flash塊表A和“熱池”NAND Flash塊表B分別包含512條表項，每個表現有32個字節，包含：塊序號(4 Bytes)+擦除次數(4 Bytes)+有效頁比例(4 Bytes)+修改時間(16 Bytes)+回收權值(4 Bytes)，則表A和表B大小分別為16 KB，一共32 KB。

圖1 雙池算法磨損均衡

以MLC顆粒的NAND Flash為例，假設每個塊擦除最大次數為3 000次，設定降溫閾值為2 000次。當系統掃描表B中第一個(塊號m)擦除次數大于2 000的塊時，系統掃描表A中擦寫次數最小的塊(塊號n)，將塊號m中的數據與塊號n中的數據對換。

1.2 塊搜索策略

雙池算法搜索的塊搜索策略采用的是排序算法，根據DP算法描述的一次“熱塊”降溫過程，搜索時間包括掃描表A查找擦寫次數最小的塊時間開銷+ 掃描表B查找第一個擦寫次數閾值的塊開銷。

掃描表A或表B在空間復雜度最低并且排序穩定的前提下，查找或插入表A和表B中一個節點的最壞時間復雜度為O(N)，每次查找操作時間為10 μs。按照最大時間計算：DPT1=0.01 ms×512×2=10.24 ms。

1.3 垃圾回收策略

雙池算法選用CAT[4]算法(Cost-Age-time Algorithm)作為垃圾回收策略。CAT算法的權重計算公式如下，選擇權重最小的塊進行回收。

(1)

式中:age表示此塊最后一次修改的時間；u表示塊有效頁比例；CT表示塊的擦除次數。

這種策略優點是綜合考慮了塊擦除次數、有效頁比例、塊最后一次修改時間等3個因素，垃圾回收效果較好；缺點是只考慮物理塊最后一次修改時間，不能真實反映物理塊年齡，同時對塊表的更新操作及頁的復制操作頻繁，系統開銷大。

雙池算法占用的空間資源包括塊信息表占用資源+塊搜索占用資源+垃圾回收策略占用資源。其中塊信息表占用資源包含所有塊完整的信息，塊搜索占用資源包含所有塊的擦除次數信息，垃圾回收策略占用資源包含所有塊的權值信息。按照最大空間復雜度計算：

DPS1=32 Byte×1 024+4 Byte×1 024×2=40 KB。

2 優先搜索樹算法

2.1 算法原理

在優先搜索樹(簡稱PST算法)中，每個樹的節點由基索引和堆索引來標識。優先搜索樹是一個依賴于基索引的搜索樹，并附加一個類堆屬性即一個節點的堆索引不會小于其子節點的堆索引，任意一個節點的左子節點基索引也都不大于右子節點基索引。

塊節點(16 Bytes)=塊序號(基索引4 Bytes)+擦除次數(堆索引4 Bytes)+有效頁比例(附加信息4 Bytes)+回收權值(附加信息4 Bytes)。

比如NAND Flash一共有1 024個塊，則整個索引表的大小為32 KB。系統初始化時，搜索算法從塊序號為0的塊按照塊序號(即基索引)開始搜索，這個搜索樹是個二叉樹卻是不對稱的，如圖2所示。

圖2 優先搜索樹算法

初始化完成后，所有節點掃描完成后形成二叉樹Cm樹。因此，根據這個二叉樹磨均衡操作的過程就是不斷從非對稱向對稱結構進行調整的過程。

2.2 塊搜索策略

還是以MLC顆粒的NAND Flash為例，假設每個塊擦除最大次數為3 000次，設定降溫閾值為2 000次。當系統從Cm樹塊序號為0的塊開始查找第一個擦除次數大于2 000 的NAND Flash塊(塊號p)，然后從Cm樹塊序號為0的塊開始查找擦除次數最小的塊(塊號q)，將塊號p中的數據與塊號q中的數據對換，并根據擦除次數調整Cm樹中節點p和q的位置。降溫一個“熱池”NAND Flash塊數據開銷：

PSTT1= 查找塊p的時間+查找塊q的時間

Cm二叉樹查找或插入一個節點最壞時間復雜度為O(log2N)，每次查找操作時間為10 μs。

按照最大時間計算：

PSTT1=0.01 ms×log21 024×2 =0.2 ms

2.3 垃圾回收策略

基于優先搜索樹的垃圾回收策略不再考慮每個塊的最后一次修改時間，而是將當前塊的擦除次數與最大擦除次數的差距作為考慮因素，權重計算如下：

(2)

式中：u表示有效頁比例,CT表示當前塊擦除次數，CTmax表示最大擦除次數。

這種策略減少了一個權重因子，公平地考慮擦除次數與有效頁比例對于磨損均衡的影響，使得回收操作不受塊更新時間因素的干擾，同時也減少了權重計算開銷。

優先搜索樹算法占用的空間資源包括塊信息表占用資源+塊搜索占用資源+垃圾回收策略占用資源。其中塊信息表占用資源包含所有塊完整的信息，塊搜索占用資源包含所有塊的擦除次數信息，垃圾回收策略占用資源包含所有塊的權值信息。按照最大空間復雜度計算：

PSTS1=16 Byte×1 024+4 Byte×1 024×2=

24 KB。

2.4 算法比較

相對于DP算法的耗費的系統資源、時間開銷也大為降低，如表1所示。

表1 算法比較

3 實驗分析

本文使用FlashSim[5]實驗平臺對設計的算法進行性能分析。

3.1 實驗環境

FlashSim是一款開源的、事件驅動的、模塊化的基于C++的SSD模擬器，內置了多種FTL策略，能夠提供響應時間、能耗的模擬及許多額外的統計信息。

FlashSim分為兩部分，軟件部分和硬件部分。硬件部分模擬SSD固態盤，其內部結構與SSD的實際結構有著很好的映射關系。FlashSim模擬器硬件部分由處理器、RAM、總線和flash芯片組成如圖3所示。

圖3 FlashSim模擬器硬件結構

設置FlashSim模擬器硬件部分Nand flash芯片參數如表2所示。

FlashSim模擬器軟件部分模擬FTL功能，運行在調試電腦Ubuntu 10.04的Linux系統上，整個實驗平臺如圖4所示。

圖4 實驗平臺

設置FlashSim模擬器軟件部分實驗參數如表3所示。

表3 實驗參數

3.2 實驗數據

為了模擬出真實環境下的算法性能，輸入文件的選擇主要來源于企業級寬頻譜的工作負載[6]。我們采用了兩種測試文件，分別是Financial、Web search。這兩種負載文件特性如表4所示。

表4 實驗數據

對于Financial文件數據，是以寫為主，具有很強的時間局限性，對于Web search，其主要是讀操作的蹤跡數。通過下載的測試源數據包，其中有兩份Financial測試數據(分別稱為F1、F2)和三份Web Search測試數據(分別稱之為W1、W2、W3)，對于這五份數據都作為實驗的測試數據源。

3.3 性能分析

在實驗中，以系統響應時間、塊磨損度作為性能指標，以此驗證PST算法和DP算法的性能。

(1) 系統平均響應時間 圖5是PST算法的FTL和DP算法的FTL在不同負載下平均響應時間對比圖。由于PST算法在系統命中率提高了很多，以至于減少了很多地址轉換過程，因此其在系統平均響應時間性能上得到優化如表5所示。

圖5 系統平均響應時間

表5 系統平均響應時間

(2) 塊磨損度 兩種算法分別用以寫入為主的Financial測試數據(分別稱為F1、F2)運行5萬次后Nand Flash的磨損情況如圖6所示，橫坐標為Nand Flash塊號，縱坐標為Nand Flash塊擦除次數。

圖6 Nand Flash的磨損情況

4 結 語

本文提出了一種基于優先搜索樹的磨損均衡算法，通過基索引和堆索引的組合進行類似二叉樹查找和排序，針對DP算法中磨損過程緩慢和磨損均衡分布不均的問題進行了改進，降低了系統響應時間和提升了塊的使用壽命，進一步優化了FTL的性能。