星载Flash阵列存储器零散化存储管理方案

任 诗 ，董振兴 ，朱 岩

（1.中国科学院复杂航天系统电子信息技术重点实验室，北京100190；2.中国科学院国家空间科学中心，北京100190；3.中国科学院大学北京100190）

随着航天技术的快速发展，多载荷飞行任务对星载存储器存储速率的要求不断提高；加之地面站接收范围等因素对卫星观测数据回传实时性的限制，又对星载存储器的存储容量提出了要求。针对以上对星载海量高速数据存储器的要求，较为普遍的做法是建立Flash阵列。

目前已有的Flash阵列由X行×Y片NAND Flash芯片组成。每行Y片Flash共用控制信号线，而IO总线则扩展为Y倍；阵列每列对应的X片Flash共享IO总线[1-4]。考虑到Flash芯片的编程延时[5]，采用行间流水线操作。这种构建Flash阵列的方案，打破了单片NAND Flash芯片存储容量的限制，并以流水的方式隐藏了芯片的编程时间，提高了吞吐速率[6]。但是，此方案需要将Flash阵列中的全部芯片都排布在同一块电路板上，当布线完成后，Flash阵列的容量和速率就成为固定值。显然，这是一种灵活性和扩展性较差的定制型Flash阵列模型。若想满足不同航天型号任务对存储器容量和速率的不同要求，需要重新设计存储器，无形中延长了工程周期。

针对已有方案灵活性和扩展性较差的问题，文中提出一种容量和速率可配置的Flash阵列模型。将原有定制型Flash阵列进行一次封装后，并以此为基础扩展为新阵列。

1 存储系统的主要硬件结构

定义Flash阵列中的最小存储模块为一个基本单元，即一个基本单元是由4行×Y片NAND Flash芯片组成[7]，行间为4级流水。每M个基本单元构成一组，同组的单元之间为串行扩展，规定存满一个单元后才能使用下一个单元，因此可以把组抽象成为宏观上的整体，取这样的N组进行并行扩展，为每组分配一个并行通道。至此，由M×N=2P，（P=0，1，2…）个单元搭建的存储器即为可配置Flash阵列，见图1。

微观上，每个独立的存储单元内部均采用4级流水的方式，FPGA每缓存4簇（簇[7]，即单元内4片并行的Flash芯片相同地址的页的集合）有效数据才会启动一次4级流水并行写入某个单元的NAND Flash芯片。宏观上，每N簇有效数据将会并行写入N个不同组的相同流水级，因此一次系统级的操作将写入4N簇数据。由此可见Flash阵列不但实现了容量的增长，也将理想情况下的存储速率提升了N倍。但是这种性能的改变是以牺牲NAND Flash芯片中数据的连续性为代价，因此需要高效的数据管理方案对分散在各单元的各NAND Flash芯片中的数据进行管理，并解决因不同NAND Flash芯片读写延时差异而导致的组间的数据对齐问题，以保证星上数据回放的连续性和正确性。

图1 存储系统硬件结构框图

2 数据零散化管理方案设计

数据的零散化管理，就是将同一个文件分散在各NAND Flash芯片中的存储块找到，并按照逻辑顺序恢复成完整的文件存储下来，并且可通过索引定位它们。因此存储系统管理软件的主要功能有：块分配表（Block Allocation Table，BAT）管理[8]，文件信息管理和目录结构建立。

2.1 块分配表的单元管理模型

管理软件需要完成NAND Flash存储器物理地址和文件系统读写命令中逻辑地址的转换[9]，即地址映射算法。通过在内存中建立BAT表，来覆盖Flash阵列的每一个存储块。表项的序号为逻辑地址；表项的内容记录当前NAND Flash芯片的使用状态，并保证实时更新功能，以方便对存储块的管理。

已知组成基本单元的NAND Flash芯片的型号和数量，故可求得整个Flash阵列中的块总数。因此可预先开辟一段连续的内存空间用于存放BAT表，也便于索引和对BAT表的更新操作。

设Flash阵列中有2P（P=1，2，3…）个基本单元，每个单元由十几个NAND Flash芯片组成，每个芯片有上千块。若在整个系统范围内对所有存储块统一顺序编号，当进行扩展时，需要修改原有存储块的块序号，硬件耦合度相对较高；若对每个单元内的数据块独立编号（且均从0开始），当进行扩展时，原有Flash芯片数据块的块序号可以保持不变，硬件耦合度降低。

由于每个存储单元在物理结构上是完全一致且相互独立的，因此可将存储系统中用来区分每个存储块的信息分为两部分，即单元号和块序号。

单元号按照公式（1）进行编号，表示为第i组的第j个存储单元，编号结果如图1所示。

块序号表示存储块在单元内的位置，编号方法为[10-11]：第0流水级的块序号依次为0～B-1；第1流水级的块序号依次为B～2B-1；……；以此类推。因此相邻两个流水级中的第一个存储块的块序号之差，即为单个流水级中的块数。

块序号对各存储单元进行独立编号，只保证同一存储单元内的各存储块的块序号不重复，而不同存储单元将会重复使用这些序号。由此可见，在Flash阵列中，每个块序号都对应M×N块存储块，需要用单元号来区分它们。因此，地址映射关系为：物理地址=单元号×单元块总数+块序号。

根据这种编码策略，将内存中的BAT表拆分成为M×N个不同的子表，每张BAT子表只记录当前单元中的存储块信息，并为每个子表单独分配一段相对较小的连续内存空间即可；而这M×N个子表可用指针数组统一管理。

这种编码策略，将每一个单元的BAT表进行独立管理，摆脱了定制型Flash阵列中固定物理结构的限制，适用于任意M和N值的可配置Flash阵列，具有较高的灵活性和复用性。

2.2 文件信息管理策略

文件信息管理，即为每个文件生成一个文件头[12-13]，其中保存信源号、文件号、文件大小、时间码、文件链表首尾块序号等关键信息，为建立目录结构提供基础。

保存在NAND Flash中的只是一些零散的数据，需要通过对文件的管理，来将这些零散的数据拼接成一个完整的文件。因此需要为每个已经写入NAND Flash的文件创建一个文件头，并在其中保存文件的关键信息。

存储系统中的每一个文件的信源号和文件号都是独一无二的，作为识别该文件的ID存在。时间码可以分为文件创建时间码和最后一次修改时间码，利于后期对文件数据进行分析。而文件占用的存储块则需要从整个Flash阵列的全部存储块中挑选出来，并以链表的形式拼接在一起。

由于数据以流水并行的形式写入Flash阵列，因此每一个文件都是从第0组的第0流水级的某块的第0簇开始，到第N组的第3流水级的某块截止。因此可以建立链表结构将文件所占用的存储块连接起来。在极端情况下，会出现某个文件既横向占用不同组的N个单元，又纵向跨越相同组的两个单元的情况，此时需要结合数据的写入顺序来充分考虑各个单元中存储块之间的关系，才能确定各存储块在文件链表中的先后顺序。

传统的并行扩展，会把已缓存的前N簇数据依次分配给各单元的0流水级；然后把接下来的N簇数据再依次分配给各单元的1流水级……直到可以触发一次并行流水操作为止。这种路由策略虽然较为符合一般意义上的并行写入，但是它将每一簇相邻数据放入不同组中，把文件打乱地过于分散，在后期回放星上数据时可能会因为流水对齐等问题而影响整体的回放速率。

因此在传统并行路由策略的基础上做如下修改：由于已经把组抽象成为了一个整体，因此可以把每次预先缓存的4N簇数据均匀切割成N份后，再分配到各组，每组4簇（这4簇数据在内容上连续，且写入时必须严格遵守4级流水操作）。

为便于理解，假设一个2×2的Flash阵列，见图2。

图2 2×2Flash阵列

在极端情况下，某文件不但横向占用单元0和2，当单元0和2的最后一块存储块被使用后，便会开始使用单元1和3。横向的跨单元存储恰恰体现出并行扩展，是Flash阵列中每一个文件都会遇到的问题；而纵向的跨单元存储体现出小组内的串行扩展，只有少部分写在存储单元边缘的文件会遇到这种问题。显然并行扩展的难度较串行扩展大，因此下面将着重分析并行扩展。

在并行扩展中，数据的写入过程如图3所示。

图3 数据写入操作流程说明

1）给连续的8簇数据依次编号0～7；

2）编号0～3的数据将被分配在0组的缓冲区；

3）编号4～7的数据将被分配在1组的缓冲区；

4）0和4簇分别写入两组的0流水级；

5）1和5簇分别写入两组的1流水级；

6）2和6簇分别写入两组的2流水级；

7）3和7簇分别写入两组的3流水级；

以上4）～7）步是一次完整的数据并行流水过程，且每次写入的8簇数据所在的簇地址一定相同。

由于在BAT表项中的“下一块地址指针”始终指向当前组的下一个流水级，数值为块序号。所以在生成文件链表时，只能建立起各组独立的小链表，而相邻小组之间的关系需要通过索引树形目录中相同的文件ID号（信源号+文件号）来确定。如果出现文件纵向存储在同组的相邻单元中，此时不需要额外的信息来区分这两个单元；因为在组内，单元是按顺序依次被使用的，因此当存在以上情况时，“下一块地址指针”的值将会出现一次跃变，从一个很大的块序号突然变成一个很小的数值，这就表明文件在组内出现了跨单元存储，而这个较小的值就是本组内下一个单元中某存储块的块序号。

这种文件信息管理策略，只在组内生成小链表，且文件头只保存当前组内的文件信息，各组独立进行管理。若为文件生成完整链表，还需考虑相邻组内存储块之间的关系，无形中增加了文件头的信息量。因此，本管理策略把实际的管理任务下放到组，降低了整体管理的复杂度。

2.3 树形目录的组成

恰当的目录结构[14-15]，可以在整个系统中快速定位所需文件[16]，方便回放和查看操作。当前建立的目录结构主要有：根，索引的总入口；组节点，记录组中各类型块的情况等；组目录，记录载荷数量和载荷目录入口；载荷目录，记录各文件头信息。

上一节生成文件链表时，为每个文件建立了N个小链表，这些链表实现了零散存储块的挑选和粗粒度的拼接工作。但是每个链表只能指示存储块在组内的关系，由于并行存储导致每个文件的数据必然分散到所有组内，因此需要将这些独立的小链表再次拼接才能实现真正意义上的文件复原。

因为每个文件头中都有“链表首地址”和“链表尾地址”这一信息，因此可以为每个小链表创建一个文件头，用于记录当前组内某文件小链表的起止块序号。目录结构见图4（仍用2×2Flash阵列举例）。

图4 树形目录结构说明

由图可知，“根/组节点0/组目录0/载荷目录0/文件 0”和“根/组节点 1/组目录 1/载荷目录 0/文件 0”这两个路径，指向的是同一个文件的不同小链表。树形目录的建立，不但为文件的索引提供依据，也将各组内相同文件的小链表关联起来，真正完成文件的零散化存储管理。

当文件回放时，以簇为单位，按照文件数据的逻辑顺序进行操作。根据并行流水过程，参考图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）依次类推，回放顺序就是文件数据的实际逻辑顺序。

由于文件索引是以组为单位的，因此不管存储器由多少个小组构成，管理思路都是一样的，这正是灵活性、可扩展性和复用性的体现。

3 结论

为解决定制型Flash阵列灵活性和扩展性较差的问题，提出了可配置型Flash阵列存储方案。本设计在单元层面上完成BAT表的管理，实现各单元物理结构和软件管理的双重独立，为配置不同M和N值的Flash阵列提供基础；在组层面上实现文件链表的管理，降低管理复杂度，省略不同组的数据块之间关系的管理，从而提高软件方面的可扩展性；在Flash阵列层面上实现文件的完整索引，将各组的文件关系用树形目录表示，便于索引的同时，还保证零散化存储的文件数据的完整性。

综上，文中提出的星载Flash阵列存储器文件零散化存储管理方案解决了目前已有Flash阵列存储器方案中定制性强、灵活性差和可复用性差的问题，并具有物理结构易扩展，软件管理方案可配置等优点。

参考文献:

[1]邬诚.基于FLASH阵列的高速大容量数据存储系统设计[J].信息化研究，2012，38（3）:34-37.

[2]王静，马婷婷，杜科，等.基于FLASH阵列的高速存储系统设计[J].指导与引信，2014，35（2）:28-33.

[3]李晴.高速大容量NANDFLASH存储系统的设计与实现[D].北京:北京理工大学，2015.

[4]蒲南江.基于闪存阵列的高速数据存储技术研究[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]朱岩.基于闪存的星载高速大容量存储技术的研究[D].北京：中国科学院研究生院，2006.

[8]宋琪.星载固态存储管理技术的应用研究[D].北京:中国科学院研究生院（空间科学与应用研究中心），2015.

[9]姜伟娜.基于NAND Flash存储器的FTL优化算法的设计与实现[D].上海:华东师范大学，2013.

[10]彭军.基于NAND Flash的多路并行存储系统的研究与实现[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高可靠自恢复实时文件系统[J].计算机工程与科学，2012，34（6）:169-173.

[13]彭涛.基于Flash存储芯片的文件存储系统设计[J].电子科技，2015，28（5）:158-160，163.

[14]吴凡.基于FPGA和NAND Flash的嵌入式存储系统设计[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.