SSD中一種地址映射算法研究

馬福祥

（青海師范大學 計算機學院，青海 西寧810008）

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

1 SSD存儲介質介紹

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

2 SSD內部結構分析

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

圖1 固態硬盤總體結構圖Fig.1 Structure diagram of the SSD

SSD是以硬盤的替代者的姿態出現的，為了與現有系統無縫對接，SSD必須對外提供塊接口，使主機端所看到的SSD是一個和HDD一樣的塊設備。為了達到模擬塊設備的目的，SSD中需要FTL作為中間層，如圖2所示，它由3部分組成，Address mapping(地址映射)、Wear leveling(損耗平衡)和Garbage collection(垃圾回收)。從圖可知，FTL從主機文件系統接收塊級請求，經過FTL的處理，產生Flash的各種控制命令。

Flash中每個塊都有一定的擦寫次數限制。如果沒有合理的管理機制，SSD在幾萬次的擦寫后就可能損壞。為了延長Flash芯片的整體壽命，增強可靠性，就要在所有的塊之間平衡擦除次數，這種技術被稱為損耗均衡。這方面的研究成果文獻已經很多，基本方法有動態損耗平衡和靜態損耗平衡。動態損耗平就是在請求到達時，選取擦除次數較少的塊作為請求的物理地址。靜態損耗平衡的基本做法是將冷數據從原塊取出，存放在擦除次數過多的塊，原來存放冷數據的塊被釋放出來，接受熱數據的擦寫。

圖2 固態硬盤結構框圖Fig.2 Structure diagram of the SSD

所謂的垃圾回收是指當需要釋放一部分空閑空間時，此塊內既有過時或者作廢的數據頁也包含有有效的數據頁，就需要把有效數據和無效數據進行分離，把所有有效數據重新移動到其它塊中，把不包含有效數據的塊進行擦除來釋放自由空間。其過程可以簡單地概括為，選擇回收對象，回收預處理和擦除整個塊3個步驟。

3 地址的映射改進算法

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

圖3 頁地址映射Fig.3 Page address mapping

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

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

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

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

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

4 結束語

文中提出了一種的基于頁地址映射和混合地址映射相互轉化的策略。當映射表沒達到閥值時該算法映射速度快，空間利用率高。當超過閥值[9-10]時采用混合地址映射，避免了存儲映射表所需的大空間，浪費過多的系統資源和映射表的更新也相當頻繁的問題。

[1]葉朝鋒,黃松嶺,徐云.基于SATA的嵌入式高速大容量數據存儲系統設計[J].電測與儀表，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]謝長生,李博等:基于片內SRAM的固態硬盤轉換層設計[J].計算機科學，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算法設計與實現[J].計算機測量與控制,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].電子科技，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下局部閾值和二值函數的邊緣檢測[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.