注記文件系統模型的建立

孫爽，鄭波盡，胡麗君

（中南民族大學 計算機科學學院，武漢 430074）

無論文件中儲存的是工作學習文檔還是日常生活中音頻視頻的數字化文件，隨著設備中文件數量增長，文件都難以管理，并且文件管理又和檔案管理［1］、個人信息管理［2］、信息行為［3］、信息檢索［4］等領域聯系緊密.

數字內容以文件的形式表示可追溯到20 世紀60 年代［5］.這種方式已經成功地在計算機領域中應用了60 多年［6］.雖然受到過質疑［7］，并被指出需要進行改善［6］，但它仍然是計算機領域中使用最久和最普遍的一種處理計算機數字內容方式，比如在Windows、Mac OS、Linux、DSB、Solaris、Android、iOS、Windows Mobile等系統中.

文件存儲在目錄中，目錄系統具有簡單、直觀和適用面廣的特點，這使它一直沿用至今.但是目錄系統有其局限性，就像文獻［8］的名稱“Hierarchical file system are dead”所言，SELTZER 和MURPHY 早在2009 年就提到分級文件系統已經不再適用于當時［8］.DINNEEN 也指出用戶會花費大量的時間去執行文件和文件夾的操作［9］.

面對具有多個分類屬性的文件時，目錄結構的創建變得困難［10］.具有多個分類屬性的文件在目錄系統中通常屬于多個子目錄，比如在某一所學校里有A、B兩個班級［圖1（a）］，現有一份文件（inf.txt）中記錄的是關于這兩個班級的信息，在兩個班級中挑選一個存放［圖1（b）］或者兩個班級中都進行存放［圖1（c）］是目錄系統中的兩種不同做法.第一種方法無法完全表述文件記錄2 個班信息的含義，第二種方式一份文件卻保存了兩份.

圖1 多分類文件舉例Fig.1 Example of multi-class files

在文件查詢上，文件的許多操作都是建立在查詢之上，比如文件修改，只有先找到目標文件才能對文件進行修該；文件移動也需要先找到目標文件再找到目標目錄才能完成文件的移動，但是隨著文件數量的增加，文件查詢效率卻在降低.

上述問題的原因是目錄系統在邏輯上是樹形結構，采用自上而下的設計哲學，即先有目錄結構再有文件，以結構為中心來管理文件，用戶雖然可以輕松地創建一個類似植物學或者動物學的分類系統［11］，但是這種設計方式使目錄結構的創建受到限制，并且查詢文件必須從指定目錄開始，導致文件查詢的效率不高.

為了解決上述問題，人們發展了以元數據為基礎的文件管理系統，它將豐富的元數據與文件聯系起來，使文件的多個分類屬性可以用多個元數據進行表示，并且有比傳統的文件系統更加高效的文件檢索能力［9］.BARREAU 等［12］設計了一種純元數據文件系統，將廣泛而豐富的數據集同文件關聯起來，AMES 和BOBB 等［13］提出名為LiFS 的文件系統，它將元數據存儲在非易失性存儲器中，用來確保用戶或者應用程序賦予文件的屬性以及文件之間所具有的聯系；隨后AMES 又和GOKHALE 等［14］提出了一個名為QMDS 的元數據管理服務，其中集成了所有文件的元數據，抽象成具有節點和邊的圖數據模型.ALBADRI 和WATSON［11］則使用基于元數據的“TreeTags”模型并引入查詢語言的方式改進文件管理系統.而董豪宇等［15］設計了一種純用戶態的網絡文件系統RUFS（Remote userspace File System），將元數據采用基于鍵值存儲與blobstore的元數據協同管理，在保證元數據操作的原子性和并發性的同時，使其具有更高的性能.但是這種方式需要在系統中附加獨立于文件系統的元數據管理服務，導致出現這兩個系統難以同步.

面對上述問題，本文基于第一性原理，以自下而上的設計哲學，提出了注記文件系統，即先有文件再向文件添加注記的方式將文件和其描述信息進行關聯，使文件目錄系統和元數據注記系統合二為一.以文件為中心，注記文件系統將目錄信息轉化為注記，在解決多分類文件目錄創建困難問題的同時提高了文件的查詢效率.

1 目錄文件系統介紹和注記數據庫介紹

1.1 目錄系統

常見文件系統有FAT、NTFS、EXFAT、EXT、HFS等，它的作用是在存儲設備上管理和存儲文件信息，文件系統的建立需要對文件和目錄進行實現，這里以EXT2為例進行介紹.

EXT2 中文件內容是保存在數據塊中，同一個文件系統中的數據塊大小相同，數據塊的大小由文件系統指定，一個文件所占用的空間以數據塊為單位進行分配.EXT2 中利用索引節點（inode）來代表一個文件，每一個inode 都有一個唯一的整數標識符，其中記錄文件的元數據，比如文件大小、訪問權限、時間戳、文件所占用數據塊等.

在Linux 系統中有一句經典的話：一切皆是文件.不僅普通的文件和目錄，就連塊設備、管道、socket 等，也都統一交給文件系統管理.與普通文件中保存文件內容不同，目錄作為特殊的文件，其中保存目錄項列表，每個目錄項中記錄目錄項的索引節點、名稱以及名稱長度，并且每個目錄的前兩個目錄項都是“.”和“..”，用來代表當前目錄和父目錄.多個目錄項之間關聯起來，形成了目錄結構.

1.2 注記數據庫

注記數據庫是一個被設計用于處理少量數據的數據庫，它利用增量式方法為現實世界建模.它是一種采用自下而上設計方法，先有數據再通過為數據加注記或關聯注記的方式來存儲和管理數據之間的關系.注記數據庫中注記是一種對多語義數據的表述方法，表示用戶為檢索信息的標注.不同于自由注記，注記數據庫中的注記用來表示復雜的數據之間的關系，實現關系數據庫的功能.

注記數據庫中為每個數據和注記都分配id，分別記為Did和Zid，通過將Did和Zid進行關聯完成對數據標注.注記數據庫中包含普通注記和識別注記兩種注記，根據被標注數據中是否具備識別特征來判斷注記為何種注記，普通注記用于表達關系數據庫中的普通屬性，識別注記用于表達關系數據庫中的鍵屬性.對于識別注記則為被標注數據標識，對于普通注記則將數據和識別注記進行關聯，在數據之間產生關聯.注記數據庫在理論上和關系數據庫等價，它能很大程度上提高數據庫存儲數據的靈活性，在數據庫中保證數據之間關聯的同時保證了數據的語義信息.

2 注記文件系統

注記是文件的描述信息，注記文件系統是一個被設計用來方便多分類文件存儲和提高文件查詢速度的文件系統，它以元數據為基礎，采用為文件加標簽的形式進行建模，使文件和注記之間建立聯系，在保證文件具有語義的同時讓文件能夠依靠注記進行文件查詢.對第1節中多分類文件的例子，在注記文件系統下的形式如圖2，將兩個班級抽象為兩個注記，同時對文件inf.txt 進行關聯，在能很好地表達該文件所描述的信息同時又保證了文件不會重復保存.本章主要介紹注記文件系統的理論模型和物理實現.

圖2 注記系統下多分類文件存儲圖Fig.2 Multi-class file storage diagram under the annotation file system

2.1 注記文件系統邏輯模型

文件所在位置的各層目錄名和文件名在對文件進行描述的作用上和注記的功能相同，可以將各層目錄名和文件名看作文件的注記，這里把目錄系統中文件的目錄名和文件名提取為注記，通過把文件和注記轉換到注記系統中的方式來介紹注記文件系統的邏輯模型.假設目錄系統存在如圖3 的文件 實例，其中file_1、file_2、file_3、file_4、file_5 和file_6 為6 個文件，A、B、C、D、E 和F 分別為其文件名，dir_1、dir_2、dir_3、dir_4和dir_5為目錄.

圖3 目錄系統下文件實例Fig.3 File instance under the directory system

提取文件名和目錄名作為注記，并在注記和文件之間進行連接，轉換到注記文件系統中，如圖4所示，此時到注記文件系統的邏輯模型是一種具有注記和文件兩種節點的二分圖，模型的定義如下：

圖4 注記系統下的文件實例Fig.4 File instance under the annotation file system

G=(F，N，E).

F：文件節點集合，其中每個元素f代表一個文件.

N：注記節點集合，其中每個元素n表示一個注記.

E：E=｛（f，n）|f∈F，n∈N｝，如果文件f具有注記n，則邊（f，n）存在，否則不存在.

對于通過多個注記對文件進行查詢的問題可以描述為：

存在圖G=(F，N，E)，求和給定注記集合M中所有元素m之間都存在邊的F節點集合I，且滿足?m∈M，m∈N，?i∈I，i∈F.

算法如右欄算法1，當圖G中與M中度數最小元素之間具有連接的F節點的個數為x（x≤|F|），并假設這x個節點平均又和y（y≤|N|）個N節點之間有連接.此時上述算法的時間復雜度T（n）=n+x（y+1）=Θ（a×b），其中a為N節點的個數，b為F節點的個數.

2.2 注記文件系統物理模型

如上一節中介紹的，在注記文件系統中需要記錄注記信息、文件信息以及注記和文件之間的關系信息，注記信息存儲方式如圖5所示，表中記錄所有的注記，并為注記分配一個索引號nid.

圖5 注記存儲表Fig.5 Annotation storage table

注記和文件之間是多對多的關系，即一個文件對應多個注記，一個注記對應多個文件.將注記索引號nid 作為注記節點，文件的inode 號作為文件節點，使用注記哈希表和文件哈希表分別表示上面兩種關系，注記哈希表中每個注記項后面跟著具有這個注記文件inode 號組成的鏈表，結構如圖6 所示.

圖6 注記哈希表Fig.6 Annotation hash table

文件哈希表中每個文件項后面跟著該文件所擁有注記組成的鏈表，結構如圖7所示.其中使用-1作為鏈表結束標識符.

圖7 文件哈希表Fig.7 File hash table

3 注記系統和目錄系統對比

在任何2 個目錄名都不相同的情況下，注記系統和目錄系統可相互轉化，但是前者在邏輯上是一種網狀結構而后者則是樹形結構，這使得文件的操作方式不同.結構決定性質，樹形結構決定每次的文件查詢需要從根目錄開始，而網狀結構則需要從節點出發，這使得文件的查詢方式也不相同.

影響文件查詢速度關鍵因素是查詢過程中需要進行對比的次數，注記文件系統中不同注記相關聯的文件數量不同，不同注記的排列組合，在多注記查詢中文件集合合并所需要比較的次數也將不同.為保證可比較性，注記系統中的文件查詢分析將目錄系統中文件轉換到注記系統中進行，并且規定目錄系統中不存在兩個相同名稱的目錄，每個文件夾下的文件個數和文件名相同.

3.1 文件操作方式比較

目錄結構下常用的文件基礎操作有查詢、刪除、移動、創建等.

（1）文件查詢.

在查詢文件上，注記的作用和目錄相同，都是用來將文件的字符串名稱映射到定位文件所需要的信息上.目錄系統下文件查詢使用遍歷文件的方式，層層篩選直到找到目標文件.注記系統下每個注記對應一組文件，取目標文件所具有的注記組中每個注記對應文件集合的交集即為查詢結果.

（2）文件刪除.

目錄系統中刪除文件需要刪除目錄項中記錄的同時刪除inode并回收所占用的磁盤空間.注記文件系統下需要刪除文件和文件所具有注記之間的關聯，即刪除文件哈希表和注記哈希表中的記錄，同時刪除inode并回收文件所占用的磁盤空間.

（3）文件移動.

目錄系統中文件移動是在目標目錄項和當前目錄項之間進行修改.而在注記文件系統中對應的是修改文件的注記，注記修改需要刪除原來注記和文件之間的關聯并創建新的關聯，即文件哈希表和注記哈希表中鏈表數據的刪除和添加.

（4）文件創建.

目錄系統中文件創建需要創建文件的inode 并在目錄項中加入文件inode號.注記文件系統中同樣的需要創建文件的inode，不同的是不再修改目錄項中的記錄而是在文件和注記之間建立關聯，即在文件哈希表和注記哈希表中加入關聯信息.

3.2 目錄系統文件查詢分析和順序注記文件查詢分析

為了方便計算，假設目錄系統下目錄深度為m每層文件夾中都具有x個文件和y個文件夾，此時目錄中一共有ym個文件夾和ym×x個文件.以遍歷文件夾的方式進行文件查詢，對每個文件夾中文件進行判斷直至找到目標文件目標文件.假設查詢文件目錄深度為n，最好情況下，每次都進入正確的文件夾，此時的對比次數為n+1，在最壞情況下，直到最后才能查找到目標，此時文件的對比次數T(n)的計算方式如下：

當n=1時：

由式（1）、（2）歸納得出：

注記文件系統中每個注記都有一個與之關聯的文件集合，文件查詢的結果是取注記集合中的每個注記元素對應文件集合的交集.注記是從目錄轉換而來，順序注記文件查詢是將注記按照目錄由淺至深進行排列，從注記文件系統中查詢然后取交集.此時，目錄深度為n的文件具有注記n+1 個，查找到目標文件的對比次數T(n)的計算方式如下：

當n=1時：

由式（4）、（5）歸納得出：

當m=n時，式（3）和式（6）相等.此時順序注記文件查詢同目錄系統中最壞情況下的查詢方式一樣，這是由于該方法總是從低目錄深度開始篩選，而在注記文件系統中低目錄深度的注記所對應文件的數量比高目錄深度注記對應文件的數量多，因此這種方式會產生大量的文件對比.從兩種文件查詢對比次數結果可知：當查詢文件所處位置在目錄中越深，兩種方式的查詢對比的次數也越接近.

3.3 非順序注記文件查詢分析

每個注記對應的文件個數不同，先對對應文件少的注記進行查詢，再在此基礎上對文件集合進行取交集，這種文件查詢方式稱為非順序注記文件查詢.

假設查詢文件的目錄深度為n，它最深層目錄轉化的注記對應的文件有ym-n個，文件名注記對應的文件有ym個.當深層目錄轉化的注記對應的文件最少，此時查詢文件需要對比的次數為：

當文件名轉化的注記對應的文件最少，此時查詢文件需要對比的次數為：

顯然式（7）、（8）的結果都是要小于式（6），因此非順序注記文件查詢的方法具有更少的對比次數，理論上查詢的效率也更高.

在不含有兩個名稱相同的文件夾并且每個文件夾下文件名都相同的目錄結構下進行文件查詢，并且將查詢結果同轉化的注記文件系統中文件查詢結果進行對比，注記文件系統采用非順序注記文件查詢的方式查詢.

根據對比次數計算公式可見：影響文件查詢速度的因素主要有3 個，即目錄深度、每層文件數量、每層文件夾數量.針對以上3 個因素設計了3 組實驗，分別在不同目錄深度、文件夾數量和文件數量下進行，為排除硬件的影響，均在相同的磁盤中進行.第1組實驗在每層目錄都有5個文件和2個文件夾，分別以目錄深度為6、8、10 和12 的情況下進行，結果見表1；第2 組實驗在每層目錄都有5個文件和目錄深度為6，分別以每層有2、3、4、5、6個文件夾的情況下進行，結果見表2；第3 組實驗在每層目錄都有2個文件夾和目錄深度為6，分別以每個文件夾下文件個數為5、10、15 和20 的情況下進行，結果見表3.每組實驗中的查詢進行了30 次，取平均值作為實驗結果，單位為ms，并計算方差.

表1 不同目錄深度下實驗數據表Tab.1 Experimental data under different directory depth

表2 不同文件夾數下實驗數據表Tab.2 Experimental data under different folder numbers

表3 不同文件夾個數下實驗數據表Tab.3 Experimental data under different file numbers

由上面3組實驗可見：隨著目錄結構變得復雜，兩種系統下文件的查詢速度均變慢，但總體上注記文件系統的查詢速度更快，注記文件系統文件查詢速度受每層文件夾數量和文件數量的影響較小，受目錄深度的影響較大.

實驗是在每個文件夾下文件名稱相同的情況下進行，但實際上目錄系統中很少出現這種極端情況，當每個文件夾下大多數文件名不相同時，文件名所轉化的注記將變為對應文件最少的注記，此時文件查詢需要進行比較的次數更少，查詢速度也更為迅速.

4 結語

本文指出了目錄系統中存在多分類文件目錄結構創建困難和文件查詢效率低的問題，分析問題的原因是目錄系統采用自上而下的設計哲學，以結構為中心的方式來管理文件.以元數據為基礎的文件管理系統雖然能夠很好地解決上述問題但是卻需要附加獨立于目錄系統的元數據管理服務，使2個系統難以同步.因此本文采用自下而上的設計哲學，以文件為中心，提出了注記文件系統，先有文件，再向文件添加描述信息的方式使文件系統和元數據管理系統合二為一.同時注記文件系統中將目錄信息轉化為注記，將其作為管理和查詢文件的依據，在解決文件多分類問題的同時提高了文件的查詢效率.

作為一個文件系統，注記文件系統并不僅限于文件的存儲和查詢.在云環境下，注記文件系統將比當前的目錄文件系統具有更大的優越性，文件的權限控制、版本控制、唯一識別、多設備同步等云原生的文件系統的性質在目錄系統下難以實現，或者具有很大的缺陷，而注記文件系統則不同，它能夠很好地滿足云環境下云原生文件系統的需求，這正是本文后期需要研究的內容.