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

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

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

　　關(guān)鍵詞：實(shí)時(shí)文件系統(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í)時(shí)數(shù)據(jù)的采集、存儲及傳輸?shù)缺粡V泛應(yīng)用在軍事、工業(yè)控制、民用以及實(shí)驗(yàn)室等場合。

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

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

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

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

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

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

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

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

　　2.2磁盤組織方式

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

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

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

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

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

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

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

　　3.1算法描述

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

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

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

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

　　計(jì)算當(dāng)前段內(nèi)平均每個(gè)數(shù)據(jù)塊的時(shí)間跨度，其中，t1、t′1分別表示Index指向數(shù)據(jù)塊的起始時(shí)間、結(jié)束時(shí)間；然后根據(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ù)塊。實(shí)際實(shí)現(xiàn)時(shí)，代碼中添加了一些技巧，減少重復(fù)步驟，如估算t在當(dāng)前讀取位置附件直接查找前一塊或者后一塊而不再循環(huán)估計(jì)、每次循環(huán)Δt最小變化α等。3.2與二分查找作比較

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

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

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

4結(jié)論

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

　　參考文獻(xiàn)

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

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

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

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

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

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

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