馬福祥

（青海師范大學(xué) 計(jì)算機(jī)學(xué)院，青海 西寧810008）

近年來(lái)，CPU的運(yùn)行速度按照摩爾定律快速增長(zhǎng)，每年大約成長(zhǎng)30%-50%，而硬盤(pán)速度由于機(jī)械尋道等原因增長(zhǎng)很慢，只能成長(zhǎng)約7%，因此在系統(tǒng)中硬盤(pán)一直都是系統(tǒng)性能的瓶頸。為解決硬盤(pán)速度慢的問(wèn)題，產(chǎn)生了磁盤(pán)陣列和固態(tài)硬盤(pán)(Solid-State Disk,SSD)兩種技術(shù)。磁盤(pán)陣列通過(guò)專(zhuān)用控制器將多組傳統(tǒng)硬盤(pán)進(jìn)行RAID （Redundant Arrays of Inexpensive Disks,RAID）組合的技術(shù)，這樣提高了讀寫(xiě)速度、存儲(chǔ)容量和可靠性，此技術(shù)一般用在機(jī)群服務(wù)里。采用多組Flash芯片的固態(tài)硬盤(pán)技術(shù)，通過(guò)將多組Flash芯片形成陣列來(lái)提高讀寫(xiě)速度和可靠性，與磁盤(pán)陣列相比，SSD技術(shù)具有成本低、體積小、重量輕、抗震摔、無(wú)噪音和工作溫度范圍大的諸多優(yōu)點(diǎn)，目前吸引了大量的工業(yè)和學(xué)術(shù)界所關(guān)注的熱點(diǎn)。它也是近幾年最有希望代替?zhèn)鹘y(tǒng)硬盤(pán)成為主流存儲(chǔ)設(shè)備的新型存儲(chǔ)設(shè)備。目前有一系列的SSD研究主題，從接口技術(shù)到緩沖器管理、從Flash轉(zhuǎn)換層 （Flash Translation Layer,FTL)到性能和能耗效率等等。在FTL中，地址映射策略是FTL最基本的組件，它在一定程度上決定了其它組件的設(shè)計(jì)，所以，地址映射機(jī)制是 FTL的核心部分，是垃圾回收和損耗均衡的基礎(chǔ)。但目前的地址映射算法都各有利弊，本文分析了一種性能較好的頁(yè)映射和混合映射按給定閥值進(jìn)行轉(zhuǎn)化的算法，此方法比較有效的避免了存儲(chǔ)映射表所需的大空間、浪費(fèi)過(guò)多的系統(tǒng)資源和映射表的更新相當(dāng)頻繁等問(wèn)題。

1 SSD存儲(chǔ)介質(zhì)介紹

目前，市場(chǎng)上SSD的組建方式有基于DRAM的和基于FLASH芯片的，由于DRAM的SSD能耗高于普通硬盤(pán)，且需要不間斷供電，因此目前應(yīng)用范圍小。而基于FLASH芯片的SSD，數(shù)據(jù)寫(xiě)入后不需要外界電力來(lái)維持其記憶，因此目前市場(chǎng)上絕大部分SSD都是基于Flash的。Flash技術(shù)主要有2種類(lèi)型，NOR（Intel 1988 年）和 NAND（Toshiba 1989 年）。 相比NOR Flash，NAND Flash具有存儲(chǔ)密度更高、容量更大、功耗更低、芯片引腳兼容性更好和成本效益更高等優(yōu)點(diǎn)，因此大多數(shù)SSD也都是基于NAND Flash。NAND Flash讀操作和寫(xiě)操作的最小單位是頁(yè) （page），擦除操作的最小單位是塊（block），對(duì)于一個(gè)已經(jīng)保存數(shù)據(jù)的頁(yè)，在寫(xiě)入新數(shù)據(jù)時(shí)，需要先擦除，再寫(xiě)新數(shù)據(jù)，每個(gè)塊擦寫(xiě)次數(shù)是有限制的，一般是10K到100K，并且每塊芯片在出廠時(shí)都有一定比例的壞塊存在。NAND Flash技術(shù)采取特殊的浮柵場(chǎng)效應(yīng)管（Field Effect Transistor,FET)通過(guò)儲(chǔ)存電荷來(lái)存儲(chǔ)數(shù)據(jù)，寫(xiě)數(shù)據(jù)就是向浮柵中注入或者排除一定量的電子，讀數(shù)據(jù)是通過(guò)檢查場(chǎng)效應(yīng)管的電流電壓，根據(jù)電流電壓的大小判斷該場(chǎng)效應(yīng)管所存儲(chǔ)的狀態(tài)。根據(jù)狀態(tài)的個(gè)數(shù)NAND Flash存儲(chǔ)單元又分為兩類(lèi)：?jiǎn)螌訂卧?(Single Layer Cell,SLC)和多層單元 (Multi-Level Cell,MLC)，SLC每個(gè)單元只存放1bit數(shù)據(jù)，能表示0和1兩種狀態(tài)。MLC每個(gè)單元可存放2bit數(shù)據(jù)，能表示00、01、10和11這4種狀態(tài)。雖然MLC提高了容量，由于存放的信息多，結(jié)構(gòu)復(fù)雜而帶來(lái)了更高的出錯(cuò)率。因此，對(duì)數(shù)據(jù)進(jìn)行修正，正是錯(cuò)誤修正這個(gè)動(dòng)作導(dǎo)致其性能相對(duì)于SLC大幅落后，此外，MLC的復(fù)寫(xiě)次數(shù)也僅為SLC的十分之一。但是由于成本和容量的優(yōu)勢(shì)，市場(chǎng)上大多數(shù)SSD都是MLC型的。

2 SSD內(nèi)部結(jié)構(gòu)分析

如圖 1所示，SSD主要由接口芯片、微處理器、DMA、DRAM和Flash存儲(chǔ)陣列組成。其中接口主要有PATA、SATA、PCIe和USB 3.0。PATA是為了與當(dāng)時(shí)的硬盤(pán)接口相吻合，以方便SSD主攻PC市場(chǎng)，讓消費(fèi)者也更容易接受SSD。 SATA接口于2001年推出SATA 1.0時(shí)，傳輸速率已達(dá)150 MB/s，高于 PATA最大傳輸速率133MB/s，隨著 SATA 2.0與3.0的陸續(xù)推出，傳輸速率更倍速成長(zhǎng)至300MB/s和600MB/s，傳輸速度演進(jìn)之快，非PATA接口能及，近年來(lái)已逐漸取代PATA，成為儲(chǔ)存設(shè)備主流接口。 SATA3是串行ATA國(guó)際組織發(fā)布的新版規(guī)范，主要是傳輸速度達(dá)到6Gbps，是未來(lái)的主流接口。SSD的核心部分是硬盤(pán)控制器[1]，一般由 FPGA作為載體，移植 MicroBlaze嵌入式處理器軟核，通過(guò)片內(nèi)總線OPB(On-Chip Peripheral Bus)連接各個(gè)功能模塊，實(shí)現(xiàn)固態(tài)硬盤(pán)控制器的功能。DRAM控制器以及外接一塊 DRAM，作為處理器工作時(shí)的程序和數(shù)據(jù)緩沖。NAND Flash控制器實(shí)現(xiàn)對(duì) NAND Flash陣列的并行操作。

圖1 固態(tài)硬盤(pán)總體結(jié)構(gòu)圖Fig.1 Structure diagram of the SSD

SSD是以硬盤(pán)的替代者的姿態(tài)出現(xiàn)的，為了與現(xiàn)有系統(tǒng)無(wú)縫對(duì)接，SSD必須對(duì)外提供塊接口，使主機(jī)端所看到的SSD是一個(gè)和HDD一樣的塊設(shè)備。為了達(dá)到模擬塊設(shè)備的目的，SSD中需要FTL作為中間層，如圖2所示，它由3部分組成，Address mapping(地址映射)、Wear leveling(損耗平衡)和Garbage collection(垃圾回收)。從圖可知，F(xiàn)TL從主機(jī)文件系統(tǒng)接收塊級(jí)請(qǐng)求，經(jīng)過(guò)FTL的處理，產(chǎn)生Flash的各種控制命令。

Flash中每個(gè)塊都有一定的擦寫(xiě)次數(shù)限制。如果沒(méi)有合理的管理機(jī)制，SSD在幾萬(wàn)次的擦寫(xiě)后就可能損壞。為了延長(zhǎng)Flash芯片的整體壽命，增強(qiáng)可靠性，就要在所有的塊之間平衡擦除次數(shù)，這種技術(shù)被稱(chēng)為損耗均衡。這方面的研究成果文獻(xiàn)已經(jīng)很多，基本方法有動(dòng)態(tài)損耗平衡和靜態(tài)損耗平衡。動(dòng)態(tài)損耗平就是在請(qǐng)求到達(dá)時(shí)，選取擦除次數(shù)較少的塊作為請(qǐng)求的物理地址。靜態(tài)損耗平衡的基本做法是將冷數(shù)據(jù)從原塊取出，存放在擦除次數(shù)過(guò)多的塊，原來(lái)存放冷數(shù)據(jù)的塊被釋放出來(lái)，接受熱數(shù)據(jù)的擦寫(xiě)。

圖2 固態(tài)硬盤(pán)結(jié)構(gòu)框圖Fig.2 Structure diagram of the SSD

所謂的垃圾回收是指當(dāng)需要釋放一部分空閑空間時(shí)，此塊內(nèi)既有過(guò)時(shí)或者作廢的數(shù)據(jù)頁(yè)也包含有有效的數(shù)據(jù)頁(yè)，就需要把有效數(shù)據(jù)和無(wú)效數(shù)據(jù)進(jìn)行分離，把所有有效數(shù)據(jù)重新移動(dòng)到其它塊中，把不包含有效數(shù)據(jù)的塊進(jìn)行擦除來(lái)釋放自由空間。其過(guò)程可以簡(jiǎn)單地概括為，選擇回收對(duì)象，回收預(yù)處理和擦除整個(gè)塊3個(gè)步驟。

3 地址的映射改進(jìn)算法

當(dāng)主機(jī)發(fā)出讀寫(xiě)操作命令，并給出將要操作的邏輯地址時(shí)，文件系統(tǒng)根據(jù)主機(jī)給出的邏輯地址計(jì)算出具體的物理地址，由于考慮到均衡損耗，每個(gè)邏輯地址對(duì)應(yīng)的實(shí)際存儲(chǔ)介質(zhì)的物理地址是變化的。因此存儲(chǔ)系統(tǒng)采用地址映射來(lái)獲取邏輯地址對(duì)應(yīng)的物理地址。根據(jù)映射的不同，F(xiàn)TL算法分為頁(yè)地址映射和塊地址映射。頁(yè)地址映射的基本是頁(yè)(page)，每個(gè)邏輯頁(yè)都被映射到任何一個(gè)物理頁(yè)[2]。因此，如果文件系統(tǒng)有 m個(gè)邏輯頁(yè)，則映射表的記錄數(shù)就有m條，如圖3所示。邏輯地址 （Logical address）4通過(guò) SRAM上的映射表（Map Table）可以找到對(duì)應(yīng)的內(nèi)容(0,3)。前者是物理塊號(hào)（Physical Block Number，PBN），后者為塊內(nèi)偏移地址，通過(guò)此方法很方便的找到了對(duì)應(yīng)的頁(yè)。該方法映射信息管理的靈活度高，空間利用率高，垃圾回收負(fù)載小。但它也有一些問(wèn)題，比如一個(gè)SSD總?cè)萘繛?28GB，每頁(yè)容量為2KB。在映射表中，總共有128GB/2KB=64,000,000條表項(xiàng)，每條表項(xiàng)所占空間為4B，所以要放下這個(gè)映射表需要4B*64,000,000=256 MB，而在運(yùn)行時(shí)映射表需要常駐SSD的RAM中，一般而言，SSD所能提供的RAM大小為16 MB到256 MB。所以，對(duì)于大容量的SSD，采用頁(yè)映射是不可能的。

圖3 頁(yè)地址映射Fig.3 Page address mapping

塊映射算法的基本單位是塊(block)。整個(gè)地址空間首先被表示為多個(gè)塊，而每個(gè)塊又包含多個(gè)頁(yè)，每個(gè)頁(yè)由所屬塊號(hào)和塊內(nèi)偏移量確定。在一個(gè)邏輯塊內(nèi)，邏輯頁(yè)的偏移量和對(duì)應(yīng)的物理塊內(nèi)的頁(yè)偏移量是相同的。因此，只有定位到塊，頁(yè)也就可以確認(rèn)了如圖4。邏輯地址包含了兩個(gè)部分，9/4=2是邏輯的塊地址，9%4=1為塊內(nèi)偏移地址。通過(guò)映射表可以知道2對(duì)應(yīng)于物理塊1，通過(guò)偏移量1可以找到其最終的物理頁(yè)，完成尋址過(guò)程。因此，塊地址映射只需要很小的RAM空間存儲(chǔ)映射信息。比如SSD總?cè)萘繛?28GB，塊映射方式下，映射表所需的容量為4 MB，極大地節(jié)約了RAM的空間。但是，這種映射方法不靈活，邏輯頁(yè)只能被映射到同一個(gè)物理頁(yè)。假如文件系統(tǒng)對(duì)同一個(gè)邏輯頁(yè)發(fā)出多次寫(xiě)請(qǐng)求，由于對(duì)應(yīng)的物理頁(yè)是同一個(gè)頁(yè)面，因此為了寫(xiě)入數(shù)據(jù)，必然對(duì)該頁(yè)產(chǎn)生大量的拷貝、擦除操作，導(dǎo)致存儲(chǔ)設(shè)備空間內(nèi)碎片較多，進(jìn)而嚴(yán)重影響存儲(chǔ)器的性能及使用壽命。

圖4 塊地址映射Fig.4 Block adress mapping

通過(guò)以上分析得知，頁(yè)映射性能好，但是映射表占用空間大。塊映射表占用空間小，但是性能差。針對(duì)此問(wèn)題，Kim等提出了一種更有效的混合地址映射算法，BAST算法[3-4]。該算法首先使用塊映射算法得到相應(yīng)的物理塊，然后在塊內(nèi)再使用頁(yè)映射算法，此算法提高了閃存的空間利用率，但在隨機(jī)寫(xiě)頻繁的情況下，會(huì)引起頻繁的塊擦除操作，導(dǎo)致隨機(jī)訪問(wèn)性能降低。為解決日志塊利用率低的問(wèn)題，Lee等人提出了FAST算法[5]，該算法進(jìn)行垃圾回收時(shí)會(huì)導(dǎo)致日志塊與多個(gè)數(shù)據(jù)塊的合并操作，影響了運(yùn)行效率。除此外，還提出了SuperBlock[6]、LAST[7]等算法。無(wú)論哪種算法，都需要兩次的映射及查表，總體性能不及前面兩種。

鑒于上面的分析，我們提出了一種算法，其思想是：首先使用一個(gè)大容量的RAM和一個(gè)大容量的SSD，并通過(guò)特定的文件系統(tǒng)進(jìn)行管理。然后設(shè)置一個(gè)閾值T[8]（根據(jù)SSD的大小按算法閾值可動(dòng)態(tài)變化），當(dāng)映射表的容量大于此值時(shí)，使用混合地址映射，否則只使用頁(yè)地址映射。其流程圖5所示。

圖5 算法的流程圖Fig.5 Flow chart the algorithm

4 結(jié)束語(yǔ)

文中提出了一種的基于頁(yè)地址映射和混合地址映射相互轉(zhuǎn)化的策略。當(dāng)映射表沒(méi)達(dá)到閥值時(shí)該算法映射速度快，空間利用率高。當(dāng)超過(guò)閥值[9-10]時(shí)采用混合地址映射，避免了存儲(chǔ)映射表所需的大空間，浪費(fèi)過(guò)多的系統(tǒng)資源和映射表的更新也相當(dāng)頻繁的問(wèn)題。

[1]葉朝鋒,黃松嶺,徐云.基于SATA的嵌入式高速大容量數(shù)據(jù)存儲(chǔ)系統(tǒng)設(shè)計(jì)[J].電測(cè)與儀表，2008，45(2)：41-44.YE Chao-feng,HUANG Song-ling,XU Yun.Design of highspeed and high-capacity embedded data store system based on SATA connection[J].Electrical Measurement&instrumentation,2008，45(2)：41-44.

[2]謝長(zhǎng)生,李博等:基于片內(nèi)SRAM的固態(tài)硬盤(pán)轉(zhuǎn)換層設(shè)計(jì)[J].計(jì)算機(jī)科學(xué)，2010,37(7):296-300.Xie Chang-sheng Li Bo,On-chip SRAM-based FTL Design for Solid-state Drive[J].Computer Science,2010,37(7):296-300.

[3]Kim J,Kim JM,Noh SH,et al.A space-efficient flash translation layer for compact flash systems [J].IEEE Transactions on Consumer Electronics,2002,48(2):366-375.

[4]邵亞剛,戴冠中等:基于日志式混合映射的FTL算法設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)測(cè)量與控制,2009,17(7):1362-1364.Shao Yagang Dai Guanzhong,Design and Implementation of A Log-structured Hybrid Mapping Algorithm for File Translation Layer of Flash Memory [J]. Computer Measurement&Control,2009,17(7):1362-1364.

[5]Lee S,Park D,Chung T,et al.A log buffer based flash translation layer using fully associative sector translation[J].ACM Trans on Embedded Computing Systems,2007,6(3):18-es.

[6]Kang J,Jo H,Kim J,et al.A superblock-based flash translation layer for NAND flash memory[C]//Proc of the 6th ACM&IEEE Int Conf on Embedded Software.ACM,2006:161-170.

[7]Lee S,Shin D,Kim Y,et al.LAST:Locality-aware sector translation for NAND flash memory-based storage systems[J].ACM IGOPSOperating System Review,2008,42(6):36-42.

[8]Gal E,Toledo S.Algorithms and Data Structures for Flash Memories[J].ACM Computing Surveys,2005,37(2):138-163.

[9]張曉寧，孫麗君.一種改進(jìn)的小波閾值信號(hào)去噪方法[J].電子科技，2012（11）:15-17.ZHANG Xiao-ning，SUN Li-jun.An improved method for wavelet threshold signal demonizing[J].Electronic Science and Technology，2012（11）:15-17.

[10]楊昊.CUDA下局部閾值和二值函數(shù)的邊緣檢測(cè)[J].電子科技，2014（3）:52-54.YANG Hao.Local threshold and boolean function edge detection alorithm using CUDA [J].Electronic Science and Technology，2014（3）:52-54.