NAND閃存的自適應(yīng)閃存映射層設(shè)計(jì)

NAND閃存的自適應(yīng)閃存映射層設(shè)計(jì)

閃存存儲(chǔ)器主要分為NAND和XOR兩種類型，其中NAND型是專為數(shù)據(jù)存儲(chǔ)設(shè)計(jì)。本文的閃存映射方法主要是針對(duì)NAND類型的閃存芯片。一個(gè)NAND類型的閃存芯片的存儲(chǔ)空間是由塊(Block)構(gòu)成，每個(gè)塊又劃分為固定大小的頁(yè)，塊是擦寫操作的最小單元，頁(yè)是讀寫操作的最小單元。由于閃存存儲(chǔ)器的硬件特性，閃存的更新操作有自己的特點(diǎn)，在對(duì)數(shù)據(jù)進(jìn)行更新前需要先進(jìn)行擦寫操作，然后才能將新數(shù)據(jù)寫入，并且擦寫操作是以塊為單位，讀寫操作是以頁(yè)為單位。由于擦寫操作涉及的最小單元遠(yuǎn)大于讀寫操作的最小單元，需要對(duì)一個(gè)擦寫塊內(nèi)不需要更新的數(shù)據(jù)提供有效的保護(hù)。在閃存存儲(chǔ)管理中普遍采用的數(shù)據(jù)更新方法是非本地更新的方法(Out-place Update)，通過(guò)構(gòu)建閃存映射層，在進(jìn)行更新操作時(shí)，將更新的數(shù)據(jù)寫到其他空閑的存儲(chǔ)位置，利用內(nèi)存中的地址映射表記錄數(shù)據(jù)存儲(chǔ)位置的變化。非本地更新的方法避免了更新時(shí)整塊數(shù)據(jù)的讀出寫入，從而減少數(shù)據(jù)復(fù)制次數(shù)和塊擦寫次數(shù)，提高系統(tǒng)的整體性能。閃存映射層是閃存進(jìn)行非本地更新存儲(chǔ)管理的關(guān)鍵，主要由地址映射和垃圾回收機(jī)制兩部分構(gòu)成。

根據(jù)地址映射粒度的不同，可以將地址映射方法分為三種：頁(yè)映射(Page Mapping)、塊映射(BlockingMapping)和混合映射(Hybrid Mapping)。頁(yè)映射是以頁(yè)為單位進(jìn)行地址映射，在內(nèi)存中保存基手頁(yè)的映射表，每一邏輯頁(yè)都有一項(xiàng)與之對(duì)應(yīng)的物理頁(yè)，頁(yè)映射方法具有靈活性高的優(yōu)點(diǎn)，但由于需要為每個(gè)邏輯頁(yè)面建立地址映射表項(xiàng)，需要占用大量?jī)?nèi)存空間。塊映射算法是以塊為單位進(jìn)行地址映射，邏輯塊內(nèi)地址偏移與物理塊內(nèi)偏移保持一致。該方法僅需要在內(nèi)存中保留塊映射表，建立從邏輯塊到物理塊的映射關(guān)系，塊映射算法優(yōu)點(diǎn)是內(nèi)存占用量少，不受閃存容量增大的影響，缺點(diǎn)是在處理小數(shù)據(jù)更新上性能較差，一小塊數(shù)據(jù)的更新會(huì)引起對(duì)整個(gè)塊內(nèi)容的復(fù)制?；旌嫌成浞椒ńY(jié)合了塊映射和頁(yè)映射的優(yōu)點(diǎn)，首先以塊映射方法建立邏輯塊和物理塊的映射關(guān)系，同時(shí)對(duì)塊內(nèi)數(shù)據(jù)采用頁(yè)映射方法組織?；旌嫌成渌惴▋?nèi)存空間占用量少，同時(shí)對(duì)小數(shù)據(jù)更新比塊映射算法更加靈活、代價(jià)少。

垃圾回收是閃存存儲(chǔ)系統(tǒng)特有的空間管理機(jī)制。在閃存存儲(chǔ)管理中，由于采用非本地更新的方法，當(dāng)閃存的存儲(chǔ)空間消耗完時(shí)，就需要回收無(wú)效數(shù)據(jù)占用的空間。為了回收無(wú)效數(shù)據(jù)占用的空間，必須先將擦寫單位內(nèi)的有效數(shù)據(jù)轉(zhuǎn)移到其他空閑區(qū)域，然后擦寫整個(gè)單元，回收過(guò)程主要涉及有效數(shù)據(jù)復(fù)制和塊擦寫兩個(gè)耗時(shí)耗能的操作。垃圾回收工作需要從閃存中選擇回收對(duì)象，轉(zhuǎn)移有效數(shù)據(jù)，最后完成對(duì)象擦除。進(jìn)行垃圾回收時(shí)選擇不同的區(qū)域進(jìn)行擦除，代價(jià)是不同的，垃圾回收器設(shè)計(jì)的目就是要減少有效數(shù)據(jù)復(fù)制和塊擦寫次數(shù)，以提高系統(tǒng)性能。不同粒度的地址映射方法在不同寫模式下，垃圾回收的性能有較大差異。在此給出了一種能夠根據(jù)寫模式進(jìn)行自適應(yīng)判斷的閃存映射方法。通過(guò)對(duì)順序?qū)懞碗S機(jī)寫進(jìn)行判斷，將順序?qū)憦碾S機(jī)寫中分離，對(duì)順序?qū)懖捎脡K映射組織日記塊數(shù)據(jù)，對(duì)隨機(jī)寫采用混合映射方法，并為熱數(shù)據(jù)分配多個(gè)日記塊，延遲對(duì)熱數(shù)據(jù)的垃圾回收，以提高垃圾回收的性能。通過(guò)實(shí)驗(yàn)表明這里構(gòu)建的閃存映射方法能夠在不需要占用大量的內(nèi)存空間前提下，減少垃圾回收過(guò)程的有效數(shù)據(jù)復(fù)制和塊擦寫，從而優(yōu)化閃存系統(tǒng)的性能。

1 閃存存儲(chǔ)系統(tǒng)的體系結(jié)構(gòu)

本文構(gòu)建的閃存存儲(chǔ)管理的體系結(jié)構(gòu)見(jiàn)圖1，將系統(tǒng)分為文件系統(tǒng)層、閃存管理層和閃存驅(qū)動(dòng)層。閃存映射層負(fù)責(zé)對(duì)閃存設(shè)備進(jìn)行存儲(chǔ)管理，通過(guò)地址映射和垃圾回收技術(shù)將閃存轉(zhuǎn)換為塊設(shè)備。地址映射主要完成閃存塊的分配和地址映射信息管理，負(fù)責(zé)處理文件系統(tǒng)層的讀寫請(qǐng)求，將文件系統(tǒng)提供的邏輯地址轉(zhuǎn)換為閃存的物理地址；垃圾回收則負(fù)責(zé)回收無(wú)效數(shù)據(jù)占用的空間，主要涉及有效數(shù)據(jù)復(fù)制和塊擦寫兩個(gè)耗時(shí)耗能的過(guò)程。



1.1?地址映射結(jié)構(gòu)

閃存映射層的作用是將文件系統(tǒng)的邏輯地址轉(zhuǎn)換為閃存的物理地址，因此需要在內(nèi)存建立邏輯地址和物理地址的映射關(guān)系，同時(shí)管理物理地址的狀態(tài)變換。本文通過(guò)圖2所示的地址映射結(jié)構(gòu)進(jìn)行地址映射管理，將文件系統(tǒng)提供的邏輯地址分為四部分：邏輯組號(hào)、組內(nèi)塊號(hào)、塊內(nèi)頁(yè)號(hào)和頁(yè)內(nèi)偏移地址。其中邏輯頁(yè)和邏輯塊大小分別與閃存存儲(chǔ)器的讀寫頁(yè)和擦寫塊大小相同。每個(gè)邏輯組是由N個(gè)連續(xù)的邏輯塊構(gòu)成，N可以根據(jù)應(yīng)用類型進(jìn)行設(shè)置，在圖2中N的數(shù)目為2。將閃存存儲(chǔ)器中的物理塊分為數(shù)據(jù)塊和日記塊，數(shù)據(jù)塊用于存放原數(shù)據(jù)，日記塊用于存放更新數(shù)據(jù)，同時(shí)又將日記塊劃分為順序日記塊和隨機(jī)日記塊。數(shù)據(jù)塊和順序日記塊內(nèi)的內(nèi)容是以塊映射方法組織，而隨機(jī)日記塊采用混合映射粒度組織數(shù)據(jù)。邏輯塊和數(shù)據(jù)塊通過(guò)內(nèi)存中的塊映射表建立對(duì)應(yīng)關(guān)系，每一個(gè)邏輯塊都有惟一的數(shù)據(jù)塊與之對(duì)應(yīng)。與邏輯組對(duì)應(yīng)的N個(gè)數(shù)據(jù)塊構(gòu)成一個(gè)數(shù)據(jù)組。每個(gè)順序日記塊對(duì)應(yīng)惟一的數(shù)據(jù)塊，在對(duì)數(shù)據(jù)塊進(jìn)行順序更新操作時(shí)，為其分配順序日記塊存儲(chǔ)更新數(shù)據(jù)。每個(gè)數(shù)據(jù)組可以根據(jù)需求動(dòng)態(tài)分配多個(gè)隨機(jī)日記塊，日記塊的數(shù)目是由該組數(shù)據(jù)訪問(wèn)的冷熱屬性來(lái)決定的，對(duì)于有頻繁更新數(shù)據(jù)的組會(huì)動(dòng)態(tài)分配較多的日記塊。隨機(jī)日記塊是組內(nèi)共享的，對(duì)組內(nèi)任一數(shù)據(jù)塊的隨機(jī)更新數(shù)據(jù)都可以存儲(chǔ)到隨機(jī)日記塊中，從而提高空間利用率。為了提高查找效率，對(duì)有隨機(jī)日記塊的數(shù)據(jù)組，在內(nèi)存中構(gòu)建組內(nèi)頁(yè)映射表，記錄邏輯地址對(duì)應(yīng)的更新數(shù)據(jù)在隨機(jī)日記塊內(nèi)的存儲(chǔ)位置，通過(guò)組內(nèi)頁(yè)映射表，在進(jìn)行讀取時(shí)不需要遍歷日記塊來(lái)獲取數(shù)據(jù)的存儲(chǔ)位置，從而提高系統(tǒng)性能。



1.2?寫請(qǐng)求處理過(guò)程

地址映射的主要作用是通過(guò)在內(nèi)存中構(gòu)建地址映射表，將文件系統(tǒng)的邏輯地址轉(zhuǎn)換為物理地址，在系統(tǒng)進(jìn)行讀請(qǐng)求時(shí)，利用地址映射表查找到存儲(chǔ)在閃存設(shè)備中的數(shù)據(jù)，在系統(tǒng)進(jìn)行寫請(qǐng)求時(shí)在閃存設(shè)備上查找空閑位置存儲(chǔ)數(shù)據(jù)，更新地址映射表，記錄數(shù)據(jù)的新存儲(chǔ)位置，同時(shí)將舊數(shù)據(jù)標(biāo)記為無(wú)效。

在本文中為每個(gè)數(shù)據(jù)塊設(shè)定狀態(tài)位來(lái)標(biāo)記該塊當(dāng)前的訪問(wèn)模式，將每個(gè)數(shù)據(jù)塊訪問(wèn)模式分為順序?qū)懞碗S機(jī)寫。在進(jìn)行寫請(qǐng)求時(shí)，首先計(jì)算出數(shù)據(jù)所屬的邏輯塊和塊內(nèi)偏移地址，判斷數(shù)據(jù)所在塊的訪問(wèn)模式，如果所在塊是順序?qū)懀脡K映射表，將數(shù)據(jù)寫到順序日記塊中。如果所在塊為隨機(jī)寫，將更新數(shù)據(jù)寫到數(shù)據(jù)組的隨機(jī)日記塊中。訪問(wèn)模式主要是根據(jù)過(guò)去的數(shù)據(jù)存儲(chǔ)訪問(wèn)行為進(jìn)行判斷的，如果對(duì)某一邏輯地址在短時(shí)間內(nèi)進(jìn)行了多次更新，認(rèn)為系統(tǒng)對(duì)該地址進(jìn)行的是隨機(jī)寫，對(duì)其所屬塊將采用混合映射方法進(jìn)行存儲(chǔ)管理，以優(yōu)化小數(shù)據(jù)頻繁更新導(dǎo)致的性能問(wèn)題。訪問(wèn)模式的判斷是通過(guò)內(nèi)存中的雙鏈表來(lái)實(shí)現(xiàn)的，如圖3所示。在內(nèi)存中構(gòu)建兩定長(zhǎng)的地址鏈表，一個(gè)鏈表為順序鏈表，另一個(gè)鏈表為隨機(jī)鏈表。順序鏈表中保存最近進(jìn)行順序?qū)懙臄?shù)據(jù)塊，而隨機(jī)鏈表中保留最近進(jìn)行隨機(jī)寫的數(shù)據(jù)組。兩鏈表都根據(jù)最后一次訪問(wèn)時(shí)間進(jìn)行排序，將鏈表分為最近最少訪問(wèn)端(LRU)和最近最多訪問(wèn)端(MRU)，在每次進(jìn)行更新操作時(shí)，將更新數(shù)據(jù)所在的塊或組提升到鏈表的最近最多訪問(wèn)端。當(dāng)對(duì)數(shù)據(jù)塊首次進(jìn)行更新操作時(shí)，判斷該數(shù)據(jù)塊進(jìn)行的是順序?qū)懀瑯?biāo)記該塊的訪問(wèn)狀態(tài)為順序?qū)?，并將該?shù)據(jù)塊添加到順序鏈表中。如果數(shù)據(jù)塊內(nèi)已更新過(guò)的數(shù)據(jù)在短時(shí)間內(nèi)再一次被更新，即順序日記塊內(nèi)對(duì)應(yīng)的存儲(chǔ)空間已填充數(shù)據(jù)，判斷該數(shù)據(jù)塊的訪問(wèn)模式為隨機(jī)寫，將其從順序鏈表中刪除，標(biāo)記該塊的訪問(wèn)狀態(tài)為隨機(jī)寫，同時(shí)添加該塊所在的數(shù)據(jù)組到隨機(jī)鏈表中，以后對(duì)該塊的更新數(shù)據(jù)將存儲(chǔ)到隨機(jī)日記塊中，直到該數(shù)據(jù)組從隨機(jī)鏈表中刪除。



順序鏈表的項(xiàng)數(shù)設(shè)有上限值，該值為系統(tǒng)中分配的順序日記塊數(shù)目。當(dāng)表項(xiàng)超過(guò)上限值時(shí)，將從順序鏈表的最近最少訪問(wèn)端刪除數(shù)據(jù)塊，合并日記塊和數(shù)據(jù)塊中的有效數(shù)據(jù)。當(dāng)順序日記塊完全更新時(shí)，即數(shù)據(jù)塊內(nèi)的數(shù)據(jù)完全無(wú)效，采用切換操作，用順序日記塊替換數(shù)據(jù)塊，并將該塊從順序鏈表中刪除。在本文中始終保留了一定數(shù)據(jù)的順序日記塊，以優(yōu)化系統(tǒng)的順序?qū)憽?br>
位于隨機(jī)鏈表中的數(shù)據(jù)組，當(dāng)需要新的存儲(chǔ)空間時(shí)，將為其分配新的隨機(jī)日記塊。隨機(jī)鏈表的項(xiàng)數(shù)也設(shè)有上限值，當(dāng)超過(guò)上限值時(shí)，將從最近最少訪問(wèn)端刪除數(shù)據(jù)組，將隨機(jī)日記塊和數(shù)據(jù)塊中的數(shù)據(jù)合并，生成新的數(shù)據(jù)塊，同時(shí)重設(shè)數(shù)據(jù)塊的狀態(tài)位，當(dāng)再一次進(jìn)行數(shù)據(jù)更新時(shí)，將重新進(jìn)行訪問(wèn)模式判斷。采用該方法能夠?qū)⒗鋽?shù)據(jù)及時(shí)從鏈表刪除，回收日記塊占用的存儲(chǔ)空間和頁(yè)映射表占用的內(nèi)存空間。

1.3?垃圾回收機(jī)制

由于采用日記結(jié)構(gòu)進(jìn)行存儲(chǔ)管理，在長(zhǎng)時(shí)間運(yùn)行時(shí)需要進(jìn)行垃圾回收。進(jìn)行垃圾回收時(shí)需要考慮的問(wèn)題是回收時(shí)機(jī)和回收對(duì)象選擇，以及回收方法。垃圾回收機(jī)制是建立在地址映射方法基礎(chǔ)上，主要由兩部分構(gòu)成：擦寫進(jìn)程和回收進(jìn)程。擦寫進(jìn)程是專門負(fù)責(zé)擦寫操作，它的優(yōu)先級(jí)比較低。在系統(tǒng)空閑的時(shí)候，擦寫進(jìn)程才會(huì)輪到執(zhí)行，每次該進(jìn)程啟動(dòng)，只負(fù)責(zé)擦寫一個(gè)塊，以免影響到正常的I／O性能?；厥者M(jìn)程是當(dāng)系統(tǒng)中的日記塊消耗完或閃存中的空閑塊低于某閾值，將從日記塊和數(shù)據(jù)塊中選擇回收對(duì)象，將有效數(shù)據(jù)復(fù)制到其他空閑區(qū)域中，將其交給擦寫進(jìn)程處理，回收存儲(chǔ)空間。

本文回收進(jìn)程主要包括兩部分，對(duì)順序日記塊的回收和對(duì)隨機(jī)日記塊的回收。當(dāng)系統(tǒng)中的順序日記塊消耗完全時(shí)，將從順序鏈表的最近最少訪問(wèn)端選擇日記塊，利用數(shù)據(jù)塊和順序日記塊內(nèi)數(shù)據(jù)組織有序的特點(diǎn)，采用如圖4所示的方法，將數(shù)據(jù)塊中的有效數(shù)據(jù)復(fù)制到日記塊中，用日記塊來(lái)替換數(shù)據(jù)塊，擦除數(shù)據(jù)塊，回收數(shù)據(jù)塊占用的空間。對(duì)于隨機(jī)日記塊，將從隨機(jī)鏈表中選擇具有最多無(wú)效數(shù)據(jù)的數(shù)據(jù)組，回收方法是從數(shù)據(jù)組中選擇兩個(gè)或多個(gè)具有較多無(wú)效數(shù)據(jù)的日記塊，將日記塊中的有效數(shù)據(jù)復(fù)制到數(shù)據(jù)組的其他隨機(jī)日記塊中，如圖5所示，擦除選中日記塊，回收日記塊空間。



通過(guò)根據(jù)順序日記塊和隨機(jī)日記塊數(shù)據(jù)組織特點(diǎn)分別采用不同的回收方法，從而優(yōu)化了垃圾回收的性能。對(duì)于順序日記塊，將數(shù)據(jù)塊與日記塊內(nèi)有效數(shù)據(jù)合并，用日記塊替換數(shù)據(jù)塊，從而減少回收過(guò)程中的有效數(shù)據(jù)復(fù)制。而對(duì)于隨機(jī)日記通過(guò)選擇無(wú)效數(shù)據(jù)最多的塊進(jìn)行回收，同時(shí)利用本文的多日記塊機(jī)制，將有效數(shù)據(jù)存儲(chǔ)到其他日記塊。從而不需要合并數(shù)據(jù)塊和日記塊的數(shù)據(jù)，減少了小數(shù)據(jù)更新情況下的有效數(shù)據(jù)的復(fù)制和塊擦寫次數(shù)，優(yōu)化了垃圾回收的性能。

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

在Linux系統(tǒng)中實(shí)現(xiàn)了本文的存儲(chǔ)管理方法，同時(shí)利用Linux自帶的閃存模擬器，模擬閃存存儲(chǔ)器的功能，在該模擬器上對(duì)本文的閃存映射方法展開(kāi)研究，并與NFTL和混合映射方法進(jìn)行比較，NFTL是Linux系統(tǒng)實(shí)現(xiàn)的塊映射方法。在實(shí)驗(yàn)中采用額外寫操作次數(shù)和擦除操作次數(shù)來(lái)衡量閃存系統(tǒng)性能的標(biāo)準(zhǔn)，其中額外寫操作次數(shù)由實(shí)驗(yàn)中閃存的實(shí)際寫次數(shù)減去用戶請(qǐng)求的寫次數(shù)來(lái)獲取，主要是由垃圾回收時(shí)有效數(shù)據(jù)的復(fù)制產(chǎn)生的。額外擦寫操作次數(shù)是指閃存系統(tǒng)的塊擦寫次數(shù)，是由于日記塊的消耗引起的。采用這兩個(gè)指標(biāo)能夠直接反應(yīng)垃圾回收的性能。首先研究了在進(jìn)行文件和圖像等存取操作下系統(tǒng)的性能。由于僅進(jìn)行圖像存取操作時(shí)，系統(tǒng)的大部分操作是順序?qū)?。圖6所示是三種方法的額外寫操作次數(shù)和擦寫操作次數(shù)對(duì)比情況。從圖6中可以看出本文方法與NFTL方法接近，需要較少的有效數(shù)據(jù)復(fù)制和塊擦寫，而混合映射方法表現(xiàn)較差，尤其是有效數(shù)據(jù)的復(fù)制次數(shù)，明顯多于其他兩種方法。主要是由于本文方法與NFTL能夠利用塊映射方法來(lái)處理順序?qū)懩Ｊ?，在進(jìn)行垃圾回收時(shí)，能夠通過(guò)將數(shù)據(jù)塊的有效數(shù)據(jù)復(fù)制到日記塊中，用日記塊替換數(shù)據(jù)塊，而不需要分配新的數(shù)據(jù)塊，減少有效數(shù)據(jù)復(fù)制和塊擦寫。而混合映射方法在進(jìn)行垃圾回收時(shí)，需要分配新的數(shù)據(jù)塊來(lái)合并舊數(shù)據(jù)塊和日記塊中的數(shù)據(jù)，導(dǎo)致系統(tǒng)進(jìn)行大量的復(fù)制操作和擦寫操作，降低垃圾回收的性能。



圖7的實(shí)驗(yàn)結(jié)果是在進(jìn)行圖像存取操作的同時(shí)加入對(duì)局部數(shù)據(jù)進(jìn)行隨機(jī)訪問(wèn)來(lái)獲取的。從結(jié)果可以看出，NFTL方法與混合映射方法的性能接近，都需要較多的額外寫次數(shù)和塊擦寫次數(shù)。本文的方法由于采用寫模式判別機(jī)制，能夠?qū)㈦S機(jī)寫從順序?qū)懼蟹蛛x出來(lái)，對(duì)順序?qū)懖捎脡K映射方法，對(duì)隨機(jī)寫采用混合映射方法進(jìn)行存儲(chǔ)管理，從而垃圾回收次數(shù)較少，優(yōu)化系統(tǒng)性能。


3 結(jié)? 語(yǔ)

在本文中給出一種閃存映射方法，通過(guò)對(duì)數(shù)據(jù)寫模式進(jìn)行區(qū)分，為不同的寫模式提供不同粒度的地址映射方法進(jìn)行存儲(chǔ)管理，從而減少了垃圾回收過(guò)程有效數(shù)據(jù)復(fù)制和塊擦寫，提高了閃存存儲(chǔ)系統(tǒng)的性能。在將來(lái)，還需要進(jìn)一步研究訪問(wèn)屬性的判別方法，減少判斷錯(cuò)誤的情況，進(jìn)一步提升垃圾回收的性能。