KFS文件系統(tǒng)的MetaServer元數(shù)據(jù)管理采用的是B+樹方式，下面將結(jié)合其源碼，對KFS MetaServer中元數(shù)據(jù)的組織形式及有關(guān)實現(xiàn)細節(jié)進行分析。
1. 相關(guān)源碼文件
KFS MetaServer元數(shù)據(jù)管理的代碼所在目錄為kfs-[version]/src/cc/meta，其中，相關(guān)的源碼文件有：
（1）meta/base.h：KFS元數(shù)據(jù)metadata中各節(jié)點的基礎(chǔ)類，包括 的類： 類Key、 類MetaNode，它們分別代表B+樹種存儲的數(shù)據(jù)、所有B+樹節(jié)點的公共基礎(chǔ)信息。
（2）meta/meta.h 和 meta/meta.cc ：封裝了 metadata 的基本數(shù)據(jù)定義，包括：類Meta、類MetaDentry、類MetaFattr和類MetaChunkInfo，它們分別代表文件系統(tǒng)中的目錄項、文件或目錄的屬性項、對于一個文件偏移（ file offset ）的 Chunk 信息。
（3）meta/kfstree.h 和 meta/kfstree.cc ：封裝了對 B+ 樹中內(nèi)部節(jié)點 Node 的各種操作及 Tree 的基本操作（與文件系統(tǒng)無關(guān)， B+ 樹底層的實現(xiàn)），如插入節(jié)點、刪除節(jié)點等。
（4）meta/kfsops.cc ：封裝了使用 B+ 樹存儲 KFS 文件系統(tǒng)，實現(xiàn)的相關(guān)基本操作，如創(chuàng)建文件、刪除文件、創(chuàng)建目錄、刪除目錄等（作為 Tree 的實現(xiàn)）。
（5）meta/request.h 和 meta/request.cc ：封裝了對 ChunkServer 或 KfsClient 發(fā)出的 meta data 請求的處理，通過 Tree metatree 執(zhí)行相應(yīng)的操作，實現(xiàn)對 KFS 文件系統(tǒng)各種基本操作的調(diào)用。
2. 為什么選用B+樹
KFS的文件系統(tǒng)采用的是B+樹，那么為什么選用B+樹而不是B-樹呢？這里做一個簡單的分析：
2.1 B-樹
B-樹的定義：
B-樹是一種平衡多路查找樹，一棵m階的B-樹，或者是一顆空樹，或者是滿足下列特征的m叉樹：
（1）樹中每個節(jié)點至多有m棵字數(shù)；
（2）若根節(jié)點不是葉子結(jié)點，則至少有2棵子樹；
（3）除根之外的所有非終端結(jié)點，則至少有[m/2]棵子樹；
（4）所有的非終端結(jié)點中包含下列信息數(shù)據(jù)：(n, p0, k1, p1, k2, p2, ..., kn, pn)，
其中：ki為關(guān)鍵字，且ki<ki+1；pi為指向子樹根結(jié)點的指針，且滿足pi所指子樹中所有結(jié)點的關(guān)鍵字均大于ki且小于ki+1，pn所指子樹中所有結(jié)點的關(guān)鍵字均大于kn；
（5）所有葉子結(jié)點均在同一層。
B-樹的檢索：
從根結(jié)點開始，對結(jié)點內(nèi)的有序關(guān)鍵字序列進行二分查找，如果命中，則直接結(jié)束查找過程；否則，進入查詢關(guān)鍵字所屬范圍的兒子結(jié)點進行查找。重復(fù)以上過程，直到所對應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點。
B-樹的特性：
（1）關(guān)鍵字集合分布在整顆樹中；
（2）任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；
（3）搜索有可能在非葉子結(jié)點結(jié)束；
（4）其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找；
（5）自動層次控制。
2.2 B+樹
B+樹的定義：
B+樹也是一種平衡多路查找樹，它是應(yīng)文件系統(tǒng)所需而出的一種B-樹的變型樹。一顆B+樹滿足以下條件：
（1）每個非終端結(jié)點至多有m顆子樹；
（2）除根結(jié)點外，其他每個非終端結(jié)點至少有[(m+1)/2]顆子樹；
（3）根結(jié)點至少有2顆子樹；
（4）有n棵子樹的結(jié)點中含有n個關(guān)鍵字；
（5）所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接；
（6）所有的非終端結(jié)點可以看成是索引部分，僅包含其各個子結(jié)點中的最大關(guān)鍵字及指向子結(jié)點的指針。
通常來說，B+樹上有兩個頭指針，一個指向根結(jié)點，一個指向關(guān)鍵字最小的葉子結(jié)點。
B+樹的檢索：
B+樹的檢索方式分為兩種：
（1）一種是從指向關(guān)鍵字最小的葉子結(jié)點的頭指針開始，進行順序查找；
（2）一種是從指向根結(jié)點的頭指針開始，進行隨機查找：與B-樹基本相同，等價于在關(guān)鍵字全集做一次二分查找，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B-樹可以在非葉子結(jié)點命中）。
B+樹的特性：
（1）所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；
（2）檢索時只有在葉子結(jié)點命中，不可能在非葉子結(jié)點命中；
（3）非葉子結(jié)點相當(dāng)于是葉子結(jié)點的索引（稀疏索引），葉子結(jié)點相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
（4）更適合文件索引系統(tǒng)。
2.3 B+樹與B-樹的比較
通過對B-樹和B+樹的定義及特性的了解，對兩者進行比較：
（1）占用空間大小方面：
- B-樹的非葉子節(jié)點中含有大量的關(guān)鍵字信息，占用的空間相對比較大；
- B+樹中只有葉子節(jié)點中才有關(guān)鍵字信息 ，非葉子節(jié)點并沒有指向關(guān)鍵字具體信息的指針，占用的空間相對比較小。
（2）檢索路徑長短方面：
- 由于 B+樹的所有關(guān)鍵字都分布在葉子節(jié)點上，其他非葉子節(jié)點都是索引部分，因此 樹階數(shù)（即樹高）要比B-大，檢索時要經(jīng)過的路徑就多，運算時間相對長一些；
- 由于 B-樹的關(guān)鍵字分布到各個節(jié)點上，相對于B+樹中完全分布到葉子節(jié)點上來說，分散分布的階數(shù)自然要小， 因此B-樹的樹階數(shù)要比B+小，查找要經(jīng)過的路徑相對比較少，運算時間相對短一些。
對于文件系統(tǒng)的設(shè)計來說，最關(guān)鍵的瓶頸在于磁盤IO操作，如果占用的磁盤空間少的話，IO操作耗時自然就少。而真正檢索內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)（如B+樹、B-樹）的過程中，運算時間相對于磁盤IO操作來說要小的多，即內(nèi)存的檢索時間不是主要的瓶頸之處。
因此，雖然對于同階的B-樹和B+樹，B+樹的樹高和平均檢索長度均大于B-樹 ，但實際上，檢索過程中，最耗時的操作是磁盤IO操作，而 B-樹占用的空間相對較大，IO操作時劣勢明顯 。由于B+樹的非葉子結(jié)點無記錄信息，只有索引，同樣大小磁盤空間就可以存放更多的索引信息，檢索訪盤次數(shù)反而少，速度也就比B-樹快。
2.4 選擇B+樹
B+樹比B-樹更適合實際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引，原因在于：
（1）磁盤讀寫代價低：即使 B-樹的 運算時間相對于B+樹來說較短 ，但由于磁盤 IO 操作方面的 劣勢，導(dǎo)致其 總體上效率不如B+樹 。
（2）查詢效率更穩(wěn)定：B+樹中任何關(guān)鍵字的查找都必須經(jīng)歷從根結(jié)點到葉子結(jié)點，因此所有關(guān)鍵字查詢的路徑長度相同，每一個數(shù)據(jù)的查詢效率相當(dāng)。
3. 元數(shù)據(jù)組織結(jié)構(gòu)
在KFS文件系統(tǒng)MetaServer元數(shù)據(jù)的實現(xiàn)中，有圖示
幾種類型的B+
樹節(jié)點：
?
（1）MetaNode: 所有葉節(jié)點和內(nèi)部節(jié)點的公共基礎(chǔ)類，其中記錄了不同樹節(jié)點的類型信息。
（2）Node：表示內(nèi)部節(jié)點，其中記錄了樹種內(nèi)部節(jié)點的各種操作。
（3）Meta: 表示葉節(jié)點，而具體來說，不同的葉節(jié)點有：
- MetaDentry: 文件目錄項（ Directory entry ），實現(xiàn)從文件名到文件 id 的映射。
- MetaFattr: 文件或目錄屬性，相當(dāng)于 KFS 中的一個 inode 節(jié)點。
- MetaChunkInfo: 對于一個文件偏移（ file offset ）的 Chunk 信息。
3.1 MetaNode
成員變量：
?
MetaType type;
//
節(jié)點類型值
int
flagbits;
//
標志位
?
構(gòu)造函數(shù)：
MetaNode(MetaType t)
//
初始化type=t, flagbits=0
MetaNode(MetaType t,
int
f)
//
初始化type=t, flagbits=f
3.2 Node
成員變量：
?
int
count;
//
孩子節(jié)點個數(shù)
Key childKey[NKEY];
//
孩子的key
MetaNode
*
childNode[NKEY];
//
孩子節(jié)點
Node
*
next;
//
下一個相鄰節(jié)點
?
構(gòu)造函數(shù)：
Node(
int
f)
//
初始化MetaNode中的節(jié)點類型type=KFS_INTERNAL，flagbits=f
3.3 Meta
成員變量：
fid_t fid;
//
文件fid
構(gòu)造函數(shù)：
Meta(MetaType t, fid_t id)
//
初始化MetaNode中的節(jié)點類型信息type=t，及自身的fid=id
3.4 MetaDentry
成員變量：
?
fid_t dir;
//
父目錄的fid
string
name;
//
目錄項的名稱
fid_t fid;
//
目錄項的文件id
?
構(gòu)造函數(shù)：
?
MetaDentry(fid_t parent,
string
fname, fid_t myID)
?
舉例說明：通過 Dentry 結(jié)構(gòu)實現(xiàn) /root/1.txt 的查找過程：
(1) 獲取 ”/” 的 fid=2
dir=2, name=“/”, fid=2
(2) 獲取 ”root” 的 fid=8
dir=2, name=“root”, fid=8
dir=2, name=“usr”, fid=6
(3) 獲取 ”1.txt” 的 fid=12
dir=8, name=”1.txt”, fid=12
dir=8, name=”2.txt”, fid=13
dir=8, name=”3.txt”, fid=14
由以上查找過程可知， /root/1.txt 的 fid 為 12 。
3.5 MetaFattr
成員變量：
?
FileType type;
//
類型（文件或目錄）
int16_t numReplicas;
//
一個文件要求的備份數(shù)
struct
timeval mtime;
//
修改時間
struct
timeval ctime;
//
屬性變更時間
struct
timeval crtime;
//
創(chuàng)建時間
long
long
chunkcount;
//
chunk數(shù)目
off_t filesize;
//
文件大小
?
構(gòu)造函數(shù)：
MetaFattr(FileType t, fid_t id, int16_t n)
MetaFattr(FileType t, fid_t id,
struct
timeval mt,
struct
timeval ct,
struct
timeval crt,
long
long
c, int16_t n)
3.6 MetaChunkInfo
成員變量：
?
chunkOff_t offset;
//
chunk在文件中的偏移
chunkId_t chunkId;
//
chunk的標識符id
seq_t chunkVersion;
//
chunk的版本號
?
?
?
構(gòu)造函數(shù)：
?
MetaChunkInfo(fid_t file, chunkOff_t off, chunkId_t id, seq_t v)
MetaChunkInfo(fid_t file, chunkOff_t off, chunkId_t id, seq_t v, CLVector
&
m)
分布式文件系統(tǒng)KFS源碼閱讀與分析（一）：MetaServer元數(shù)據(jù)組織結(jié)構(gòu)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
