一種多路flash存儲結(jié)構(gòu)的磨損均衡分析

1存儲了存儲的存儲環(huán)境flash內(nèi)存（也稱為內(nèi)存）是一種功率小、體積大、抗災(zāi)、能耗低、數(shù)據(jù)丟失等特點。隨著近年來Flash存儲器存儲容量和穩(wěn)定性等技術(shù)的突破性發(fā)展,越來越多的嵌入式系統(tǒng)或移動設(shè)備采用Flash存儲器作為存儲介質(zhì)。例如,在便攜式設(shè)備中使用Flash存儲器,低能耗的特點將使得這類使用電池的設(shè)備能夠工作更長的時間,工廠中嵌入式控制系統(tǒng)常常需要能夠承受劇烈顫動的影響,這類顫動對磁盤系統(tǒng)將造成嚴(yán)重?fù)p壞,而Flash存儲器正適合在這樣的環(huán)境中使用。Flash存儲介質(zhì)在進(jìn)行讀寫擦除時具有一定時間的編程操作延遲,隨著大數(shù)據(jù)的應(yīng)用不斷增多,在應(yīng)對大量突發(fā)性寫操作時往往響應(yīng)時間較長,不能很好地滿足實時性要求。因此,采用多芯片并行讀寫來提高存儲空間響應(yīng)效率的思想2多芯片性能整合通用Flash存儲器的類型主要是NOR型和NAND型。由于NAND型芯片容量大、價格低,在需要存儲大數(shù)據(jù)量的系統(tǒng)中廣泛使用。現(xiàn)有系統(tǒng)中一般都使用NAND型芯片作為數(shù)據(jù)存儲器件。NAND型芯片以頁(512B)為讀寫單位,以塊(128KB)為擦除單位。通過整合多個NAND型芯片的多路并行存儲結(jié)構(gòu),采用模N算法使連續(xù)的Flash邏輯頁被分配至不同的物理芯片上。多路結(jié)構(gòu)使得某些時候讀寫擦除操作的編程延遲等待基本被忽略,但是多個讀寫事務(wù)并發(fā)時讀寫隊列中相鄰頁的邏輯頁號可能取相同余值而無法發(fā)揮多路讀寫效率;同時該算法沒有考慮到寫操作在邏輯空間分布不均時會導(dǎo)致各芯片間無法實現(xiàn)Flash存儲的磨損均衡。目前熱數(shù)據(jù)判斷方法ChangandKuo本文提出基于數(shù)據(jù)訪問頻率的熱數(shù)據(jù)判斷方法,不僅在垃圾回收的時候能根據(jù)此熱數(shù)據(jù)判斷方法在單個芯片中選擇廢棄塊回收,尤其重要的是能在數(shù)據(jù)寫入的時候判斷寫入的數(shù)據(jù)是否熱數(shù)據(jù),將熱數(shù)據(jù)較平均地分布在各個芯片上,使得垃圾回收的時候不需要中斷正在進(jìn)行的寫操作并且各個芯片之間能滿足磨損均衡。3多段并行存儲結(jié)構(gòu)本節(jié)介紹多路并行Flash存儲結(jié)構(gòu),在此基礎(chǔ)上討論多路并行寫入的策略和基于數(shù)據(jù)訪問頻率的熱數(shù)據(jù)判斷方法。3.1路的存儲結(jié)構(gòu)在多路并行的存儲系統(tǒng)中采用NAND型芯片作為數(shù)據(jù)存儲器件。通常NAND型芯片的讀寫擦除操作分為2個階段:設(shè)置階段和編程階段(見表1)多路的存儲體系結(jié)構(gòu)如圖2所示,即由多個NAND型芯片組合而成,多個芯片形成一個并行多路結(jié)構(gòu),每個芯片都能獨立地操作芯片內(nèi)的一個閃存單元。通過多路并行I/O來忽略Flash芯片讀寫擦除操作時的編程延遲,即CPU下達(dá)寫或擦除指令后不必等待Flash芯片編程結(jié)束而在另一個芯片上啟動下一步的讀寫操作(圖1(b))。多路并行結(jié)構(gòu)能夠應(yīng)對突發(fā)大數(shù)據(jù)量的寫操作,減少系統(tǒng)編程等待時間以提高實時系統(tǒng)的讀寫響應(yīng)速度。3.2熱數(shù)據(jù)的判斷使用多路Flash存儲方法通常采用多路并行寫入技術(shù)。本文采用的自適應(yīng)多路寫入機(jī)制,其寫入過程如下:(1)將多個Flash芯片組織成循環(huán)鏈表,設(shè)定寫操作在該鏈表上移動,即寫操作都是寫循環(huán)鏈表中的下一個芯片。(2)在數(shù)據(jù)寫入芯片之前的地址翻譯過程中給出熱數(shù)據(jù)判斷,若數(shù)據(jù)是非熱數(shù)據(jù)則直接寫入下一個芯片中,若數(shù)據(jù)是熱數(shù)據(jù)則判斷下一個將寫入的芯片中含有的熱數(shù)據(jù)比例是否達(dá)到一個控制閾值,如果沒有達(dá)到則寫入該芯片中。若達(dá)到了則跳過該芯片至循環(huán)鏈表的下一個芯片進(jìn)行判斷,如圖3所示。(3)當(dāng)前芯片的空閑空間不足而不得不等待回收算法完成垃圾回收時,如果事務(wù)沒有實時性要求,則等待芯片完成垃圾回收后進(jìn)行寫操作。(4)如果當(dāng)前芯片的空閑空間不足而事務(wù)要求高實時性,則跳過該存儲芯片移動至循環(huán)鏈表中下一個芯片,等待事務(wù)執(zhí)行結(jié)束后該芯片再進(jìn)行垃圾回收。上述機(jī)制使得熱數(shù)據(jù)不會過多集中在單一芯片上造成產(chǎn)生大量廢棄塊而頻繁進(jìn)行垃圾回收操作,可以較好地實現(xiàn)芯片之間的耗損均衡;當(dāng)數(shù)據(jù)被分配到指定芯片中以后在該芯片上的分配和垃圾回收操作則可以沿用目前已經(jīng)成熟的存儲管理方法3.3表lbainfo內(nèi)消極電路根據(jù)對磁盤文件系統(tǒng)訪問追蹤研究表明,當(dāng)有大量數(shù)據(jù)訪問情況下,超過2/3的寫操作是集中在少量的磁盤數(shù)據(jù)上的,也就是說可以假設(shè)數(shù)據(jù)訪問是近似滿足雙峰分布的本文提出的基于數(shù)據(jù)訪問頻率的熱數(shù)據(jù)判斷方法是用一個固定大小的表LBAinfo來保存LBA(LogicalBlockAddress)地址和訪問次數(shù)。LBA是數(shù)據(jù)訪問的單位。Flash的讀操作并不會引起數(shù)據(jù)的重寫和塊擦除,這里的訪問也就特指寫操作。表LBAinfo中元組的結(jié)構(gòu)(見圖4)由一個記錄LBA的域、一個記錄訪問次數(shù)的C位計數(shù)器以及一個記錄衰減操作次數(shù)的H位計數(shù)器組成。參數(shù)含義見表2。數(shù)據(jù)訪問頻繁與否和時間是有關(guān)的,即一塊頻繁訪問的數(shù)據(jù)在經(jīng)過某段時間后可能會成為非頻繁訪問的數(shù)據(jù),因此,將表LBAinfo設(shè)置為固定大小(略大于時間段內(nèi)熱數(shù)據(jù)個數(shù))并且引入一個衰減過程。衰減過程負(fù)責(zé)在一段時間后將表LBAinfo中的C位計數(shù)器作衰減操作,并將一些非熱LBA移出表,以保證記錄的訪問頻率取決于當(dāng)前時間點以前的一段歷史時間段?；跀?shù)據(jù)訪問頻率的熱數(shù)據(jù)判斷的策略是:(1)當(dāng)訪問一個LBA時,先在表LBAinfo中查找是否存在這個LBA,如果找到,在其C位計數(shù)器上加1,然后進(jìn)行判斷。設(shè)A為C位計數(shù)器的值,B為H位計數(shù)器的值,令W=A+B。數(shù)據(jù)熱判斷的規(guī)則是若W值大于等于2(2)如果表LBAinfo是被初始化后裝載率第1次達(dá)到給定閾值K時,或者在后來每次表滿時都執(zhí)行一次衰減過程,即將所有的C位計數(shù)器的值都作減1操作,將所有的H位計數(shù)器的值都作加1操作,當(dāng)C位計數(shù)器的值被減為-1時將此LBA元組移出表LBAinfo;若執(zhí)行一次以后表仍滿則循環(huán)執(zhí)行此過程直到表不滿為止。由于表中一定存在非熱數(shù)據(jù),因此循環(huán)執(zhí)行此操作的最多次數(shù)不會超過2(3)當(dāng)表LBAinfo中某個元組的C位計數(shù)器和H位計數(shù)器在進(jìn)行加1操作溢出時保持其為計數(shù)器的最大值不變。在執(zhí)行衰減過程時,C位計數(shù)器值表示訪問該LBA次數(shù)與執(zhí)行衰減過程次數(shù)的差值,值為0的LBA仍然會保存在表中,只有值為-1的時候才會從表中移出。即新插入表中的LBA會經(jīng)過2次衰減過程,并且在這2次衰減過程之內(nèi)并沒有再被訪問過才會移出表,這就保證對于每個移出表的LBA都是經(jīng)過一段歷史時間的積累后才作出是非熱數(shù)據(jù)判斷才將其移出表的。這段歷史時間即2次衰減過程之中進(jìn)行寫操作次數(shù)是由執(zhí)行衰減過程前即將被移出表的非熱數(shù)據(jù)個數(shù)決定的。熱數(shù)據(jù)個數(shù)可以由R求出其上限,因此,2次衰減過程間隔的下限可以由表LBAinfo大小N決定。熱數(shù)據(jù)判斷的閾值(由H決定),執(zhí)行衰減操作的頻率(由N,K決定)以及記錄過去訪問歷史長短(由C決定)可由需要自行設(shè)定,因此,更加準(zhǔn)確和靈活。4lbaindex[n]的更換加標(biāo)算法實驗的平臺是普通的AMD臺式機(jī)(AMDAthlonXP1.54GHz,256MB)。熱數(shù)據(jù)判斷是基于某個歷史段上對數(shù)據(jù)的訪問,因此,在本實驗中在經(jīng)過N次寫操作后對熱數(shù)據(jù)進(jìn)行判斷,假設(shè)在熱數(shù)據(jù)的判斷過程中不會出現(xiàn)熱數(shù)據(jù)變?yōu)榉菬釘?shù)據(jù)的情況。實驗輸入數(shù)據(jù)采用隨機(jī)生成滿足雙峰分布為了使LBA在表LBAinfo中查找時間復(fù)雜度降低,減少LBA排序在表中移動次數(shù),需要增加一個帶標(biāo)志位的指針數(shù)組LBAIndex[N],用于為表LBAinfo中的元組按LBA大小排序。當(dāng)表中有元組需要移出時并不需要在LBAIndex[N]或是表LBAinfo中刪除元組,只需要將LBAIndex[N]中該元素的標(biāo)志位置0即可。由于查找和插入可以同時進(jìn)行,因此選擇折半插入方法使得指針數(shù)組LBAIndex[N]根據(jù)LBA地址有序。在進(jìn)行LBA查找時只需復(fù)雜度為log(N)的比較次數(shù)。在查找成功的情況下需要1次計數(shù)器自增操作;在查找失敗情況下,需要在指針數(shù)組上對LBA進(jìn)行排序操作,但在查找過程中已經(jīng)確定了插入位置,因此,只需移動k個指針,在指針數(shù)組中大多數(shù)情況下無效的指針存在多個,指針平均移動的個數(shù)k≈N/(m+1)(N是指針數(shù)組大小,m是無效指針個數(shù))。令a表示生成數(shù)據(jù)時是熱LBAs而被基于頻率的熱數(shù)據(jù)判斷方法錯誤判斷為非熱LBAs的個數(shù),b表示生成數(shù)據(jù)時是非熱LBAs而被2-LRU錯誤判斷為熱LBAs的個數(shù),c是LBAs總數(shù),那么a/c是基于數(shù)據(jù)訪問頻率的熱數(shù)據(jù)判斷方法的判斷錯誤率,而b/c是2-LRU判斷方法的判斷錯誤率。圖5比較在不同R下基于數(shù)據(jù)訪問頻率的熱數(shù)據(jù)判斷方法的判斷錯誤率和2-LRU判斷方法的判斷錯誤率。從圖中可以看出基于頻率的熱數(shù)據(jù)的判斷錯誤率是2-LRU方法的判斷錯誤率的1/3左右,即基于頻率的熱數(shù)據(jù)判斷方法更為準(zhǔn)確?；陬l率的熱數(shù)據(jù)判斷方法產(chǎn)生的錯誤判斷是由于數(shù)據(jù)訪問分布原因,少量訪問次數(shù)剛好是熱數(shù)據(jù)判斷閾值H的數(shù)據(jù)在執(zhí)行衰減過程時曾被判斷為非熱數(shù)據(jù)而移出過表外,在實驗最終進(jìn)行統(tǒng)計判斷時因為移出表前的訪問次數(shù)沒有計算到,被判斷為非熱數(shù)據(jù)。2-LRU熱數(shù)據(jù)判斷方法是將在一段時間內(nèi)訪問超過2次的數(shù)據(jù)都判斷為熱數(shù)據(jù)。也就是說基于頻率的熱數(shù)據(jù)判斷方法將一些在熱數(shù)據(jù)劃分中處于臨界的熱數(shù)據(jù)判斷為非熱數(shù)據(jù),這對于選出更為頻繁訪問的數(shù)據(jù)而將它們均衡分布到各個芯片當(dāng)中是幾乎沒有影響的;相反2-LRU方法將非熱數(shù)據(jù)判斷為熱數(shù)據(jù)這會很大程度