Copy-on-Write

BTRFS (B-Tree File-system)

Btrfs 是 Linux 最廣為使用的 copy-on-write（CoW）檔案系統。 Meta 宣稱將幾百萬台機器的檔案系統從 ext4 換成 Btrfs，替全公司省下「數十億美金等級」的儲存成本。台灣的 Synology NAS 跑的 DSM 系統也是用 Btrfs。他的正確念法是：Butter-Filesystem！

上學期我們講過 Hans Reiser 與 ReiserFS 的故事。ReiserFS 是一個偉大的檔案系統，可惜 Hans Reiser 因刑事案件服刑至今，ReiserFS 在 2024 年也從 Linux 移除。但他提出的「用 B-tree 當整個檔案系統的骨架」這個想法沒有跟著消失。Ohad Rodeh 在 2013 的經典論文寫到：

BTRFS development started in 2007, by Mason. He combined ideas from ReiserFS [Reiser 2001], with COW friendly B-trees suggested by O. Rodeh [Rodeh 2008], to create a new Linux filesystem.

最壞的事情永遠可能發生

Niko 的 Mac mini 撞地板那一幕：kernel 在記憶體裡有四個 dirty 的 on-disk 結構（data block、inode size、extent list、bitmap），但我們保證它們寫到 SSD 的順序，crash 時剛好寫完，哪個 subset 就對應一種不同的殘局。而 CoW 的解決辦法是：既然「原地改」(in-plate update) 會留下「一半舊一半新」的時間空窗，那乾脆永遠不要原地改 (out-place update)。

In-place Update

假設你要修改一個 4 KB 的 data block，同時這個 block 配著一份 32-byte 的 checksum 存在某個 metadata block 裡。In-place update 的話，要把新 data 寫回原位、把新 checksum 寫回另一個 block。兩個步驟中間若斷電，data 和 checksum 就對不起來，filesystem 下次 mount 會以為自己壞了，但其實只是兩個步驟沒有 atomic。 Journaling 用 log 紀錄這兩個步驟，藉此解決這個問題。CoW 用另一招：out-place update。

Wa! CoW

任何 block 一旦寫過，就再也不被原地覆蓋。你要改它，就把改過的版本寫到一個全新的 block。

但指向那個 block 的 pointer 存在它的 parent block 裡，parent block 同樣不能被原地覆蓋，於是你也得寫一份新的 parent。parent 的 parent 同理，一路往上爬到 filesystem 的 root pointer。最後一步，把 superblock 裡的 root pointer 從舊樹的 root 改成新樹的 root，這是整個流程裡唯一一個 in-place update 的動作，而且它只是一個 8-byte 寫入。

In-place update vs Copy-on-Write: partial-write crash window vs atomic pointer swap — In-place 改有 crash window，CoW 靠一個 atomic pointer swap 把舊樹翻成新樹

8 bytes 的寫入硬體上幾乎一定是 atomic（硬碟保證寫入一個 sector 為 atomic）。在那個 atomic write 之前，整顆 disk 看起來是舊的；之後，整顆 disk 看起來是新的；中間沒有「半新半舊」的瞬間。crash consistency 由結構本身保證，不再需要 log。

CoW pointer cascade: modifying one leaf rewrites the entire path to the root — Pointer cascade：改一個 leaf 觸發整條 root-to-leaf path 的重寫

代價：每改一個 leaf，整條 path 都重寫

CoW 的代價不小。一棵深度 4 的 tree，改一個 leaf 要寫 4 個新 block：新 leaf、它的新 parent、新 grand-parent、新 root。原本只想改 4 KB 的 data，最後寫了 $4 \times 4 KB = 16 KB$ 。這就是 filesystem-layer write amplification，在學術界稱為 wandering tree problem。

Initial tree, modified tree with shadowed path, and checkpoint, from Rodeh 2008 Figure 4 — Initial → modified → checkpoint：一個 leaf 修改如何沿著 path 複製出新的 B-tree （圖片來源：Rodeh, B-trees, Shadowing, and Clones (TOS 2008), Figure 4）

Btrfs 會把短時間內多個寫合併到同一棵新 tree，試著 amortize 這個成本。精神和 ext4 的 delayed allocation 類似：把 dirty 留在記憶體，累積後一次 flush。差別在 delayed allocation 降低 fragmentation，Btrfs 省下 pointer cascade。

好處：Snapshot 快速

剛才那張 cascade 圖裡，old tree 的所有 block 還躺在 disk 上。我們本來打算釋放它們。但只要不釋放、把舊 root pointer 留下來，那就是一份 snapshot：整顆 filesystem 在 pointer swap 那一瞬間的完整 view。讀 snapshot 跟讀現任 filesystem 一樣快，因為它就是一棵真的 tree，只是 root 換成舊的而已。

Synology 的 Snapshot Replication 就是利用這個機制來快速產生 snapshot，若遇到勒索病毒把家庭照片全加密，rollback 到一小時前的 root 就好，因為加密寫到的是新 block，舊 block 沒被動到。

隨著新寫入不斷產生新 path，舊 snapshot 會慢慢累積，要定期刪掉才騰得出空間。一個從沒被改過的 block，通常會被好幾份 snapshot 同時指到、一起共用。那刪掉其中一份 snapshot 時，filesystem 要怎麼知道哪些 block 可以釋放、哪些還被其他 snapshot 共用？Btrfs 給每個 block 配一個 reference count：拍 snapshot 時共用 block 的 refcount +1，刪 snapshot 時對應 path 上的 block refcount -1，降到 0 才真的釋放該 data block 的磁碟空間。

和 OS 課的 CoW 有什麼不一樣？

看到 copy-on-write 你可能立刻想到 OS 課的 fork()：parent 和 child 共用 physical pages，有一方真的要寫下去時才 duplicate，所以 fork 很便宜。檔案系統的 CoW 精神一樣，但有兩個差異：

觸發時機。虛擬記憶體的 CoW 是 lazy，MMU 把共用 page 標成 read-only，真的有人寫下去才觸發 page fault、才複製。檔案系統的 CoW 是 eager，每筆 write() 都立刻寫新 block、沿 path 往上一路複製到 root。
持久性。虛擬記憶體 CoW 產生的複製只活在 RAM，斷電就沒了；檔案系統 CoW 產生的複製就是 disk 上的正式版本，靠 atomic root swap 讓 snapshot 就算斷電也還在。

CoW 的壞處

每次寫都寫到新位置，意味著一個檔案被反覆編輯後，它的 block 會散在 disk 各處。對讀取大檔案的 workload（例如：影片）這還能接受；但對原地修改頻繁的 workload（例如：資料庫），CoW 加速了 fragmentation。

自問自答

試著用自己的話回答以下問題。如果卡住了，回去重讀對應的段落。

一棵深度 5 的 CoW tree，每個 block 4 KB。Niko 修改了一個 leaf 裡 100 bytes 的資料。這次寫入會觸發多少 bytes 的 disk write？對應的 filesystem-layer WAF 是多少？
為什麼壓縮在 CoW 系統裡幾乎不增加 latency，但在 ext4 這種 in-place filesystem 上會比較難加進去。