刘炜东，张玉生，康卫，胡爱兰

　　(华北计算机系统工程研究所，北京 100083)

　　摘要：Linux下常见的十余种文件系统的实时性都不理想。针对归档存储数据的特点，提出一种实时文件系统设计方案，并且设计了一种按照时间点检索的检索算法。文件系统的设计以减少读写文件时的不确定延迟为目的，主要减少写时寻道时间，简化索引机制，简化空闲磁盘块管理。

　　关键词：实时文件系统；数据索引；检索方法

0引言

　　工业生产环境对大规模数据的高效存储和访问有较高的需求。目前通用的关系型数据库的存储和检索速度不能满足这些场景的需求，而数据库对数据的存储和检索与文件系统对数据的组织管理和检索方式有较密切关系。

　　实时数据的采集、存储及传输等被广泛应用在军事、工业控制、民用以及实验室等场合。

　　目前，Linux操作系统已有文件系统的内部设计大多十分复杂,通用性好，功能多。但是针对特殊场景下的数据文件存储，它们复杂的存储结构导致存储延时大，限制系统性能，而且这些复杂设计中很多功能不会用到。因此，针对特定业务需求推出自己的文件系统是十分必要的。

1国内外研究现状

　　目前，文件系统实时化方案主要通过消除文件系统读写文件时给进程的执行引入的不确定时间延迟来实现［1］，如文件的存取空间分配一次完成，采用文件分级机制［2］；对同一文件的物理磁盘块采取连续分配策略，减少寻址消耗［3］；简化文件系统目录结构，只有一个根目录，允许存入127个文件，其索引节点全部保存在超级块中，绕过I/O高速缓冲，在外存与内存空间之间直接传输数据［1］。同时，另一方面研究在实时前提下提高文件系统的可靠性、可恢复性，如把文件存储到一块或多块，将文件特征信息保存到Flash块第一页，通过扫描文件特征恢复文件［4］。文件系统任务调度的实现也是一个研究方向，通过优化调整任务调度，提高文件服务的灵活性［5］。

2文件系统结构设计

　　针对应用设计的文件系统，其设计目的因具体应用场景不同而不同。因此，文件组织、文件管理、文件索引等方面的设计也不尽相同。专用的文件系统往往根据其独特的需求做修改，去掉不需要的功能，增加辅助接口，根据情境简化磁盘块管理的复杂度。

　　2.1数据索引方式

　　简化文件系统结构，只保留启动块、超级块和i_node区，一个文件对应一个i_node，重新设计文件内部数据块以及数据块的索引方式。如图1所示，数据索引使用两种索引：（1）数据索引，索引块之间通过链表的形式连接，当前索引块存储下一个数据索引块的位置；（2）数据索引的索引（二级索引）,存储所有数据索引块的位置，可能有多块，在文件关闭时，为二级索引分配连续磁盘块。i_node存储第一块数据索引的位置以及数据二级索引的位置和块数。

　　根据二级索引和索引可以计算出指定文件的指定数据块所在的磁盘块号。数据块使用1 KB，磁盘块号大小为32 bit，则一个索引块可以索引256 KB数据，一个二级索引块可以索引64 MB数据。一个1 TB硬盘中二级索引大小为16 MB。为减少读写数据时磁盘访问次数，在打开文件时，将二级索引全部缓存到内存；在关闭文件时，将二级索引一次性写回或者同步到磁盘。这样在读数据时，每次只需要两次读盘操作。在读写过程中，出现断电等情况可能导致二级索引没有写到磁盘，此时二级索引不可用。针对这种情况，文件系统可以通过顺序读取文件一级索引链恢复出文件二级索引。

　　2.2磁盘组织方式

　　由于存储的是归档历史数据，文件系统不提供删除文件功能，故可以简化磁盘空闲块管理（磁盘空闲块连续）和i_node管理，只需要记录下一个可以分配的磁盘块号或i_node即可，不再需要使用位示图等机制管理空闲块，减少了申请块等待时间［2］。文件系统在挂载时，读取超级块信息挂载磁盘，但不向VFS提供一致接口［6］，单独增加系统调用，在核心中增加代码向用户提供接口［7］。

　　如图2所示，文件i_node指向第一索引块，每一块索引存储下一索引块的块号，连接形式类似链表。这样保证了索引与数据相距不远，节省磁盘寻道时间。由于出现多个文件同时写，文件的索引块、文件的数据块都不连续，文件系统只保证二级索引是存储在内存中，在文件关闭时强制分配连续磁盘块一次性写入。

　　(1)数据块直接写到磁盘；数据块索引在存满后才写入磁盘，后于它索引的数据，如果在此期间出现问题，将导致索引丢失；索引的索引文件关闭时写到磁盘。

　　(2)超级块使用缓存，在空闲时或者一定时间内强制刷新；i_node区改写时同步到磁盘。

3数据检索机制

　　将归档数据的索引方式和文件系统中数据的索引方式融合在一起，即数据库和文件系统融合将提高数据库索引速度。

　　本文提出的文件系统设计方案针对的是存储数据，是按时间递增且采集频率在小范围内波动的归档历史数据。文件系统假设了每个文件存储的数据都是同类的格式化数据记录，也即每条记录的字段组成、字段长度相同。经过分析要存储的归档数据的特点，本文提出一种融合到文件系统中的数据检索算法，可以按时间点快速检索要查找数据记录所在的数据块。

　　3.1算法描述

　　通过已经读取的数据块中的时间点信息估算要搜索的时间点所在的索引块号。假设每个数据块中记录的时间跨度是Δt，Index0表示待搜索数据段的起始块号，t0、t′0分别表示起始块中起始时间、结束时间，t表示要搜索的时间点，则根据公式：

　　Index=Index0+(t－t0)/Δt

　　可以估算出数据块的位置Index，其中，Δt初始值Δt=t′0－t0，Index0=0。然后根据公式：

　　Δt′=(t′1－t0)·Δt/(t－t0)

　　计算当前段内平均每个数据块的时间跨度，其中，t1、t′1分别表示Index指向数据块的起始时间、结束时间；然后根据以下原则调整Δt、Index0、t0：

　　if(t1>t)

　　if(Δt<=Δt′+α)

　　Δt′=Δt′+α

　　Δt=Δt′

　　elif(t′1<t)

　　if(Index==TOTAL)

　　return－1//failed

　　if(Δt>=Δt′－α)

　　Δt′=Δt′－α

　　Δt=Δt′

　　if(Δt==0)return－1//failed

　　Index0=Index

　　t0=t1

　　else

　　return Index//find

　　重复以上步骤，可以逐渐逼近t所在的数据块。实际实现时，代码中添加了一些技巧，减少重复步骤，如估算t在当前读取位置附件直接查找前一块或者后一块而不再循环估计、每次循环Δt最小变化α等。3.2与二分查找作比较

　　通过与二分查找作比较来评估算法性能。对比结果是两种方法在相同的数据文件（时间点随机生成）中查找相同的时间点作比较，结果如表1所示。

注：文件是随机生成的1 000万条记录，随机查找给定时间范围内10万条记录。多次运行取平均结果。

　　从表1可以看出，在采集频率在小范围内波动的归档数据上按时间点检索数据，本文提出的检索算法优于二分检索，且两种算法检索成功和检索失败耗时相差不多，这是由于磁盘数据检索耗时主要在寻道和读磁盘块。

4结论

　　本文提出了一种新的文件数据组织索引结构，针对这种索引结构简化了磁盘上超级块、i_node等信息的组织结构。这种新的磁盘文件组织结构中新的空闲管理方式几乎可以保证只在写文件时磁头单向移动，减少了磁盘的寻道时间。同时，针对归档历史数据的特点设计了一种数据检索方式，通过与二分检索比较可以看出，这种检索方式对采集频率在一定范围波动的归档数据进行检索有显著的优势。

　　参考文献

　　［1］ 王振宇. Unix实时文件系统的设计［J］. 微电子学与计算机, 1996(4):3539.

　　［2］ 姜守旭, 蒋宗礼, 王丽. Linux下的实时文件系统研究［J］. 哈尔滨商业大学学报（自然科学版）, 2002, 18(2):151155.

　　［3］ 刘云生, 郭元苏. 实时文件系统的体系结构与调度策略［J］.计算机工程，2003，29(8):3233.

　　［4］ 张少波, 徐广辉, 田小锋,等. 基于NandFLASH高可靠自恢复实时文件系统［J］. 计算机工程与科学, 2012，34(6):169173.

　　［5］ 陈天洲, 赵懿, 沙峰, 等. 一种嵌入式实时文件系统任务调度的实现方法［P］.中国: CN 1877534 A， 20061213.

　　［6］ 顾喜梅, 顾宝根. 基于LINUX的文件系统机制的研究及实现方法［J］. 计算机工程与设计, 2002, 23(7):2022.

　　［7］ 谷建华, 朱庆九. UNIX文件系统实时化的实现［J］. 微电子学与计算机, 1995(5):1012.