固態硬盤SSD內部管理算法研究綜述

巴書法

摘要：固態硬盤英文縮寫SSD（Solid State Drive）是一種以閃存（NAND Flash）為存儲介質的存儲設備。作為SSD核心技術之一，控制器內部管理算法FTL（Flash Translation Layer）負責地址映射，壞塊管理，垃圾回收，磨損均衡等關鍵功能，管理算法的優劣直接影響SSD的性能和壽命。近年來，隨著閃存（NAND Flash）技術的不斷發展，FTL的算法也在不斷演進，根據映射表的特點，將其劃分頁（Page）映射算法、塊（Block）映射算法和頁塊混合映射算法。根據邏輯區域劃分，可分為分區映射和全區映射，同時冷熱數據分類存儲也成為FTL的一個重要功能。該文介紹了近年來具有代表性的研究成果，并對于各類算法的優缺點以及在適配3D NAND所遇到的問題進行綜述。為進一步設計更加完善的FTL算法提供指南。

關鍵詞：固態存儲; 閃存;冷熱數據;地址映射; 垃圾回收; 磨損均衡

固態硬盤（SSD）是由控制器和閃存芯片（NAND）組成，利用閃存的區塊存儲特點進行讀寫操作，其憑借多項優點，如：響應快、帶寬高、功耗低、工作溫寬大，抗震性強，輕便等，廣泛應用于數據中心，個人電腦，工控機，汽車電子，物聯網等設備。隨著超過100層3D NAND閃存的量產，SSD的容量變得越來越大，其單GB成本逐年降低，配合高速的SATA/PCIe接口，其性價比日益突出，SSD替代傳統機械硬盤的趨勢正在加速。

FTL是 SSD控制器的核心控制算法，其主要任務是管理邏輯地址到物理地址的映射，其次它還負責分離冷熱數據，垃圾回收和磨損均衡等重要功能。由于閃存的操作方式為頁（Page）寫入，塊（Block）擦除，在未擦除之前不允許覆蓋寫入，所以當SSD接受到主機的寫入命令時，FTL負責將邏輯地址映射到對應的物理地址，并將用戶數據寫入到NAND閃存的有效頁上，當NAND閃存完成編程（Program）后， FTL負責更新邏輯地址到物理地址的映射表。通過這種方式，SSD就能準確記錄所有用戶數據的準確物理位置。

FTL設計的合理性直接影響著SSD的性能和壽命，隨著NAND制程以及SSD控制器硬件的不斷改進，FTL的設計也在不斷演進。本文對近年來FTL的主要研究結果以及經典FTL算法進行梳理，歸納，并對比各自的優缺點，同時結合3D NAND的最新特性，對設計下一代FTL所面臨的問題進行分析與表述。

1 SSD相關基礎理論知識

SSD是由控制器和一組NAND閃存芯片組成，其中控制器負責運行FTL，其為SSD的核心部件，內部由一個或者多個微處理器，NAND 閃存控制單元，ECC加解密模塊以及負責數據傳輸的DMA組成，控制器通常支持多個通道并通過ONFI接口與外部的NAND閃存連接。

1.1閃存顆粒（NAND Flash）

1.1.1 NAND閃存的基本知識

閃存（NAND）是固態硬盤的主要存儲介質，1989年首先由東芝提出NAND閃存的基礎構架，它的基本存儲單元為稱為Cell。Cell是在晶閘管（MOSFET）的結構上添加了一層浮柵極用來捕獲電子用來實現數據的存儲。下圖為NAND的Cell的結構和MOSFET的區別：

NAND閃存在寫入數據的時候，通過往NAND的Cell單元注入不同數量的電荷量，Cell的導通的閾值電壓Vt也會隨之發生變化。通過這些不同Vt電壓，就可以表示不同的數據。通俗的說，比如注入1庫倫電荷之后電壓為Vt=1V，充入2庫倫的電荷之后電壓為Vt=2V，充入3庫倫的電荷之后電壓為Vt=3V，充入4庫倫的電荷之后電壓為Vt=4V，我們就可以用1V表示00b，2V表示01b，3V表示10b，4V表示11b。NAND擦除的時候通過施加反向電壓，將F/G中的捕獲的電荷釋放出去。

不同類型的NAND，其Cell單元存儲比特數也不同，分為：

SLC NAND：一個Cell表示一個比特。

MLC NAND：一個Cell表示兩個比特。

TLC NAND：一個Cell表示三個比特。

QLC NAND：一個Cell表示四個比特。

SLC NAND具有寫入速度快，數據保持力強等優點，但容量比較低且價格比較高，一般適用于工業，航天，軍工等特殊領域。MLC和TLC具有容量大，價格便宜，所以廣泛應用于消費級固態存儲設備上。隨著NAND技術的不斷進步，QLC NAND憑借其超大容量和極低的價格，逐漸在消費級產品被采用。

1.1.2 NAND閃存塊組織結構和特點

NAND閃存的基本寫入單位為頁，每一個頁由數據區（Data area）和冗余區（Spare area）組成，冗余區也叫做OOB（Out of Band）區域，它用來存儲關鍵的元數據，數據區用來存儲用戶數據或者管理數據，設備在復位重新啟動后，SSD固件會掃描元數據區域用來重建映射表或者恢復內部管理結構。元數據的存儲通常分為緊鄰存儲和分立存儲兩種。NAND閃存的基本擦出單位為塊（Block），一個物理塊有多個頁組成，通常為256，512或者1024個頁。NAND閃存采用塊擦除，頁寫入策略。為了提高NAND的并行操作速度，NAND通常都會將塊分成不同的組，稱為Plane。多個Plane能同時進行讀寫擦操作。

NAND操作具有以下特點：

①寫入單位為頁，在塊擦除之前不能進行重復寫操作。

②塊內必須按照頁順序寫入，不能跳躍寫入。

③擦除單位為塊，塊擦除會清空塊內所有頁的數據。

④隨著塊擦寫次數的增加，數據保持能力會大大降低。

1.2固件地址映射算法

FTL最重要的工作就是完成邏輯地址到物理地址的映射。按照映射的粒度分類可以歸為三類：

塊（Block）映射算法：FTL的映射粒度為閃存的物理塊，采用塊映射算法最大的優點就是RAM占用量極低，同時擁有良好的順序讀寫速度。它最大的缺點就是隨機性能差，較高的寫放大系數以及較低的垃圾回收效率。隨著閃存的發展，物理塊變得越來越大，現在單純使用塊映射的FTL如文獻[1]已經很少采用。

頁（Page）映射算法：FTL的映射粒度為頁，此處的頁大小可以為NAND的物理頁大小的，也可以是4KB的數據單元。采用頁映射的FTL需要為每一個頁維護一條邏輯地址到物理地址的記錄，比如采用4KB頁映射，每一個4KB頁需要4字節來記錄邏輯位置到物理位置的映射。頁映射算法具有良好的隨機讀寫性能以及較低的寫放大系數（WAF），缺點是內存占用量大。經典的采用頁映射的FTL算法如文獻[2][3]。

頁塊（Page/Block）混合映射算法：頁塊混合映射FTL將NAND物理塊分成兩個區域，數據區和緩存區，數據區采用塊映射算法以減少映射表內存使用量，緩沖區采用頁映射算法，它用來保存隨機數據或者熱數據。混合映射算法最大的優點就是具有良好的性能以及適中的內存使用率。但由于如果系統存在大量的隨機寫入，垃圾回收的效率會大大降低。文獻[4][5]為典型的混合映射FTL算法。

2 經典FTL算法研究

本章將介紹幾種FTL的經典算法，并分析各個算法的優缺點，為后續的研究打下基礎。

2.1塊映射的算法

Ban在文獻[1]首先提出了針對NAND閃存設計的基于塊的映射算法NFTL。它的基本思想是將磁盤的邏輯空間分成若干個邏輯塊，每一個邏輯塊映射到至少一個物理塊，其中一個物理塊稱為主塊（Primary Block），在主塊中邏輯頁在邏輯塊中的偏移量跟物理頁在物理塊的偏移量相同，如果主機寫入的邏輯地址之前已經寫過，NFTL會重新申請一個物理塊來保存新的數據，這個物理塊叫做替換塊（Replacement Block），替換塊中的映射關系記錄在替換塊Page的OOB區域。這種映射算法只需要很少的RAM使用量來記錄塊映射關系。

上圖是主機寫入以下數據后的示意圖：

LPN0～LPN5：A0～A5

LPN4：E1

LPN5：B1

塊映射算法的優缺點如下：

優點：

①需要極少的RAM來保存塊映射關系。

②算法實現簡單，順序讀寫性能突出。

缺點：

①隨機讀寫效率低，性能差。

②讀取性能差，最差情況需要掃描整個替換塊。

③垃圾回收過多的Merge操作，導致寫放大系數增大，NAND物理塊損耗過快。

2.2頁塊的混合映射的算法

為了提高塊映射算法的隨機讀寫性能，并減少垃圾回收損耗。Kim提出了塊頁混合算法BAST文獻[4]。Kim在塊映射的基礎上，增加了一個Log Buffer用來存儲主機的寫入數據， Log Buffer由固定數目的物理塊組成，并使用頁映射表來管理Log Buffer，為了加快讀速度，BAST將頁映射關系存儲到RAM中。為了減少RAM的使用量BAST用塊映射表來管理數據塊。每一個邏輯塊最多對應一個數據塊和一個Log Buffer塊。

當主機寫入數據時BAST會根據要寫入的LBA首先計算出其邏輯塊號LBN，如果邏輯塊有對應的Log Block，則將其寫入到Log Block中，如果沒有Log Block， BAST從Free Block中取出一個塊作為Log Block，并將數據從頁0開始寫入到Log Block中。如果Log Block被寫滿或者Free Block Pool中的空閑塊不足，則需要啟動垃圾回收來釋放被占用的物理塊。垃圾回收將Data Blocks 和 Log Blocks的有效數據進行組合寫入到一個新的Block中， 這個目標Block會轉換為新的Data Block， 同時舊的Data Block和Log Block會被擦除放入到Free Block Pool。這在BAST稱謂Merge操作。在隨機寫操作比較頻繁的應用場景，會導致Log Block消耗過快，而且垃圾回收機制強迫進行Merge操作，導致Log Block空間利用率不足，嚴重影響系統的性能。為了解決這個問題，S.-W. Lee提出了全關聯映射算法FAST文獻[5]。所謂的全關聯映射指的是所有的邏輯塊共享Log Buffer。Log Block不在局限于特定的邏輯塊。當主機寫入數據時，數據先寫入到Log Block中，然后通過垃圾回收轉換為數據塊。由于FAST的設計采用類似于CPU Cache的全關聯映射策略，有效提高了Log Buffer的空間利用率。

頁塊混合映射算法的優缺點如下：

優點：

①對RAM資源要求不高，在有限的RAM資源情況下，由于Log Block采用頁映射表記錄，相比塊映射算法隨機寫入性能得到明顯改善。

②數據塊采用塊映射表記錄，順序讀寫性能突出。

缺點：

①如果隨機寫入頻繁，由于Log Block的空間利用率低，其導致垃圾回收開銷過大。

②垃圾回收過多的Merge操作，導致寫放大系數增大。

2.3基于頁映射的算法

A.Gupta提出了一種適用于NAND閃存的基于頁的映射算法DFTL文獻[3]。其成為當今SSD所應用最廣泛的算法。

DFTL維護了全部邏輯頁到物理頁的映射表，并將頁映射表保存在閃存的上，通過GTD進行映射表的追蹤。當主機寫入數據時，DFTL將數據按頁寫到數據塊上，并將新的映射關系緩存在CMT上。CMT是在內存中開辟的臨時緩沖區，當CMT寫滿以后，DFTL采用批量更新的算法將CMT中屬于同一個GTD頁的映射項一次更新到閃存上，從而減少系統的映射表更新消耗。DFTL的邏輯空間到物理空間的映射關系采用頁映射表管理，邏輯頁可以映射到任何物理頁，有效提高了隨機寫入的性能，同時采用貪婪的垃圾回收機制，隨著主機寫入數據，當空閑塊減少到一個設定的閾值后，垃圾回收啟動并選中有效數據最少的數據塊作為回收對象。DFTL將有效頁搬移到一個新的數據塊上，擦除舊的數據塊。這種貪婪的垃圾回收機制配合頁映射管理算法，使垃圾回收的效率大幅提高，有效避免了頁塊混合映射算法的Log Block空間利用率不足的問題。

在DFTL的基礎上， 為了提高系統的健壯性，并縮減內存的使用量，DongZhe Ma提出的LazyFTL文獻[4]，LazyFTL將用戶數據分為三個區域，DBA，CBA和UBA。 DBA作為主存儲區域用來存儲已經完整寫入的數據，UBA用來存儲主機正在寫入的熱數據，CBA用來存儲垃圾回收正在寫入的冷數據。LazyFTL將全局映射表存儲到MBA上，并通過GMD進行追蹤。與DFTL相比，LazyFTL開辟了兩個小區域CBA和UBA，其用來存儲剛剛寫入的數據，并使用UMT來緩存更新的映射表。LazyFTL通過Convert將Block N從CBA或者UBA區域轉化到DBA區域，同時UMT中指向Block N的所有映射表被寫入到MBA上。LazyFTL有效減少了設備掉電后的數據恢復時間。

頁映射算法的優缺點如下：

優點：

①由于不需要Log Buffer，所有數據直接寫到數據塊中，不需要Merge操作，垃圾回收效率大幅提高。

②全部數據采用頁映射關系，邏輯頁可以映射到任何物理頁上，系統響應時間快，性能最為突出。

③由于沒有不必要Merge操作，寫放大系數WAF得到有效控制，從而延長了SSD的使用壽命。

缺點：

①由于采用頁映射關系，映射表通常是用戶容量的千分之一。其會占用大量NAND閃存塊用來存儲全局映射表，導致用戶可用空間減小。

②需要大量內存資源來緩存映射表以便加速系統的訪問。

③由于取消了邏輯塊和數據塊的對應關系，邏輯頁可以映射表任意物理頁，當主機覆蓋寫大范圍的邏輯空間時，物理塊不能快速釋放，其導致性能降低。

3 FTL算法面臨的新問題和挑戰

隨著SSD的使用越來越普及，不同的應用場景對SSD的特性也有不同的要求，其對FTL的設計提出了新的挑戰。同時隨著NAND制程的演進以及最新糾錯算法LDPC的使用。 FTL的設計也要針對這些變化做出相應調整。

（1）NAND閃存的Paired Page 問題

NAND Paired Page問題是指當一個NAND Cell的低頁（LSB）已經編程完畢后，如果在編程高頁（MSB）的數據時，如果發生掉電事件，其LSB中已經成功寫入的數據也會被破壞掉。對于FTL的設計，如果沒有考慮此問題，主機會看到之前已經寫入成功的數據丟失掉，這通常不可接受的，會導致嚴重的數據丟失問題。

（2）先進制程閃存需要更復雜的出錯處理

隨著NAND閃存制程的發展，從一個Cell存儲1個比特的SLC，到一個Cell存儲2個比特的MLC，再到存儲3個比特的TLC和存儲4個比特的QLC，單位面積數據密度越來越大，其錯誤率也越來越高。

同時錯誤的類型也越來越復雜，如P/E cycle錯誤 Read Disturb錯誤等等，需要更復雜的FTL算法來處理這些錯誤，從而保證數據的正確性。

（3）FTL映射表需要更多的RAM資源

基于頁的映射算法擁有良好的性能，以及高效的垃圾回收效率，其已經成為主流FTL映射算法，但是隨著SSD容量的增大，頁映射表所需要的RAM資源會隨之增大，比如：4TB的SSD，如果4KB作為一個映射單元，4B來記錄一條映射關系，全局映射表需要4GB的存儲空間，如果CMT中只緩沖其中的千分之一的映射表，也需要近4MB的RAM空間，這對于很多控制器的設計來說是不可接受的。

（4）全局映射表存儲塊的磨損問題

FTL通常需要將全局映射表存儲到NAND閃存的管理塊上，由于控制器內部將部分更新的映射表緩存在CMT中，當SSD工作在一個隨機寫負載很重的環境中時，CMT中緩存的更新后的映射表項（Dirty Entry）會不斷地被刷新到存儲GMT的閃存塊中，一次更新至少需要讀一頁映射表，并寫入一頁映射表。所以GMT物理塊的磨損速度是用戶數據的10倍甚至更多。如何減少全局映射表存儲塊的磨損是設計下一代FTL應該考慮的重要內容之一。

4 總結與展望

SSD替代傳統HDD的速度正在加快，越來越多的SSD被用在數據中心，云計算，IoT設備，工控，汽車以及航空等領域。隨著5G、AI等先進技術的快速發展，對存儲需求不僅僅表現在大容量上，不同應用場景產生了多元化的需求，比如性能、功耗、散熱、耐久度等方面，這對FTL的設計提出了新的挑戰。本文對FTL的功能以及閃存的特性做了基本介紹，并分析了近些年幾種經典FTL的實現方法以及優缺點，同時結合筆者的經驗對將來FTL的設計所面臨的挑戰和問題提出了一些淺顯的分析，希望對SSD FTL的設計提供一定的參考意義。

參考文獻：

[1] A. Ban and R. Hasharon. Flash File System Optimized for Page-mode Flash Technologies， Aug.1999. United States Patent No. 5，937，425.

[2] A. Gupta， Y. Kim， and B. Urgaonkar. DFTL： A Flash Translation Layer Employing Demand-based Selective Caching of Page-level Address Mappings. ACM SIGARCH Computer Architecture News. Volume 37. Issue 1. March 2009. Pages 229–240.

[3] Dongzhe Ma， Jianhua Feng， and Guoliang Li. LazyFTL： A page-level flash translation layer optimized for NAND flash memory. SIGMOD ‘11： Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. June 2011. Pages 1–12

[4] Jesung Kim， Jong Min Kim， Sam H. Noh， et al. 2002. A space-efficient flash translation layer for compact flash systems. IEEE Transactions on Consumer Electronics. Volume 48. Issue 2. May 2002. Pages 366–375.

[5] S. Lee， D. Park， T. Chung， D. Lee， S. Park， and H. Song. A Log Buffer based Flash Translation Layer Using Fully Associative Sector Translation. ACM Transactions on Embedded Computing Systems. Volume 6. Issue 3. July 2007. Pages 18–es.