NAND閃存的自適應閃存映射層設計

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

根據地址映射粒度的不同，可以將地址映射方法分為三種：頁映射(Page Mapping)、塊映射(BlockingMapping)和混合映射(Hybrid Mapping)。頁映射是以頁為單位進行地址映射，在內存中保存基手頁的映射表，每一邏輯頁都有一項與之對應的物理頁，頁映射方法具有靈活性高的優點，但由于需要為每個邏輯頁面建立地址映射表項，需要占用大量內存空間。塊映射算法是以塊為單位進行地址映射，邏輯塊內地址偏移與物理塊內偏移保持一致。該方法僅需要在內存中保留塊映射表，建立從邏輯塊到物理塊的映射關系，塊映射算法優點是內存占用量少，不受閃存容量增大的影響，缺點是在處理小數據更新上性能較差，一小塊數據的更新會引起對整個塊內容的復制。混合映射方法結合了塊映射和頁映射的優點，首先以塊映射方法建立邏輯塊和物理塊的映射關系，同時對塊內數據采用頁映射方法組織。混合映射算法內存空間占用量少，同時對小數據更新比塊映射算法更加靈活、代價少。

垃圾回收是閃存存儲系統特有的空間管理機制。在閃存存儲管理中，由于采用非本地更新的方法，當閃存的存儲空間消耗完時，就需要回收無效數據占用的空間。為了回收無效數據占用的空間，必須先將擦寫單位內的有效數據轉移到其他空閑區域，然后擦寫整個單元，回收過程主要涉及有效數據復制和塊擦寫兩個耗時耗能的操作。垃圾回收工作需要從閃存中選擇回收對象，轉移有效數據，最后完成對象擦除。進行垃圾回收時選擇不同的區域進行擦除，代價是不同的，垃圾回收器設計的目就是要減少有效數據復制和塊擦寫次數，以提高系統性能。不同粒度的地址映射方法在不同寫模式下，垃圾回收的性能有較大差異。在此給出了一種能夠根據寫模式進行自適應判斷的閃存映射方法。通過對順序寫和隨機寫進行判斷，將順序寫從隨機寫中分離，對順序寫采用塊映射組織日記塊數據，對隨機寫采用混合映射方法，并為熱數據分配多個日記塊，延遲對熱數據的垃圾回收，以提高垃圾回收的性能。通過實驗表明這里構建的閃存映射方法能夠在不需要占用大量的內存空間前提下，減少垃圾回收過程的有效數據復制和塊擦寫，從而優化閃存系統的性能。

1 閃存存儲系統的體系結構

本文構建的閃存存儲管理的體系結構見圖1，將系統分為文件系統層、閃存管理層和閃存驅動層。閃存映射層負責對閃存設備進行存儲管理，通過地址映射和垃圾回收技術將閃存轉換為塊設備。地址映射主要完成閃存塊的分配和地址映射信息管理，負責處理文件系統層的讀寫請求，將文件系統提供的邏輯地址轉換為閃存的物理地址；垃圾回收則負責回收無效數據占用的空間，主要涉及有效數據復制和塊擦寫兩個耗時耗能的過程。



1.1?地址映射結構

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



1.2?寫請求處理過程

地址映射的主要作用是通過在內存中構建地址映射表，將文件系統的邏輯地址轉換為物理地址，在系統進行讀請求時，利用地址映射表查找到存儲在閃存設備中的數據，在系統進行寫請求時在閃存設備上查找空閑位置存儲數據，更新地址映射表，記錄數據的新存儲位置，同時將舊數據標記為無效。

在本文中為每個數據塊設定狀態位來標記該塊當前的訪問模式，將每個數據塊訪問模式分為順序寫和隨機寫。在進行寫請求時，首先計算出數據所屬的邏輯塊和塊內偏移地址，判斷數據所在塊的訪問模式，如果所在塊是順序寫，利用塊映射表，將數據寫到順序日記塊中。如果所在塊為隨機寫，將更新數據寫到數據組的隨機日記塊中。訪問模式主要是根據過去的數據存儲訪問行為進行判斷的，如果對某一邏輯地址在短時間內進行了多次更新，認為系統對該地址進行的是隨機寫，對其所屬塊將采用混合映射方法進行存儲管理，以優化小數據頻繁更新導致的性能問題。訪問模式的判斷是通過內存中的雙鏈表來實現的，如圖3所示。在內存中構建兩定長的地址鏈表，一個鏈表為順序鏈表，另一個鏈表為隨機鏈表。順序鏈表中保存最近進行順序寫的數據塊，而隨機鏈表中保留最近進行隨機寫的數據組。兩鏈表都根據最后一次訪問時間進行排序，將鏈表分為最近最少訪問端(LRU)和最近最多訪問端(MRU)，在每次進行更新操作時，將更新數據所在的塊或組提升到鏈表的最近最多訪問端。當對數據塊首次進行更新操作時，判斷該數據塊進行的是順序寫，標記該塊的訪問狀態為順序寫，并將該數據塊添加到順序鏈表中。如果數據塊內已更新過的數據在短時間內再一次被更新，即順序日記塊內對應的存儲空間已填充數據，判斷該數據塊的訪問模式為隨機寫，將其從順序鏈表中刪除，標記該塊的訪問狀態為隨機寫，同時添加該塊所在的數據組到隨機鏈表中，以后對該塊的更新數據將存儲到隨機日記塊中，直到該數據組從隨機鏈表中刪除。



順序鏈表的項數設有上限值，該值為系統中分配的順序日記塊數目。當表項超過上限值時，將從順序鏈表的最近最少訪問端刪除數據塊，合并日記塊和數據塊中的有效數據。當順序日記塊完全更新時，即數據塊內的數據完全無效，采用切換操作，用順序日記塊替換數據塊，并將該塊從順序鏈表中刪除。在本文中始終保留了一定數據的順序日記塊，以優化系統的順序寫。

位于隨機鏈表中的數據組，當需要新的存儲空間時，將為其分配新的隨機日記塊。隨機鏈表的項數也設有上限值，當超過上限值時，將從最近最少訪問端刪除數據組，將隨機日記塊和數據塊中的數據合并，生成新的數據塊，同時重設數據塊的狀態位，當再一次進行數據更新時，將重新進行訪問模式判斷。采用該方法能夠將冷數據及時從鏈表刪除，回收日記塊占用的存儲空間和頁映射表占用的內存空間。

1.3?垃圾回收機制

由于采用日記結構進行存儲管理，在長時間運行時需要進行垃圾回收。進行垃圾回收時需要考慮的問題是回收時機和回收對象選擇，以及回收方法。垃圾回收機制是建立在地址映射方法基礎上，主要由兩部分構成：擦寫進程和回收進程。擦寫進程是專門負責擦寫操作，它的優先級比較低。在系統空閑的時候，擦寫進程才會輪到執行，每次該進程啟動，只負責擦寫一個塊，以免影響到正常的I／O性能。回收進程是當系統中的日記塊消耗完或閃存中的空閑塊低于某閾值，將從日記塊和數據塊中選擇回收對象，將有效數據復制到其他空閑區域中，將其交給擦寫進程處理，回收存儲空間。

本文回收進程主要包括兩部分，對順序日記塊的回收和對隨機日記塊的回收。當系統中的順序日記塊消耗完全時，將從順序鏈表的最近最少訪問端選擇日記塊，利用數據塊和順序日記塊內數據組織有序的特點，采用如圖4所示的方法，將數據塊中的有效數據復制到日記塊中，用日記塊來替換數據塊，擦除數據塊，回收數據塊占用的空間。對于隨機日記塊，將從隨機鏈表中選擇具有最多無效數據的數據組，回收方法是從數據組中選擇兩個或多個具有較多無效數據的日記塊，將日記塊中的有效數據復制到數據組的其他隨機日記塊中，如圖5所示，擦除選中日記塊，回收日記塊空間。



通過根據順序日記塊和隨機日記塊數據組織特點分別采用不同的回收方法，從而優化了垃圾回收的性能。對于順序日記塊，將數據塊與日記塊內有效數據合并，用日記塊替換數據塊，從而減少回收過程中的有效數據復制。而對于隨機日記通過選擇無效數據最多的塊進行回收，同時利用本文的多日記塊機制，將有效數據存儲到其他日記塊。從而不需要合并數據塊和日記塊的數據，減少了小數據更新情況下的有效數據的復制和塊擦寫次數，優化了垃圾回收的性能。

2 試驗結果與分析

在Linux系統中實現了本文的存儲管理方法，同時利用Linux自帶的閃存模擬器，模擬閃存存儲器的功能，在該模擬器上對本文的閃存映射方法展開研究，并與NFTL和混合映射方法進行比較，NFTL是Linux系統實現的塊映射方法。在實驗中采用額外寫操作次數和擦除操作次數來衡量閃存系統性能的標準，其中額外寫操作次數由實驗中閃存的實際寫次數減去用戶請求的寫次數來獲取，主要是由垃圾回收時有效數據的復制產生的。額外擦寫操作次數是指閃存系統的塊擦寫次數，是由于日記塊的消耗引起的。采用這兩個指標能夠直接反應垃圾回收的性能。首先研究了在進行文件和圖像等存取操作下系統的性能。由于僅進行圖像存取操作時，系統的大部分操作是順序寫。圖6所示是三種方法的額外寫操作次數和擦寫操作次數對比情況。從圖6中可以看出本文方法與NFTL方法接近，需要較少的有效數據復制和塊擦寫，而混合映射方法表現較差，尤其是有效數據的復制次數，明顯多于其他兩種方法。主要是由于本文方法與NFTL能夠利用塊映射方法來處理順序寫模式，在進行垃圾回收時，能夠通過將數據塊的有效數據復制到日記塊中，用日記塊替換數據塊，而不需要分配新的數據塊，減少有效數據復制和塊擦寫。而混合映射方法在進行垃圾回收時，需要分配新的數據塊來合并舊數據塊和日記塊中的數據，導致系統進行大量的復制操作和擦寫操作，降低垃圾回收的性能。



圖7的實驗結果是在進行圖像存取操作的同時加入對局部數據進行隨機訪問來獲取的。從結果可以看出，NFTL方法與混合映射方法的性能接近，都需要較多的額外寫次數和塊擦寫次數。本文的方法由于采用寫模式判別機制，能夠將隨機寫從順序寫中分離出來，對順序寫采用塊映射方法，對隨機寫采用混合映射方法進行存儲管理，從而垃圾回收次數較少，優化系統性能。


3 結? 語

在本文中給出一種閃存映射方法，通過對數據寫模式進行區分，為不同的寫模式提供不同粒度的地址映射方法進行存儲管理，從而減少了垃圾回收過程有效數據復制和塊擦寫，提高了閃存存儲系統的性能。在將來，還需要進一步研究訪問屬性的判別方法，減少判斷錯誤的情況，進一步提升垃圾回收的性能。