星載Flash陣列存儲器零散化存儲管理方案

任 詩 ，董振興 ，朱 巖

（1.中國科學院復(fù)雜航天系統(tǒng)電子信息技術(shù)重點實驗室，北京100190；2.中國科學院國家空間科學中心，北京100190；3.中國科學院大學北京100190）

隨著航天技術(shù)的快速發(fā)展，多載荷飛行任務(wù)對星載存儲器存儲速率的要求不斷提高；加之地面站接收范圍等因素對衛(wèi)星觀測數(shù)據(jù)回傳實時性的限制，又對星載存儲器的存儲容量提出了要求。針對以上對星載海量高速數(shù)據(jù)存儲器的要求，較為普遍的做法是建立Flash陣列。

目前已有的Flash陣列由X行×Y片NAND Flash芯片組成。每行Y片F(xiàn)lash共用控制信號線，而IO總線則擴展為Y倍；陣列每列對應(yīng)的X片F(xiàn)lash共享IO總線[1-4]。考慮到Flash芯片的編程延時[5]，采用行間流水線操作。這種構(gòu)建Flash陣列的方案，打破了單片NAND Flash芯片存儲容量的限制，并以流水的方式隱藏了芯片的編程時間，提高了吞吐速率[6]。但是，此方案需要將Flash陣列中的全部芯片都排布在同一塊電路板上，當布線完成后，F(xiàn)lash陣列的容量和速率就成為固定值。顯然，這是一種靈活性和擴展性較差的定制型Flash陣列模型。若想滿足不同航天型號任務(wù)對存儲器容量和速率的不同要求，需要重新設(shè)計存儲器，無形中延長了工程周期。

針對已有方案靈活性和擴展性較差的問題，文中提出一種容量和速率可配置的Flash陣列模型。將原有定制型Flash陣列進行一次封裝后，并以此為基礎(chǔ)擴展為新陣列。

1 存儲系統(tǒng)的主要硬件結(jié)構(gòu)

定義Flash陣列中的最小存儲模塊為一個基本單元，即一個基本單元是由4行×Y片NAND Flash芯片組成[7]，行間為4級流水。每M個基本單元構(gòu)成一組，同組的單元之間為串行擴展，規(guī)定存滿一個單元后才能使用下一個單元，因此可以把組抽象成為宏觀上的整體，取這樣的N組進行并行擴展，為每組分配一個并行通道。至此，由M×N=2P，（P=0，1，2…）個單元搭建的存儲器即為可配置Flash陣列，見圖1。

微觀上，每個獨立的存儲單元內(nèi)部均采用4級流水的方式，F(xiàn)PGA每緩存4簇（簇[7]，即單元內(nèi)4片并行的Flash芯片相同地址的頁的集合）有效數(shù)據(jù)才會啟動一次4級流水并行寫入某個單元的NAND Flash芯片。宏觀上，每N簇有效數(shù)據(jù)將會并行寫入N個不同組的相同流水級，因此一次系統(tǒng)級的操作將寫入4N簇數(shù)據(jù)。由此可見Flash陣列不但實現(xiàn)了容量的增長，也將理想情況下的存儲速率提升了N倍。但是這種性能的改變是以犧牲NAND Flash芯片中數(shù)據(jù)的連續(xù)性為代價，因此需要高效的數(shù)據(jù)管理方案對分散在各單元的各NAND Flash芯片中的數(shù)據(jù)進行管理，并解決因不同NAND Flash芯片讀寫延時差異而導致的組間的數(shù)據(jù)對齊問題，以保證星上數(shù)據(jù)回放的連續(xù)性和正確性。

圖1 存儲系統(tǒng)硬件結(jié)構(gòu)框圖

2 數(shù)據(jù)零散化管理方案設(shè)計

數(shù)據(jù)的零散化管理，就是將同一個文件分散在各NAND Flash芯片中的存儲塊找到，并按照邏輯順序恢復(fù)成完整的文件存儲下來，并且可通過索引定位它們。因此存儲系統(tǒng)管理軟件的主要功能有：塊分配表（Block Allocation Table，BAT）管理[8]，文件信息管理和目錄結(jié)構(gòu)建立。

2.1 塊分配表的單元管理模型

管理軟件需要完成NAND Flash存儲器物理地址和文件系統(tǒng)讀寫命令中邏輯地址的轉(zhuǎn)換[9]，即地址映射算法。通過在內(nèi)存中建立BAT表，來覆蓋Flash陣列的每一個存儲塊。表項的序號為邏輯地址；表項的內(nèi)容記錄當前NAND Flash芯片的使用狀態(tài)，并保證實時更新功能，以方便對存儲塊的管理。

已知組成基本單元的NAND Flash芯片的型號和數(shù)量，故可求得整個Flash陣列中的塊總數(shù)。因此可預(yù)先開辟一段連續(xù)的內(nèi)存空間用于存放BAT表，也便于索引和對BAT表的更新操作。

設(shè)Flash陣列中有2P（P=1，2，3…）個基本單元，每個單元由十幾個NAND Flash芯片組成，每個芯片有上千塊。若在整個系統(tǒng)范圍內(nèi)對所有存儲塊統(tǒng)一順序編號，當進行擴展時，需要修改原有存儲塊的塊序號，硬件耦合度相對較高；若對每個單元內(nèi)的數(shù)據(jù)塊獨立編號（且均從0開始），當進行擴展時，原有Flash芯片數(shù)據(jù)塊的塊序號可以保持不變，硬件耦合度降低。

由于每個存儲單元在物理結(jié)構(gòu)上是完全一致且相互獨立的，因此可將存儲系統(tǒng)中用來區(qū)分每個存儲塊的信息分為兩部分，即單元號和塊序號。

單元號按照公式（1）進行編號，表示為第i組的第j個存儲單元，編號結(jié)果如圖1所示。

塊序號表示存儲塊在單元內(nèi)的位置，編號方法為[10-11]：第0流水級的塊序號依次為0～B-1；第1流水級的塊序號依次為B～2B-1；……；以此類推。因此相鄰兩個流水級中的第一個存儲塊的塊序號之差，即為單個流水級中的塊數(shù)。

塊序號對各存儲單元進行獨立編號，只保證同一存儲單元內(nèi)的各存儲塊的塊序號不重復(fù)，而不同存儲單元將會重復(fù)使用這些序號。由此可見，在Flash陣列中，每個塊序號都對應(yīng)M×N塊存儲塊，需要用單元號來區(qū)分它們。因此，地址映射關(guān)系為：物理地址=單元號×單元塊總數(shù)+塊序號。

根據(jù)這種編碼策略，將內(nèi)存中的BAT表拆分成為M×N個不同的子表，每張BAT子表只記錄當前單元中的存儲塊信息，并為每個子表單獨分配一段相對較小的連續(xù)內(nèi)存空間即可；而這M×N個子表可用指針數(shù)組統(tǒng)一管理。

這種編碼策略，將每一個單元的BAT表進行獨立管理，擺脫了定制型Flash陣列中固定物理結(jié)構(gòu)的限制，適用于任意M和N值的可配置Flash陣列，具有較高的靈活性和復(fù)用性。

2.2 文件信息管理策略

文件信息管理，即為每個文件生成一個文件頭[12-13]，其中保存信源號、文件號、文件大小、時間碼、文件鏈表首尾塊序號等關(guān)鍵信息，為建立目錄結(jié)構(gòu)提供基礎(chǔ)。

保存在NAND Flash中的只是一些零散的數(shù)據(jù)，需要通過對文件的管理，來將這些零散的數(shù)據(jù)拼接成一個完整的文件。因此需要為每個已經(jīng)寫入NAND Flash的文件創(chuàng)建一個文件頭，并在其中保存文件的關(guān)鍵信息。

存儲系統(tǒng)中的每一個文件的信源號和文件號都是獨一無二的，作為識別該文件的ID存在。時間碼可以分為文件創(chuàng)建時間碼和最后一次修改時間碼，利于后期對文件數(shù)據(jù)進行分析。而文件占用的存儲塊則需要從整個Flash陣列的全部存儲塊中挑選出來，并以鏈表的形式拼接在一起。

由于數(shù)據(jù)以流水并行的形式寫入Flash陣列，因此每一個文件都是從第0組的第0流水級的某塊的第0簇開始，到第N組的第3流水級的某塊截止。因此可以建立鏈表結(jié)構(gòu)將文件所占用的存儲塊連接起來。在極端情況下，會出現(xiàn)某個文件既橫向占用不同組的N個單元，又縱向跨越相同組的兩個單元的情況，此時需要結(jié)合數(shù)據(jù)的寫入順序來充分考慮各個單元中存儲塊之間的關(guān)系，才能確定各存儲塊在文件鏈表中的先后順序。

傳統(tǒng)的并行擴展，會把已緩存的前N簇數(shù)據(jù)依次分配給各單元的0流水級；然后把接下來的N簇數(shù)據(jù)再依次分配給各單元的1流水級……直到可以觸發(fā)一次并行流水操作為止。這種路由策略雖然較為符合一般意義上的并行寫入，但是它將每一簇相鄰數(shù)據(jù)放入不同組中，把文件打亂地過于分散，在后期回放星上數(shù)據(jù)時可能會因為流水對齊等問題而影響整體的回放速率。

因此在傳統(tǒng)并行路由策略的基礎(chǔ)上做如下修改：由于已經(jīng)把組抽象成為了一個整體，因此可以把每次預(yù)先緩存的4N簇數(shù)據(jù)均勻切割成N份后，再分配到各組，每組4簇（這4簇數(shù)據(jù)在內(nèi)容上連續(xù)，且寫入時必須嚴格遵守4級流水操作）。

為便于理解，假設(shè)一個2×2的Flash陣列，見圖2。

圖2 2×2Flash陣列

在極端情況下，某文件不但橫向占用單元0和2，當單元0和2的最后一塊存儲塊被使用后，便會開始使用單元1和3。橫向的跨單元存儲恰恰體現(xiàn)出并行擴展，是Flash陣列中每一個文件都會遇到的問題；而縱向的跨單元存儲體現(xiàn)出小組內(nèi)的串行擴展，只有少部分寫在存儲單元邊緣的文件會遇到這種問題。顯然并行擴展的難度較串行擴展大，因此下面將著重分析并行擴展。

在并行擴展中，數(shù)據(jù)的寫入過程如圖3所示。

圖3 數(shù)據(jù)寫入操作流程說明

1）給連續(xù)的8簇數(shù)據(jù)依次編號0～7；

2）編號0～3的數(shù)據(jù)將被分配在0組的緩沖區(qū)；

3）編號4～7的數(shù)據(jù)將被分配在1組的緩沖區(qū)；

4）0和4簇分別寫入兩組的0流水級；

5）1和5簇分別寫入兩組的1流水級；

6）2和6簇分別寫入兩組的2流水級；

7）3和7簇分別寫入兩組的3流水級；

以上4）～7）步是一次完整的數(shù)據(jù)并行流水過程，且每次寫入的8簇數(shù)據(jù)所在的簇地址一定相同。

由于在BAT表項中的“下一塊地址指針”始終指向當前組的下一個流水級，數(shù)值為塊序號。所以在生成文件鏈表時，只能建立起各組獨立的小鏈表，而相鄰小組之間的關(guān)系需要通過索引樹形目錄中相同的文件ID號（信源號+文件號）來確定。如果出現(xiàn)文件縱向存儲在同組的相鄰單元中，此時不需要額外的信息來區(qū)分這兩個單元；因為在組內(nèi)，單元是按順序依次被使用的，因此當存在以上情況時，“下一塊地址指針”的值將會出現(xiàn)一次躍變，從一個很大的塊序號突然變成一個很小的數(shù)值，這就表明文件在組內(nèi)出現(xiàn)了跨單元存儲，而這個較小的值就是本組內(nèi)下一個單元中某存儲塊的塊序號。

這種文件信息管理策略，只在組內(nèi)生成小鏈表，且文件頭只保存當前組內(nèi)的文件信息，各組獨立進行管理。若為文件生成完整鏈表，還需考慮相鄰組內(nèi)存儲塊之間的關(guān)系，無形中增加了文件頭的信息量。因此，本管理策略把實際的管理任務(wù)下放到組，降低了整體管理的復(fù)雜度。

2.3 樹形目錄的組成

恰當?shù)哪夸浗Y(jié)構(gòu)[14-15]，可以在整個系統(tǒng)中快速定位所需文件[16]，方便回放和查看操作。當前建立的目錄結(jié)構(gòu)主要有：根，索引的總?cè)肟?；組節(jié)點，記錄組中各類型塊的情況等；組目錄，記錄載荷數(shù)量和載荷目錄入口；載荷目錄，記錄各文件頭信息。

上一節(jié)生成文件鏈表時，為每個文件建立了N個小鏈表，這些鏈表實現(xiàn)了零散存儲塊的挑選和粗粒度的拼接工作。但是每個鏈表只能指示存儲塊在組內(nèi)的關(guān)系，由于并行存儲導致每個文件的數(shù)據(jù)必然分散到所有組內(nèi)，因此需要將這些獨立的小鏈表再次拼接才能實現(xiàn)真正意義上的文件復(fù)原。

因為每個文件頭中都有“鏈表首地址”和“鏈表尾地址”這一信息，因此可以為每個小鏈表創(chuàng)建一個文件頭，用于記錄當前組內(nèi)某文件小鏈表的起止塊序號。目錄結(jié)構(gòu)見圖4（仍用2×2Flash陣列舉例）。

圖4 樹形目錄結(jié)構(gòu)說明

由圖可知，“根/組節(jié)點0/組目錄0/載荷目錄0/文件 0”和“根/組節(jié)點 1/組目錄 1/載荷目錄 0/文件 0”這兩個路徑，指向的是同一個文件的不同小鏈表。樹形目錄的建立，不但為文件的索引提供依據(jù)，也將各組內(nèi)相同文件的小鏈表關(guān)聯(lián)起來，真正完成文件的零散化存儲管理。

當文件回放時，以簇為單位，按照文件數(shù)據(jù)的邏輯順序進行操作。根據(jù)并行流水過程，參考圖3，可知回放過程如下：

1）回放0組鏈表中前4塊的第一簇0/1/2/3；

2）回放1組鏈表中前4塊的第一簇4/5/6/7；

3）回放0組鏈表中前4塊的第二簇8/9/10/11；

4）……

5）回放0組鏈表中接下來4塊的第一簇；

6）……

7）依次類推，回放順序就是文件數(shù)據(jù)的實際邏輯順序。

由于文件索引是以組為單位的，因此不管存儲器由多少個小組構(gòu)成，管理思路都是一樣的，這正是靈活性、可擴展性和復(fù)用性的體現(xiàn)。

3 結(jié)論

為解決定制型Flash陣列靈活性和擴展性較差的問題，提出了可配置型Flash陣列存儲方案。本設(shè)計在單元層面上完成BAT表的管理，實現(xiàn)各單元物理結(jié)構(gòu)和軟件管理的雙重獨立，為配置不同M和N值的Flash陣列提供基礎(chǔ)；在組層面上實現(xiàn)文件鏈表的管理，降低管理復(fù)雜度，省略不同組的數(shù)據(jù)塊之間關(guān)系的管理，從而提高軟件方面的可擴展性；在Flash陣列層面上實現(xiàn)文件的完整索引，將各組的文件關(guān)系用樹形目錄表示，便于索引的同時，還保證零散化存儲的文件數(shù)據(jù)的完整性。

綜上，文中提出的星載Flash陣列存儲器文件零散化存儲管理方案解決了目前已有Flash陣列存儲器方案中定制性強、靈活性差和可復(fù)用性差的問題，并具有物理結(jié)構(gòu)易擴展，軟件管理方案可配置等優(yōu)點。

參考文獻:

[1]鄔誠.基于FLASH陣列的高速大容量數(shù)據(jù)存儲系統(tǒng)設(shè)計[J].信息化研究，2012，38（3）:34-37.

[2]王靜，馬婷婷，杜科，等.基于FLASH陣列的高速存儲系統(tǒng)設(shè)計[J].指導與引信，2014，35（2）:28-33.

[3]李晴.高速大容量NANDFLASH存儲系統(tǒng)的設(shè)計與實現(xiàn)[D].北京:北京理工大學，2015.

[4]蒲南江.基于閃存陣列的高速數(shù)據(jù)存儲技術(shù)研究[D].太原:中北大學，2012.

[5]SAMSUNGELECTRONICS.1Gx8bit-2Gx8bitNAND Flash Memory_K9F8G08UXM[R].South Korea:Samsung Corporation，2012.

[6]張雯，崔建杰，張新.一種多通道NAND Flash陣列的壞塊管理方案[J].電子器件，2014，37（5）:816-821.

[7]朱巖.基于閃存的星載高速大容量存儲技術(shù)的研究[D].北京：中國科學院研究生院，2006.

[8]宋琪.星載固態(tài)存儲管理技術(shù)的應(yīng)用研究[D].北京:中國科學院研究生院（空間科學與應(yīng)用研究中心），2015.

[9]姜偉娜.基于NAND Flash存儲器的FTL優(yōu)化算法的設(shè)計與實現(xiàn)[D].上海:華東師范大學，2013.

[10]彭軍.基于NAND Flash的多路并行存儲系統(tǒng)的研究與實現(xiàn)[D].長沙:湖南大學，2013.

[11]CHEN Z，XIAO N，LIU F，et al.PBFTL:The Page to Block Mapping FTL with Low Response Time[C].Proceedings of the 2011 IEEE 19th An?nual International Symposium on Modelling，Anal?ysis，and Simulation of Computer and Telecommu?nication Systems.Washington，DC，USA:IEEE Computer Society，2011:475-477

[12]張少波，徐廣輝，田小鋒，等.基于NandFLASH高可靠自恢復(fù)實時文件系統(tǒng)[J].計算機工程與科學，2012，34（6）:169-173.

[13]彭濤.基于Flash存儲芯片的文件存儲系統(tǒng)設(shè)計[J].電子科技，2015，28（5）:158-160，163.

[14]吳凡.基于FPGA和NAND Flash的嵌入式存儲系統(tǒng)設(shè)計[J].電子科技，2016，29（3）:97-101.

[15]PARK S O，LEE Y S，KIM S J.A high perfor?mance NAND array file system based on multiple NAND flash memories[J].The Journal of Supercom?puting，2013，64（2）:492-506.

[16]趙培.閃存的存儲管理及索引方法研究[D].武漢:華中科技大學，2011.