多維元數(shù)據(jù)索引文件系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

史軍勇 李文靜

摘要：容量龐大的磁盤外部存儲(chǔ)設(shè)備導(dǎo)致文件檢索性能下降，傳統(tǒng)的“按名檢索”方法已經(jīng)無法滿足海量文件系統(tǒng)檢索需求，面向近些年流行的多維索引技術(shù)，應(yīng)用R樹設(shè)計(jì)和實(shí)現(xiàn)一個(gè)基于文件屬性的多維元數(shù)據(jù)索引文件系統(tǒng)MIFS，分析了MIFS目錄樹多屬性索引結(jié)構(gòu)和插入、刪除、分裂操作算法，闡述了MIFS索引結(jié)構(gòu)的物理實(shí)現(xiàn)及其用戶接口，最后，實(shí)驗(yàn)測(cè)試了MIFS和Ext 3文件系統(tǒng)用戶接口的周轉(zhuǎn)時(shí)間，結(jié)果表明MIFS文件檢索性能得到了顯著提高。

關(guān)鍵詞：多維元數(shù)據(jù)索引;文件系統(tǒng);R樹;降維;用戶接口

中圖分類號(hào)：TP316? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）16-0026-04

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

Research and Implementation of Multi-dimensional Meta-data Indexing File System

SHI Jun-yong， LI Wen-jing

（Zhengzhou Institute of Aeronautical Industry Management， Zhengzhou 450046，China）

Abstract：Huge capacity of disk storage device descends the file searching performance and traditional method of searching by name couldnt satisfied the demand of file system. Combined with the popular multi-dimension indexing technology in recent years， a kind of multi-dimension meta-data indexing file system named MIFS is designed and realized based on R-tree. Multi-properties index structure of file system directory tree and operating algorithms which include insert， delete， split are analyzed. Physical realization of index structure and user interface are discussed. In the end， the turnaround time of MIFS user interface operations is compared with Ext3 file system user interface operations and the test result shows that the file searching performance of MIFS is substantially improved.

Key words：multi-dimension meta-data index; file syste; R-tree; dimension reduction; user interface

1 引言

為了滿足海量信息存儲(chǔ)，外存儲(chǔ)設(shè)備容量在過去的10年得到顯著提升，磁盤存儲(chǔ)容量已經(jīng)從GB數(shù)量級(jí)上升到TB數(shù)量級(jí)，基于外存儲(chǔ)設(shè)備的文件檢索已經(jīng)成為系統(tǒng)軟件設(shè)計(jì)者必須面臨的一個(gè)問題。

外存儲(chǔ)設(shè)備的信息存儲(chǔ)結(jié)構(gòu)相比于存儲(chǔ)容量發(fā)展緩慢，依然以文件作為基本信息存儲(chǔ)單元，采用多層樹狀目錄結(jié)構(gòu)，文件系統(tǒng)類型主要有FAT、NTFS和EXT2。FAT文件系統(tǒng)采用順序檢索，效率不高。為了改善“按名檢索”的效率，NTFS文件系統(tǒng)采用B+樹結(jié)構(gòu)按文件名索引目錄項(xiàng)[1]，Ext2/Ext3文件系統(tǒng)則將文件名和文件屬性分開存儲(chǔ)，引入索引結(jié)點(diǎn)概念。傳統(tǒng)的“按名檢索”僅能從一維空間區(qū)分文件，而無法從多維空間區(qū)分文件。Apple公司在Mac OS中實(shí)現(xiàn)的Spotlight基于文件屬性存取允許從多維空間區(qū)分文件，但其封閉性無法得到廣泛推廣。近些年，多維索引技術(shù)不斷被應(yīng)用到文件系統(tǒng)中，如K-D樹[2]、四叉樹[3]。本文在Ext2/Ext3文件系統(tǒng)的基礎(chǔ)上，提出了一種采用R樹實(shí)現(xiàn)的多維元數(shù)據(jù)索引文件系統(tǒng)（Multi-dimensional Indexing File System， MIFS），能夠?qū)Χ嗑S文件屬性索引，實(shí)現(xiàn)多字段聯(lián)合查詢，提高文件檢索效率。

2 R樹

1984年，R[4]樹由Guttman提出，它是目前最流行的動(dòng)態(tài)空間索引結(jié)構(gòu)之一，廣泛應(yīng)用于原型研究和商用空間數(shù)據(jù)庫系統(tǒng)。R樹是一棵平衡樹，中間結(jié)點(diǎn)和葉子結(jié)點(diǎn)由M個(gè)結(jié)構(gòu)為（I，Pointer）的單元組成，中間結(jié)點(diǎn)的Pointer指向子結(jié)點(diǎn)，葉子結(jié)點(diǎn)的Pointer指向索引對(duì)象。I定義為：

I=（I1， I2， I3， I4， … ， In）

式中，n是空間對(duì)象的維數(shù)，Ii是第i維上的坐標(biāo)范圍[a，b]。若結(jié)點(diǎn)是中間結(jié)點(diǎn)，則I是其所有子結(jié)點(diǎn)的最小包含矩形MBR;若結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則I是索引對(duì)象的最小包含矩形MBR。

R樹上定義的操作有初始化、檢索、插入、刪除和分裂。

Initialize（R） 初始化操作，設(shè)置一個(gè)空的R樹。

Search（R， S） 檢索操作，在R樹中查找位于S超幾何體域中的空間對(duì)象，S超幾何體的空間維數(shù)等同于R樹索引對(duì)象維數(shù)。

Insert（R， Obj） 插入操作，在R樹中插入Obj空間對(duì)象。

Delete（R， Obj） 刪除操作，在R樹中刪除Obj空間對(duì)象。

Split（R， Node） 分裂操作，當(dāng)R樹的中間結(jié)點(diǎn)或葉子結(jié)點(diǎn)達(dá)到最大單元個(gè)數(shù)時(shí)，執(zhí)行此操作。Node指向R樹的中間結(jié)點(diǎn)或葉子結(jié)點(diǎn)。

R樹是一種動(dòng)態(tài)查找結(jié)構(gòu)，插入、刪除和檢索可以同時(shí)進(jìn)行，不需要周期性地重組查找結(jié)構(gòu)。R樹兄弟結(jié)點(diǎn)索引區(qū)域重疊，存在多路徑查詢問題，如圖1所示。為了提高R樹的檢索性能，Selis等人于1987年提出了R+樹[5]，通過對(duì)象分割，解決多路徑查詢問題。而Beckmann等人認(rèn)為區(qū)域重疊并不會(huì)導(dǎo)致更壞的檢索性能，于1990年設(shè)計(jì)了R*樹[6]，通過優(yōu)化R樹結(jié)點(diǎn)分裂方法，使得目錄矩形（某一查詢路徑的所有MBR）更近似于正方形。另外，R樹的優(yōu)化還在于提高結(jié)點(diǎn)存儲(chǔ)利用率，如Hilbert R樹[7]、Compact R樹[8]等。

3 MIFS文件系統(tǒng)設(shè)計(jì)

3.1 多維文件屬性索引

異構(gòu)文件系統(tǒng)設(shè)有不同數(shù)量的文件屬性，但通常都包含基本文件管理信息、文件安全管理信息和文件存儲(chǔ)結(jié)構(gòu)信息。基本文件管理信息如文件名、文件主、關(guān)鍵字、摘要、文件訪問時(shí)間等。文件安全管理信息用于文件存取訪問控制，實(shí)現(xiàn)文件的安全管理，如文件主訪問控制列表、文件主組訪問控制列表等。文件存儲(chǔ)結(jié)構(gòu)信息包含文件的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)信息，描述文件信息的組織方式。文件系統(tǒng)用戶接口大多基于基本文件管理信息，如文件創(chuàng)建、刪除、檢索等操作。表1列出了Ext2/Ext3文件系統(tǒng)支持的基本文件管理信息[9]。

MIFS文件系統(tǒng)對(duì)多維文件屬性采用R樹索引結(jié)構(gòu)。R樹的索引空間通常都會(huì)選擇3～4維，隨著維數(shù)的增加，R樹結(jié)點(diǎn)間重疊區(qū)域快速增長(zhǎng)，檢索性能也急劇惡化，最終會(huì)陷入維數(shù)危機(jī)[10]。MIFS按文件屬性類型及其相關(guān)性分為k個(gè)組，每一個(gè)組定義為一個(gè)屬性組（G）。Ext2/Ext3文件系統(tǒng)基本文件管理信息可以分為4個(gè)組，即文件名組、用戶標(biāo)識(shí)符組，尺寸組和時(shí)間組，文件名組只包含name，用戶標(biāo)識(shí)符組包含i_uid和i_gid，尺寸組包含i_size和i_blocks，時(shí)間組包含i_atime、i_ctime、i_mtime和i_dtime。設(shè)每個(gè)屬性組包含有di個(gè)文件屬性θ，定義第i個(gè)屬性組Gi定義為一個(gè)二維向量，如公式（1）。

[Gi=α，βα=MINθ1，θ2，...，θdiβ=MAXθ1，θ2，...，θdi]? ? ? ? ? ? ? ? ? ? ? （1）

MIFS按屬性組索引，由先前的文件點(diǎn)對(duì)象索引轉(zhuǎn)換成對(duì)超幾何體對(duì)象的索引，R樹結(jié)點(diǎn)中的任一個(gè)單元描述一個(gè)超幾何體，父結(jié)點(diǎn)的超幾何體包含所有子結(jié)點(diǎn)的超幾何體，索引維數(shù)從[i=1kdi]維降低到k維。文件檢索算法首先是用超幾何體對(duì)象圈定一個(gè)文件存在的粗糙范圍，然后再精確匹配文件，具體過程可描述為：

step 1：將以多維完全或非完全屬性檢索的文件對(duì)象按公式（1）轉(zhuǎn)換為k維超幾何體Obj。未指定屬性取值范圍設(shè)定為正負(fù)無窮;屬性組內(nèi)屬性取值范圍邏輯關(guān)系始終為或，取最小值與最大值作為范圍;屬性組間屬性取值邏輯關(guān)系若為且，則檢索的k維超幾何體只有一個(gè)，若為或，則檢索的k維超幾何體有多個(gè)，每一個(gè)或因子即為一個(gè)被檢索超幾何體。

step 2：從R樹的根結(jié)點(diǎn)L開始。如果L不是葉子結(jié)點(diǎn)，遍歷L中的所有單元，判斷每一個(gè)單元I與Obj的關(guān)系，如果I與Obj相交，則令單元所指的子結(jié)點(diǎn)為根結(jié)點(diǎn)L，遞歸調(diào)用直到L是葉子結(jié)點(diǎn)。

step 3：判斷L結(jié)點(diǎn)中的空間對(duì)象是否滿足多維屬性檢索要求，如果滿足，則輸出該文件對(duì)象，否則，略過。

3.2 插入文件算法

插入文件算法描述為：

step 1： 按公式（1）將文件對(duì)象轉(zhuǎn)換為k維超幾何體Obj。

step 2： 尋找一個(gè)合適的葉子結(jié)點(diǎn)L存放文件對(duì)象。如果L中沒有空閑單元，則分裂L結(jié)點(diǎn)，生成新的L和L”結(jié)點(diǎn)，將文件點(diǎn)對(duì)象存入L結(jié)點(diǎn)中，更新L父結(jié)點(diǎn)P的MBR使其包含L，令L=P，Obj=L”;否則，在L中存入文件對(duì)象，退出。

step 3： 在L中存入超幾何體Obj。如果L中沒有空閑單元，則分裂L結(jié)點(diǎn)，生成新的L和L”結(jié)點(diǎn)，在L中存放Obj，更新L父結(jié)點(diǎn)P的MBR使其包含L，令L=P，Obj=L”，重復(fù)step 3，直到L中有空閑單元或者L為根結(jié)點(diǎn)。

step 4 如果L中有空閑單元，則存入Obj;否則，分裂L生成新的根結(jié)點(diǎn)，存入原根結(jié)點(diǎn)和Obj。

3.3 刪除文件操作

刪除文件算法描述為：

step 1：按公式（1）將文件對(duì)象轉(zhuǎn)換為k維超幾何體Obj。

step 2：用Obj檢索文件對(duì)象所在的葉子結(jié)點(diǎn)L。刪除L中文件對(duì)象所對(duì)應(yīng)的單元，刪除后若L中空閑單元數(shù)大于M/2，則刪除L結(jié)點(diǎn)下的所有文件對(duì)象，并把刪除的文件對(duì)象添加到T集合。

step 3：令Obj為L(zhǎng)父結(jié)點(diǎn)單元所對(duì)應(yīng)的超幾何體，L為L(zhǎng)結(jié)點(diǎn)的父結(jié)點(diǎn)，重復(fù)step 4在L中刪除Obj，直到L中空閑單元數(shù)小于M/2或者L為根結(jié)點(diǎn)。

step 4：在L中刪除超幾何體Obj，并將T中的文件對(duì)象重新插入到R樹中。

3.4 結(jié)點(diǎn)分裂操作

R樹分裂算法要盡可能減少重復(fù)檢索路徑，分裂的優(yōu)劣將影響到檢索性能。Guttman以面積為計(jì)算標(biāo)準(zhǔn)，選取分裂后兩組單元MBR面積和最小的分裂方法，劃分M個(gè)單元為兩組窮舉會(huì)有[CM2M2]種，時(shí)間復(fù)雜度較高。為減小分裂算法時(shí)間復(fù)雜度，Guttman介紹了平方耗費(fèi)算法（Quadratic-Cost Algorithm），通過選取兩個(gè)種子單元，采取面積遞增最小的方法分裂R樹結(jié)點(diǎn)，種子選取的方法有[C2M]種。MIFS索引結(jié)構(gòu)插入、刪除、檢索算法參照降維后的超幾何體，分裂時(shí)以超幾何體體積最小增長(zhǎng)為標(biāo)準(zhǔn)，超幾何體的體積定義為：

V（I）=LI1*LI2*LI3*…*LIn

其中，LIi表示超幾何體每一維的取值范圍。結(jié)點(diǎn)分裂思想適用于插入算法中尋找合適葉子結(jié)點(diǎn)的過程，尋找到的葉子結(jié)點(diǎn)要使得插入文件對(duì)象后的超幾何體體積增長(zhǎng)最小。

4 MIFS文件系統(tǒng)的實(shí)現(xiàn)

4.1 MIFS的實(shí)現(xiàn)

Ext2/Ext3文件系統(tǒng)文件名與文件屬性分開存儲(chǔ)，節(jié)約了讀取的數(shù)據(jù)量，提高了“按名檢索”的效率，但檢索只能采用遍歷目錄樹的方法。MIFS文件系統(tǒng)在Ext2/Ext3的基礎(chǔ)上，在目錄樹的頂層增加一個(gè)R樹文件，對(duì)目錄樹中的所有文件對(duì)象（包括目錄文件）進(jìn)行索引。R樹葉子結(jié)點(diǎn)指針指向文件對(duì)象，文件對(duì)象用i結(jié)點(diǎn)描述。另外，為了快速定位文件的位置，再增加一個(gè)i結(jié)點(diǎn)到文件位置的映射文件，通過對(duì)R樹的檢索，既可以快速獲取檢索文件的位置信息，也可以通過直接讀取i結(jié)點(diǎn)得到文件屬性的詳細(xì)列表。

R樹文件是一個(gè)定長(zhǎng)記錄文件，記錄定義為：

struct r_file_rec{

int deleted;

int flag;

int num;

struct r_node n;

int pnum;

};

其中deleted域表示該記錄是否被刪除;flag域表示該記錄是R樹葉子結(jié)點(diǎn)，還是中間結(jié)點(diǎn);num域是R樹的結(jié)點(diǎn)號(hào)，結(jié)點(diǎn)號(hào)按記錄在文件中的位置順序編排;n域表示R樹的結(jié)點(diǎn)，結(jié)點(diǎn)的大小由R樹的度決定;pnum域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。

映射文件采用索引順序文件結(jié)構(gòu)，如圖2所示。索引文件記錄i結(jié)點(diǎn)號(hào)及其路徑在路徑文件中的偏移，Del是記錄刪除標(biāo)記，i記錄文件結(jié)點(diǎn)號(hào)，len是路徑的長(zhǎng)度，off記錄路徑存儲(chǔ)偏移量。路徑文件由不定長(zhǎng)的絕對(duì)路徑順序存放組成。

R樹文件和映射文件上定義記錄分配、刪除、壓縮等操作，實(shí)現(xiàn)記錄存儲(chǔ)空間的管理，為用戶層文件對(duì)象創(chuàng)建、刪除等操作服務(wù)，實(shí)現(xiàn)R樹結(jié)點(diǎn)插入、刪除、分裂等任務(wù)。

4.2? MIFS用戶接口

系統(tǒng)調(diào)用是操作系統(tǒng)提供給用戶的程序接口，用戶層軟件通過系統(tǒng)調(diào)用實(shí)現(xiàn)。POSIX.1標(biāo)準(zhǔn)規(guī)定了操作系統(tǒng)內(nèi)核提供給用戶的標(biāo)準(zhǔn)程序集，其中文件操作函數(shù)如open、create、lseek、read、write、truncate等，目錄操作函數(shù)如mkdir、rmdir、chown、fchown、lchown、link、unlink、remove、rename、symlink、utime等。Linux平臺(tái)下，用戶層軟件（如shell命令）提供的文件操作命令如vi，目錄操作如mkdir、rmdir、chown、mv等，目錄檢索操作如ls、locate、find等。MIFS不改變操作系統(tǒng)原有內(nèi)核結(jié)構(gòu)，重定義操作系統(tǒng)用戶層軟件，本質(zhì)上可視為一種新的操作系統(tǒng)接口，與Ext2/Ext3文件系統(tǒng)文件/目錄操作相仿。在Linux平臺(tái)上，MIFS用戶接口用shell腳本語言編程，包含測(cè)試文件/目錄操作命令是否正確執(zhí)行、轉(zhuǎn)換相對(duì)路徑為絕對(duì)路徑、測(cè)試文件的屬性、調(diào)用R樹文件和索引文件操作函數(shù)等步驟。

5 性能測(cè)試

Linux系統(tǒng)中find命令從目錄樹結(jié)構(gòu)指定結(jié)點(diǎn)開始，采用遞歸遍歷的方法尋找目錄樹下與文件名通配字符模式匹配，或者具有給定屬性的文件或目錄。若查找以字符串libc開頭、大小在200字節(jié)到300字節(jié)之間、用戶名是root、修改時(shí)間在9年前與10年后的文件，命令描述為：

#find -name ‘libc* -a -size +200c -a -size -300c -a -user root -a -mtime -3660 -a -mtime +2928

在主頻為2GHz、內(nèi)存為2GB、磁盤容量8GB、文件系統(tǒng)為Ext3的Linux虛擬機(jī)上，對(duì)結(jié)點(diǎn)數(shù)量級(jí)不同的目錄樹用time工具比較find命令和MIFS檢索命令的周轉(zhuǎn)時(shí)間，實(shí)驗(yàn)結(jié)果如圖3所示。橫坐標(biāo)代表目錄樹中文件的結(jié)點(diǎn)數(shù)，以萬為單位，縱坐標(biāo)代表周轉(zhuǎn)時(shí)間，以秒為單位。

find對(duì)磁盤目錄樹結(jié)構(gòu)遞歸遍歷查找，隨著目錄樹結(jié)點(diǎn)的增加，檢索時(shí)間顯著增長(zhǎng);而MIFS的檢索時(shí)間增長(zhǎng)相對(duì)緩慢，檢索時(shí)間主要用于R樹文件和映射文件檢索，且R樹文件、映射文件相對(duì)較小，就18萬個(gè)結(jié)點(diǎn)的目錄樹，R樹文件大約為50MB。另外，R樹索引結(jié)構(gòu)滿足了文件系統(tǒng)多屬性索引的要求。

MIFS用戶接口其它操作周轉(zhuǎn)時(shí)間與Ext3文件系統(tǒng)文件/目錄操作周轉(zhuǎn)時(shí)間比較結(jié)果如圖4所示。由于MIFS用戶接口在完成常規(guī)文件/目錄操作后，還要即時(shí)修正R樹文件及映射文件，故而時(shí)間耗費(fèi)相對(duì)常規(guī)文件系統(tǒng)接口要多。為了改善該問題，可以引入日志操作，對(duì)R樹文件及映射文件進(jìn)行批量修改。

6 結(jié)束語

本文采用近些年流行的R樹多維索引結(jié)構(gòu)，通過研究R樹的查找、插入、刪除和分裂操作，就當(dāng)前磁盤空間容量日益龐大，檢索時(shí)間過長(zhǎng)問題，提出并實(shí)現(xiàn)了一種多維文件屬性元數(shù)據(jù)索引的文件系統(tǒng)，對(duì)文件屬性分類降低索引維數(shù)，重定義R樹的查找、插入、刪除和分裂操作，在現(xiàn)有Ext3文件系統(tǒng)的基礎(chǔ)上，用shell腳本語言在原有文件/目錄操作的基礎(chǔ)上重新定義多維元數(shù)據(jù)索引文件系統(tǒng)操作，實(shí)驗(yàn)結(jié)果表明該方法能夠有效提高檢索效率，而對(duì)文件系統(tǒng)接口其他操作時(shí)間影響有限。

參考文獻(xiàn)：

[1] 吳偉民，盧琦，王振華，蘇慶. NTFS目錄下索引B+樹結(jié)構(gòu)動(dòng)態(tài)解析[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2010（22）：4843-4846.

[2] Andrew W. Leung， Minglong Shao， Timothy Bisson， Shankar Pasupathy， Ethan L. Miller. Spyglass： Fast， Scalable Metadata Search for Large-Scale Storage Systems[EB/OL]. [2013-7-28]. http：//static.usenix.org/events/fast09/tech/full_papers/leung/leung_html/.

[3] 王柏，胡谷雨，羅健欣. 一種高效的海量數(shù)據(jù)儲(chǔ)存方案[J]. 計(jì)算機(jī)工程，2012，38（18）：65-67.

[4] Guttman A. R-trees： A dynamic index structure for spatial searching[C]. In： Processdings of ACM SIGMOD， Boston， MA， 1984， 47-57

[5] Selis T. K.， Roussopoulos N.， Faloutsos C.. The R+-tree： A dynamic index for multi-dimensional objects [C]. In： Proceedings of the 13th VLDB， Brighton， England， 1987， 507-518

[6] Beckmann N.， Kriegel H.P.， Schneider R.， Seeger B.. The R*-tree： An efficient and robust access method for points and rectangles [C]. In： Proceedings of SIGMOD， Atlantic City， New Jersey， 1990， 322-331

[7] Kamel I.， Faloutsos C.. Helbert R-tree： An improved R-tree using fractals [C]. In： Proceedings of the 20th VLDB， Santiago Chile， 1994， 500-509

[8] Huang P. W.， Lin P. L.， Lin H. Y.. Optimizing storage utilization in R-tree dynamic index structure for spatial databases [J]. Journal of Systems and Software， 2001， 55（3）：291-299

[9] Bovet， D.P.， Cesati， M.. Understanding the Linux Kernel， Second Edition [M]. OReilly Media， Inc.， 2003

[10] 夏宇，朱欣焰. 高維空間數(shù)據(jù)索引技術(shù)研究[J]. 測(cè)繪科學(xué). 2009，34（1）：60-62

【通聯(lián)編輯：王力】