基于二元组索引的低内存开销快速文件管理方法_姜菁菁.pdf

第 卷 第 期 年 月空间控制技术与应用 :引引用用格格式式：姜菁菁，乔磊，杨孟飞等 基于二元组索引的低内存开销快速文件管理方法 空间控制技术与应用，（）：，（）：（）：基于二元组索引的低内存开销快速文件管理方法姜菁菁，乔 磊，杨孟飞，苗志富，周育逵，刘 波，田 飞 北京控制工程研究所，北京 中国空间技术研究院，北京 中国科学院软件研究所计算机科学国家重点实验室，北京 建设综合勘查研究设计院有限公司，北京 摘 要：在航天器上采用 设备作为存储介质，需要采用文件系统来管理存储设备 在航天嵌入式系统中，数据存储的规模越来越大，进行采集任务产生的数据量将达到 级别 出于安全性的考虑，航天器嵌入式系统内存容量受限，并且实时性要求极高 普通嵌入式系统在内存容量和实时性的要求同航天嵌入式系统相差较多，因此不适用于航天嵌入式系统 本文针对航天器系统资源受限的特殊需求，对嵌入式系统中常用的 文件系统中存在的内存中文件索引结构占用空间随文件数据量线性增长的问题，提出基于二元组索引的低内存开销快速文件管理（，）方法，通过基于 树引入二元组链表结构对连续 页进行统一索引，并依据索引结构设计文件读、文件写操作算法，具有文件系统内存占用小，读写文件速度快的特点 实验结果表明，相比于 索引方法，对任意数据量的文件：）当文件数据所在闪存页达到平均 个页以上连续时，方法内存占用低于 方法，最高节省 ；）在文件规模大于 时，方法的文件读写时间始终小于 的文件读写时间，并且 文件写时间和 写时间之差随文件大小呈线性增长趋势 方法更适合于文件数据量大且存储在大量连续页的情境下关键词：航天器；文件系统；二元组；索引中图分类号：文献标志码：文章编号：（）收稿日期：；录用日期：基金项目：国家自然科学基金资助项目（）通信作者：引 言随着航天器等无人系统智能化要求越来越高，比如火星车，需要在遥远火星开展自主任务规划，并要保证快速反应以确保可靠性 在此过程中，持续产生的大规模图像、视频流数据将存放在火星车的大容量 闪存介质中，通过闪存文件系统进行存储和管理 闪存文件系统能够有效管理闪存空间，即闪存区域中每个闪存块、闪存页的使用情况、每个文件的属性、每个文件的数据在闪存中的存储位置等信息能够在内存中正确的表示出来 通过内存中的文件系统信息，能够对分配闪存空间、回收闪存空间、查找文件数据在闪存的位置等操作进行管理 在系统断电之前，将内存中的文件系统信息写入到闪存中，以使得闪存中记录的文件系统属性信息为最新的属性信息，使得文件系统属性信息与闪存中的信息保持一致性另一方面，由于航天器特殊的运行环境，其上计算、存储等资源受到极大制约，航天器嵌入式计第 期姜菁菁等：基于二元组索引的低内存开销快速文件管理方法算机系统内存空间通常为几兆字节到几十兆字节规模 在这种内存资源受限的条件下，当 存储介质的存储容量较大且需要存储大规模流数据时，文件系统在内存中因构建索引结构而占用的空间随文件数量线性增长，一般的嵌入式文件系统难以直接应用，主要存在问题：）为保证嵌入式系统的实时性，一些文件系统的索引结构采用将索引文件数据的结构放入内存中维护，且文件数据的索引一般采用树型结构或链表结构，导致内存消耗较大；）为降低嵌入式系统中文件系统占用的内存空间，一些文件系统将文件数据的索引放入外部存储设备或非易失性内存中去维护，导致文件操作的响应时间长 而目前的研究没有充分考虑这两个方面性能的均衡性本文针对上述问题，兼顾两个方面，提出基于二元组索引的低内存开销快速文件管理（，）方法，该方法既考虑到内存空间占用又考虑文件读写操作的时间 本文主要贡献在于：）方法基于二元组结构来索引连续闪存页中存储的数据，当文件数据存储在大量连续的闪存页时，能够有效降低内存中文件索引占用的内存空间；）在索引结构的基础上设计新的文件读写操作算法，设计的向文件中写入数据时采取一次性分配完需要的闪存页并以二元组链表记录，分配完成后将数据依次写入到这些闪存页中，并将二元组链表插入到文件索引树中，这个过程同 每次分配一个页并将一个页插入到文件索引树中的过程相比，能够有效降低建立索引树的时间；）将 应用在火星车操作系统中，并对内存占用情况和文件读写操作时间进行实验验证和评价 相关研究闪存由于其本身的结构和特点不同于磁盘，因此传统的磁盘文件系统无法直接应用到基于闪存介质的系统中 目前有两种方法来管理闪存空间，基于 闪存转换层的磁盘文件系统和直接管理闪存的直接闪存文件系统 闪存转换层将闪存空间模拟成磁盘空间，每次将数据写入闪存或从指定闪存位置读出数据时都需要计算闪存页与磁盘块的对应关系，这会导致文件系统对闪存的管理是低效的，对于要求高实时性的嵌入式文件系统并不适用 与带 层的磁盘文件系统相比，直接管理闪存的文件系统更加高效 对于文件系统，主要有两个方面的研究：内存资源消耗和文件操作时间在降低内存资源消耗方面，一些文件系统将文件索引结构放入外部存储设备中去维护 文件系统将文件对应的 树结构写在闪存中特定区域，并在闪存上维护 在 中，访问一个文件时，首先需要将该文件对应的索引结构加载到内存中，然后完成文件的读取访问操作 但是，当更新文件时，该文件以及包含该文件的目录会进行更新，同样，后面的目录需依次更新，直到完成根目录的更新，这个过程会导致大量的 操作，对于实时性要求高的系统并不适用 文件系统为降低内存占用，只将文件目录树以及目录元数据索引数组放入内存中，当读取一个指定文件的数据时，首先通过目录树找到该文件对应的目录，然后从闪存中该目录的数据中定位到该文件元数据所在的闪存页，然后通过文件的元数据找到文件数据的位置 在内存中换入换出文件目录的数据会增大定位文件数据的时间开销 等采用一个简易的树结构对闪存数据块进行索引，对文件进行随机读写时，能够保证随文件数据量的增大，页面读写数量不变 但是，当对文件进行更新时，对一个块中的数据进行更新则会将该块中不需更新的部分写入到新分配的块中并将该块号添加到索引树中，在这个过程数据的换入换出导致大量的 操作，在实时性系统中并不适用 等设计采用非易失性内存作为存储文件元数据的介质，闪存作为文件数据的存储介质，对数据进行了有效管理来降低传统的存储在闪存中的索引开销，但是非易失性内存容易带来安全问题，在航天器应用场景中，被野指针修改非易失性内存上的数据会带来严重问题 等提出了一种轻量级、快速、可靠的文件系统，将文件系统中的元数据设置为固定大小的格式，该文件系统基于 来持久化存储文件元数据，用闪存持久化存储文件数据，并且在文件系统存在周期内需要将文件元数据加载到 内存中，中数据修改的同时要修改 以保持一致性，这会消耗较长的操作时间 空间控制技术与应用第 卷等为解决存储在大容量存储设备上的文件索引频繁的 操作带来的性能下降的问题，提出一个轻量级索引结构，该结构将 同该 的子索引项存储到同一个闪存页中，当查找时将该 加载到内存中，否则该 只存储在闪存中 这些设计充分考虑了文件索引如何尽量减小内存占用量，但是，这些设计的大量 操作会导致文件操作的执行时间增大，无法保证文件操作的实时性 为降低由于大量小文件导致的元数据占用内存大的场景，等提出一种复合文件文件系统方法，该方法将每个文件对应一个元数据的方法改进为多个文件对应一个元数据，当多个文件经常一起访问时，可以合并这些文件来降低内存占用 但是，定位每个文件的数据索引时，相比于一对一的文件和元数据的方法，会增加定位到文件数据的时间 为减少由于更新数据导致的写放大问题，等提出引入一个新的层，当数据被更新时，这些数据将以持久的方式被记录到该层中，从而实现更好的写性能，降低写放大带来的闪存块过早成为坏块 采用这种方式可以节省闪存区域并且减少写放大，但是读取文件数据时会放大文件读取的时间在降低文件操作的时间方面，有些文件系统将文件索引结构放入内存中维护且采用树等结构提高查找效率 同 最大的不同为：在挂载过程中需要扫描所有的闪存页并将文件的索引结构在内存中建立起来并在内存中维护，中挂载时不需要将所有文件的索引加载到内存中，当要访问一个文件时才将文件的索引结构从闪存中加载到内存中 在内存中定义了一系列链表用来索引文件数据，在内存中定义文件 树结构，用来索引文件数据，叶子节点索引文件数据在闪存页的位置，内部节点索引下一层节点的首地址 中 树方法对闪存页进行索引时，每个叶子节点中的一个位置对应一个闪存页号，对于查找指定的页或删除指定的页，能够以（）的时间复杂度完成 文件系统采用区段树索引存储设 备 的 块号，其中间接索引结构的叶子节点采用（首块 偏移量）的形式表示，这种形式可以用一个节点表示多个块号 但是当需要定位指定偏移的节点时，由于每个 表示的块数不确定，需要从头遍历所有的叶子节点直到搜索指定节点，相对于 的索引方式，该方法在搜索指定偏移量时需耗费更多的时间 相对于，虽然采用树结构，但是同 的链表结构相比，文件系统的内存占用要低于 因此，本研究基于现有的文件系统，在内存占用和文件操作的时间两个方面进行研究，设计索引结构和相应文件操作 文件管理方法 航天器在数据管理方面的背景需求航天器系统中，数据存储的规模越来越大，并且数据形式越来越多样，图像视频等流式多媒体越来越海量 流式文件的读写具有顺序性、规模大的特点 在实际数据采集过程中，一般情况下只有该任务进行，没有其他任务打断该任务 在这种背景之下，文件系统的设计需要充分利用这两个方面特性，以达到充分满足占用内存资源较小的情况下有效管理各种文件的目标 内存中索引结构设计由于空间环境的特殊条件，空间嵌入式系统的资源通常十分有限 考虑到星上采集的数据大多为流数据，数据量大，且数据在闪存中的存储位置大部分连续 采取传统的 树结构的单一叶子节点对应一个闪存物理页的方式，没有充分利用连续页的优势，占用大量内存空间本文提出的 方法（如图）采用纵向与横向结构混合的方式设计新的文件数据索引结构：内部节点采用 树的结构，叶子节点采用二元组链表表示 每个内部节点由一组长度为 的数组表示，数组中每个位置存储下一层的每个节点的首地址每个内部节点占用的空间为 位 位，每个叶子节点以一组二元组结构链表的形式表示，每个二元组节点存储一个二元组结构，二元组结构为（，），由 位的无符号整型数据表示，由 位的无符号整型数据表示 其中 所代表的长度为可变长度，该二元组代表着数据存储的位置从前到后依次为，每组链表总共能够索引 个闪存页 当数据存储在大量连续页的情况时，通过这种方式可以保证叶子节点内存占用量小 纵向上采用树的结构能够保持查找指定闪存页的时间 横向上将叶子节点设计为一组链表的结构，一组叶子节点链表能够索引第 期姜菁菁等：基于二元组索引的低内存开销快速文件管理方法特定个数的物理页，这种方式使得在对指定的偏移页进行查找时能够准确定义该位置对应的叶子节点链表首地址，采用链表的形式索引物理页二元组，当删除操作执行时，能够实现灵活的删除节点，相对于数组形式的索引，降低了内存空间 对于文件中某些数据页更新能实现快速定位到链表首节点位置以及通过增加或删除节点实现对闪存页序号索引的更新 与 的索引方法相比，该方法在查找指定偏移对应的物理页时能够通过计算定位到该偏移对应的链表的首地址，而不需要遍历所有叶子节点，节省了查找时间 并且在文件中数据更新时，的索引方法会导致写放大的问题，而本文提出的方法不会造成写放大对于 方法，无论叶子节点还是内部节点，每个节点占用的内存空间都为 位 位 假设一个文件对应的 树的高度为，则该树能表示的文件最大页数 为：位（）此时，内部节点占用 总空间为：位（）叶子节点占用总空间：位；（）因此，一个高度为 的最大文件索引树占用的总内存空间占用 为：（）方法的索引结构能够表示的最大文件页数 和索引最大文件页数内部节点占用的空间同 方法的相同 在 方法中，由于叶子节点采用链表形式表示，每个链表中包含三个元素：二元组首页，二元组偏移，指向下一个节点的指针 因此链表中每个节点占用 位 位的内存空间 假设平均（且 为 的整数倍）个页连续，则索引树高为 的文件最大页数需要的