基于需求的三級(jí)映射管理的閃存轉(zhuǎn)換層算法

韓曉軍王舉利，張 南高會(huì)娟

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

基于需求的三級(jí)映射管理的閃存轉(zhuǎn)換層算法

韓曉軍1王舉利1，2張 南1高會(huì)娟2

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

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

三級(jí)映射管理；NAND閃存；閃存轉(zhuǎn)換層；地址映射；垃圾回收；磨損均衡

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

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

1 三級(jí)映射管理的閃存轉(zhuǎn)換層（TFTL）

1.1 TFTL映射算法

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

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

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

圖1 TFTL設(shè)計(jì)原理圖Fig.1 Schematic of TFTL

1.2 TFTL映射算法設(shè)計(jì)

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

圖2 三級(jí)管理映射關(guān)系Fig.2 Management of three-level mapping

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

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

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

1.3 TFTL映射算法尋址

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

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

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

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

圖4 尋址過(guò)程Fig.4 Process of addressing

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

2 TFTL算法仿真和結(jié)果分析

在仿真實(shí)驗(yàn)中［13］，選擇系統(tǒng)響應(yīng)時(shí)間［14］、系統(tǒng)響應(yīng)時(shí)間的標(biāo)準(zhǔn)差［15］和功耗作為主要性能指標(biāo).

2.1 系統(tǒng)響應(yīng)時(shí)間

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

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

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

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

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

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

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

2.2 系統(tǒng)響應(yīng)時(shí)間的標(biāo)準(zhǔn)差

系統(tǒng)響應(yīng)時(shí)間的標(biāo)準(zhǔn)差是指請(qǐng)求的系統(tǒng)響應(yīng)時(shí)間與請(qǐng)求平均響應(yīng)時(shí)間之間的標(biāo)準(zhǔn)差，用于表示各個(gè)請(qǐng)求之間的波動(dòng)性.值越小，表示請(qǐng)求之間的差距越小，緊密性越好.圖8所示為系統(tǒng)性響應(yīng)時(shí)間的標(biāo)準(zhǔn)差.

圖8 系統(tǒng)響應(yīng)時(shí)間的標(biāo)準(zhǔn)差Fig.8 Standard deviation of system response time

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

2.3 功 耗

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

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

［1］劉洋，王峰.Dual-FTL：一種基于MLC/SLC雙模閃存芯片的閃存轉(zhuǎn)換層［J］.河南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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］.軟件學(xué)報(bào)，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］袁芳，劉偉，宋賀論，等.基于時(shí)間戳的FTL實(shí)現(xiàn)連續(xù)數(shù)據(jù)恢復(fù)方法［J］.計(jì)算機(jī)工程與設(shè)計(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］楊龍嬰.一種對(duì)NAND閃存硬件和閃存轉(zhuǎn)換層軟件的形式化建模［D］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)，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］杜溢墨，肖儂，劉芳，等.一種可定制模塊化的閃存轉(zhuǎn)換層的設(shè)計(jì)與實(shí)現(xiàn)［J］.西安交通大學(xué)學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助項(xiàng)目（61405144）

韓曉軍（1958—），女，教授，主要研究方向?yàn)閳D像處理與模式識(shí)別.E-mail：hanxiaojun@tjpu.edu.cn