0 引言

    隨著半導體技術(shù)的進步，NAND型閃存(Flash Memory)容量越來越大，價格也卻越來越便宜，固態(tài)硬盤SSD在越來越多的領(lǐng)域取代以磁帶為媒介的傳統(tǒng)機械硬盤(HDD)。與傳統(tǒng)機械硬盤相比，固態(tài)盤因無伺服尋址、盤片旋轉(zhuǎn)和剩磁的影響而具有較高的帶寬、低能耗、抗震性和數(shù)據(jù)的完全可刪除性的特點而成為研究熱點^[1，2]。并且固態(tài)硬盤具有更快的數(shù)據(jù)處理速度，更高的可靠性和耐用性^[3，4]。固態(tài)硬盤的存儲器件采用的是閃存^[5]，具有以下幾個特點：

    (1)讀寫基本單位是以頁（Page）為單位，擦除是以塊（Block）為單位。

    (2)每個物理塊，必須先擦除，才能夠?qū)懭霐?shù)據(jù)。

    (3)每個塊有一定的壽命，即擦除次數(shù)是有限的。

    基于這些問題，在固態(tài)硬盤中引入了閃存轉(zhuǎn)換層FTL^[6]。它包括數(shù)據(jù)映射、垃圾回收、損耗均衡、數(shù)據(jù)緩存等問題。FTL算法，特別是閃存映射表FMT(Flash Mapping Table)，是影響固態(tài)硬盤性能高低的關(guān)鍵。傳統(tǒng)的數(shù)據(jù)映射方式采用頁映射，隨著閃存頁面的增大，頁映射在隨機讀寫上速度的不足顯現(xiàn)出來。本文提出一種以4 KB數(shù)據(jù)塊為單元做映射的算法(以下簡稱4 KB映射算法)來改善隨機讀寫的速度，并通過測試驗證該算法的有效性。

1 FTL及頁映射

    FTL位于文件系統(tǒng)和物理介質(zhì)之間，把Flash的操作習慣虛擬成以傳統(tǒng)硬盤的512 B扇區(qū)進行操作。操作系統(tǒng)就可以按照傳統(tǒng)的扇區(qū)方式操作，而不用擔心之前說的擦除/讀/寫問題。一切邏輯到物理的轉(zhuǎn)換，都由FTL來完成。

    頁映射是將邏輯頁映射到Flash中的任何一個物理頁。該映射算法在物理頁不大于4 KB時性能最好。但是隨著Flash物理頁的增大，目前主流基本為16 KB的物理頁，并有擴大到32 KB的趨勢，寫入放大WA(Write Amplification)系數(shù)就會變大，隨著物理頁大小的增大，這種算法的劣勢會越來越大。假設(shè)Page大小為16 KB，每次寫入4 KB，基本需要：

    (1)讀出此Page內(nèi)不需要修改的12 KB；

    (2)尋找新的物理Page寫入完整的16 KB數(shù)據(jù)(包括讀出的12 KB、新寫入的4 KB)。也就是說，寫入4 KB， 實際上寫入16 KB，寫入放大系數(shù)為式(1)：

    考慮到映射表格FMT的更新以及其他管理資源的調(diào)度，實際WA肯定是大于4。顯然，按照這樣簡單的映射方法是無法滿足寫入速度的要求，同時，也大大消耗了閃存的“壽命”。

2 基于4 KB數(shù)據(jù)塊映射的FTL設(shè)計

2.1 4 KB數(shù)據(jù)塊映射算法

    根據(jù)隨機讀寫數(shù)據(jù)的最小單元4 KB，把FTL的最小管理單元也適應性地調(diào)整為4 KB數(shù)據(jù)塊來進行映射和管理?；驹頌椋簛碜灾鳈C的寫入數(shù)據(jù)，每4 KB給予一個地址進行管理，連續(xù)幾個4 KB達到一個完整的閃存Page數(shù)據(jù)量的時候，把它們一次性寫入一個完整的閃存Page。如圖1所示，頁映射一個Page只是寫入了4 KB，剩余的部分用其他數(shù)據(jù)填滿，16 KB的空間只記錄了4 KB有效數(shù)據(jù)，特別當Flash讀寫采用4 KB隨機讀寫(4 KB Random R/W)時，頁映射的劣勢特別明顯，而4 KB映射的寫優(yōu)勢就凸顯出來。理性狀態(tài)下，4 KB映射寫入放大系數(shù)WA=1。這種寫入方法使得隨機寫入速度幾乎接近于連續(xù)數(shù)據(jù)流的寫入，大大提高了隨機寫入的性能。

    當然，上述分析是理想狀態(tài)的，前提是具有無限的空白閃存塊（或者頁）等待著使用。實際上，閃存塊（頁）是有限的，閃存管理需要把一些包含了無效數(shù)據(jù)的塊釋放出來，這就是通常說的垃圾回收“Garbage Collection”，并且要把回收的塊在合適的時機擦除干凈備用。這就會引起映射表的更新（寫），使得WA略大于1。同時，垃圾回收和塊擦除也需要時間，使得隨機寫入速度雖然接近連續(xù)寫入數(shù)據(jù)流，但是真實測試還是只能夠“接近”而不是“等于”或者“超過”。

    基于4 KB為單元的映射，固然大大提高了寫入性能，但在讀取信息的時候，帶來了額外的負擔：

    (1)在16 KB Page的映射情況下，一次映射表的搜索，可以讀取16 KB數(shù)據(jù)，即每16 KB搜索一次閃存映射表。在4 KB為單元的映射下，讀取時候的搜索就變?yōu)槊? KB就要搜索一次。因此，隨機寫性能的增加，一定程度上是以降低隨機讀性能為折中的。只是在硬件性能大大提高的前提下，搜索速度很高，隨機讀速度的降低相比于隨機寫性能的提高和寫入放大系數(shù)WA的降低，這是非常值得的。

    (2)以4 KB為最小單元的映射引起了映射表存儲空間的成倍增大。

    假設(shè)硬盤存儲空間128 GB，每個映射單元的地址表征字節(jié)數(shù)為4，采用4 KB映射，映射表大小為128 MB。由于映射表需在集成電路芯片內(nèi)調(diào)度使用，芯片內(nèi)的緩存一般采用SRAM來實現(xiàn)。超過1 MB大小的SRAM空間對于當前的集成電路芯片需占據(jù)很大的空間，性價比不高?，F(xiàn)實設(shè)計中，采用分段調(diào)度的方式可以解決問題。即把當前需用到的表格部分讀入SRAM，而把其余部分存放在芯片外部空間。芯片外部空間存放的形式有兩種：外部的DRAM（Dynamic Random Access Memory)和閃存（Flash Memory）。

2.2 算法讀寫速度及性能分析

    下面分析隨機寫入4個4 KB的數(shù)據(jù)，F(xiàn)lash的頁大小為16 KB的兩種映射的速度。

    隨機寫入4個4 KB的數(shù)據(jù)時，4 KB映射算法最大寫速度（不更換映射表）見式(3)：

    最小寫速度(每個4 KB都要更換全部的映射表)見式(6)：

    T_p是一個12 KB數(shù)據(jù)的搬移時間，Tr是一個讀的延遲時間(即讀busy)。對比式(3)和式(5)，式(4)和式(6)，得知4 KB映射的寫速度高于頁映射。

    針對128 GB的固態(tài)硬盤，閃存映射表為32 MB，按本文芯片資源給予的8 KB SRAM，具有4 M個“映射表段”(每個8 KB大小)，其中只有一段8 KB映射表段被導入SRAM(稱為“當前內(nèi)存表段”)，可以隨時被搜索查詢。因此，隨機寫入的4個4 KB數(shù)據(jù)，有4種可能性分布對應于落入FMT中：

3 基于4 KB數(shù)據(jù)塊映射算法的芯片架構(gòu)

    固態(tài)硬盤控制器的算法主體最終是以固件形式在固態(tài)硬盤控制器芯片內(nèi)運行的。針對本文的4 KB數(shù)據(jù)塊映射的算法，圖2給出了用來驗證算法的固態(tài)硬盤控制器芯片的結(jié)構(gòu)。該芯片分成兩部分：主監(jiān)處理器模塊(Supervisor Processor Unit，SPU)和閃存通道控制器(Channel Processor，CHP)。

    SPU模塊包括32位CPU、SATA接口模塊、相應的數(shù)據(jù)緩存和芯片的周邊接口。這里特別需要SPU針對NCQ(Native Command Que)做出高效的處理，這是隨機讀寫性能的又一重點要素。NCQ處理需要配合閃存4 KB映射算法做一些針對性的重新排隊，盡量使連續(xù)4個4 KB數(shù)據(jù)的讀(或?qū)?，不僅數(shù)據(jù)流方向一致，而且最好落在同一個映射表段內(nèi)，即2.2表述的情形(1)，提高情形(1)的概率對于算法是最有利的。此款控制器芯片有5個獨立的CHP，提供真正的5路并行處理能力。每個CHP模塊包括一個8位的RISC CPU、DMA(Direct Memory Access)、數(shù)據(jù)緩存和閃存總線控制。數(shù)據(jù)緩存區(qū)采用16 K Buffer和8 K FIFO，由于FMT占據(jù)空間較大，采用分段調(diào)度調(diào)用FMT表，而每次調(diào)表的大小和SRAM的大小有關(guān)，SRAM內(nèi)存越大，能夠調(diào)用的映射表段越大，那么映射表段的數(shù)量會越少，根據(jù)2.2內(nèi)表述的情形(1)，表段越少，相應落入同一個映射表的概率就會增大，這也是提高算法的一個有利因素。

4 實驗結(jié)果

    基于算法思路和芯片架構(gòu)，本文實現(xiàn)了一顆固態(tài)硬盤控制器芯片的設(shè)計。該芯片采用110 nm工藝，已在8英寸硅片上實現(xiàn)了批量生產(chǎn)。芯片尺寸3.908 mm×3.746 mm，SATA PHY為高速模擬電路，具有3 Gb/s的數(shù)據(jù)傳輸速率。映射表存儲采用SRAM實現(xiàn)。片上集成的電源管理電路，把5 V電源轉(zhuǎn)換成I/O電路和閃存芯片需要的3.3 V電壓，也產(chǎn)生芯片內(nèi)部需要的1.2 V電源。

    為檢驗本文的算法的效果，采用市場上M公司的兩個NAND閃存型號來進行測試和比較，其中一個閃存Page Size為8 KB，另一個閃存為16 KB，出自同系列產(chǎn)品，其余參數(shù)基本一致，如讀取等待時間為75 μs，編程(寫入)等待時間1 300 μs。通過測速軟件來測試這兩款Flash使用頁映射和4 KB映射的隨機傳輸4 KB數(shù)據(jù)的寫速度，如表1所示?？梢钥闯觯簾o論頁面大小是8 KB還是16 KB，4 KB映射的平均速度明顯比頁映射的速度快,并且頁面越大，4 KB映射的速度與頁映射的速度差距增大。

5 結(jié)論

    本文提出了一種基于4 KB數(shù)據(jù)塊映射的FTL算法，并證明了基于4 KB數(shù)據(jù)塊大小的映射可以有效提高隨機讀寫速度，尤其是針對算法構(gòu)建了一顆固態(tài)硬盤芯片，通過真正的芯片實體驗證了理論分析。本課題組還將進一步研究，包括SATA-III速度匹配的電路結(jié)構(gòu)、如何以有限的片上存儲空間來實現(xiàn)越來越大的映射表，以及針對大數(shù)據(jù)存儲要求，處理熱數(shù)據(jù)和冷數(shù)據(jù)對于固態(tài)硬盤存儲的差異性。

參考文獻

[1] LAURA M G，ADRIAN M C，JOEL C，et al.Characterizing flash memory anmomalies，observations and applications[C]//Proceedings of 42nd annual IEEE/ACM international Symposium on Micro-achiteture，2009：24-33.

[2] TANAKAMARU S，DOI M，TAKEUCHI K.NAND flash Memory/ReRAM hybrid unified solid-state-storage architecture[J].IEEE Transactions on Circuits and Systems I：Regular Papers，2014，61(4)：1119-1132.

[3] Huang Jian，AnirudhBadam，Moinuddin K Qureshi，et al.Unified address translation for memory-mapped SSDs with Flash Map[C]//Proceedings of the 42nd Annual International Symposium on Computer Architecture(ISCA).ACM，2015.

[4] Xia Qianbin，Xiao Weijun.Flash-aware high performance and endurable cache[C]//In 23rd IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems(MASCOTS)，2015.

[5] IAN S.Osborne.Flash Memory[J].Science，2000，289(5477)：217.

[6] Lee Sang-Won，Park Dong-Joo，Chung Tae-Sun，et al.A log buffer-based flash translation layer using fully-associative sector translation[J].ACM Transactions on Embedded Computing Systems，2007，6(3)：1-27.

作者信息:

駱建軍1，陳艷芬1，方立春1，Chris Tsu2

（1．杭州電子科技大學，浙江 杭州310018；2.Sage Microelectronics Corp，California 95008）