基于需求的三級映射管理的閃存轉換層算法

韓曉軍王舉利，張 南高會娟

（1.天津工業(yè)大學電子與信息工程學院，天津 300378；2.北京兆易創(chuàng)新科技有限公司，北京 100083）

基于需求的三級映射管理的閃存轉換層算法

韓曉軍1王舉利1，2張 南1高會娟2

（1.天津工業(yè)大學電子與信息工程學院，天津 300378；2.北京兆易創(chuàng)新科技有限公司，北京 100083）

使用NAND Flash作為存儲介質的存儲設備常需要閃存轉換層（FTL）對NAND進行管理.頁映射是一種常見的映射方式，但需要很大的內(nèi)存存放頁映射表.針對該問題，提出了基于需求的三級映射管理的閃存轉換層算法（TFTL）.映射表保存在NAND閃存塊中，減輕SRAM的壓力，采用頁置換法把需求的映射表搬移到SRAM中.由TFTL算法與Page mapping FTL、FAST、DFTL的對比分析可知：NAND閃存塊擦除次數(shù)均衡性較好，系統(tǒng)響應時間和系統(tǒng)響應時間的標準差與Page mapping FTL等算法差異小.

三級映射管理；NAND閃存；閃存轉換層；地址映射；垃圾回收；磨損均衡

通常，閃存轉換層［1-2］固化在控制器中，接收前段解析的命令和控制后端NAND閃存陣列.控制器作為主機和NAND陣列的橋梁，同時借助于其內(nèi)部的閃存轉化層，可以簡化主機端文件系統(tǒng)的操作.文件系統(tǒng)訪問嵌入式多媒體卡（eMMC）時，可以像訪問傳統(tǒng)機械硬盤一樣.閃存轉換層內(nèi)部主要算法包括：地址映射［3］、垃圾回收［4］、磨損均衡［5］、數(shù)據(jù)恢復［6］等.地址映射實現(xiàn)邏輯地址到物理地址的映射；磨損均衡和垃圾回收平衡每個NAND閃存的擦除次數(shù)和搬移有效數(shù)據(jù)回收垃圾NAND閃存；數(shù)據(jù)恢復確保數(shù)據(jù)的穩(wěn)定性和數(shù)據(jù)意外丟失的恢復.在eMMC內(nèi)部軟件架構中，主機端發(fā)送請求，控制器內(nèi)部經(jīng)過NVME、SATA、eMMC等協(xié)議解析主機的請求，閃存轉換層接收到請求，執(zhí)行請求的任務：讀寫或者擦除底層NAND閃存［7-8］.主機端的每一個請求必須經(jīng)過閃存換層的解析，因此閃存轉換層在eMMC內(nèi)部有著十分重要的作用.閃存轉換層算法的復雜度和算法的運行速度對eMMC的性能有決定性的影響［9］，但閃存轉換層算法的保密性和特殊性，使得每個廠家生產(chǎn)出來的eMMC內(nèi)部算法都不一樣.所以在閃存轉換層算法研究時需要模擬NAND底層，仿真實現(xiàn)和測試閃存轉換層算法的性能，避免在真實的NAND閃存塊中運行失敗.

頁映射是一種高效的映射方法，可以在邏輯頁和物理頁之間直接建立映射關系，每個映射關系建立一條映射條目.頁映射邏輯簡單，易于實現(xiàn)，但頁映射需要很大的內(nèi)存空間來存儲完整的映射表，在內(nèi)存較小的控制器中難以實現(xiàn).為了更好地利用有限的SRAM空間，Gupta［10］提出了DFTL算法，可以較好地減少垃圾回收負荷，同時僅需要較小的內(nèi)存空間.DFTL算法不像傳統(tǒng)的方法將映射表存儲在SRAM里面［11］，而是把所有的映射表存儲在NAND閃存里［12］，根據(jù)負載訪問方式動態(tài)的上傳和下載映射表.本文基于DFTL設計TFTL，TFTL采用頁映射算法用來管理邏輯頁到物理頁的映射關系.設計中通過root、segment、zone三級映射關系來管理邏輯頁和物理頁的對應關系.

1 三級映射管理的閃存轉換層（TFTL）

1.1 TFTL映射算法

DFTL算法中，NAND閃存分為數(shù)據(jù)塊和轉換塊，數(shù)據(jù)塊只能存放用戶數(shù)據(jù)，轉換塊只能存放映射表.在實際應用中，用戶數(shù)據(jù)會經(jīng)常更新，導致數(shù)據(jù)塊的擦寫次數(shù)下降的速度較快.轉換塊存放的映射表，更新速度慢，占用的NAND閃存的擦寫次數(shù)下降的速度較慢.這必然會導致數(shù)據(jù)塊和轉換塊擦寫次數(shù)不均衡，數(shù)據(jù)塊已經(jīng)達到NAND閃存擦寫的最大極限，但轉換塊擦寫次數(shù)很少，沒有達到NAND閃存擦寫的最大極限.這種情況不論是動態(tài)磨損均衡還是靜態(tài)磨損均衡都不能保持NAND閃存擦寫次數(shù)的均衡性，致使NAND閃存的利用率較低.

為了改進DFTL在磨損均衡中的磨損均衡的缺陷，本文提出了TFTL算法，其如圖1所示.

TFTL不區(qū)分NAND閃存數(shù)據(jù)塊和轉換塊，數(shù)據(jù)和映射表可以共用所有可用的NAND閃存，但一個NAND閃存中僅保存一種數(shù)據(jù)，不可能既保存用戶數(shù)據(jù)又保存映射表.NAND閃存在使用的過程中，用狀態(tài)位標識NAND閃存塊中存儲的內(nèi)容，映射表以TABLE作為標志，數(shù)據(jù)區(qū)以LOG作為標志.在NAND閃存寫滿數(shù)據(jù)時，轉變?yōu)閂ALID狀態(tài).eMMC擦除NAND閃存時，NAND閃存的狀態(tài)轉變?yōu)槌跏紶顟B(tài)INVALID.初始狀態(tài)的NAND閃存，可以存放任何數(shù)據(jù).映射表記錄NAND閃存中邏輯頁到物理頁的映射關系.映射表的更新，僅在NAND閃存數(shù)據(jù)寫滿時.如果NAND閃存沒有寫滿數(shù)據(jù)，建立一張位圖表標識NAND閃存中存有數(shù)據(jù).NAND閃存的最后一頁，保存映射反表，記錄物理頁到邏輯頁的映射關系.垃圾回收時，利用映射表和映射反表的映射條目一致性，判定數(shù)據(jù)的有效性.

圖1 TFTL設計原理圖Fig.1 Schematic of TFTL

1.2 TFTL映射算法設計

TFTL采用頁映射算法用來管理邏輯頁到物理頁的映射關系.設計中通過root、segment、zone三級映射關系來管理邏輯頁和物理頁的對應關系.設計32個root管理32個segment，每個segment管理2 000個zone，每個zone管理250個映射條目，總共有16 000 000條映射條目.如果每一個物理頁存放的數(shù)據(jù)是8 kB，則eMMC最大容量是64 GB.root、segment、zone三級管理層次關系如圖2所示.

圖2 三級管理映射關系Fig.2 Management of three-level mapping

圖2 中：segment和root記錄頁映射的映射信息，zone實現(xiàn)最基本的頁映射.root一級管理，記錄最新的segment位置；segment二級管理，記錄zone的序號，實現(xiàn)zone條目的管理；zone三級管理，記錄邏輯頁到物理頁的映射條目，實現(xiàn)基本的頁映射.

映射表保存如圖3所示.圖3中，32個segment中有1個segment常駐SRAM中，其他的segment保存在NAND閃存中，同時SRAM中常駐8個有效的zone映射表.這種做法類似其他閃存轉化層中的Cache機制，如果在SRAM中的zone中有記錄映射表的信息，可以快速地查詢到邏輯頁和物理頁之間的映射關系，加速數(shù)據(jù)的讀取.

圖3 映射表保存Fig.3 Save mapping table

1.3 TFTL映射算法尋址

邏輯地址到物理地址的尋址，核心是找到邏輯頁對應的zone表里存儲的物理頁.閃存轉換層中，邏輯地址以扇區(qū)為單位，邏輯頁由若干（標記為count，論文中以0×10為例）扇區(qū)組成.在TFTL映射算中，邏輯地址線性的分布在邏輯頁中，邏輯地址對count取摸可以得到邏輯頁.root表記錄最新的segment表，且root表保存在segment結構體中.在segment結構體中，當segment表自身結構體的索引號與root表記錄的segment表相同時，此時的segment表就是最新的segment表；segment結構體中同時包含有zone表地址，邏輯地址對應的zone表，記錄著邏輯頁對應的物理頁信息.以邏輯地址0×75 400尋址到物理地址0×830為例，介紹具體的尋址方式，圖4為具體的尋址過程.

1.4 TFTL數(shù)據(jù)流

TFTL數(shù)據(jù)流如圖5所示.

數(shù)據(jù)在eMMC協(xié)議層和SRAM之間傳輸，需要乒乓緩沖區(qū)自動在2個緩沖區(qū)之間切換搬移數(shù)據(jù). SRAM與乒乓緩沖區(qū)數(shù)據(jù)由DMA搬移.SRAM數(shù)據(jù)傳輸?shù)絅AND Flash主要由TFTL負責，TFTL內(nèi)部的地址映射等算法把底層NAND Flash模擬成虛擬的塊設備，以頁為傳輸單元傳輸數(shù)據(jù).

圖4 尋址過程Fig.4 Process of addressing

圖5 TFTL數(shù)據(jù)流Fig.5 Data path of TFTL

2 TFTL算法仿真和結果分析

在仿真實驗中［13］，選擇系統(tǒng)響應時間［14］、系統(tǒng)響應時間的標準差［15］和功耗作為主要性能指標.

2.1 系統(tǒng)響應時間

系統(tǒng)響應時間，是指從主機端發(fā)送請求到設備端響應主機命令之間的時間，是評估閃存轉換層的一個重要參數(shù).它包括地址轉換消耗的時間、eMMC讀寫消耗的時間、垃圾回收消耗的時間.

系統(tǒng)響應時間（Financial Trace）如圖6所示.

在不同的工作負載下系統(tǒng)響應時間不同.由圖6可見，運行工作負載Financial時，TFTL的系統(tǒng)響應時間接近page mapping FTL的系統(tǒng)響應時間.與pagemapping FTL算法對比，TFTL減少了整個NAND塊的擦除次數(shù)，同時減少了大約額外的3倍頁讀的運行次數(shù).圖6的運行結果表明，TFTL提升了設備服務的時間，減少了隊列等待的時延.與混合映射FAST算法對比，TFTL又提升了大約78%的整體I/O系統(tǒng)響應時間.對于以讀為導向的工作負載，TFTL會帶來更大的附加地址轉換開銷.在性能表現(xiàn)方面，與page mapping FTL算法比較偏差較大.系統(tǒng)響應時間（TPC-H Trace）如圖7所示.

圖6 系統(tǒng)響應時間（Financial Trace）Fig.6 System response time（Financial Trace）

圖7 系統(tǒng)響應時間（TPC-H Trace）Fig.7 System response time（TPC-H Trace）

由圖7可見，當運行工作負載TPC-H時，F(xiàn)AST算法系統(tǒng)響應遲緩，根本原因是消耗在完全的映射合并和潛在的等待請求I/O隊列時的時間.即使FAST算法可以提升大約95%的請求服務，但相對于TFTL算法，系統(tǒng)響應時間會因潛在的剩余I/O請求隊列出現(xiàn)長時間等待.

綜合圖6和圖7的結果可以看到，TFTL算法在2個工作負載下，性能都能與最優(yōu)算法相匹配：在工作負載Financial下，page mapping FTL算法性能最優(yōu)，但TFTL算法的性能表現(xiàn)可以接近于page mapping FTL算法，都可以在4 ms左右響應系統(tǒng)請求；在工作負載TPC-H下，F(xiàn)AST算法性能最優(yōu)，同樣的TFTL算法的性能表現(xiàn)可以接近于FAST算法.3種算法系統(tǒng)響應時間接近，TFTL算法和page mapping FTL算法在前期響應較快，呈現(xiàn)出逐步增加的趨勢.

2.2 系統(tǒng)響應時間的標準差

系統(tǒng)響應時間的標準差是指請求的系統(tǒng)響應時間與請求平均響應時間之間的標準差，用于表示各個請求之間的波動性.值越小，表示請求之間的差距越小，緊密性越好.圖8所示為系統(tǒng)性響應時間的標準差.

圖8 系統(tǒng)響應時間的標準差Fig.8 Standard deviation of system response time

由圖8可以清晰地看出，無論運行工作負載Financial還是運行工作負載TPC-H時，F(xiàn)AST算法的標準差都較大，性能最差.FAST算法采用數(shù)據(jù)項和日志項存放數(shù)據(jù)，由于日志項占用的NAND閃存較少，且使用頻率較高，即數(shù)據(jù)的寫入都要用到日志項，又由于NAND閃存的寫之前必須擦除特性，導致FAST算法垃圾回收比較頻繁.垃圾回收要搬移數(shù)據(jù)，耗時嚴重，嚴重影響了系統(tǒng)的響應時間，導致系統(tǒng)響應時間的標準差升高.Page mapping FTL算法使用一級頁映射，沒有額外的地址轉換開銷，請求的服務時間差別不大，而且在進行垃圾回收時能取得全局最優(yōu)，所以使得各個請求的系統(tǒng)響應時間差別最小，標準差最小. TFTL算法與Page mapping FTL算法對比，標準差大一點，是因為TFTL算法的映射表都存儲在NAND閃存塊中，是一種基于需求的頁映射算法.映射表和數(shù)據(jù)一樣保存到NAND閃存中，提升了做垃圾回收的頻率，延緩了系統(tǒng)響應時間，導致標準差較Page mapping FTL算法相比增大.

2.3 功 耗

eMMC內(nèi)部垃圾回收時產(chǎn)生的功耗，可以作為衡量eMMC內(nèi)部固件算法性能的一個重要參數(shù).不同于讀和寫的操作，垃圾回收對eMMC整體的功耗會產(chǎn)生一個重要影響，一個給定的工作負載，對于不同的FTL算法，內(nèi)部的垃圾回收運行的平率差距較大.圖9顯示了運行工作負載Financial和TPC-H時不同的FTL算法產(chǎn)生的功耗.

工作負載Financial主要以隨機寫為主，工作負載TPC-H主要以讀為主，在考慮垃圾回收產(chǎn)生的功耗時，工作負載Financial要遠高于工作負載TPC-H. TFTL是基于需求的FTL算法，當映射表不在內(nèi)存中時，TFTL需要額外的讀寫操作搬移映射表到內(nèi)存中，導致在2種負載中產(chǎn)生比page mapping FTL更多的功耗.混合FAST算法，需要經(jīng)常運行垃圾回收搬移數(shù)據(jù)從日志項到數(shù)據(jù)項，同時需要擦除日志項，因此，混合FAST算法功耗最大.

圖9 Financial和TPC-H產(chǎn)生的功耗Fig.9 Power consumption of Financial and TPC-H

在垃圾回收時，除了因NAND閃存自身運行時的功耗外，eMMC內(nèi)部的控制器產(chǎn)生的功耗也是不可忽略的一個因素.垃圾回收時，控制器需要尋找被搬移數(shù)據(jù)的NAND閃存，盡量去查收有效頁最少的NAND閃存搬移，減少有效頁的數(shù)據(jù)搬移時的功耗.圖10顯示了在運行工作負載Financial時，不同的FTL算法的垃圾回收的查詢NAND閃存與系統(tǒng)響應時間之間的關系.

圖10 NAND閃存與系統(tǒng)響應時間之間的關系Fig.10 Relation between the NAND flash and system system response time

從圖10中可以看到，更高的搜索操作降低了響應時間，同時消耗更多的能量.原因為：①NAND閃存中的數(shù)據(jù)越少，數(shù)據(jù)搬移越少；②查詢操作引起控制器和系統(tǒng)總線產(chǎn)生功耗.垃圾回收時，要權衡考慮查詢操作和數(shù)據(jù)搬移之間的功耗問題.查詢操作的不精確可能會增加系統(tǒng)響應時間，因為一個不完整的查詢操作，可能會選擇出一個有效數(shù)據(jù)頁較多的NAND閃存塊，進行數(shù)據(jù)的搬移.

片上內(nèi)存RAM的功耗是另外一個需要考慮的因素.頁映射與塊映射對比需要更多的內(nèi)存空間存儲映射表，因此頁映射會消耗更多的能量.混合映射FAST算法數(shù)據(jù)項使用塊映射，日志項使用頁映射，需要較少的內(nèi)存空間，功耗也較小.TFTL與FAST類似，由于映射表主要存儲在NAND閃存塊中，需要的內(nèi)存空間少，功耗也會隨之減少.

3 結語

本文在DFTL算法的基礎上提出了TFTL算法，不需區(qū)分數(shù)據(jù)塊和轉換塊，可以較好地解決NAND閃存磨損均衡的問題.實驗結果表明，TFTL算法比FAST算法系統(tǒng)響應時間快且垃圾回收功耗小，TFTL系統(tǒng)響應標準差比page mapping FTL的標準差稍大，原因是TFTL算法是基于需求的映射算法，映射表存儲在NAND中，需要搬移映射到SRAM.

TFTL映射表的管理較復雜，但在數(shù)據(jù)恢復過程中，TFTL可以快速建立映射表.

［1］劉洋，王峰.Dual-FTL：一種基于MLC/SLC雙模閃存芯片的閃存轉換層［J］.河南師范大學學報：自然科學版，2014，42（5）：148-154. LIU Y，WANG F.Dual-FTL MLC/SLC dual flash memory chip based flash translation layer［J］.Journal of Henan Normal University：Natural Science Edition，2014，42（5）：148-154（in Chinese）.

［2］ KIM J，KIM J M，NOH S H，et al.A space-efficient flash translation layer for Compact Flash systems［J］.IEEE Transactions on Consumer Electronics，2002，48（2）：366-375.

［3］張琦，王林章，張?zhí)欤?一種優(yōu)化的閃存地址映射方法［J］.軟件學報，2014，25（2）：314-325. ZHANG Q，WANG L Z，ZHANG T，et al.Optimized address translation method for flash memory［J］.Journal of Software，2014，25（2）：314-325（in Chinese）.

［4］JANG K H，HAN T H.Efficient garbage collection policy and block management method for NAND flash memory［C］//Mechanical and Electronics Engineering（ICMEE），2010，2nd.International Conference on.2010：327-331.

［5］JIANG A，MATEESCU R，YAAKOBI E，et al.Storage coding for wear leveling in flash memories［J］.IEEE Transactions on Information Theory，2009，56（10）：5290-5299.

［6］袁芳，劉偉，宋賀論，等.基于時間戳的FTL實現(xiàn)連續(xù)數(shù)據(jù)恢復方法［J］.計算機工程與設計，2015，36（1）：150-155. YUAN F，LIU W，SONG H L，et al.Continuous data recovery method based on FTL with timestamp［J］.Computer Engineering and Design，2015，36（1）：150-155（in Chinese）.

［7］PARK D J，CHOI W K，LEE S W，et al.FAST：A log buffer scheme with fully associative sector translation for efficient FTL in flash memory［J］.Kips Transactions Parta，2005，12A（3）：205-214.

［8］PRATIBHA S，SUVARNA M.Efficient flash translation layer for flash memory［J］.Emerging Directions in Embedded&U－biquitous Computing，2006，4097（4）：879-887.

［9］GUO X F，WANG Y P.Optimizing random write performance of FAST FTL for NAND flash memory［J］.Science China，2015，58（3）：1-14.

［10］GUPTA A，KIM Y，URGAONKAR B.DFTL：a flash translation layer employing demand-based selective caching of pagelevel address mappings［J］.AcmSigplan Notices，2009，44（3）：229-240.

［11］楊龍嬰.一種對NAND閃存硬件和閃存轉換層軟件的形式化建模［D］.合肥：中國科學技術大學，2015. YANG L Y.Formal modeling of NAND hardware and flash translation layer［D］.Hefei：University of Science and Technol，ogy of China，2015（in Chinese）.

［12］杜溢墨，肖儂，劉芳，等.一種可定制模塊化的閃存轉換層的設計與實現(xiàn)［J］.西安交通大學學報，2010，44（8）：42-47. DU Y M，XIAO N，LIU F，et al.A customizable and modular flash translation layer（FTL）［J］.Journal of Xi′an Jiaotong University.2010，44（8）：42-47（in Chinese）.

［13］BUCY J S，GANGER G R.The diskSim simulation environment version 3.0 reference manual［J］.Kwartalnik Historii Kultury Materialnej，2003，29（4）：102-103.

［14］SCHELLHORN Q，ERNST G，PFSHLER J，et al.Development of a Verified FlashFile System［M］.Berlin：Springer，2014：9-24.

［15］KELLER G，MURRAY T，AMANI S，et al.File systems deserve verification tool［J］.ACM SIGOPSOperating Systems Review，2014，48（1）：58-64.

Three-level mapping management flash translation layer algorithm based on demands

HAN Xiao-jun1，WANG Ju-li1，2，ZHANG Nan1，GAO Hui-juan2
（1.School of Electronics and Information Engineering，Tianjin Polytechnic University，Tianjin 300387，China；2.Beijing Zhaoyi Innovation Science and Technology Co Ltd（GigaDevice），Beijing 100083，China）

Flash translation layer（FTL）is always needed when NAND Flash is used in a memory device.Page level translation is the most popular，but needs a large RAM to store mapping table.A three-level mapping management FTL based on the requirement（TFTL）is presented.The mapping tables stored in the NAND block to relieve pressure for SRAM and the page displacement method is used to move the mapping table in NAND block to SRAM.Compared with Page mapping FTL，DFTL and FAST，TFTL has a better performance on the NAND wear leveling. The system response time，and the standard deviation of system response time of TFTL have little difference with those of Page mapping FTL.

three-level mapping management；NAND flash；flash translation layer（FTL）；address mapping；garbage collection；wear leveling

TP333

A

1671-024X（2016）05-0066-06

10.3969/j.issn.1671-024x.2016.05.012

2015-12-15

國家自然科學基金資助項目（61405144）

韓曉軍（1958—），女，教授，主要研究方向為圖像處理與模式識別.E-mail：hanxiaojun@tjpu.edu.cn