基於4 KB數據塊映射的固態硬盤算法

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

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

固態硬盤(Solid-State Drive，SSD)採用NAND型閃存(Flash Memory)為主要存儲介質，閃存的讀寫不同於其他介質，需要閃存轉換層(Flash Translation Layer，FTL)對閃存的存儲空間進行管理。傳統方式的映射算法隨著頁面(Page-size)的逐漸擴大，在隨機數據塊寫入的速度方面難以提升。針對這個問題，提出一種基於4 KB數據塊映射的閃存轉換層算法，固態硬盤控制器芯片採用110 nm工藝實現，集成了SATA-II接口(3 Gb/s數據傳輸速率)，最大可以並行驅動5通道的閃存芯片。該算法結合芯片的內部資源，經過了可靠性檢測，達到了預期的可靠性和讀寫速度。

閃存(Flash Memory)；固態硬盤(SSD)；閃存轉化層(FTL)

中圖分類號：TP391.41

文獻標識碼：A

DOI：10.16157/j.issn.0258-7998.2017.04.009

中文引用格式：駱建軍，陳豔芬，方立春，等. 基於4 KB數據塊映射的固態硬盤算法[J].電子技術應用，2017，43(4)：36-38，42.

英文引用格式：Luo Jianjun，Chen Yanfen，Fang 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 引言

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

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

(2)每個物理塊，必須先擦除，才能夠寫入數據。

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

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

1 FTL及頁映射

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

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

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

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

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

2 基於4 KB數據塊映射的FTL設計

2.1 4 KB數據塊映射算法

根據隨機讀寫數據的最小單元4 KB，把FTL的最小管理單元也適應性地調整為4 KB數據塊來進行映射和管理。基本原理為：來自主機的寫入數據，每4 KB給予一個地址進行管理，連續幾個4 KB達到一個完整的閃存Page數據量的時候，把它們一次性寫入一個完整的閃存Page。如圖1所示，頁映射一個Page只是寫入了4 KB，剩餘的部分用其他數據填滿，16 KB的空間只記錄了4 KB有效數據，特別當Flash讀寫採用4 KB隨機讀寫(4 KB Random R/W)時，頁映射的劣勢特別明顯，而4 KB映射的寫優勢就凸顯出來。理性狀態下，4 KB映射寫入放大係數WA=1。這種寫入方法使得隨機寫入速度幾乎接近於連續數據流的寫入，大大提高了隨機寫入的性能。

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

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

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

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

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

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

下面分析隨機寫入4個4 KB的數據，Flash的頁大小為16 KB的兩種映射的速度。

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

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

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

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

3 基於4 KB數據塊映射算法的芯片架構

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

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

4 實驗結果

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

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

5 結論

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

參考文獻

[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.