秦曉安

（安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽蕪湖241002）

大塊NAND閃存的轉(zhuǎn)換層優(yōu)化算法設(shè)計(jì)

秦曉安

（安徽商貿(mào)職業(yè)技術(shù)學(xué)院電子信息工程系，安徽蕪湖241002）

通過運(yùn)用大塊NAND研究閃存轉(zhuǎn)換層的基本原理，針對(duì)物理閃存中的數(shù)據(jù)塊和更新塊，利用地址混合映射的方法，對(duì)邏輯塊號(hào)和頁號(hào)進(jìn)行拆分，區(qū)分更新塊的熱門頁及數(shù)據(jù)塊的冷門頁，使用改進(jìn)的優(yōu)化算法根據(jù)其空閑程度進(jìn)行部分、完全或交換合并優(yōu)化，最后通過實(shí)驗(yàn)對(duì)存儲(chǔ)利用率和緩存大小影響進(jìn)行性能分析，實(shí)驗(yàn)數(shù)據(jù)表明：運(yùn)用該算法可以有效提高NAND閃存存儲(chǔ)效率.

NAND閃存；閃存轉(zhuǎn)換層；地址映射；垃圾回收

NAND閃存是一種比硬盤驅(qū)動(dòng)器更好的存儲(chǔ)方案，這在不超過4GB的低容量應(yīng)用中表現(xiàn)得猶為明顯.隨著人們持續(xù)追求功耗更低、重量更輕和性能更佳的產(chǎn)品，NAND正被證明極具吸引力[1].

通過對(duì)NAND Flash的存儲(chǔ)及操作特性的研究，發(fā)現(xiàn)通用文件系統(tǒng)不能直接用于管理Flash設(shè)備[2].最近，一種新型NAND閃存存儲(chǔ)器已經(jīng)問世，稱之為大塊NAND，它可以提供高密度及高性能的大塊數(shù)據(jù)傳輸.在大塊NAND閃存存儲(chǔ)器中，每頁由2 K字節(jié)主數(shù)據(jù)區(qū)和64字節(jié)空閑區(qū)組成，其中1塊由64頁組成.但是大塊NAND有一個(gè)使用限制：在一個(gè)塊中，頁寫必須按照從頁0到頁63的順序，塊中隨機(jī)頁寫是被禁止的.

NAND閃存不同于磁盤或是SRAM和DRAM，與讀操作相比，寫操作需要更長的時(shí)間.因?yàn)樵趯懖僮髦敖?jīng)常需要先進(jìn)行擦除操作，所以擦寫操作時(shí)間會(huì)更長.大塊NAND閃存存儲(chǔ)器的另外一個(gè)局限是單位塊的擦寫，極限是大約100 000到1 000 000次，而且必須先擦后寫.因此，本文研究改進(jìn)的辦法盡可能地減少擦寫操作次數(shù)，以提高整體性能和延長大塊NAND閃存的壽命.

1 算法研究

1.1 基本原理

閃存轉(zhuǎn)換層（FTL）是NAND閃存存儲(chǔ)器的軟件中間層，它的主要作用是用來消除上層對(duì)于NAND閃存存儲(chǔ)器先擦后寫的限制[3]，其中最主要的兩個(gè)部分是地址映射和垃圾回收.地址映射的主要工作是將目標(biāo)邏輯頁與對(duì)應(yīng)的物理頁進(jìn)行映射，根據(jù)所映射的顆粒度大小，可以分為頁映射和塊映射；垃圾回收是指擦除特定塊進(jìn)行回收空白頁的過程.

隨著NAND閃存存儲(chǔ)容量的增加，頁映射需要更多RAM，這將會(huì)導(dǎo)致很嚴(yán)重的成本問題.比如，一個(gè)4G字節(jié)的NAND閃存，頁映射需要8M字節(jié)的RAM用來管理映射表，而塊映射只需要128 K字節(jié).所以，一些基于塊映射的閃存轉(zhuǎn)換層改進(jìn)機(jī)制被廣泛應(yīng)用于NAND閃存的存儲(chǔ)系統(tǒng).

通常根據(jù)塊的用途，可以把物理閃存中的塊分為D-blocks（數(shù)據(jù)塊）和U-blocks（更新塊）[4].當(dāng)一個(gè)寫操作發(fā)生、且寫操作無法在所要求的D-block完成時(shí)，閃存轉(zhuǎn)換層會(huì)將新數(shù)據(jù)寫入U(xiǎn)-block同時(shí)置原D-block為無效.一旦U-block被分配出來，接下去原D-block上的寫操作就會(huì)被重定向到相關(guān)的U-block上.當(dāng)U-block寫滿之后，閃存轉(zhuǎn)換層可以分配一個(gè)新的U-block或者通過合并U-block和原D-block生成一個(gè)新的D-block.雖然有許多不同的塊映射閃存轉(zhuǎn)換層實(shí)現(xiàn)，區(qū)別主要來自如何管理D-blocks和U-blocks，如什么時(shí)候分配多少U-blocks給一個(gè)D-block，或者合并操作如何完成.

1.2 算法實(shí)現(xiàn)

在垃圾回收過程中，首先挑選擁有最大序號(hào)的U-block的D-block為目標(biāo)塊，將所有的有效頁拷貝到最后一個(gè)U-block.接著最后的U-block將成為新的D-block.因?yàn)轫摽偸潜缓喜⑷胱詈笠粋€(gè)U-block，所以只有部分合并和交換合并操作.替換塊機(jī)制存儲(chǔ)空間利用率很差，特別是當(dāng)塊中只有部分頁被頻繁更新時(shí).且這種機(jī)制不適用于大塊NAND閃存，由于塊中的頁無法進(jìn)行隨機(jī)寫操作.

由于閃存轉(zhuǎn)換層只使用少量的U-block，額外的映射開銷會(huì)比較小.當(dāng)所有的U-block都被使用了，部分U-block會(huì)與對(duì)應(yīng)的D-block進(jìn)行合并以釋放出新的空閑U-block.由于D-block是被in-place方式管理的，完全合并會(huì)用來將out-of-place轉(zhuǎn)換為in-place.另外，即使D-block中一頁更新，也需要一個(gè)完整的U-block，類似于替換塊機(jī)制，U-block的空間使用率還是比較低.

塊級(jí)別的空間局部性通常存在于，當(dāng)兩個(gè)或者多個(gè)相鄰邏輯塊被文件系統(tǒng)分配給同一文件或者一些元數(shù)據(jù)，如FAT、目錄、i-node或者bitmap.因此，如果幾個(gè)相鄰邏輯塊共享一個(gè)U-block，U-block的存儲(chǔ)利用率會(huì)提高.

U-block被相關(guān)的塊用來利用塊級(jí)別的時(shí)間局部性和空間局部性.一旦U-block被分配給塊，接下來的塊的寫請(qǐng)求被從第一頁開始按順序記錄到U-block中.這種out-of-place機(jī)制同樣適用于塊中必須從第一頁到最后一頁順序?qū)懙拇髩KNAND閃存存儲(chǔ)器.當(dāng)U-block中沒有空閑頁的時(shí)候，新的U-block被分配給塊.

因?yàn)榇髩KNAND閃存存儲(chǔ)器單頁空閑區(qū)域的容量限制，整個(gè)頁表會(huì)被分成4個(gè)獨(dú)立的PT.PMD的作用就是定位每個(gè)PT的最新位置，最新PMD的位置信息被PGD所管理.PGD儲(chǔ)存在主存儲(chǔ)中，而PMD和PT被儲(chǔ)存在空閑區(qū)域中.因?yàn)镻GD的條數(shù)等于邏輯塊數(shù)，所以PGD的存儲(chǔ)占用與其他塊級(jí)別的閃存管理層機(jī)制是相當(dāng)?shù)?

圖1舉例說明了地址映射的過程.假設(shè)想找到邏輯塊17中邏輯頁12的物理地址.邏輯塊號(hào)被拆為塊號(hào)4及PGD序號(hào)1，邏輯頁號(hào)又可以拆分為PMD序號(hào)0及PTE序號(hào)12.如圖所示，從塊4及PGD 1中找到邏輯塊17最新的PMD.PMD被從空閑區(qū)域中讀出，從第一個(gè)名錄找到PT0的位置，PT0保存有PTE0到PTE15的信息.最終數(shù)據(jù)的位置可以從PT0中的PTE12讀到.

圖1 地址映射的過程

在拆分結(jié)束后，進(jìn)行合并操作.具體操作方法是首先找到一個(gè)物理塊沒有任何有效頁.如果這樣的塊存在，擦除該塊并分配給新塊.如果所選的塊為D-block，則針對(duì)U-block交換合并成D-block.如果這一步不成功，其次找到新塊中含有最少最近改寫的U-block，如果D-block含有足夠的空閑頁，則進(jìn)行部分合并.在其他的情況下，從新塊中挑選兩個(gè)含有最少有效頁的D-block，然后執(zhí)行完全合并.完全合并后，新塊被重新組成：新的塊和U-block成為了D-block，原先的D-block被擦除后被用作空閑U-block.

這種做法的理由是U-block通常含有熱門頁，而D-block含有冷門頁.因此，將冷門頁一起放在D-block中對(duì)于未來的垃圾回收是十分理想的.當(dāng)完全合并后，塊被重新組成：新的塊和U-block成為了D-block，原先的D-block被擦除后被用作空閑U-block.這樣可以將塊中更新頻率接近的頁放入一個(gè)D-block中.因?yàn)閮蓚€(gè)D-block所含的有效頁數(shù)可能超過空閑塊中可以存儲(chǔ)的頁數(shù)，完全合并將一直進(jìn)行到所有的有效頁都被處理完.

如前一小點(diǎn)所述，由于維護(hù)映射信息的限制，分配給新塊的U-block和D-block數(shù)量不能超過8個(gè).因此，當(dāng)嘗試為超級(jí)塊分配第9個(gè)物理塊時(shí)，同樣的垃圾收集將被執(zhí)行以用來回收一個(gè)物理塊.

當(dāng)一個(gè)邏輯頁被更新，更新后的頁映射信息依然存放在空閑區(qū)域中.比如，假如上一段例子中的邏輯頁被更新了，PTE12將指向邏輯頁將要被寫入的位置，第一個(gè)PMD條目將指向同樣的物理頁，因?yàn)閾碛辛诵碌腜T0.當(dāng)頁中被寫入了修改過的PMD和PT0，第二個(gè)PGD條目也將被改為指向新的地點(diǎn).由于更新的PMD和相對(duì)應(yīng)的PT不管何時(shí)頁被更新了都被儲(chǔ)存在閃存存儲(chǔ)中，因而可以保證PMD和PT的每個(gè)條目始終指向有效頁.

因?yàn)槊看巫x、寫或拷貝一頁的時(shí)候，都應(yīng)該讀出PMD和對(duì)應(yīng)的PT，所以采用緩存的方式來減少閃存讀操作的次數(shù).緩存條目包括PMD和對(duì)應(yīng)的4條被用來記錄單塊邏輯塊頁映射信息的PT.緩存條目的數(shù)量是固定的，使用最近最少使用（LRU）替換的機(jī)制來管理這些條目[5].這樣的緩存機(jī)制類似于日志塊機(jī)制和FAST中使用的機(jī)制.實(shí)驗(yàn)顯示少量的緩存條目工作得非常好.

2 性能分析

2.1 存儲(chǔ)利用率

存儲(chǔ)利用率是影響閃存轉(zhuǎn)換層性能的一個(gè)很重要的因素，因?yàn)檩^低的存儲(chǔ)利用率會(huì)導(dǎo)致更頻繁的垃圾回收[6].為了研究每種閃存轉(zhuǎn)換層算法的存儲(chǔ)利用率的影響，統(tǒng)計(jì)了每個(gè)U-block已寫頁的數(shù)量（當(dāng)一個(gè)塊被選為垃圾回收的目標(biāo)塊時(shí)）.圖2顯示了PC場(chǎng)景下統(tǒng)計(jì)的累積分布（CDF）.

圖2 PC場(chǎng)景下統(tǒng)計(jì)的累積分布（CDF）

圖2顯示了大部分的目標(biāo)塊，或已滿了或只占用不到4頁.因?yàn)榇髩KNAND閃存物理塊有64頁，圖中的數(shù)值顯示的都是已寫頁塊所占的百分比.在日志塊機(jī)制下，當(dāng)它們被選作垃圾回收的目標(biāo)塊時(shí)，大約65%的塊是完全被使用的.如預(yù)期一致，由于提高了共享的程度，與日志塊機(jī)制相比FAST顯示了更好的存儲(chǔ)利用率.FAST下完全使用塊百分比上升到了75%.

完全使用塊所占百分比在塊機(jī)制下大約為85%，明顯比FAST利用率更高.因?yàn)镕AST中U-block是被所有的邏輯塊共享的，而在塊機(jī)制中這些是只在同一塊中的邏輯塊間共享的.測(cè)試顯示這是由于FAST算法中的一個(gè)缺點(diǎn)造成的.FAST使用順序的日志塊以優(yōu)化順序?qū)?，不像其他隨機(jī)日志塊，這種順序日志塊是被分配給特定的邏輯塊，這與日志塊機(jī)制相同[7].如果基于順序操作的預(yù)測(cè)錯(cuò)了，順序日志塊會(huì)被合并即使沒有寫滿.塊機(jī)制不會(huì)有這樣的問題，因?yàn)橐粋€(gè)塊中若干相鄰邏輯塊總是共享一個(gè)U-block.因此，可以看到所介紹的塊機(jī)制是利用塊級(jí)別空間局限性更加有效和更加健全的方法.

圖3根據(jù)完全合并、部分合并和交換合并操作類型詳細(xì)對(duì)比了擦除操作的執(zhí)行時(shí)間.

圖3 不同類型合并操作對(duì)比擦除操作的執(zhí)行時(shí)間

通過圖3可以發(fā)現(xiàn)，與FAST機(jī)制相比塊機(jī)制中72%以上的擦除操作是由于交換合并.這是因?yàn)橐环矫?，塊機(jī)制在多個(gè)邏輯塊之間共享D-block和U-block，且同時(shí)使用out-of-place機(jī)制來管理所有的物理塊，提高了交換合并的幾率.另一方面，由于完全合并造成的擦除操作數(shù)量顯著減少.當(dāng)U-block中的頁不是順序的，日志塊機(jī)制和FAST需要完全合并操作以滿足in-place機(jī)制維護(hù)D-block.然而，塊機(jī)制可以轉(zhuǎn)換U-block為一個(gè)新的D-block，很簡(jiǎn)單將一個(gè)完全合并轉(zhuǎn)化為交換合并.

2.2 緩存大小的影響

圖4顯示了緩存條目從16到1 024緩存命中率的變化.注意最小緩存大小下對(duì)于所有類型請(qǐng)求緩存命中率高于93%.這顯示了測(cè)試中很高的塊級(jí)別的時(shí)間局部性及頁級(jí)別的空間局部性.

緩存條目從16到1 024，命中率只最多提高了1.2%.因此16個(gè)緩存條目在多數(shù)情況下已經(jīng)足夠.

圖4 緩存條目從16到1024緩存命中率的變化

3 結(jié)語

針對(duì)大塊NAND閃存存儲(chǔ)器只能先擦后寫的局限，研究基于塊映射的閃存轉(zhuǎn)換層進(jìn)行改進(jìn)，仍然使用原有塊映射技術(shù)，但是允許塊中的邏輯頁自由映射到任一分配的物理塊.這種混合映射技術(shù)具有細(xì)顆粒度地址映射的靈活性，同時(shí)將空間消耗降低到粗顆粒度映射級(jí)別.通過與原有技術(shù)進(jìn)行性能對(duì)比，實(shí)驗(yàn)表明，優(yōu)化的算法不僅降低了垃圾回收的的次數(shù)，而且提高了交換合并的幾率用以取代代價(jià)很大的完全合并.

[1]互動(dòng)百科.NAND閃存[EB/OL].(2010-02-03)[2014-07-22].http: //www.baike.com/wiki/NAND%E9%97%AA%E5%AD%98.

[2]唐衛(wèi)明.大容量NAND閃存存儲(chǔ)管理研究[D].長沙：國防科學(xué)技術(shù)大學(xué),2009.

[3]劉芳，劉志龍，肖儂，等.一種基于數(shù)據(jù)壓縮的高效閃存轉(zhuǎn)換層設(shè)計(jì)[J].計(jì)算機(jī)研究與發(fā)展,2011(S1):317-321.

[4]Park C,Cheon W,Kang J,etal.A reconfigurable FTL(flash translation layer)architecture for NAND flash-based applications[J]. ACM Transactions on Embedded Computing Systems(TECS). 2008,7(4),Article38.

[5]郁志平，劉偉，彭虎,等.一種混合映射閃存轉(zhuǎn)換層的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程,2014(2):300-303.

[6]趙培.閃存的存儲(chǔ)管理及索引方法研究[D].武漢：華中科技大學(xué),2011.

[7]Leventhal A.Flash storage memory[J].Communications of the ACM,2008,51(7):41-57.

【編校：王露】

Optim ization Design for the Conversion of Bulk NAND Flash Layer

QIN Xiao'an
(Department of Electronic Information Engineering,Anhui Business College of Vocational Technology,Wuhu,Anhui 241002,China)

Based on thebasic principleofbulk NAND flash translation layer,taking into consideration the block of data in flashmemory and physicalupdate block,using themethod ofmixedmapping address,the logicalblock numberand page numberwere split to distinguish popular page ofdata block from unpopular ones;using optimization algorithm to come up with the optimized solution based on its idle degree so as to decidewhether to improve partly or totally,or exchange data. Performance analysiswas carried out through the experimentof storage utilization and cache size influence,which shows that the algorithm can effectively improve theefficiency ofNAND flashmemory.

NAND flashmemory;flash translation layer;addressmapping;garbage collection

TP301.6

A

1671-5365(2014)12-0099-03

2014-07-24修回：2014-08-14

秦曉安(1982-)，男，講師，碩士，研究方向?yàn)榍度胧?、程序算?/p>

時(shí)間：2014-08-22 15:23

http://www.cnki.net/kcms/detail/51.1630.Z.20140822.1523.002.htm l