大塊NAND閃存的轉換層優化算法設計

秦曉安

（安徽商貿職業技術學院電子信息工程系，安徽蕪湖241002）

大塊NAND閃存的轉換層優化算法設計

秦曉安

（安徽商貿職業技術學院電子信息工程系，安徽蕪湖241002）

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

NAND閃存；閃存轉換層；地址映射；垃圾回收

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

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

NAND閃存不同于磁盤或是SRAM和DRAM，與讀操作相比，寫操作需要更長的時間.因為在寫操作之前經常需要先進行擦除操作，所以擦寫操作時間會更長.大塊NAND閃存存儲器的另外一個局限是單位塊的擦寫，極限是大約100 000到1 000 000次，而且必須先擦后寫.因此，本文研究改進的辦法盡可能地減少擦寫操作次數，以提高整體性能和延長大塊NAND閃存的壽命.

1 算法研究

1.1 基本原理

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

隨著NAND閃存存儲容量的增加，頁映射需要更多RAM，這將會導致很嚴重的成本問題.比如，一個4G字節的NAND閃存，頁映射需要8M字節的RAM用來管理映射表，而塊映射只需要128 K字節.所以，一些基于塊映射的閃存轉換層改進機制被廣泛應用于NAND閃存的存儲系統.

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

1.2 算法實現

在垃圾回收過程中，首先挑選擁有最大序號的U-block的D-block為目標塊，將所有的有效頁拷貝到最后一個U-block.接著最后的U-block將成為新的D-block.因為頁總是被合并入最后一個U-block，所以只有部分合并和交換合并操作.替換塊機制存儲空間利用率很差，特別是當塊中只有部分頁被頻繁更新時.且這種機制不適用于大塊NAND閃存，由于塊中的頁無法進行隨機寫操作.

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

塊級別的空間局部性通常存在于，當兩個或者多個相鄰邏輯塊被文件系統分配給同一文件或者一些元數據，如FAT、目錄、i-node或者bitmap.因此，如果幾個相鄰邏輯塊共享一個U-block，U-block的存儲利用率會提高.

U-block被相關的塊用來利用塊級別的時間局部性和空間局部性.一旦U-block被分配給塊，接下來的塊的寫請求被從第一頁開始按順序記錄到U-block中.這種out-of-place機制同樣適用于塊中必須從第一頁到最后一頁順序寫的大塊NAND閃存存儲器.當U-block中沒有空閑頁的時候，新的U-block被分配給塊.

因為大塊NAND閃存存儲器單頁空閑區域的容量限制，整個頁表會被分成4個獨立的PT.PMD的作用就是定位每個PT的最新位置，最新PMD的位置信息被PGD所管理.PGD儲存在主存儲中，而PMD和PT被儲存在空閑區域中.因為PGD的條數等于邏輯塊數，所以PGD的存儲占用與其他塊級別的閃存管理層機制是相當的.

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

圖1 地址映射的過程

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

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

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

當一個邏輯頁被更新，更新后的頁映射信息依然存放在空閑區域中.比如，假如上一段例子中的邏輯頁被更新了，PTE12將指向邏輯頁將要被寫入的位置，第一個PMD條目將指向同樣的物理頁，因為擁有了新的PT0.當頁中被寫入了修改過的PMD和PT0，第二個PGD條目也將被改為指向新的地點.由于更新的PMD和相對應的PT不管何時頁被更新了都被儲存在閃存存儲中，因而可以保證PMD和PT的每個條目始終指向有效頁.

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

2 性能分析

2.1 存儲利用率

存儲利用率是影響閃存轉換層性能的一個很重要的因素，因為較低的存儲利用率會導致更頻繁的垃圾回收[6].為了研究每種閃存轉換層算法的存儲利用率的影響，統計了每個U-block已寫頁的數量（當一個塊被選為垃圾回收的目標塊時）.圖2顯示了PC場景下統計的累積分布（CDF）.

圖2 PC場景下統計的累積分布（CDF）

圖2顯示了大部分的目標塊，或已滿了或只占用不到4頁.因為大塊NAND閃存物理塊有64頁，圖中的數值顯示的都是已寫頁塊所占的百分比.在日志塊機制下，當它們被選作垃圾回收的目標塊時，大約65%的塊是完全被使用的.如預期一致，由于提高了共享的程度，與日志塊機制相比FAST顯示了更好的存儲利用率.FAST下完全使用塊百分比上升到了75%.

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

圖3根據完全合并、部分合并和交換合并操作類型詳細對比了擦除操作的執行時間.

圖3 不同類型合并操作對比擦除操作的執行時間

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

2.2 緩存大小的影響

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

緩存條目從16到1 024，命中率只最多提高了1.2%.因此16個緩存條目在多數情況下已經足夠.

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

3 結語

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

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

[2]唐衛明.大容量NAND閃存存儲管理研究[D].長沙：國防科學技術大學,2009.

[3]劉芳，劉志龍，肖儂，等.一種基于數據壓縮的高效閃存轉換層設計[J].計算機研究與發展,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]郁志平，劉偉，彭虎,等.一種混合映射閃存轉換層的設計與實現[J].計算機工程,2014(2):300-303.

[6]趙培.閃存的存儲管理及索引方法研究[D].武漢：華中科技大學,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-)，男，講師，碩士，研究方向為嵌入式、程序算法

時間：2014-08-22 15:23

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