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

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

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

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

0引言

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

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

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

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

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

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

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

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

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

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

　　2.2磁盤組織方式

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

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

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

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

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

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

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

　　3.1算法描述

　　通過(guò)已經(jīng)讀取的數(shù)據(jù)塊中的時(shí)間點(diǎn)信息估算要搜索的時(shí)間點(diǎn)所在的索引塊號(hào)。假設(shè)每個(gè)數(shù)據(jù)塊中記錄的時(shí)間跨度是Δt，Index0表示待搜索數(shù)據(jù)段的起始?jí)K號(hào)，t0、t′0分別表示起始?jí)K中起始時(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與二分查找作比較

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

注：文件是隨機(jī)生成的1 000萬(wàn)條記錄，隨機(jī)查找給定時(shí)間范圍內(nèi)10萬(wàn)條記錄。多次運(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)，針對(duì)這種索引結(jié)構(gòu)簡(jiǎn)化了磁盤上超級(jí)塊、i_node等信息的組織結(jié)構(gòu)。這種新的磁盤文件組織結(jié)構(gòu)中新的空閑管理方式幾乎可以保證只在寫文件時(shí)磁頭單向移動(dòng)，減少了磁盤的尋道時(shí)間。同時(shí)，針對(duì)歸檔歷史數(shù)據(jù)的特點(diǎn)設(shè)計(jì)了一種數(shù)據(jù)檢索方式，通過(guò)與二分檢索比較可以看出，這種檢索方式對(duì)采集頻率在一定范圍波動(dòng)的歸檔數(shù)據(jù)進(jìn)行檢索有顯著的優(yōu)勢(shì)。

　　參考文獻(xiàn)

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

　　［2］ 姜守旭, 蔣宗禮, 王麗. 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.

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

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

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