一種優化的閃存轉換層的設計與實現*

王志奇，何欣霖

（成都三零嘉微電子有限公司，四川 成都 610041）

0 引言

固態硬盤（Solid State Disk，SSD）作為新型的存儲介質，具有體積小、速度快、抗震性好以及溫度適應性強等特點，被廣泛應用于軍工、車載、工控、電力以及醫療等領域。隨著技術的不斷成熟以及存儲介質工藝的不斷提升，固態硬盤逐漸普及到消費電子領域。該類硬盤主要由主控器和存儲介質組成，目前大容量存儲介質主要為NAND Flash。

NAND Flash 具有體積小、重量輕、功耗低[1]、抗震性強以及性能高等優點。但是，NAND Flash本身也存在缺陷，數據翻新時需要將數據按塊擦除之后才能進行數據的再次寫入。為了解決這個問題，設計了閃存轉換層（Flash Translation Layer，FTL），將上層應用與存儲介質獨立開來，通過地址映射將NAND Flash 先擦后寫的特性限制消除，后通過壞塊管理、垃圾回收以及磨損均衡等功能配合，確保NAND Flash 的使用壽命，保證數據的安全。本文實現了一種優化的閃存轉換層并在固態硬盤上進行實施部署，實現了固態硬盤的功能。

1 研究背景

1.1 NAND Flash

NAND Flash 最小的讀寫單位是頁，擦除單位是塊，每個塊由多個頁組成。每個頁分為主區和備用區，主區用來存儲用戶的數據，備用區用戶存儲用戶數據的ECC 校驗碼和閃存轉換層的一些元數據信息。

NAND Flash 分為SLC、MLC[2]、TLC 以及3D NAND 等幾種類型。這幾種NAND Flash 都有共同的特點，塊的擦除次數有限。其中，TLC 型NAND Flash 塊擦除次數僅為1 000 次左右，所以閃存轉換層會通過磨損均衡、垃圾回收以及壞塊管理等功能顯著的提升固態硬盤的使用壽命。

1.2 閃存轉換層（FTL）

閃存轉換層（FTL）主要功能是將NAND Flash抽象成塊設備[3]和目前主流的磁盤設備操作方式進行兼容。閃存轉換層既要保證讀寫的性能，也要保證NAND Flash的使用壽命，主要包含以下幾個部分。

1.2.1 地址映射

地址映射負責將邏輯地址轉換成實際的物理地址，對于NAND Flash 來說就是轉換成物理頁地址。根據映射粒度不同常用的地址映射算法有頁映射、塊映射和混合映射3 種。頁映射的映射粒度是NAND Flash 的頁，所以頁映射表所占資源比較大，是該算法的主要缺點；塊映射顧名思義就是映射粒度為塊，優點是占用資源較小，但是在數據合并時會出現整塊數據拷貝的問題，導致寫入效率低下，典型代表是NFTL（NAND Flash Translation Layer）[4]；混合映射算法是對頁映射和塊映射的一種平衡，使得在資源占用盡量小的情況下達到符合設計的性能。

1.2.2 垃圾回收

隨著用戶的使用和更新，備用塊被使用完成，這時必須觸發垃圾回收以釋放空塊。垃圾回收策略是通過擦除包含無效數據的塊來獲得更多使用空間[5]。該操作對用戶體驗有著非常重要的影響，不當的垃圾回收可能會造成用戶命令被阻塞而無法保證命令得到及時響應。

1.2.3 壞塊管理

由于NAND Flash 的生產工藝特性，它不能保證所有存儲空間在其生命周期內保持可用性，因此在NAND Flash 的生產和使用過程中會產生壞塊。FTL 需要建立壞塊表。該表是動態更新的查找表，可以識別所有NAND Flash 壞塊，并將壞塊信息添加到壞塊列表中，并保證整個壞塊列表得到不斷維護和更新。

1.2.4 磨損均衡

在使用過程中存在用戶數據和訪問行為冷熱不均的情況，導致NAND Flash 的某些物理塊長期不被使用，而另一些物理塊被頻繁使用。隨著使用時間的推移會出現某些塊提前達到擦除次數而出現不穩定的情況，會影響整個NAND Flash 的使用壽命。為了解決這個問題，必須要采取某種策略使得對閃存的擦除操作盡可能均衡分布在整個存儲介質上，這就是磨損均衡。

2 FTL 算法設計與實現

FTL 的主要功能是實現邏輯地址到NAND Flash的物理地址的轉換。由于NAND Flash 的特點，所有塊的生命周期如圖1 所示。剛開始是一塊空塊，里面沒有任何數據；在需要的時候被分配使用，寫入數據成為有效數據塊；數據被更新，由于不能直接更新，數據會被寫到其他塊上，這個塊上的數據變為無效數據塊；無效數據塊被回收擦除掉，重新成為空閑塊可以再次使用。

由于這些特性，不能將NAND Flash 所有塊上都放上有效數據，必須有一部分塊作為備用塊，用來做為數據更新時的緩沖塊，這部分塊稱為保留塊。這是NAND Flash 提供的實際容量小于標稱容量的原因。保留塊的多少與FTL 的映射算法有關，所以不同的算法實現其有效容量會不相同。

圖1 塊生命周期變化

2.1 地址映射

固態盤中的映射管理機制是FTL 中非常重要的一個模塊，直接影響實際固態盤的I/O 性能。目前的映射方式有頁映射、塊映射和混合映射幾種。這些映射方式的基本單位即決定固態盤的固件程序能夠操作的最小單元。粒度越大即操作的基本單位越小，其I/O 性能表現得越好。粒度越大，帶來的問題是映射表越大，需要較大的SDRAM 存放映射表，所以需要一種相對最優的映射管理方式，既能保證映射機制提供較好的I/O 性能，又不能帶來太大的開銷。在FTL 設計中，涉及的地址映射算法是對性能和資源開銷的一個折中處理，即在不影響性能的情況下，只消耗相當少一部分資源。

本文設計的FTL 中，地址映射采用的是頁映射方式。頁映射表是一種全相聯模式，記錄所有邏輯頁到物理頁的映射關系[6]，其性能是最好的。由于傳統的頁映射機制占用資源太多，本文為解決這個問題設計了一種優化算法。它不是所有的映射表項都存入SRAM 中，而是動態地根據工作負載載入或載出映射所需的表項。同時，它在NAND Flash介質上維護全盤的映射表的完整鏡像，如圖2 所示。將物理頁分為data-pages 和translation-pages，其中data-pages 存放在I/O 中訪問的真實數據，而translation-pages 則存放邏輯-物理的地址映射表。同理，data-BLOCKs 和translation-BLOCKs 則分別由這兩種pages 組成。

圖2 頁映射框架

由于不是所有的表項都存儲在SRAM 中，必然會存在部分映射表的載入和載出操作。映射的地址處理機制：如果對所要處理的I/O 請求，其所需的映射信息存在于SRAM 中的CMT（Cached Mapping Table），那么將直接用這個已存在的映射信息；如果該映射信息不存在SRAM 中，那么需要從NAND Flash 介質中取出，即需從Translation BLOCKS 中取出映射信息后載入CMT。另外，需要根據CMT 的工作狀態和替換算法，將部分失效或不經常訪問的映射信息載出，寫入translations blocks 中。

2.2 垃圾回收

垃圾回收最初由John M[7]提出，分為主動垃圾回收和被動垃圾回收兩種。被動垃圾回收是指在使用過程中因為保留塊全部都被使用，必須回收一部分保留塊以供使用。此時需要使用最快的方法進行垃圾回收，即選擇有效頁數最少的塊，以保證拷貝數量最少，提高回收效率。主動垃圾回收一般是在空閑時，通過主動回收釋放一些保留塊，以提升后續寫操作時的性能。這時垃圾回收是以能夠將有效數據整理得更有序為準，需要考慮到數據的冷熱等因素。

選用回收目標塊時采用模糊策略。為了保證對計算資源及緩存資源最少占用時達到較好的效果，本文設計的算法對此進行了優化，將所有塊按有效頁數劃分為不同級別，如圖3 所示，可以根據回收的目標選擇合適的目標塊進行垃圾回收。

圖3 有效頁分級情況

L0～L3 鏈表均為雙向鏈表，每次數據更新引起表項變化時，都將需要將目標塊向雙向鏈的頭部移動。這樣越靠近雙向鏈的頭部的塊越是最近訪問的塊，其存儲的數據可能是熱數據；越靠近雙向鏈尾部的塊越是最長時間沒訪問，其存儲的數據相對要冷一些。這樣通過雙向鏈的頭尾可以表示一部分冷熱數據的特征，作為垃圾回收時的選擇參考因素之一。

2.3 壞塊管理

初次使用NAND Flash 時，塊擦除之前要讀取壞塊信息構建壞塊表，否則將擦除初始化的固有壞塊信息。

對NAND Flash 的寫入、讀取操作，必須首先查找壞塊表，判斷該塊是否為壞塊，避免在壞塊上進行各種操作。同時，在讀取和寫入操作后，需要判斷操作的狀態，判斷是否有新的壞塊產生。若產生了壞塊，則必須將該塊數據翻新到新的塊中，同步更新壞塊表。為了達到該效果，壞塊模塊需要檢測每次操作NAND Flash 時ECC 的錯誤狀態。當ECC 錯誤的位數將要超過設定的門限值時，將該塊信息加入到壞塊表中，同時觸發主動垃圾回收過程，將數據更新到新的塊中。

2.4 磨損均衡

本文提出了一種磨損均衡的算法，主要遵從兩個原則：物理塊中存放不經常更新的數據；存放冷熱數據的物理塊要經常進行數據交換。

把NAND Flash 在邏輯上分成熱池和冷池兩部分，分別用來存放經常訪問的數據和不經常訪問的數據。用兩個隊列定位熱數據和冷數據，隊列按照它們已被擦除的次數進行排列。對于隊列Q，函數H+(Q)和H-(Q)分別返回最大和最小列表頭部的塊。對于塊B，EC(B)是指它的擦除次數。起初，塊隨機分配在兩個池中，定義參數TH為擦除次數的閾值。TH越小，所有的塊之間的使用就越均衡。

該算法主要包括3 個步驟：

（2）為了避免使熱池中的數據變得不活躍或是冷池中的數據變得活躍，在一定時間之后檢查表達式是否成立，如成立，則交換相應的塊；

（3）由于可能有塊進行之前的操作，因此要引入EEC（Effective Erase Cycle）表示經過第一步操作后的有效擦除次數，所以引入隊列和，分別用來標志熱池和冷池中的EEC屬性。在一定擦除操作完成后，檢查表達式如成立，交換隊列中的塊。

2.5 高速緩存

使用固態盤內的RAM 作數據傳輸的緩存，利用數據訪問的時間和空間局部性原理，系統在一段時間內可能會對同一塊數據進行反復的讀寫，而寫緩存管理可以不用立即將新的數據寫入NAND Flash而是推遲一段時間后再寫。這不僅降低了寫請求的響應時間，而且減少了固態盤讀寫的次數。此外，讀寫請求的分布還具有空間局部性，連續的多個請求可能合并成一筆讀寫操作，提高了固態盤操作的效率。

緩存的替換策略主要是決定哪些將從緩存中清除。緩存中最常用的有最近最少用（Least Recently Used，LRU）、使用頻率最小（Least Frequently Used，LFU）等算法。基于對緩存空間劃分的技術，在邏輯上，緩存包含一個數據塊棧，最經使用的塊壓入棧頂，每個數據塊有自己的引用數，即被調用的次數。當某塊第一次調用緩存，其引用數初始值為0。由于緩存分為MRU（Most Recently Used）段、LRU 段和中間段，當緩存命中即數據塊在緩存中時，引用數保持不變。也就是說，如果該塊在MRU 段中再次或多次被調用時，引用數保持不變。只有當該塊從LRU 段調入MRU 段時，引用數才加1。與LRU 算法不同的是，當緩存失敗時，選擇MRU 段以外應用數最小的數據塊進行替換。如果可選塊不止一塊時，應用LRU 算法，淘汰其中最近最少使用的塊。

3 試驗結果與分析

本文實驗平臺是一塊固態硬盤開發板，該開發板容量為512 GB，NAND 控制器具有4 個通道，可并行處理NAND 命令，SRAM 大小為1 MB，DDR 容量為512 MB，采用高速的SATA 接口和主機進行通信。

通過主機應用程序DiskGenius 工具可以看到固態硬盤被系統正常識別，如圖4 所示，SSD512GB的磁盤即為測試目標磁盤。

用HD Tune Pro 工具對硬盤做性能測試，測試結果如圖5 所示。

圖4 被系統識別的固態硬盤

圖5 磁盤性能測試結果

通過測試結果可以看出，順序讀寫的性能比較高，但是隨機讀寫的性能比較差。4 kB 的IOPS 表現不理想，主要是因為隨機讀寫時緩存的命中率會變低，映射表更新次數過多導致性能損失嚴重，這是后續需要繼續優化的地方。

4 結語

在基于NAND Flash 的存儲系統內，往往因為有限的資源而無法采用頁映射機制。本文對傳統的頁映射機制進行優化，將映射表分成兩部分分別存儲在RAM 中和NAND Flash 中，通過載入和載出實現映射表的存儲和更新。同時，為了保證高速的I/O 響應，本文還設計了高速緩存模塊，使得固態硬盤具有較好的順序讀寫性能。本文設計的閃存轉換層仍存在不足，讀寫性能和映射表的載入載出頻率以及高速緩存的命中率有很大的關聯，需要改進算法，以減少映射表的更新次數和提高緩存的命中率。