Log結構文件系統的設計與實現

The Design and Implementation of a Log-Structured File System[1]論文中提出一種基於Log結構來實現文件系統。下面分析傳統文件系統（以Ext2為例）和Log File System（簡稱為LFS）2種實現的差異。

EXT2實現[2]

EXT2文件系統將磁碟空間劃分為多個cylinder group，每個cylinder group結構如下：

其中：

Inode Bitmap :每位代表一個Inode，代表空塊，1代表數據塊

Block Bitmap :每位代表一個Data Block

Inode table：Inode塊的連續段，Inode是通過Inode number計算出在Inode table偏移量獲取。

Data Blocks :Data Block的連續段。

Inode塊是存儲文件（目錄也是文件）的元數據信息。包含：文件類型，大小，創建時間，修改時間，指向數據塊的指針。

綜上所述，每當創建一個文件時，至少需要6次寫（目錄數據，目錄屬性，文件數據，文件屬性，文件數據所在的Bitmap，文件屬性所在的Bitmap），同時每次寫到需要磁碟定址，而且這6個區域不是連續存儲，磁頭需要做多次移動。

由於EXT2的寫性能，論文中提出一種優化寫的文件系統（論文中對比的文件系統是Unix FFS，但EXT2也是相似的實現）。

LFS實現

Log寫與讀

LFS（Log-Structured File System）是通過每次更新（包括創建，刪除）文件的信息（包括Data Block, Inode,目錄等）連續存儲到Log中。與EXT2相比，多次隨機寫過程大大減少。

那LFS如何查詢文件信息呢？遍歷所有的日誌？當然不是。寫入LOG的還有Inode map，其中保存有Inode編號到Inode的映射關係，Inode map也會放置到內存中，查找Inodes時直接在內存中進行。

上圖給出了LFS和FFS（文中用Ext2代替），明顯可以看到創建2個文件，LFS需要1次寫入（先緩存到內存，類似與Page Cache），而FFS需要8次定址和更新。

垃圾清理

用LOG做數據，最大的問題是隨著文件的更新，刪除，歷史的垃圾信息也隨之增多，所以如何對這些數據進行壓縮，刪除。

LFS把磁碟劃分為固定大小的空間，稱為段（segments）。每次寫數據追加Log到當前段，如果寫滿了，就取下一個空閑段(clean segment)。當空閑段數量小於閾值，便開始清理數據段，直到空閑段數量達到另一個閾值。

對於清理哪些數據段，LFS使用段使用表（Segment usage table）來記錄數據段的有效數據大小和其中數據快的最近更新時間，然後清理最大使用量數據。

參考文獻：

[1] Mendel Rosenblum and John K. Ousterhou . 「The Design and Implementation of a Log-Structured File System」https://people.eecs.berkeley.edu/~brewer/cs262/LFS.pdf

[2] EXT2http://www.tldp.org/LDP/tlk/fs/filesystem.html#tth_sEc9.1.49.1節

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！