如何利用leveldb實現文件系統的目錄樹

本篇文章給大家分享的是有關如何利用leveldb實現文件系統的目錄樹，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

利用leveldb實現文件系統的目錄樹

目錄樹維護了整個文件系統的元信息，所有對文件系統中文件的增刪查改操作都首先需要經過目錄樹的操作才能進行。百度開源的分布式文件系統BFS(開源地址：https://github.com/baidu/bfs)利用leveldb，實現了目錄樹的管理，使得目錄樹的實現非常簡潔，同時對目錄樹的操作十分高效。本文將為你解析其具體設計及實現思路。

目錄樹為一個樹型結構，而leveldb是一個kv存儲引擎，因此，如果想用通過leveldb實現目錄樹，則需要把樹型結構映射成kv的扁平化結構。

單獨就每個文件或者目錄來講，其信息只需要一條kv記錄即可保存，而這條kv中的value需要保存該目錄或文件的屬性信息，可變動的空間不大。所以，從樹型結構到kv記錄的映射 ，關鍵在于key的選取。

在BFS的目錄樹中，定義了一個int64_t的整型數字作為EntryID，每個文件或目錄擁有一個EntryID，并且全局唯一，根目錄的EntryID規定為1。假設有如下目錄結構：

/home/dirx/
          /filex
      diry/
          /filey
/tmp/
     filez

按照創建順序，我們依次給/home分配的EntryID為2，/tmp的EntryID為3，/home/dirx的EntryId為4，/home/diry的EntryID為5，/home/tmp/filez的EntryID為6，/home/dirx/filex的EntryID為7，/home/diry/filey的EntryID為8。

注意到每個目錄擁有一個自己的EntryID的同時，又肯定擁有一個父目錄，其父目錄又肯定擁有一個EntryID，可以利用這一點，通過父目錄的EntryID和子目錄中的文件名，來確定一條記錄的key：對于每個文件或者目錄，我們規定：每條kv記錄的key為 "父目錄的EntryID+自身文件名"，同時在value中存儲自己的EntryID這樣編碼后，上述目錄樹便可以表示為如下kv記錄：

1home -> 2 + xxx
1tmp -> 3 + xxx
2dirx -> 4 + xxx
2diry -> 5 + xxx
3filez -> 6 + xxx
4filex -> 7 + xxx
5filey -> 8 + xxx

其中，xxx表示該目錄或文件的其它信息，如大小，創建時間，實際數據存放位置等。

到此，目錄樹這個樹型結構，便已經平展成為一條條的kv記錄，對目錄樹的操作，便轉化成了對某幾條kv記錄的操作：

• 對于創建文件操作，比如想創建/home/work/目錄，則首先在/目錄中查找home目錄，由于/的EntryID為1，所以第一次查找時，key為1home，然后讀出其value，解析后發現/home的EntryID為2，則將此EntryID記下，繼續往下走，發現work即為所需要創建的文件，則為其申請一個EntryID（假設為9），此時，寫入一條記錄，按照上面的規則，其key為2work，value為work創建的時間等信息，以及work的EntryID（9）

• 對于刪除操作，比如把剛剛創建的/home/work目錄刪除，只需要將key為2work的這條記錄刪除即可

• 對于讀取操作，比如想讀取/home/dirx/filex文件中的內容，則首先讀取1home這條key所對應的value，解析發現value中記錄的EntryID為2，然后再去讀取2dirx這條key所對應的value，解析發現value中記錄的EntryID為4，然后再去讀取4filex這條key所對應的value，從里面解析出/home/dirx/filex的實際數據存放位置，進行文件內容的讀取

• 對于List目錄操作，比如想看看根目錄下有哪些文件和目錄，由于每個文件和目錄在存儲時，其key中都包含父目錄的EntryID，因此，只需進行一次掃描即可。比如ls /，則只需掃描leveldb中，以1\0x0為前綴的key即可，當遇到2時停止，所得結果即為/目錄下的所有內容

• 對于Rename操作，只需要改動其key即可。比如想要把/home/diry/filey文件移動到home/dirx目錄中，按照之前的規則，/home/diry/filey在leveldb中存儲的key為5filey，/home/dirx的EntryID為4，把5filey這條記錄中的內存讀取出來，以4filey為key，再次存儲到leveldbk ，然后將5filey這條記錄刪除，即完成了Rename操作

這樣，一個目錄樹所需要的基本操作便已經支持，由于leveldb引擎本身寫入速度較快，并且在讀取時，內部本身已經有cache來緩存住較熱的kv數據，并且緩存大小可配置，所以一個非常簡潔高效的目錄樹便實現了~

以上就是如何利用leveldb實現文件系統的目錄樹，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。