Log-structured File System

來自專欄 FLP Impossibility15 人贊了文章

「The Design and Implementation of a Log-Structured File System「 是 Mendel Rosenblum 和 John K. Ousterhout 在90年代初發表的一篇經典論文。且不提論文的兩個作者都大名鼎鼎：Rosenblum 是 Vmware 的聯合創始人，Ousterhout 是 Raft的作者之一（Ongaro 的老闆）; 這篇論文在發表之後就引起了長達數年的 Fast File System 和 LFS 之間的口水戰。LFS 在提出後的前10多年裡並沒有被業界採用（猜猜為什麼），但當 SSD 的價格下降並成為主流後，LFS 卻煥發了第二春：LFS 被廣泛運用在 SSD 的 firmware 中，而且新的文件系統，譬如基於 journal 的 ext3/ext4和支持 copy on write 的 btrfs都吸取了LFS 的 idea；甚至我們常用的LSM演算法都能看到 LFS 的影子。

動機

在90年代初，計算機的硬體性能開始了爆髮式增長：CPU 的速度越來越快，RAM 也越來越大；然而，雖然硬碟的順序讀寫速度也在提高，但是隨機讀寫速度，受制於物理上的尋道時間，卻難以短於10ms。另一方面，當時的文件系統不論是 Unix File System 還是 FFS，都有大量的隨機讀寫（在 FFS 中創建一個新文件至少需要5次隨機寫），因此成為整個系統的性能瓶頸。同時因為 Page cache 的存在，作者認為隨機讀不是 主要問題：隨著越來越大的內存，大部分的讀操作都能被 cache，因此 LFS 主要要解決的是減少對硬碟的隨機寫操作。

File System as a Log

那麼LFS是怎麼減少隨機寫入呢？它基於一個很簡單的 idea: 把整個磁碟看做一個 append only log,永遠都是順序寫入。每當我們寫入新文件時，我們總是順序地追加在log 的最後；不同於 FFS/UFS, LFS 對文件的更改並不修改現有內容，而是把增量追加在硬碟的最後。

管理空餘空間：段(Segements)

這樣的設計有一個明顯的問題：硬碟大小是有限的，當我們的 log 把硬碟寫滿以後，我們就不能再往硬碟里寫入新的數據。但是正如圖一所示，我們在操作文件系統時，我們會刪除文件，或是用新的內容覆蓋舊的內容；因此在 log 中會有過期數據。因此我們需要設計垃圾回收機制和空餘空間管理機制。

在 LFS 中，空餘空間是用固定大小的段(Segment)來管理的：硬碟被分割成固定大小的段；寫操作首先會被寫入到內存中；當內存中緩存的數據超過段的大小後，LFS 將數據一次性寫入到空閑的段中。

LFS 的讀操作

基於段的批量寫入解決了隨機寫入問題，但是LFS 如何實現讀操作呢？類似 UFS/FFS, LFS 的在段內存儲文件內容時，也存儲了文件的索引。具體的來說：

• 在 Segment 中，文件內容存儲在固定大小的 data block 中
• Segment 中同時存儲了 data block 的索引, a.k.a inode. 每個 inode 存儲了對應文件的 data block 的索引和 data block 的地址

在下圖的例子中，Segment0 里存儲了文件2的兩個 data block。而之後的 inode2 中存儲了這兩個 data block 的索引。

然而不同於 UFS/FFS, LFS 的 inode 是動態分配的，因此 LFS 在每個 Segment 的尾部存儲了對 inode 的索引， 稱為 inode map。在 LFS 中，所有的 inode map 內容都會被緩存到內容中，從而加快讀取速度。

有了 inode/inode map 和 data block; 在 LFS 中讀取一個inode 號為 i 的文件流程如下:

1. 從內存中緩存的 inode map 中找到所有的段中 inode 為 i 的地址
2. 根據不同段中的 inode 找到對應的 data block 地址
3. 讀取 data block 中的數據

因為 LFS 是 append only，所以對同一個文件的同一個 data block 可能存在多個版本（在不同段中）。但是通過比較不同段的更新時間，LFS就能判斷出哪個 segment 中的 data block 是最新版本。

垃圾回收

正如前文所說，LFS 需要設計垃圾回收機制來刪除舊數據。 在 LFS 中，多個包含過期數據 block 的段（文件內容被更新或是文件被刪除）會被 compact 成新的數據段，同時其中的舊數據會被刪除。

但是 LFS 是如何檢查段中的過期 block 呢？LFS 在每個段的頭部存儲了名為 Segment Summary 的數據結構。在 Segment Summary 中存儲了段中每個 data block 的地址，和這個 data block 的 inode number （文件號），以及該 block 在文件中的 offset。對於任意 block，只要對比該 block 的地址，和通過 inode map 查詢這個 block 的地址是否相同，就能判斷這個 block 是否過期。

故障恢復

顯然任何文件系統都要能從故障中恢複數據。不同於 UFS 用 fsck 命令對故障進行恢復，LFS 對整個硬碟存儲了 Checkpoint:

• 因為 LFS 的每個 Segment 都存儲了下一個 Segment 的地址，整個文件系統就像一個鏈表一樣被組織在一起。
• 在 Checkpoint 中，LFS 存儲了這個鏈表的第一個 Segment 和最後一個 Segment 的地址，因此只要讀取 Checkpoint 就能恢復出整個文件系統。
• LFS 每 30秒更新一次 Checkpoint 中的數據。

如果LFS 在創建 Checkpoint 時崩潰，比如只更新了 Checkpoint 的頭指針而沒有更新尾指針。對此 LFS 的解決方案是：

• LFS 在硬碟的頭部和尾部存儲了兩個 Checkpoint，每次 Checkpoint 時 LFS 交替地存儲在頭部或是尾部的 Checkpoint 中。 這樣即使寫入一個 Checkpoint 失敗， LFS 也能恢復到上一個 Checkpoint。
• 同時 LFS 利用時間戳來檢測 Checkpoint 的失敗：在寫入 Checkpoint 時，先更新頭指針和對應的時間戳，再更新 Checkpoint 中的其它內容，最後更新尾指針和相同的時間戳。如果 LFS 在讀取 Checkpoint 時發現頭指針和尾指針的時間戳不一致，就知道這個 Checkpoint 並沒有完成。

如果 LFS 在創建 Checkpoint 之間失敗，顯然系統可以恢復到上一次 Checkpoint 時的狀態。然而這會丟失一部分數據。對此 LFS 效仿了資料庫的 redo log：LFS 會嘗試從當前的 segment 鏈表尾部恢復出已經成功寫入但沒有被 Checkpoint 的數據段。

總結

從今天算起，LFS 已經發布了將近 30 年；然而正式由於作者對未來的正確假設，使得 LFS 的設計思想和理念卻仍然深刻地影相了文件系統設計：LFS 的基於 Segment 的設計和 SSD 的物理特性不謀而合，因此被廣泛應用在 SSD 的 firmware 中；LSM 的 memory table/compaction 與 LFS 的 memeory buffer 和 GC 一脈相承；而新的文件系統例如 btrfs 也基於 LSM append only 的特點實現了 copy-on-write 或是 multi-version 的特性。

參考文獻

1. The Design and Implementation of a Log-Structured File System
2. Log-structured file systems: Theres one in every SSD
3. CS 161: Lecture 15

推薦閱讀：