2020, Vol. 52
2. 中国科学院大学, 北京 100190
2. University of Chinese Academy of Sciences, Beijing 100190, China
随着国内航天事业的高速发展，卫星搭载的有效载荷种类和数量日益增多，对星上数据存储管理提出了更高要求.星载固态存储系统作为卫星的数据中心，承载着有效载荷数据的存储与发送[1].NAND FLASH因其存储密度高、非易失等特点已成为当前星上数据的主要存储介质.
固态存储系统一般由主机、闪存转换层及FLASH芯片组成.闪存转换层是位于主机和FLASH芯片间的中间软件层，目前针对FTL的研究大多集中在商用FLASH存储系统中，对于航天环境下固态存储算法的研究成果较少.基于商用FLASH系统设计的FLT算法管理复杂、处理器性能要求高、接口速率存在瓶颈，不适用于航天任务[2]；传统星载FTL算法[3-5]大多采用页级地址映射方式和固定分区的文件管理模式，其优点是实现简单、可靠性高，但存在主机占用率高、系统响应时间长以及没有充分考虑FLASH芯片的磨损均衡等问题.因此，基于卫星型号任务实际应用，提出一种适用于星载固态存储系统数据驱动的自适应超级块FTL(Data-driven adaptive superblock FTL, DASFTL)算法，以解决传统星载存储系统存在的主机占用率高、系统响应时间慢以及FLASH芯片磨损不均衡等问题.
1 星载固态存储系统概述星载固态存储系统采用NAND FLASH作为主存储器介质，现场可编程逻辑阵列(Field Programmable Gate Array, FPGA)作为FLASH控制器，并配备中央处理器(Central Processing Unit, CPU)单元负责地址管理和系统维护.一种典型星载固态存储系统结构见图 1.
|
图 1 典型星载固态存储系统结构框图 Fig. 1 Structural diagram of typical spaceborne solid state storage system |
卫星有效载荷产生的数据首先进入合路输入模块，数据按格式打包后送入存储控制单元，同时存储控制单元向主控CPU单元请求写数据页地址.FLASH控制模块收到源包数据后，进行RS编码(Reed-solomon codes)，并送入随机存取存储器(Random Access Memory, RAM)中进行缓存.当RAM缓存的数据达到FLASH一页大小时，将缓存数据写入主控CPU单元预分配的页地址.回放数据时，主控CPU单元向存储控制单元发送回放块地址和回放指令，存储控制单元在收到回放指令和地址后，将数据从存储区读出并解码，最后将数据加载至复接输出单元[6].
闪存转换层作为中间软件层位于主控CPU单元中，完成地址映射、垃圾回收和负载均衡等功能[7].地址映射将主控CPU单元中应用的逻辑地址转换为FLASH芯片中的物理地址.垃圾回收为当收到数据写入请求时，FTL寻找一个空页用于写入数据，若不存在空页或空余页余量不足，将会触发垃圾回收并选择一个完整的块作为回收对象.垃圾回收通过擦除过时的数据块来释放存储空间.负载均衡是在FLASH芯片的使用过程中，使其内部块的磨损程度尽可能均衡.
页级FTL[8]、块级FTL[9]和页块混合级FTL[10]是目前FTL设计中三种主要映射方案.页级FTL以页为单位将一个逻辑地址映射到一个物理地址，其优点为转换效率高，但存储在RAM中的地址映射表较大.块级FTL以块为单位进行逻辑地址到物理地址的映射，其基本思想是逻辑块中的逻辑页偏移量与物理块中物理页的偏移量相同.相比之下，块级FTL的映射表要比页级FTL映射表小得多，但块级FTL的转换效率较低.页块混合级FTL使用块级映射技术来获得相应的物理块地址，使用页级映射技术来定位可用的物理页，页块混合级FTL在较长时间的极限工况下表现出较好的地址转换效率[11].
2 数据驱动的自适应超级块FTL算法(DASFTL) 2.1 地址映射Jung等最先提出基于超级块的闪存转换层算法[12]，其比块级FTL算法更进一步，它将多个连续的逻辑块组合成一个超级块.例如，超级块的大小为4，那么逻辑块编号为0, 1, 2, 3的4个逻辑块构成了超级块0.虽然超级块闪存转换层算法能在块级FTL算法上进一步减少RAM的占用空间，但其只是由几个连续的逻辑块组合而成，无法根据实际系统中数据的运行特点进行调整.因此，提出了一种数据驱动的自适应超级块FTL算法(DASFTL)，其地址映射机制见图 2.
|
图 2 DASFTL地址映射机制 Fig. 2 Address mapping mechanism of DASFTL |
超级块映射表SMT和页地址映射表PMT组成两级映射，其中超级块映射表SMT为一级映射，页地址映射表为二级映射.超级块映射表SMT由超级块号SBN进行索引，每个超级映射表项由逻辑块号LBN、页映射表PMT和逻辑块权重WRecy组成.与Superblock FTL不同，在DASFTL中，超级块不是由几个连续的逻辑块简单组合而成，而是根据系统中数据运行的特点动态组合而成.每个超级块中所拥有的逻辑块数为K, K的取值范围从0到存储系统中所有有效物理块的个数.这K个逻辑块可以是连续的逻辑块也可以是不连续的，并且不同超级块的K值可能不同.具体哪些逻辑块组合成为一个超级块由块回收权重WRecy决定.在超级块内部采用页级映射，超级块中每一个映射表项都可以映射至其对应的实际物理页上.PMT被分为S个页映射子表(PMST1、PMST2、…、PMSTs)，由页映射表索引PMTI进行索引.页映射表索引的内容为物理页码，页映射子表的内容由物理页码PPN和页热度Hpage两部分组成，其中S的值可由OOB区的大小和逻辑块数计算得到.假设每个物理块包含α个物理页，每个OOB区可以存储m(0 < m≤α)个页映射条目，则每个超级块所含有的页地址映射项为m×α个，由此可得S=(m×α)÷K.逻辑块号LBN和页地址映射表偏移量PMToffset的计算公式为：
| $ {\rm{LBN}} = {\rm{LPN}} \div \alpha , {\rm{ }} $ | (1) |
| $ {\rm{PMToffset }} = \alpha \times {\rm{SBO}} + {\rm{LPN}}\% \alpha . $ | (2) |
式中：LBN为逻辑块号, LPN为逻辑页号, α为每物理块中的物理页数, SBO为超级块偏移量, PMToffset为页地址映射表偏移量.
每个FLASH块中含有的物理页数α是固定的，因此逻辑块号可以由逻辑页号LPN除以物理页数计算得到.之后查找超级块映射表可以得到其所在的超级块号SBN和此超级块偏移量SBO，利用式(1)~(2)就可以计算得到该逻辑页号在所对应的页地址映射表偏移量PMToffset.根据得到的PMToffset查找页地址映射表PMT就可以得到相应的物理页地址.在DASFTL算法中，每个页映射子表PMST都将在FLASH写操作过程中，写入到最新分配的物理页OOB区.在逻辑地址转换物理地址的过程中，可以通过读取PMTI所指示物理页的OOB区来直接获得PMST.这种分级映射方式通过维护两个短的映射链表来实现地址转换，避免了维护一个很长的地址链表所造成的搜索时间长和RAM占用率高等缺点，从而提高系统的响应速度并减少主机的占用，适用于RAM空间有限和实时性强的嵌入式系统.
2.2 读写地址管理星载固态存储系统主要工作在连续读/写模式下.传统星载存储系统大都采用页级FTL映射方案，其中每次读/写操作都需向主机请求地址，当存储系统连续写入数据时会造成存储系统大量占用主机资源，并且随着读写请求的不断累积系统响应时间将会变长.为此，DASFTL算法将超级块作为读/写操作的最小单位，当存储控制单元接收到数据并向主控CPU单元产生写请求时，主控CPU单元会一次性将块回收权重WRecy最小的超级块地址分配给存储控制单元，若一次写请求将整个超级块地址都分配之后仍未完成则向主控CPU单元请求新的超级块，若还有部分地址未分配则该超级块的地址分配信息存储在存储控制单元中待下次写请求继续使用.
对给定超级块的第一个写请求是由该超级块的第一个空闲逻辑块来提供服务.当一个物理块被选中分配给该逻辑块之后，物理块中的页将按顺序执行写操作.当其中一个物理页被分配之后，首先从该页的OOB区读出其相对应的页映射子表，将页映射子表中的PPN更新为将写入的新页面的PPN.然后将新的PMST写入到OOB区域、数据写入到DATA区域.写操作响应Twr时间为
| $ {T_{\rm{wr}}} = {T_{{\rm{wrask }}}} + {T_{{\rm{rdoob }}}} + {T_{{\rm{wrpg }}}}. $ | (3) |
式中：Twrask为发出写请求到主机返回写地址的系统响应时间，Trdoob为读取OOB中旧PMST的时间，Twrpg为写入一页数据和更新OOB区PMST的时间.
对于读操作，主控CPU单元会给定起始逻辑页LPN，然后LPN被翻译成逻辑块号LBN和超级块偏移量SBO.通过LBN和SBO可以计算得到此逻辑页所对应的页映射子表PMST及其所在的物理块号，之后读取PMST可以得到其所对应的物理页码.读操作响应时间Trd为
| $ {T_{{\rm{rd}}}} = {T_{{\rm{rdask}}}} + {T_{{\rm{rdoob}}}} + {T_{{\rm{rdpg}}}}. $ | (4) |
式中：Trdask为发出读请求到主机返回读地址的系统响应时间，Trdoob为读取OOB中旧PMST的时间，Trdpg为读取一页数据的时间.
2.3 垃圾回收当存储系统没有足够的空闲块来响应写请求时，将会触发垃圾回收.卫星处于地面接收站的范围内时，会将存储系统内的数据下传至地面, 随后数据就会被标记为“冷数据”.当触发垃圾回收机制时将优先回收冷数据块.星载存储系统中，对于冷数据的回收只执行擦除操作.传统星载存储系统大都基于固定分区的文件管理策略[5]，分区内部采用顺序回收机制.由于不同分区的数据热度和输入速率不同，会导致某些物理块的擦写次数不断攀升，直到该块的擦写次数到达上限变为无效块.为此，DASFTL算法不采用分区的文件管理策略，而将所有文件进行动态管理，其中超级块作为擦除的最小单位.在超级块内部，同一分区的逻辑地址是连续的但是其对应的物理地址不一定是连续的.
在DASFTL中，为兼顾存储系统的性能和使用寿命，引入数据页热度Hpage和物理块擦除次数Nearse来作为目标擦除块的选择因素.Hpage由式(5)计算得到.其中，f为一段时间内回放次数，fk+1－fk为第k次及第k+1次触发垃圾回收时该页的回放次数.页回放次数越多则该页的热度越大.
| $ {H_{{\rm{page}}}} = \left\{ {\begin{array}{*{20}{l}} {{f_{k + 1}} - {f_k}, \;\;\;{\kern 1pt} 0 < \left( {{f_{k + 1}} - {f_k}} \right);}\\ {0, \;\;\;{\kern 1pt} 0 > \left( {{f_{k + 1}} - {f_k}} \right).} \end{array}} \right. $ | (5) |
将页热度Hpage代入式(6)可得块平均热度
| $ {\bar H_{{\rm{block}}}} = \frac{{\sum\limits_{i = 1}^\alpha {{H_{{\rm{page}}}}} (i)}}{\alpha }. $ | (6) |
将
| $ {W_{{\rm{Resy }}}} = \left( {\frac{{P\left( {{N_{{\rm{thre }}}} - {N_{{\rm{care }}}}} \right)}}{{{N_{{\rm{thre }}}}}} + \frac{{(1 - P)\left( {{H_{{\rm{max }}}} - {{\bar H}_{{\rm{luax }}}}} \right)}}{{{H_{{\rm{max }}}}}}} \right) \times 10. $ | (7) |
在DASFTL算法中，块回收权重WRecy将作为超级块组成单位的度量单位.存储系统初次使用时，每个逻辑块的初始块回收权重都为0.随着存储系统的运行，超级块映射表SMT会计算并保存每个逻辑块的块回收权重.块回收权重WRecy相同的逻辑块将被组合成为一个超级块，即使这些逻辑块所对应的物理块地址是离散的.图 3为DASFTL算法垃圾回收流程图.当超级块映射表SMT中没有足够的空闲块来响应写操作时将触发垃圾回收.与响应写操作相同，主控CPU单元在响应垃圾回收操作时，将块回收权重最大的整个超级块下发给存储控制单元.存储控制单元会按照顺序依次回收超级块内的逻辑块.在完成一次回收之后超级块映射表SMT将更新块回收权重和新的映射索引.
|
图 3 DASFTL垃圾回收流程图 Fig. 3 Flow chart of DASFTL garbage collection |
为评估本文提出的DASFTL算法，设计并搭建了星载固态存储系统硬件测试平台，见图 4.
|
图 4 星载固态存储系统测试平台 Fig. 4 Test platform for spaceborne solid state storage system |
测试平台选用龙芯1E作为主控CPU，龙芯1E是以WH1770为核心的高性能应用处理器.软件工作在内嵌的VxWorks操作系统上，用于存储系统的任务管理与调度、中断与异常管理以及闪存转换层算法.CPU内存采用三片ISSI公司IS45S163型支持EDAC的SDRAM，容量为3 Gb.CPU程序存储器选用复旦微电子生产的JFM29LV64型号NOR FLASH，容量为64 Mb.FPGA选用Microsemi公司M2GL150T FPGA芯片，完成大容量固态存储管理、数据接收、复接及部分逻辑粘合功能.大容量固态存储器采用两片珠海欧比特公司VDNF64G08型NAND FLASH，单片容量64 Gb，总容量为128 Gb.FLASH芯片参数和内部编程时间见表 1.
|
表 1 FLASH芯片参数及编程时间 Tab. 1 Parameters and programming time of FLASH |
基于测试平台，对DASFTL算法与传统星载FTL算法在主机占用率、读/写响应时间和FLASH块擦除次数进行测试.在主机占用率测试中，共进行300 000次I/O请求，其中0~ 100 000次存储系统只进行写数据操作；之后对存储区数据进行全擦除，将存储系统设置在写数据与读数据同时工作模式下，进行100 000次I/O请求实验；最后重置存储区，工作模式设置为最大工况，存储系统同时进行写、读、擦操作.记录每次I/O操作时主机占用率，为排除系统其它部分占用主机资源对实验造成干扰，屏蔽系统内其他功能并以每25 000次I/O为一组计算主机占用率的平均值，实验结果见图 5.
|
图 5 传统星载FTL算法与DASFTL算法主机占用率 Fig. 5 Host occupancy rate of traditional spaceborne FTL and DASFTL algorithms |
系统上电后，主控CPU单元会遍历整个存储区并建立索引表，此时两者主机占用率都在80%左右.当进行写操作时，DASFTL主机占用率迅速下降并维持在31.2%左右，而传统星载FTL算法维持在60.5%左右.当同时进行读写操作时，DASFTL算法的主机占用率维持在39.7%左右，传统星载FTL算法上升至75.0%左右.最大工况下，DASFTL算法占用率稳定在44.8%左右，传统星载FTL算法则上升至86.1%.综上，采用超级块地址映射机制的DASFTL算法相比于传统星载FTL算法在主机占用率上平均降低51.7%.
分别独立进行100 000次读、写操作实验，通过龙芯CPU记录每次收到读/写请求至返回读/写地址的系统响应时间(Twrask/Trdask)，通过式(3)~(4), 计算得每次读、写操作的响应时间Trd和Twr.对Trd和Twr进行累和求均值，测试结果见图 6.
|
图 6 传统星载FTL算法与DASFTL算法读/写响应时间 Fig. 6 Read/Write response time of traditional spaceborne FTL and DASFTL algorithms |
传统星载FTL算法读/写操作平均响应时间分别为206 μs和408 μs，其中系统响应时间Trdask为90 μs、Twrask为115 μs.DASFTL算法读/写操作平均响应时间分别为159 μs和344 μs，其中系统响应时间Trdask为43 μs、Twrask为51 μs，相比于传统星载FTL算法读/写操作的系统响应时间下降了46.1%.
模拟卫星工作模式，设置三路输入数据分别为文件1、文件2和文件3.文件1数据输入速率为100 Mbps，文件2输入速率为150 Mbps，文件3输入速率为50 Mbps.实验剔除75块初始无效块，实际有效物理块为32 693块.设置实验运行时间为当存储控制单元共执行326 930次擦除操作时停止.实验结果见图 7.
|
图 7 传统星载FTL算法与DASFTL算法物理块擦除次数分布 Fig. 7 Distribution of physical block erasure times of traditional spaceborne FTL and DASFTL algorithms |
基于固定分区的传统星载FTL算法因各文件输入速率的差异，造成不同物理块的擦除次数呈现显著差异，文件2分区的物理块擦除次数高于文件1和文件3分区.DASFTL算法的擦除块选择策略只与当前块的热度和擦除次数相关，相同实验条件下，DASFTL算法的各物理块擦除次数相比于传统星载FTL算法更加均衡，有效避免了部分物理块过早磨损.
综上，DASFTL算法相比于传统星载FTL算法在主机占用率、系统响应时间以及FLASH磨损均衡等方面均有明显的性能提升.DASFTL算法的实际测试结果与预期结果吻合，证明了该算法的可行性和实用性.
4 结论针对传统星载闪存转换层算法存在的问题，提出了一种数据驱动的自适应超级块FTL算法，采用了基于超级块的地址映射策略，并引入动态块回收权重作为目标回收块选择的标准.实验结果表明，DASFTL算法相比于传统星载FTL算法在主机资源占用率由81.4%下降至44.8%、系统读/写响应时间由206 us/408 us提升至159 us/344 us，响应时间提升46.1%.FLASH芯片磨损均衡性能方面DASFTL算法在长时间工作下，各物理块擦除次数更加均衡，可有效避免部分物理块的过早磨损，提升FLASH芯片的使用寿命.但DASFTL算法仍存在代码实现复杂、后期维护困难等问题.
| [1] |
李姗, 宋琪, 朱岩, 等. 星载大容量固态存储器快速可靠启动算法设计[J]. 哈尔滨工业大学学报, 2015, 47(10): 100. LI Shan, SONG Qi, ZHU Yan, et al. Design of quick initialization algorithm for spaces borne solid state recorder[J]. Journal of Harbin Institute of Technology, 2015, 47(10): 100. DOI:10.11918/j.issn.0367-6234.2015.10.022 |
| [2] |
YANG Mingchang, CHANG Yuanhao, KUO Teiwei, et al. Reducing data migration overheads of flash wear leveling in a progressive way[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(5): 1808. DOI:10.1109/tvlsi.2015.2495252 |
| [3] |
许志宏.面向星载一体化综合电子系统的固态存储技术研究[D].北京: 中国科学院大学, 2017 XU Zhihong. Research on solid-state storage technology for integrated spaceborne electronic systems[D]. Beijing: University of Chinese Academy of Sciences, 2017 http://cdmd.cnki.com.cn/Article/CDMD-80073-1017119858.htm |
| [4] |
宋琪.星载固态存储管理技术的应用研究[D].北京: 中国科学院大学, 2015 SONG Qi. Applied research of space-borne solid state storage management technology[D]. Beijing: University of Chinese Academy of Sciences, 2015 http://cdmd.cnki.com.cn/Article/CDMD-80073-1015351185.htm |
| [5] |
董振兴.星载固态存储文件化管理方案应用研究[D].北京: 中国科学院大学, 2017 DONG Zhenxing. Applied research on filing management scheme of spaceborne solid state storage[D]. Beijing: University of Chinese Academy of Sciences, 2017 |
| [6] |
董振兴, 朱岩, 许志宏, 等. 星载存储器吞吐率瓶颈与高速并行缓存机制[J]. 哈尔滨工业大学学报, 2017, 49(11): 52. DONG Zhenxing, ZHU Yan, XU Zhihong, et al. Bottleneck analysis of spaceborne memory throughput and high-speed parallel caching mechanism design[J]. Journal of Harbin Institute of Technology, 2017, 49(11): 52. DOI:10.11918/j.issn.0367-6234.201611144 |
| [7] |
JI S, SHIN D. An efficient garbage collection for flash memory-based virtual memory systems[J]. IEEE Transactions on Consumer Electronics, 2010, 56(4): 2355. DOI:10.1109/TCE.2010.5681112 |
| [8] |
MA Dongzhe, FENG Jianhua, LI Guoliang. LazyFTL: A page-level flash translation layer optimized for NAND flash memory[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data. Athens, NJ: ACM, 2011: 12
|
| [9] |
GUAN Yong, WANG Guohui, WANG Yi, et al. BLog:Block-level log-block management for NAND flash memory storage systems[J]. ACM SIGPLAN Notices, 2013, 48(5): 111. DOI:10.1145/2499369.2465560 |
| [10] |
CHOUDHURI S, GIVARGIS T. Real-time access guarantees for NAND flash using partial block cleaning[C]//Proceedings of Software Technologies for Embedded and Ubiquitous Systems, 6th IFIP WG 10.2 International Workshop. Anacarpi, IT: Springer-Verlag, 2008. DOI: 10.1007/978-3-540-87785-1_13
|
| [11] |
QIN Zhiwei, WANG Yi, LIU Duo, et al. Real-time flash translation layer for NAND flash memory storage systems[C]//Proceedings of 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium. Beijing: IEEE, 2012: 1. DOI: 10.1109/RTAS.2012.27
|
| [12] |
JUNG D, KANG J U, JO H, et al. Superblock FTL:A superblock-based flash translation layer with a hybrid address translation scheme[J]. ACM Transactions on Embedded Computing Systems, 2010, 9(4): 1. DOI:10.1145/1721695.1721706 |