文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2017.04.009
中文引用格式： 駱建軍，陳艷芬，方立春，等. 基于4 KB數(shù)據(jù)塊映射的固態(tài)硬盤算法[J].電子技術(shù)應(yīng)用，2017，43(4)：36-38，42.
英文引用格式： Luo Jianjun，Chen Yanfen，F(xiàn)ang Lichun，et al. A solid-state drive controller design based on 4 KB-size flash translation layer[J].Application of Electronic Technique，2017，43(4)：36-38，42.
0 引言
隨著半導(dǎo)體技術(shù)的進(jìn)步，NAND型閃存(Flash Memory)容量越來(lái)越大，價(jià)格也卻越來(lái)越便宜，固態(tài)硬盤SSD在越來(lái)越多的領(lǐng)域取代以磁帶為媒介的傳統(tǒng)機(jī)械硬盤(HDD)。與傳統(tǒng)機(jī)械硬盤相比，固態(tài)盤因無(wú)伺服尋址、盤片旋轉(zhuǎn)和剩磁的影響而具有較高的帶寬、低能耗、抗震性和數(shù)據(jù)的完全可刪除性的特點(diǎn)而成為研究熱點(diǎn)[1，2]。并且固態(tài)硬盤具有更快的數(shù)據(jù)處理速度，更高的可靠性和耐用性[3，4]。固態(tài)硬盤的存儲(chǔ)器件采用的是閃存[5]，具有以下幾個(gè)特點(diǎn)：
(1)讀寫基本單位是以頁(yè)（Page）為單位，擦除是以塊（Block）為單位。
(2)每個(gè)物理塊，必須先擦除，才能夠?qū)懭霐?shù)據(jù)。
(3)每個(gè)塊有一定的壽命，即擦除次數(shù)是有限的。
基于這些問(wèn)題，在固態(tài)硬盤中引入了閃存轉(zhuǎn)換層FTL[6]。它包括數(shù)據(jù)映射、垃圾回收、損耗均衡、數(shù)據(jù)緩存等問(wèn)題。FTL算法，特別是閃存映射表FMT(Flash Mapping Table)，是影響固態(tài)硬盤性能高低的關(guān)鍵。傳統(tǒng)的數(shù)據(jù)映射方式采用頁(yè)映射，隨著閃存頁(yè)面的增大，頁(yè)映射在隨機(jī)讀寫上速度的不足顯現(xiàn)出來(lái)。本文提出一種以4 KB數(shù)據(jù)塊為單元做映射的算法(以下簡(jiǎn)稱4 KB映射算法)來(lái)改善隨機(jī)讀寫的速度，并通過(guò)測(cè)試驗(yàn)證該算法的有效性。
1 FTL及頁(yè)映射
FTL位于文件系統(tǒng)和物理介質(zhì)之間，把Flash的操作習(xí)慣虛擬成以傳統(tǒng)硬盤的512 B扇區(qū)進(jìn)行操作。操作系統(tǒng)就可以按照傳統(tǒng)的扇區(qū)方式操作，而不用擔(dān)心之前說(shuō)的擦除/讀/寫問(wèn)題。一切邏輯到物理的轉(zhuǎn)換，都由FTL來(lái)完成。
頁(yè)映射是將邏輯頁(yè)映射到Flash中的任何一個(gè)物理頁(yè)。該映射算法在物理頁(yè)不大于4 KB時(shí)性能最好。但是隨著Flash物理頁(yè)的增大，目前主流基本為16 KB的物理頁(yè)，并有擴(kuò)大到32 KB的趨勢(shì)，寫入放大WA(Write Amplification)系數(shù)就會(huì)變大，隨著物理頁(yè)大小的增大，這種算法的劣勢(shì)會(huì)越來(lái)越大。假設(shè)Page大小為16 KB，每次寫入4 KB，基本需要：
(1)讀出此Page內(nèi)不需要修改的12 KB；
(2)尋找新的物理Page寫入完整的16 KB數(shù)據(jù)(包括讀出的12 KB、新寫入的4 KB)。也就是說(shuō)，寫入4 KB， 實(shí)際上寫入16 KB，寫入放大系數(shù)為式(1)：
考慮到映射表格FMT的更新以及其他管理資源的調(diào)度，實(shí)際WA肯定是大于4。顯然，按照這樣簡(jiǎn)單的映射方法是無(wú)法滿足寫入速度的要求，同時(shí)，也大大消耗了閃存的“壽命”。
2 基于4 KB數(shù)據(jù)塊映射的FTL設(shè)計(jì)
2.1 4 KB數(shù)據(jù)塊映射算法
根據(jù)隨機(jī)讀寫數(shù)據(jù)的最小單元4 KB，把FTL的最小管理單元也適應(yīng)性地調(diào)整為4 KB數(shù)據(jù)塊來(lái)進(jìn)行映射和管理?；驹頌椋簛?lái)自主機(jī)的寫入數(shù)據(jù)，每4 KB給予一個(gè)地址進(jìn)行管理，連續(xù)幾個(gè)4 KB達(dá)到一個(gè)完整的閃存Page數(shù)據(jù)量的時(shí)候，把它們一次性寫入一個(gè)完整的閃存Page。如圖1所示，頁(yè)映射一個(gè)Page只是寫入了4 KB，剩余的部分用其他數(shù)據(jù)填滿，16 KB的空間只記錄了4 KB有效數(shù)據(jù)，特別當(dāng)Flash讀寫采用4 KB隨機(jī)讀寫(4 KB Random R/W)時(shí)，頁(yè)映射的劣勢(shì)特別明顯，而4 KB映射的寫優(yōu)勢(shì)就凸顯出來(lái)。理性狀態(tài)下，4 KB映射寫入放大系數(shù)WA=1。這種寫入方法使得隨機(jī)寫入速度幾乎接近于連續(xù)數(shù)據(jù)流的寫入，大大提高了隨機(jī)寫入的性能。
當(dāng)然，上述分析是理想狀態(tài)的，前提是具有無(wú)限的空白閃存塊（或者頁(yè)）等待著使用。實(shí)際上，閃存塊（頁(yè)）是有限的，閃存管理需要把一些包含了無(wú)效數(shù)據(jù)的塊釋放出來(lái)，這就是通常說(shuō)的垃圾回收“Garbage Collection”，并且要把回收的塊在合適的時(shí)機(jī)擦除干凈備用。這就會(huì)引起映射表的更新（寫），使得WA略大于1。同時(shí)，垃圾回收和塊擦除也需要時(shí)間，使得隨機(jī)寫入速度雖然接近連續(xù)寫入數(shù)據(jù)流，但是真實(shí)測(cè)試還是只能夠“接近”而不是“等于”或者“超過(guò)”。
基于4 KB為單元的映射，固然大大提高了寫入性能，但在讀取信息的時(shí)候，帶來(lái)了額外的負(fù)擔(dān)：
(1)在16 KB Page的映射情況下，一次映射表的搜索，可以讀取16 KB數(shù)據(jù)，即每16 KB搜索一次閃存映射表。在4 KB為單元的映射下，讀取時(shí)候的搜索就變?yōu)槊? KB就要搜索一次。因此，隨機(jī)寫性能的增加，一定程度上是以降低隨機(jī)讀性能為折中的。只是在硬件性能大大提高的前提下，搜索速度很高，隨機(jī)讀速度的降低相比于隨機(jī)寫性能的提高和寫入放大系數(shù)WA的降低，這是非常值得的。
(2)以4 KB為最小單元的映射引起了映射表存儲(chǔ)空間的成倍增大。
假設(shè)硬盤存儲(chǔ)空間128 GB，每個(gè)映射單元的地址表征字節(jié)數(shù)為4，采用4 KB映射，映射表大小為128 MB。由于映射表需在集成電路芯片內(nèi)調(diào)度使用，芯片內(nèi)的緩存一般采用SRAM來(lái)實(shí)現(xiàn)。超過(guò)1 MB大小的SRAM空間對(duì)于當(dāng)前的集成電路芯片需占據(jù)很大的空間，性價(jià)比不高?，F(xiàn)實(shí)設(shè)計(jì)中，采用分段調(diào)度的方式可以解決問(wèn)題。即把當(dāng)前需用到的表格部分讀入SRAM，而把其余部分存放在芯片外部空間。芯片外部空間存放的形式有兩種：外部的DRAM（Dynamic Random Access Memory)和閃存（Flash Memory）。
2.2 算法讀寫速度及性能分析
下面分析隨機(jī)寫入4個(gè)4 KB的數(shù)據(jù)，F(xiàn)lash的頁(yè)大小為16 KB的兩種映射的速度。
隨機(jī)寫入4個(gè)4 KB的數(shù)據(jù)時(shí)，4 KB映射算法最大寫速度（不更換映射表）見式(3)：
最小寫速度(每個(gè)4 KB都要更換全部的映射表)見式(6)：
Tp是一個(gè)12 KB數(shù)據(jù)的搬移時(shí)間，Tr是一個(gè)讀的延遲時(shí)間(即讀busy)。對(duì)比式(3)和式(5)，式(4)和式(6)，得知4 KB映射的寫速度高于頁(yè)映射。
針對(duì)128 GB的固態(tài)硬盤，閃存映射表為32 MB，按本文芯片資源給予的8 KB SRAM，具有4 M個(gè)“映射表段”(每個(gè)8 KB大小)，其中只有一段8 KB映射表段被導(dǎo)入SRAM(稱為“當(dāng)前內(nèi)存表段”)，可以隨時(shí)被搜索查詢。因此，隨機(jī)寫入的4個(gè)4 KB數(shù)據(jù)，有4種可能性分布對(duì)應(yīng)于落入FMT中：
3 基于4 KB數(shù)據(jù)塊映射算法的芯片架構(gòu)
固態(tài)硬盤控制器的算法主體最終是以固件形式在固態(tài)硬盤控制器芯片內(nèi)運(yùn)行的。針對(duì)本文的4 KB數(shù)據(jù)塊映射的算法，圖2給出了用來(lái)驗(yàn)證算法的固態(tài)硬盤控制器芯片的結(jié)構(gòu)。該芯片分成兩部分：主監(jiān)處理器模塊(Supervisor Processor Unit，SPU)和閃存通道控制器(Channel Processor，CHP)。
SPU模塊包括32位CPU、SATA接口模塊、相應(yīng)的數(shù)據(jù)緩存和芯片的周邊接口。這里特別需要SPU針對(duì)NCQ(Native Command Que)做出高效的處理，這是隨機(jī)讀寫性能的又一重點(diǎn)要素。NCQ處理需要配合閃存4 KB映射算法做一些針對(duì)性的重新排隊(duì)，盡量使連續(xù)4個(gè)4 KB數(shù)據(jù)的讀(或?qū)?，不僅數(shù)據(jù)流方向一致，而且最好落在同一個(gè)映射表段內(nèi)，即2.2表述的情形(1)，提高情形(1)的概率對(duì)于算法是最有利的。此款控制器芯片有5個(gè)獨(dú)立的CHP，提供真正的5路并行處理能力。每個(gè)CHP模塊包括一個(gè)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ù)量會(huì)越少，根據(jù)2.2內(nèi)表述的情形(1)，表段越少，相應(yīng)落入同一個(gè)映射表的概率就會(huì)增大，這也是提高算法的一個(gè)有利因素。
4 實(shí)驗(yàn)結(jié)果
基于算法思路和芯片架構(gòu)，本文實(shí)現(xiàn)了一顆固態(tài)硬盤控制器芯片的設(shè)計(jì)。該芯片采用110 nm工藝，已在8英寸硅片上實(shí)現(xiàn)了批量生產(chǎn)。芯片尺寸3.908 mm×3.746 mm，SATA PHY為高速模擬電路，具有3 Gb/s的數(shù)據(jù)傳輸速率。映射表存儲(chǔ)采用SRAM實(shí)現(xiàn)。片上集成的電源管理電路，把5 V電源轉(zhuǎn)換成I/O電路和閃存芯片需要的3.3 V電壓，也產(chǎn)生芯片內(nèi)部需要的1.2 V電源。
為檢驗(yàn)本文的算法的效果，采用市場(chǎng)上M公司的兩個(gè)NAND閃存型號(hào)來(lái)進(jìn)行測(cè)試和比較，其中一個(gè)閃存Page Size為8 KB，另一個(gè)閃存為16 KB，出自同系列產(chǎn)品，其余參數(shù)基本一致，如讀取等待時(shí)間為75 μs，編程(寫入)等待時(shí)間1 300 μs。通過(guò)測(cè)速軟件來(lái)測(cè)試這兩款Flash使用頁(yè)映射和4 KB映射的隨機(jī)傳輸4 KB數(shù)據(jù)的寫速度，如表1所示。可以看出：無(wú)論頁(yè)面大小是8 KB還是16 KB，4 KB映射的平均速度明顯比頁(yè)映射的速度快,并且頁(yè)面越大，4 KB映射的速度與頁(yè)映射的速度差距增大。
5 結(jié)論
本文提出了一種基于4 KB數(shù)據(jù)塊映射的FTL算法，并證明了基于4 KB數(shù)據(jù)塊大小的映射可以有效提高隨機(jī)讀寫速度，尤其是針對(duì)算法構(gòu)建了一顆固態(tài)硬盤芯片，通過(guò)真正的芯片實(shí)體驗(yàn)證了理論分析。本課題組還將進(jìn)一步研究，包括SATA-III速度匹配的電路結(jié)構(gòu)、如何以有限的片上存儲(chǔ)空間來(lái)實(shí)現(xiàn)越來(lái)越大的映射表，以及針對(duì)大數(shù)據(jù)存儲(chǔ)要求，處理熱數(shù)據(jù)和冷數(shù)據(jù)對(duì)于固態(tài)硬盤存儲(chǔ)的差異性。
參考文獻(xiàn)
[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．杭州電子科技大學(xué)，浙江 杭州310018；2.Sage Microelectronics Corp，California 95008）