劉煒東，張玉生，康衛(wèi)，胡愛蘭

　　(華北計算機系統(tǒng)工程研究所，北京 100083)

　　摘要：Linux下常見的十余種文件系統(tǒng)的實時性都不理想。針對歸檔存儲數(shù)據(jù)的特點，提出一種實時文件系統(tǒng)設(shè)計方案，并且設(shè)計了一種按照時間點檢索的檢索算法。文件系統(tǒng)的設(shè)計以減少讀寫文件時的不確定延遲為目的，主要減少寫時尋道時間，簡化索引機制，簡化空閑磁盤塊管理。

　　關(guān)鍵詞：實時文件系統(tǒng)；數(shù)據(jù)索引；檢索方法

0引言

　　工業(yè)生產(chǎn)環(huán)境對大規(guī)模數(shù)據(jù)的高效存儲和訪問有較高的需求。目前通用的關(guān)系型數(shù)據(jù)庫的存儲和檢索速度不能滿足這些場景的需求，而數(shù)據(jù)庫對數(shù)據(jù)的存儲和檢索與文件系統(tǒng)對數(shù)據(jù)的組織管理和檢索方式有較密切關(guān)系。

　　實時數(shù)據(jù)的采集、存儲及傳輸?shù)缺粡V泛應(yīng)用在軍事、工業(yè)控制、民用以及實驗室等場合。

　　目前，Linux操作系統(tǒng)已有文件系統(tǒng)的內(nèi)部設(shè)計大多十分復(fù)雜,通用性好，功能多。但是針對特殊場景下的數(shù)據(jù)文件存儲，它們復(fù)雜的存儲結(jié)構(gòu)導(dǎo)致存儲延時大，限制系統(tǒng)性能，而且這些復(fù)雜設(shè)計中很多功能不會用到。因此，針對特定業(yè)務(wù)需求推出自己的文件系統(tǒng)是十分必要的。

1國內(nèi)外研究現(xiàn)狀

　　目前，文件系統(tǒng)實時化方案主要通過消除文件系統(tǒng)讀寫文件時給進程的執(zhí)行引入的不確定時間延遲來實現(xiàn)［1］，如文件的存取空間分配一次完成，采用文件分級機制［2］；對同一文件的物理磁盤塊采取連續(xù)分配策略，減少尋址消耗［3］；簡化文件系統(tǒng)目錄結(jié)構(gòu)，只有一個根目錄，允許存入127個文件，其索引節(jié)點全部保存在超級塊中，繞過I/O高速緩沖，在外存與內(nèi)存空間之間直接傳輸數(shù)據(jù)［1］。同時，另一方面研究在實時前提下提高文件系統(tǒng)的可靠性、可恢復(fù)性，如把文件存儲到一塊或多塊，將文件特征信息保存到Flash塊第一頁，通過掃描文件特征恢復(fù)文件［4］。文件系統(tǒng)任務(wù)調(diào)度的實現(xiàn)也是一個研究方向，通過優(yōu)化調(diào)整任務(wù)調(diào)度，提高文件服務(wù)的靈活性［5］。

2文件系統(tǒng)結(jié)構(gòu)設(shè)計

　　針對應(yīng)用設(shè)計的文件系統(tǒng)，其設(shè)計目的因具體應(yīng)用場景不同而不同。因此，文件組織、文件管理、文件索引等方面的設(shè)計也不盡相同。專用的文件系統(tǒng)往往根據(jù)其獨特的需求做修改，去掉不需要的功能，增加輔助接口，根據(jù)情境簡化磁盤塊管理的復(fù)雜度。

　　2.1數(shù)據(jù)索引方式

　　簡化文件系統(tǒng)結(jié)構(gòu)，只保留啟動塊、超級塊和i_node區(qū)，一個文件對應(yīng)一個i_node，重新設(shè)計文件內(nèi)部數(shù)據(jù)塊以及數(shù)據(jù)塊的索引方式。如圖1所示，數(shù)據(jù)索引使用兩種索引：（1）數(shù)據(jù)索引，索引塊之間通過鏈表的形式連接，當(dāng)前索引塊存儲下一個數(shù)據(jù)索引塊的位置；（2）數(shù)據(jù)索引的索引（二級索引）,存儲所有數(shù)據(jù)索引塊的位置，可能有多塊，在文件關(guān)閉時，為二級索引分配連續(xù)磁盤塊。i_node存儲第一塊數(shù)據(jù)索引的位置以及數(shù)據(jù)二級索引的位置和塊數(shù)。

　　根據(jù)二級索引和索引可以計算出指定文件的指定數(shù)據(jù)塊所在的磁盤塊號。數(shù)據(jù)塊使用1 KB，磁盤塊號大小為32 bit，則一個索引塊可以索引256 KB數(shù)據(jù)，一個二級索引塊可以索引64 MB數(shù)據(jù)。一個1 TB硬盤中二級索引大小為16 MB。為減少讀寫數(shù)據(jù)時磁盤訪問次數(shù)，在打開文件時，將二級索引全部緩存到內(nèi)存；在關(guān)閉文件時，將二級索引一次性寫回或者同步到磁盤。這樣在讀數(shù)據(jù)時，每次只需要兩次讀盤操作。在讀寫過程中，出現(xiàn)斷電等情況可能導(dǎo)致二級索引沒有寫到磁盤，此時二級索引不可用。針對這種情況，文件系統(tǒng)可以通過順序讀取文件一級索引鏈恢復(fù)出文件二級索引。

　　2.2磁盤組織方式

　　由于存儲的是歸檔歷史數(shù)據(jù)，文件系統(tǒng)不提供刪除文件功能，故可以簡化磁盤空閑塊管理（磁盤空閑塊連續(xù)）和i_node管理，只需要記錄下一個可以分配的磁盤塊號或i_node即可，不再需要使用位示圖等機制管理空閑塊，減少了申請塊等待時間［2］。文件系統(tǒng)在掛載時，讀取超級塊信息掛載磁盤，但不向VFS提供一致接口［6］，單獨增加系統(tǒng)調(diào)用，在核心中增加代碼向用戶提供接口［7］。

　　如圖2所示，文件i_node指向第一索引塊，每一塊索引存儲下一索引塊的塊號，連接形式類似鏈表。這樣保證了索引與數(shù)據(jù)相距不遠(yuǎn)，節(jié)省磁盤尋道時間。由于出現(xiàn)多個文件同時寫，文件的索引塊、文件的數(shù)據(jù)塊都不連續(xù)，文件系統(tǒng)只保證二級索引是存儲在內(nèi)存中，在文件關(guān)閉時強制分配連續(xù)磁盤塊一次性寫入。

　　(1)數(shù)據(jù)塊直接寫到磁盤；數(shù)據(jù)塊索引在存滿后才寫入磁盤，后于它索引的數(shù)據(jù)，如果在此期間出現(xiàn)問題，將導(dǎo)致索引丟失；索引的索引文件關(guān)閉時寫到磁盤。

　　(2)超級塊使用緩存，在空閑時或者一定時間內(nèi)強制刷新；i_node區(qū)改寫時同步到磁盤。

3數(shù)據(jù)檢索機制

　　將歸檔數(shù)據(jù)的索引方式和文件系統(tǒng)中數(shù)據(jù)的索引方式融合在一起，即數(shù)據(jù)庫和文件系統(tǒng)融合將提高數(shù)據(jù)庫索引速度。

　　本文提出的文件系統(tǒng)設(shè)計方案針對的是存儲數(shù)據(jù)，是按時間遞增且采集頻率在小范圍內(nèi)波動的歸檔歷史數(shù)據(jù)。文件系統(tǒng)假設(shè)了每個文件存儲的數(shù)據(jù)都是同類的格式化數(shù)據(jù)記錄，也即每條記錄的字段組成、字段長度相同。經(jīng)過分析要存儲的歸檔數(shù)據(jù)的特點，本文提出一種融合到文件系統(tǒng)中的數(shù)據(jù)檢索算法，可以按時間點快速檢索要查找數(shù)據(jù)記錄所在的數(shù)據(jù)塊。

　　3.1算法描述

　　通過已經(jīng)讀取的數(shù)據(jù)塊中的時間點信息估算要搜索的時間點所在的索引塊號。假設(shè)每個數(shù)據(jù)塊中記錄的時間跨度是Δt，Index0表示待搜索數(shù)據(jù)段的起始塊號，t0、t′0分別表示起始塊中起始時間、結(jié)束時間，t表示要搜索的時間點，則根據(jù)公式：

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

　　可以估算出數(shù)據(jù)塊的位置Index，其中，Δt初始值Δt=t′0－t0，Index0=0。然后根據(jù)公式：

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

　　計算當(dāng)前段內(nèi)平均每個數(shù)據(jù)塊的時間跨度，其中，t1、t′1分別表示Index指向數(shù)據(jù)塊的起始時間、結(jié)束時間；然后根據(jù)以下原則調(diào)整Δ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

　　重復(fù)以上步驟，可以逐漸逼近t所在的數(shù)據(jù)塊。實際實現(xiàn)時，代碼中添加了一些技巧，減少重復(fù)步驟，如估算t在當(dāng)前讀取位置附件直接查找前一塊或者后一塊而不再循環(huán)估計、每次循環(huán)Δt最小變化α等。3.2與二分查找作比較

　　通過與二分查找作比較來評估算法性能。對比結(jié)果是兩種方法在相同的數(shù)據(jù)文件（時間點隨機生成）中查找相同的時間點作比較，結(jié)果如表1所示。

注：文件是隨機生成的1 000萬條記錄，隨機查找給定時間范圍內(nèi)10萬條記錄。多次運行取平均結(jié)果。

　　從表1可以看出，在采集頻率在小范圍內(nèi)波動的歸檔數(shù)據(jù)上按時間點檢索數(shù)據(jù)，本文提出的檢索算法優(yōu)于二分檢索，且兩種算法檢索成功和檢索失敗耗時相差不多，這是由于磁盤數(shù)據(jù)檢索耗時主要在尋道和讀磁盤塊。

4結(jié)論

　　本文提出了一種新的文件數(shù)據(jù)組織索引結(jié)構(gòu)，針對這種索引結(jié)構(gòu)簡化了磁盤上超級塊、i_node等信息的組織結(jié)構(gòu)。這種新的磁盤文件組織結(jié)構(gòu)中新的空閑管理方式幾乎可以保證只在寫文件時磁頭單向移動，減少了磁盤的尋道時間。同時，針對歸檔歷史數(shù)據(jù)的特點設(shè)計了一種數(shù)據(jù)檢索方式，通過與二分檢索比較可以看出，這種檢索方式對采集頻率在一定范圍波動的歸檔數(shù)據(jù)進行檢索有顯著的優(yōu)勢。

　　參考文獻

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

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

　?。?］ 劉云生, 郭元蘇. 實時文件系統(tǒng)的體系結(jié)構(gòu)與調(diào)度策略［J］.計算機工程，2003，29(8):3233.

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

　　［5］ 陳天洲, 趙懿, 沙峰, 等. 一種嵌入式實時文件系統(tǒng)任務(wù)調(diào)度的實現(xiàn)方法［P］.中國: CN 1877534 A， 20061213.

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

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