第十章、分布式件系統(tǒng)名字空間實現(xiàn)研究

1、第十章.分布式文件系統(tǒng)名字空間實現(xiàn)研究1、空間概述名字空間(namespace)即文件系統(tǒng)文件目錄的組織方式，是文件系統(tǒng)的重要 組成部分，為用戶捉供可視化的、可理解的文件系統(tǒng)視圖，從而解決或降低人類 與計算機之間在數(shù)據(jù)存儲上的語義間隔。目前樹狀結(jié)構(gòu)的文件系統(tǒng)組織方式與現(xiàn) 實世界的組織結(jié)構(gòu)最為相似，被人們所廣泛接受。因此絕大多數(shù)的文件系統(tǒng)皆以 tree方式來組織文件目錄,包括各種磁盤文件系統(tǒng)(extx, xfs, jfs, rciscrfs, zfs, btrfs, ntfs, fat32 等)、網(wǎng)絡文件系統(tǒng)(nfs, aes, c1fs/smb 等)、集群 文件系統(tǒng)(lustre, pnfs,

2、 pvfs, gpfs, panfs 等)、分布式文件系統(tǒng)(googlefs, hdfs, mfs, kfs, taobaofs, fastdfs 等)。隨著面向?qū)ο蟠鎯驮拼鎯Φ陌l(fā)展，出現(xiàn)了一種稱為偏平化(flat)的文件系 統(tǒng)組織方式，典型代表有 lustre, panfs, amazon s3, google storageo 這種 方式把所有文件目錄看作對象object,每一個對象有一個全局唯一的標識uuid, 戶使用此uuid(而非路徑)來訪問存儲系統(tǒng)。然而，uuid僅僅對計算機有意義， 在用戶接口層往往還是需耍提供樹狀文件系統(tǒng)視圖，再由系統(tǒng)在path和uutd 之間進行轉(zhuǎn)換。在對象

3、存儲層，對象或?qū)ο髷?shù)據(jù)分片以文件形式存儲在磁盤文件 系統(tǒng)z上，物理存儲層仍然是樹狀存儲結(jié)構(gòu)。另外，對于法規(guī)遵從數(shù)據(jù)存儲領域 廣泛使用的固定內(nèi)容存儲系統(tǒng)cas (content addressed storage,內(nèi)容尋址存 儲)，采用基于對象的存儲系統(tǒng)，機制與此類似。具體實現(xiàn)上，磁盤文件系統(tǒng)的名字空間宜接在磁盤上來實現(xiàn)，通常以 b*/b+/b-樹的形式來組織，元數(shù)據(jù)和數(shù)據(jù)存儲在相同的介質(zhì)上。而對于分布式文 件系統(tǒng)來說，兀數(shù)據(jù)和數(shù)據(jù)和存儲和訪問是分離的，這是由高性能、可用性、可 擴展性等設計要求所決定的。通常，數(shù)據(jù)的存取由i/o服務器來實現(xiàn)，而元數(shù)據(jù) 由元數(shù)據(jù)服務器來負責。名字空間是元數(shù)據(jù)服務器

4、的核心任務z-,此外可能還 耍負責安全機制(如授權(quán)與認證)、鎖機制、i/o負載均衡等。因此，rfl于元數(shù)據(jù) 與數(shù)據(jù)的分離，分布式文件系統(tǒng)名字空間實現(xiàn)的自由度比較大，實現(xiàn)方式有更多 的選擇空間。這里將要介紹四種分布式文件系統(tǒng)名字空間實現(xiàn)機制，均為樹狀文 件系統(tǒng)視圖，大致分為基于文件系統(tǒng)的實現(xiàn)和基于全內(nèi)存的實現(xiàn)，但不包括基于 數(shù)據(jù)庫的實現(xiàn)。基于數(shù)據(jù)庫來實現(xiàn)文件系統(tǒng)名字間有眾所周知的性能問題，尤其 是遞歸遍歷文件目錄空間。2、文件系統(tǒng)名字空間實現(xiàn)(1) 基于文件系統(tǒng)的設計這是一種站在巨人肩膀上的設計。磁盤文件系統(tǒng)本身就是樹狀結(jié)構(gòu)視圖, 因此可以利用這現(xiàn)成的機制在元數(shù)據(jù)服務器上實現(xiàn)名字空間。對于分布式

5、文件系統(tǒng)屮的每一個目錄或文件，在元數(shù)據(jù)服務器的本地文件系統(tǒng)z上一一對應創(chuàng)建一 個目錄或文件（以下稱為元目錄和元文件），兩者之間的映射關(guān)系如圖1所示。元 目錄用來表示dfs屮的目錄，其元目錄屈性保存dfs目錄屈性；元文件用來表示dfs中的文件，元文件屬性保存dfs文件屬性，元文件內(nèi)容則用來保存元數(shù)據(jù),包括更詳細的文件屈性、訪問控制信息、數(shù)據(jù)分片信息、數(shù)據(jù)存儲位置等信息。dfs名了空間本地文件系統(tǒng)名字空間圖1基于文件系統(tǒng)的設計（dfs與本地文件系統(tǒng)名字映射）基于文件系統(tǒng)我們以極小的代價構(gòu)建了 dfs的名字空間，實現(xiàn)起來簡單快速。 元文件僅用來存儲數(shù)據(jù)文件的元數(shù)據(jù)，一般都是小于1kb的小文件，如果文

6、件口 錄數(shù)量達到千萬量級就會形成losf（lots of small files）的性能問題。實際應 用中如何來解決這種問題呢？目前主要有兩種解決方法，一是采用適合海量小文 件存儲的文件系統(tǒng)。reiserfs對小文件存儲進行了特別優(yōu)化，它不僅文件查找 效率高，而且節(jié)省磁盤存儲空間，實際測試結(jié)果也驗證了這一點。二是采用高性 能的存儲介質(zhì)，尤其是i0ps指標。非常幸運，固態(tài)硬盤ssd技術(shù)上已經(jīng)比較成 熟，成本不斷降低，非常適合高性能的存儲應用。ssd的特點是i0ps高，普通 ssd讀寫ipos可以達到10000 50000,高端ssd甚至可以達到100000以上， 而fc、sas、sata磁盤的1

7、pos基本小于300,遠遠小于ssd。因此，采用ssd 和reiserfs文件系統(tǒng)，性能能夠得到大幅提升，大多數(shù)應用問題不大。（2）基于全內(nèi)存的分層設計這種方式與hdfs實現(xiàn)相仿。與基于文件系統(tǒng)的實現(xiàn)不同，名字空間完全在 元數(shù)據(jù)服務器的內(nèi)存中，使用層次結(jié)構(gòu)來表示，如圖2所示。這種層次結(jié)構(gòu)相當 于一棵樹，每個結(jié)點表示dfs的一個口錄或文件，結(jié)點的孩子結(jié)點理論上沒有數(shù) 量限制（取決于內(nèi)存可用量），孩子結(jié)點使用動態(tài)數(shù)組來表示。結(jié)點數(shù)據(jù)結(jié)構(gòu)如下 所示，其中metadata表示（1）中文件目錄類似的元數(shù)據(jù)信息，ch訂dren是孩了 結(jié)點動態(tài)數(shù)組，使用二分法實現(xiàn)插入、查找和刪除操作，嚴格按照名稱進行升序

8、排序。root圖2基于全內(nèi)存的分層設計cppview plaincopyprint?1. struct inode 2. char *dname; /*目錄或文件名，不包括路徑*/3. char *metadata; /* 元數(shù)據(jù) */4. struct inode *children; /* 孩子結(jié)點數(shù)組 */5. uint32_t count; /*子el錄和文件計數(shù)器*/6；對于文件系統(tǒng)is操作，首先對路徑進行解析并拆分成獨立的目錄名，然后 從root結(jié)點開始查找，孩子結(jié)點數(shù)組使用logn的二分搜索binarysearch查找， 直到找到對應的目錄結(jié)點，然后遍歷結(jié)點的孩子結(jié)點數(shù)組即叮。假

9、設目錄深度為 h, 口錄寬度為n,貝ij查找口錄文件的時間復雜度為0(h*log(n)。對于文件系 統(tǒng)來說，這種查找時間復雜度顯得有點高，尤其是目錄層次很深、子目錄文件數(shù) 量龐大的分布式文件系統(tǒng)。hdfs的設計思想源口 gfs,可是在名字空間設計上還 是與gfs存在一定的差距，可謂形似而神不似。另外，全內(nèi)存設計對內(nèi)存需求比 較高，假設每個目錄文件的元數(shù)據(jù)大小為loo字節(jié)，則1千力目錄文件的元數(shù)據(jù) 大小總量約等于1, 000, 000, 000 = 1gb。如果需要支持更多的目錄文件,則需要 應增加內(nèi)存量。(3) 基于全內(nèi)存的hash設計這種方式與gfs實現(xiàn)相仿。gfs論文屮指出其名字空間采用了

10、全內(nèi)存設計、 偏平式組織、前綴壓縮算法、二分查找算法、沒有支持is的數(shù)據(jù)結(jié)構(gòu)，論文中 還指出is操作的效率較低。gfs沒有開源，不像iidfs可以查閱原代碼，因此也 無法完全重現(xiàn)gfs的名字空間實現(xiàn)，基本全內(nèi)存的hash設計可能比較接近其設 計。這種設計采用hash和二分查找相結(jié)合的來實現(xiàn)，即目錄以完整的絕對路徑 進行hash定位，該口錄下的孩子結(jié)點使用二分查找進行定位，如圖3所示。它 與分層設計的主要不同在于，只需要一次hash和一次二分查找，而分層設計需 要多次的二分查找，在性能上更優(yōu)。我們僅對目錄進行hash,名字空間具有一 定的偏平性，但沒有達到gfs的完全偏平；子文件口錄不包括父路徑

11、部分，相當 于作了前綴壓縮，但不如分層前綴壓縮徹底。大膽猜測，gfs可能采用了全hash 設計或全列表設計，is操作通過前綴匹配來實現(xiàn)，即具有相同前綴的文件屈于 同一個目錄，如此實現(xiàn)名字空間。圖3基于內(nèi)存的hash設計這種設計下，查找指定文件或執(zhí)行is,首先將路徑分解成父路徑名和目錄文 件名，對父路徑名進行hash運算定位至其孩子結(jié)點列表，然后二分查找指定文 件，或者遍歷孩子結(jié)點列表實現(xiàn)is操作。假設目錄寬度為n,查找時間復雜性 為log(n),在內(nèi)存占用量上要稍稍大于分層設計，因為口錄結(jié)點均重復一次。 這種設計具有支持is的數(shù)據(jù)結(jié)構(gòu)，相對于gfs來說，執(zhí)行is效率要高出許多, 如果gfs是全

12、hash設計則需要遍丿力整個文件空間進行前綴匹配，如果gfs是全 列表設計則需要以父路徑名進行二分查找然后局部前綴匹配。(4) 基于全內(nèi)存的雙重hash設計這種方式是對基于全內(nèi)存hash設計的改進。它先對目錄進行第一次hash運 算，然后對子文件目錄進行第二次hash運算，從而將查找時間復雜性從log(n) 進一步降低至0(2),如圖4所示。目錄hash表是全局的，而目錄結(jié)點的hash 表是局部的，每一個口錄結(jié)點都包含一個hash表，僅用來存儲木口錄下的子文 件目錄信息，目錄結(jié)點數(shù)據(jù)結(jié)構(gòu)如下所示。子文件目錄局部hnsh表圖4基于內(nèi)存的雙重hash設計cppview plaincopyprint

13、?1.struct inode 2.char *dname; /* h錄或文件名，包:括路徑*/3char *metadata; /* 元數(shù)據(jù) */4.hashtable *children; /* 孩子結(jié)點 hash 表5.uint32_t count; /*子目錄和文件計數(shù)器*/6.；structinode char *dname; /*目錄或文件名,包括路徑*/char *metadata; /* 元數(shù)據(jù) */hashtable *children; /* 孩子結(jié)點 hash 表 */uint32_t count; /*子目錄和文件計數(shù)器*/；對于文件系統(tǒng)1s操作，對路徑名進行一次has

14、h運算定位到目錄結(jié)點，然后 對目錄結(jié)點屮的hash表進行遍丿力即可。文件查找時，首先將路徑名分解成父路 徑名和文件目錄名，對父路徑名進行hash運算定位父目錄結(jié)點，然后對文件目 錄名進行hash運算并在父目錄結(jié)點中的hash表進行定位。目錄結(jié)點中的hash 表初始為未創(chuàng)建，直到第一次創(chuàng)建子文件目錄時方才創(chuàng)建，屆sh表項數(shù)量定義 為平均目錄包含的了文件目錄數(shù)量，在性能和內(nèi)存空間節(jié)省z間進行折中。如杲 內(nèi)存充足，hash表項數(shù)量應該盡量設置大些，以達到更好的散列效果。與基于 全內(nèi)存的hash設計相比，這種設計查找性能上更上層樓，內(nèi)存消耗相應有所增 加。3、分析與應用選擇上述分布式文件系統(tǒng)名字空間的四種實現(xiàn)方式，按照實現(xiàn)位置劃分，可分為 基于文件系統(tǒng)的實現(xiàn)和基于內(nèi)存的實現(xiàn)?；谖募到y(tǒng)實現(xiàn)的優(yōu)點是實現(xiàn)簡單, 內(nèi)存要求低，可以運行在普通的機器上，缺