王志奇，何欣霖

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

0 引言

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

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

1 研究背景

1.1 NAND Flash

NAND Flash 最小的讀寫單位是頁，擦除單位是塊，每個(gè)塊由多個(gè)頁組成。每個(gè)頁分為主區(qū)和備用區(qū)，主區(qū)用來存儲(chǔ)用戶的數(shù)據(jù)，備用區(qū)用戶存儲(chǔ)用戶數(shù)據(jù)的ECC 校驗(yàn)碼和閃存轉(zhuǎn)換層的一些元數(shù)據(jù)信息。

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

1.2 閃存轉(zhuǎn)換層（FTL）

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

1.2.1 地址映射

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

1.2.2 垃圾回收

隨著用戶的使用和更新，備用塊被使用完成，這時(shí)必須觸發(fā)垃圾回收以釋放空塊。垃圾回收策略是通過擦除包含無效數(shù)據(jù)的塊來獲得更多使用空間[5]。該操作對用戶體驗(yàn)有著非常重要的影響，不當(dāng)?shù)睦厥湛赡軙?huì)造成用戶命令被阻塞而無法保證命令得到及時(shí)響應(yīng)。

1.2.3 壞塊管理

由于NAND Flash 的生產(chǎn)工藝特性，它不能保證所有存儲(chǔ)空間在其生命周期內(nèi)保持可用性，因此在NAND Flash 的生產(chǎn)和使用過程中會(huì)產(chǎn)生壞塊。FTL 需要建立壞塊表。該表是動(dòng)態(tài)更新的查找表，可以識(shí)別所有NAND Flash 壞塊，并將壞塊信息添加到壞塊列表中，并保證整個(gè)壞塊列表得到不斷維護(hù)和更新。

1.2.4 磨損均衡

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

2 FTL 算法設(shè)計(jì)與實(shí)現(xiàn)

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

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

圖1 塊生命周期變化

2.1 地址映射

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

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

圖2 頁映射框架

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

2.2 垃圾回收

垃圾回收最初由John M[7]提出，分為主動(dòng)垃圾回收和被動(dòng)垃圾回收兩種。被動(dòng)垃圾回收是指在使用過程中因?yàn)楸Ａ魤K全部都被使用，必須回收一部分保留塊以供使用。此時(shí)需要使用最快的方法進(jìn)行垃圾回收，即選擇有效頁數(shù)最少的塊，以保證拷貝數(shù)量最少，提高回收效率。主動(dòng)垃圾回收一般是在空閑時(shí)，通過主動(dòng)回收釋放一些保留塊，以提升后續(xù)寫操作時(shí)的性能。這時(shí)垃圾回收是以能夠?qū)⒂行?shù)據(jù)整理得更有序?yàn)闇?zhǔn)，需要考慮到數(shù)據(jù)的冷熱等因素。

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

圖3 有效頁分級(jí)情況

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

2.3 壞塊管理

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

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

2.4 磨損均衡

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

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

該算法主要包括3 個(gè)步驟：

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

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

2.5 高速緩存

使用固態(tài)盤內(nèi)的RAM 作數(shù)據(jù)傳輸?shù)木彺妫脭?shù)據(jù)訪問的時(shí)間和空間局部性原理，系統(tǒng)在一段時(shí)間內(nèi)可能會(huì)對同一塊數(shù)據(jù)進(jìn)行反復(fù)的讀寫，而寫緩存管理可以不用立即將新的數(shù)據(jù)寫入NAND Flash而是推遲一段時(shí)間后再寫。這不僅降低了寫請求的響應(yīng)時(shí)間，而且減少了固態(tài)盤讀寫的次數(shù)。此外，讀寫請求的分布還具有空間局部性，連續(xù)的多個(gè)請求可能合并成一筆讀寫操作，提高了固態(tài)盤操作的效率。

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

3 試驗(yàn)結(jié)果與分析

本文實(shí)驗(yàn)平臺(tái)是一塊固態(tài)硬盤開發(fā)板，該開發(fā)板容量為512 GB，NAND 控制器具有4 個(gè)通道，可并行處理NAND 命令，SRAM 大小為1 MB，DDR 容量為512 MB，采用高速的SATA 接口和主機(jī)進(jìn)行通信。

通過主機(jī)應(yīng)用程序DiskGenius 工具可以看到固態(tài)硬盤被系統(tǒng)正常識(shí)別，如圖4 所示，SSD512GB的磁盤即為測試目標(biāo)磁盤。

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

圖4 被系統(tǒng)識(shí)別的固態(tài)硬盤

圖5 磁盤性能測試結(jié)果

通過測試結(jié)果可以看出，順序讀寫的性能比較高，但是隨機(jī)讀寫的性能比較差。4 kB 的IOPS 表現(xiàn)不理想，主要是因?yàn)殡S機(jī)讀寫時(shí)緩存的命中率會(huì)變低，映射表更新次數(shù)過多導(dǎo)致性能損失嚴(yán)重，這是后續(xù)需要繼續(xù)優(yōu)化的地方。

4 結(jié)語

在基于NAND Flash 的存儲(chǔ)系統(tǒng)內(nèi)，往往因?yàn)橛邢薜馁Y源而無法采用頁映射機(jī)制。本文對傳統(tǒng)的頁映射機(jī)制進(jìn)行優(yōu)化，將映射表分成兩部分分別存儲(chǔ)在RAM 中和NAND Flash 中，通過載入和載出實(shí)現(xiàn)映射表的存儲(chǔ)和更新。同時(shí)，為了保證高速的I/O 響應(yīng)，本文還設(shè)計(jì)了高速緩存模塊，使得固態(tài)硬盤具有較好的順序讀寫性能。本文設(shè)計(jì)的閃存轉(zhuǎn)換層仍存在不足，讀寫性能和映射表的載入載出頻率以及高速緩存的命中率有很大的關(guān)聯(lián)，需要改進(jìn)算法，以減少映射表的更新次數(shù)和提高緩存的命中率。