基于NAND Flash存儲(chǔ)器的磨損均衡DP算法優(yōu)化

薛 鐳

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

0 引 言

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

經(jīng)常使用讀寫的數(shù)據(jù)稱為熱數(shù)據(jù),很少被讀寫到的數(shù)據(jù)稱為冷數(shù)據(jù)，冷數(shù)據(jù)和熱數(shù)據(jù)將導(dǎo)致存儲(chǔ)在NAND介質(zhì)上的數(shù)據(jù)塊的讀寫擦除計(jì)數(shù)出現(xiàn)嚴(yán)重不平衡。為了保持NAND Flash性能的穩(wěn)定，必須提出一種方法使每個(gè)塊的擦除操作盡可能均衡，這種方法就是磨損均衡算法。

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

1 雙池算法

1.1 算法原理

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

比如NAND Flash一共有1 024個(gè)塊，系統(tǒng)初始化時(shí)，給“冷池”分配序號(hào)為奇數(shù)的塊，給“熱池”分配序號(hào)為偶數(shù)的塊如圖1所示?！袄涑亍盢AND Flash塊表A和“熱池”NAND Flash塊表B分別包含512條表項(xiàng)，每個(gè)表現(xiàn)有32個(gè)字節(jié)，包含：塊序號(hào)(4 Bytes)+擦除次數(shù)(4 Bytes)+有效頁(yè)比例(4 Bytes)+修改時(shí)間(16 Bytes)+回收權(quán)值(4 Bytes)，則表A和表B大小分別為16 KB，一共32 KB。

圖1 雙池算法磨損均衡

以MLC顆粒的NAND Flash為例，假設(shè)每個(gè)塊擦除最大次數(shù)為3 000次，設(shè)定降溫閾值為2 000次。當(dāng)系統(tǒng)掃描表B中第一個(gè)(塊號(hào)m)擦除次數(shù)大于2 000的塊時(shí)，系統(tǒng)掃描表A中擦寫次數(shù)最小的塊(塊號(hào)n)，將塊號(hào)m中的數(shù)據(jù)與塊號(hào)n中的數(shù)據(jù)對(duì)換。

1.2 塊搜索策略

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

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

1.3 垃圾回收策略

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

(1)

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

這種策略優(yōu)點(diǎn)是綜合考慮了塊擦除次數(shù)、有效頁(yè)比例、塊最后一次修改時(shí)間等3個(gè)因素，垃圾回收效果較好；缺點(diǎn)是只考慮物理塊最后一次修改時(shí)間，不能真實(shí)反映物理塊年齡，同時(shí)對(duì)塊表的更新操作及頁(yè)的復(fù)制操作頻繁，系統(tǒng)開銷大。

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

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

2 優(yōu)先搜索樹算法

2.1 算法原理

在優(yōu)先搜索樹(簡(jiǎn)稱PST算法)中，每個(gè)樹的節(jié)點(diǎn)由基索引和堆索引來(lái)標(biāo)識(shí)。優(yōu)先搜索樹是一個(gè)依賴于基索引的搜索樹，并附加一個(gè)類堆屬性即一個(gè)節(jié)點(diǎn)的堆索引不會(huì)小于其子節(jié)點(diǎn)的堆索引，任意一個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)基索引也都不大于右子節(jié)點(diǎn)基索引。

塊節(jié)點(diǎn)(16 Bytes)=塊序號(hào)(基索引4 Bytes)+擦除次數(shù)(堆索引4 Bytes)+有效頁(yè)比例(附加信息4 Bytes)+回收權(quán)值(附加信息4 Bytes)。

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

圖2 優(yōu)先搜索樹算法

初始化完成后，所有節(jié)點(diǎn)掃描完成后形成二叉樹Cm樹。因此，根據(jù)這個(gè)二叉樹磨均衡操作的過(guò)程就是不斷從非對(duì)稱向?qū)ΨQ結(jié)構(gòu)進(jìn)行調(diào)整的過(guò)程。

2.2 塊搜索策略

還是以MLC顆粒的NAND Flash為例，假設(shè)每個(gè)塊擦除最大次數(shù)為3 000次，設(shè)定降溫閾值為2 000次。當(dāng)系統(tǒng)從Cm樹塊序號(hào)為0的塊開始查找第一個(gè)擦除次數(shù)大于2 000 的NAND Flash塊(塊號(hào)p)，然后從Cm樹塊序號(hào)為0的塊開始查找擦除次數(shù)最小的塊(塊號(hào)q)，將塊號(hào)p中的數(shù)據(jù)與塊號(hào)q中的數(shù)據(jù)對(duì)換，并根據(jù)擦除次數(shù)調(diào)整Cm樹中節(jié)點(diǎn)p和q的位置。降溫一個(gè)“熱池”NAND Flash塊數(shù)據(jù)開銷：

PSTT1= 查找塊p的時(shí)間+查找塊q的時(shí)間

Cm二叉樹查找或插入一個(gè)節(jié)點(diǎn)最壞時(shí)間復(fù)雜度為O(log2N)，每次查找操作時(shí)間為10 μs。

按照最大時(shí)間計(jì)算：

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

2.3 垃圾回收策略

基于優(yōu)先搜索樹的垃圾回收策略不再考慮每個(gè)塊的最后一次修改時(shí)間，而是將當(dāng)前塊的擦除次數(shù)與最大擦除次數(shù)的差距作為考慮因素，權(quán)重計(jì)算如下：

(2)

式中：u表示有效頁(yè)比例,CT表示當(dāng)前塊擦除次數(shù)，CTmax表示最大擦除次數(shù)。

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

優(yōu)先搜索樹算法占用的空間資源包括塊信息表占用資源+塊搜索占用資源+垃圾回收策略占用資源。其中塊信息表占用資源包含所有塊完整的信息，塊搜索占用資源包含所有塊的擦除次數(shù)信息，垃圾回收策略占用資源包含所有塊的權(quán)值信息。按照最大空間復(fù)雜度計(jì)算：

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

24 KB。

2.4 算法比較

相對(duì)于DP算法的耗費(fèi)的系統(tǒng)資源、時(shí)間開銷也大為降低，如表1所示。

表1 算法比較

3 實(shí)驗(yàn)分析

本文使用FlashSim[5]實(shí)驗(yàn)平臺(tái)對(duì)設(shè)計(jì)的算法進(jìn)行性能分析。

3.1 實(shí)驗(yàn)環(huán)境

FlashSim是一款開源的、事件驅(qū)動(dòng)的、模塊化的基于C++的SSD模擬器，內(nèi)置了多種FTL策略，能夠提供響應(yīng)時(shí)間、能耗的模擬及許多額外的統(tǒng)計(jì)信息。

FlashSim分為兩部分，軟件部分和硬件部分。硬件部分模擬SSD固態(tài)盤，其內(nèi)部結(jié)構(gòu)與SSD的實(shí)際結(jié)構(gòu)有著很好的映射關(guān)系。FlashSim模擬器硬件部分由處理器、RAM、總線和flash芯片組成如圖3所示。

圖3 FlashSim模擬器硬件結(jié)構(gòu)

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

FlashSim模擬器軟件部分模擬FTL功能，運(yùn)行在調(diào)試電腦Ubuntu 10.04的Linux系統(tǒng)上，整個(gè)實(shí)驗(yàn)平臺(tái)如圖4所示。

圖4 實(shí)驗(yàn)平臺(tái)

設(shè)置FlashSim模擬器軟件部分實(shí)驗(yàn)參數(shù)如表3所示。

表3 實(shí)驗(yàn)參數(shù)

3.2 實(shí)驗(yàn)數(shù)據(jù)

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

表4 實(shí)驗(yàn)數(shù)據(jù)

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

3.3 性能分析

在實(shí)驗(yàn)中，以系統(tǒng)響應(yīng)時(shí)間、塊磨損度作為性能指標(biāo)，以此驗(yàn)證PST算法和DP算法的性能。

(1) 系統(tǒng)平均響應(yīng)時(shí)間 圖5是PST算法的FTL和DP算法的FTL在不同負(fù)載下平均響應(yīng)時(shí)間對(duì)比圖。由于PST算法在系統(tǒng)命中率提高了很多，以至于減少了很多地址轉(zhuǎn)換過(guò)程，因此其在系統(tǒng)平均響應(yīng)時(shí)間性能上得到優(yōu)化如表5所示。

圖5 系統(tǒng)平均響應(yīng)時(shí)間

表5 系統(tǒng)平均響應(yīng)時(shí)間

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

圖6 Nand Flash的磨損情況

4 結(jié) 語(yǔ)

本文提出了一種基于優(yōu)先搜索樹的磨損均衡算法，通過(guò)基索引和堆索引的組合進(jìn)行類似二叉樹查找和排序，針對(duì)DP算法中磨損過(guò)程緩慢和磨損均衡分布不均的問(wèn)題進(jìn)行了改進(jìn)，降低了系統(tǒng)響應(yīng)時(shí)間和提升了塊的使用壽命，進(jìn)一步優(yōu)化了FTL的性能。