760
存儲那些事兒（五）：BTRFS文件係統之Btree結構詳解
Btree數據結構可以說是BTRFS文件係統的基礎。它提供了一個通用的方式去存儲不同的數據類型。它僅僅存儲3個數據類型：key， item和block header。
btrfs_header的定義如下：
struct btrfs_header {
u8 csum[32];
u8 fsid[16];
__le64 blocknr;
__le64 flags;
u8 chunk_tree_uid[16];
__le64 generation;
__le64 owner;
__le32 nritems;
u8 level;
} btrfs_disk_key的定義如下：
struct btrfs_disk_key {
__le64 objectid;
u8 type;
__le64 offset;
} btrfs_item的定義如下：
struct btrfs_item {
struct btrfs_disk_key key;
__le32 offset;
__le32 size;
}
對於b-tree的非葉子節點，它僅僅保存了[Key, block-pointer]。而葉子（Leaf）節點則保存了[item, data]。data的大小是不固定的。leaf在開始的地方保存了items的一個數組。而在結尾則以反方向保存了data的數組。這兩個數組是向中間增長的。結構體btrfs_item.offset保存了data的偏移量，而btrfs_item.size則保存了data的大小。下麵的圖可以形象的說明這個問題：
item的data大小是不固定的。並且對於不同的數據結構，這個data的類型也是不一樣的。struct btrfs_disk_key::type則說明了data的不同類別。
btrfs_header保存了這個節點數據的一個checksum，擁有這個節點的文件係統的id，這個節點在樹中的level，這個節點所占用的block數目。這些成員數據可以在讀取數據的時候對元數據進行驗證。對於指向這個btree 節點的所有者來說，它會存儲generation的值，這能夠保證元數據的正確性。
對於指向下層節點的node指針來說，為了簡化文件回寫的邏輯，下層節點的checksum並不會被保存。generation在節點插入btree時已經被計算出了，但是checksum則僅僅在將這個數據塊寫回到disk時才會計算。因此，使用generation將會使得Btrfs檢測到錯誤的回寫。如果使用checksum，那麼由於下層節點的checksum僅僅在會寫到disk時才會計算，那麼計算得到checksum後不得不修改上層指向該節點的checksum，非常低效。
那麼generation是怎麼計算出來的？就是分配當前節點的transaction id。這樣也使得增量備份變得簡單。當然了，這個transaction id是被COW的transaction子係統使用的。
對於struct btrfs_key.objectid來說，它唯一標識了該邏輯單元，或者叫object。BTRFS就是由這些objects構成的。當object創建時，一個未被其他object使用的object id就會賦給它。objectid可以說是key中最重要的元素。通過objectid，所有的object 都可以組織到b-tree中。
inode
inode是存在struct btrfs_inode_item中的，其中key.offset == 0 並且 key.type == 1。inode的item肯定都是最前麵；它們保存了傳統文件和目錄的狀態信息。它相對來說很小，並且不包含內嵌的文件數據或者擴展的屬性。這些信息都是保存到其他類型的item中的。
文件
小文件如果可以放到一個leaf 節點的話，它是有可能會被放到擴展的item中的。在這種情況下，key.offset保存了文件數據的在extent中的offset；在btrfs_item.size保存了這個文件的大小。這種文件成為inline file，這種文件由於減少了尋址和IO，因此非常快。
對於大文件來說，它們是存到extent中的。struct_file_extent_item存儲了這個extent的generation number 和一個[ disk block, disk num blocks ]數對以記錄這個文件存儲到的磁盤位置。
尊重原創，轉載請注明出處 anzhsoft: https://blog.csdn.net/anzhsoft/article/details/20382885
參考資料：
1. https://btrfs.wiki.kernel.org/index.php/Btrfs_design
2. BTRFS: The Linux B-tree Filesystem - IBM Research
最後更新：2017-04-03 12:55:38