log structured file systems

fcamel

Published in

fcamel的程式開發心得

9 min readJun 1, 2017

這篇是閱讀 Operating Systems: Three Easy Pieces 的 Log-structured File Systems 的心得。

基本假設

近年來硬體進步不少，file system 的設計可以基於這些進展而獲得更好的效能。相關的進展有：

更大的 memory → 更大的 file cache → file read 效率良好。
硬碟的 sequential read/write 頻寬提升的速度大於 seek 和轉速。

由此可知， file read 效率不是問題，問題在如何降低 random write。

打包寫入資料

若考慮 read 的效率，將同個檔案的 meta data 和全部資料放在連續的位置，讀檔時最有效率。但是更新檔案的時候 (例如在中間插入資料) 會很沒效率，所以將資料切成多個 data block，然後記錄各個 data block 的位置，這樣更新檔案只需更新部份 data block，不用搬移既有的資料。

有了 data block 的概念後，再來要考慮如何配置 data block 的位置。既然 file cache 很大，大多數資料只需讀一次，data block 不見得要放得很近。再者，每次更新資料都需要跟著更新 meta data (UNIX-like file system 的 inode)，這樣至少要寫入兩個不同的位置 (一個 data block、一個 meta data)。

換個角度思考：若是不更新資料，而是直接寫入新的 data block，並寫入新的 meta data，讓新的 meta data 指向新的 data block，這樣一次 sequential write 就搞定了。

比方說使用者新增兩個檔案，分別有 4 個 data block 和 1 個 data block。我們可以 buffer 這兩個更新，再一次寫入硬碟，如下圖所示：

http://pages.cs.wisc.edu/~remzi/OSTEP/file-lfs.pdf

D[j,0]: inode j 的第 0 個 data block。
Ax：硬碟 physical address。

buffer 愈大，寫入效率愈好。就和一般 buffer 的設計一樣，可以設個上限，然後在 buffer 滿了或過段時間自動 flush buffer 到硬碟。

LFS 稱一次寫入的資料為 segment， segment 會另外記錄一些資訊，後面再說明 segment 這樣設計的用意。

合理的 buffer 大小

我們可以用硬碟移動讀取頭的時間 (T position)、硬碟寫入最佳效率 (R peak)、期望達到最佳效率多少比例效能 (F)，來計算合理的 buffer 大小：

推導過程很簡單，詳見原始文章。假設 T positoin = 10 ms、 R peak = 100 MB/s、F = 0.9，可算出 D = 9 MB。

更新 inode map

file system 會用一個 inode map (imap) 記錄：檔名 → inode 的 physical address。LFS 會一直改變 inode 的位置，自然也會一直改變 inode map 內容。那麼，更新後的 inode map 該存在那裡？

用同樣的思路來看，為了保持 sequential write，附加在更新的最後面滿合理的。但得處理另一個問題：初始化 LFS 的時候，怎麼知道 inode map 在那？所以還是得存 inode map 到固定的位置。LFS 在硬碟的開頭存 inode map、first segment、last segment 等資訊，這些資訊合稱 checking region (CR)：

讀檔的例子

以讀取 /dir/foo 為例，需要作：

從 / 的 inode 裡取得 dir 對到的 inode number。
從 imap 找到 inode I[dir] 的位置。
從 I[dir] 找到它的資料 D[dir] 的位置。
從 D[dir] 的表找到 foo 的 inode number 是 k。
從 imap 找到 k 的位置。
從 I[k] 找到 D[k] 的位置。
讀取 D[k] 的內容。

示意圖如下：

注意目錄是存檔案的 inode number，不是 physical address，這樣更動 inode 位置的時候，只需要更新 imap 就好，不用更新目錄。

Garbage Collection

不斷地附加新資料，最後硬碟滿了就不能用了。所以要定期清掉沒有在用的 inode 和 data block。概念是找出 M 個 segments，將它們合在一起寫作 N 個 segments，使得 M > N。這樣可以清出更多空間供之後寫入。

幾個重點：

何時作 garbage connection (GC)？
找那些 segment 來清理？
如何判斷某個 inode / data block 沒有在使用？

作 GC 的時機和其它 GC 一樣，系統閒置或資料滿的時候。文內有稍微談一下要找那些 segment，然後說更多討論見別的文章。

判斷 inode / data block 是否有在使用

判斷 inode 很簡單，查 imap 比對位置就知道了。data block 的話，如果我們能知道它的 inode number，就能透過它的 inode 得知它是否還有記錄在 inode 裡。

LFS 將 data block 的 inode number 和它在檔案裡的 offset 記錄在 segment 的開頭，稱為 segment summary block (SS)，如下圖所示：

有了 SS，判斷的方法如下：

// For a block D with address A0
(k, 0) = SegmentSummary[A0];
I[k] = Read(imap[k]);
if (I[k]->blk[0] == A0)
    // block D is alive
else
    // block D is garbage

另外，針對砍檔或 truncate 內容可以最佳化 GC 的效率。讓 inode 有 version number，檔案被砍掉或 truncate 後就遞增 version number。若 imap 和 SS 內存的 inode number 有帶 version number 的話，可以先比對 version number 判斷 data block 是否有效，省去讀取 data block 的 inode。

Crash 後的復原

若剛好在寫入 checking region (CR) 的時候掛了會很慘，所以會有兩份 CR 分別放在硬碟兩端，然後交錯寫入不同位置的 CR。寫入 CR 的時候，依序寫入 timestamp、imap 位置、first segment、last segment、timestamp (同開頭 timestamp 的值)。之後可以比對開頭和結尾的 timestamp 是否一樣，得知 CR 資料是否正確。此外，每個 segment 都會記錄它下一個 segment 的位置。

有了這些記錄，重新啟動系統的流程如下：

比對兩個 CR，用 timetsamp 最新且資料正確的 CR。
取出 last segment，由 segment 取出 next segment。若 next segment 資料完整，更新 last segment 指向更新的 segment。反覆直到沒有 next valid segment。
更新 CR。

這樣不管是在寫入 CR 或是寫入 segment 時 crash，都能回復到最新的有效資料。

Snapshot

文中沒有說 LFS 支援 snapshot，不過以 LFS 的結構來說，每一版 imap 自成一份 snapshot，要讓 LFS 支援 snapshot 很簡單。以前覺得 snapshot 是很酷的功能，沒想到可以這麼容易達成。

其它 log-structured storage

看完 LFS 的介紹後，滿呀異 LFS 沒有廣被使用。查了 wikipedia，實作 LFS 的 file system 似乎都滿冷門的？或許是資料快滿的時候，GC 會很慘。以 file system 來說，這是無法接受的事。

但使用 log-structured 概念的 storage 倒是滿多的，在《Damn Cool Algorithms: Log structured storage》和《Persistent Trees in git, Clojure and CouchDB》有相關介紹，像 git、CouchDB 這類知名應用軟體有用一樣的概念，也因此和 LFS 有一樣的缺點，資料量可能長得很快，需要偶而作 GC。

插曲：A level of indirection

這篇文中提到：

People often say that the solution to all problems in Computer Science is simply a level of indirection. This is clearly not true; it is just the solution to most problems (yes, this is still too strong of a comment, but you get the point). You certainly can think of every virtualization we have studied, e.g., virtual memory, or the notion of a file, as simply a level of indirection. And certainly the inode map in LFS is a virtualization of inode numbers.

想想頗有道理的，軟體設計裡不斷地使用這個想法，像模組化也是 a level of indirection。

2017–06–03 更新

Weiyu 指出 GC 最佳化的部份有錯，已修正。