劉煒東，張玉生，康衛，胡愛蘭

　　(華北計算機系統工程研究所，北京 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等信息的組織結構。這種新的磁盤文件組織結構中新的空閑管理方式幾乎可以保證只在寫文件時磁頭單向移動，減少了磁盤的尋道時間。同時，針對歸檔歷史數據的特點設計了一種數據檢索方式，通過與二分檢索比較可以看出，這種檢索方式對采集頻率在一定范圍波動的歸檔數據進行檢索有顯著的優勢。

　　參考文獻

　?。?］ 王振宇. Unix實時文件系統的設計［J］. 微電子學與計算機, 1996(4):3539.

　　［2］ 姜守旭, 蔣宗禮, 王麗. Linux下的實時文件系統研究［J］. 哈爾濱商業大學學報（自然科學版）, 2002, 18(2):151155.

　?。?］ 劉云生, 郭元蘇. 實時文件系統的體系結構與調度策略［J］.計算機工程，2003，29(8):3233.

　?。?］ 張少波, 徐廣輝, 田小鋒,等. 基于NandFLASH高可靠自恢復實時文件系統［J］. 計算機工程與科學, 2012，34(6):169173.

　?。?］ 陳天洲, 趙懿, 沙峰, 等. 一種嵌入式實時文件系統任務調度的實現方法［P］.中國: CN 1877534 A， 20061213.

　?。?］ 顧喜梅, 顧寶根. 基于LINUX的文件系統機制的研究及實現方法［J］. 計算機工程與設計, 2002, 23(7):2022.

　?。?］ 谷建華, 朱慶九. UNIX文件系統實時化的實現［J］. 微電子學與計算機, 1995(5):1012.