軟體設計備忘錄《Btrfs & B-tree Shadowing》

Valerie Aurora在LWN上面寫了一篇關於Btrfs的短篇專文，簡短的介紹了Btrfs的歷史。Btrfs是由Chris Mason所開發的File System，即將取代Ext4成為Linux上預設的File System。Chris引進Ohad Rodeh在USENIX FAST '07發表的B-tree on Shadowing研究成果，改良Btrfs的設計。簡單整理了Rodeh的成果：

1. Proactive Split/Merge on B-tree Updating：在Insertion或Deletion，在尋訪的過程中先做Split/Merge的動作。於是乎消除了Backtrace回去修改Parent Node的行為，如此一來就不會有Multi-thread Deadlock的情況發生。
2. Reference Counting for COW：在做Snapshot的時候，會Shadow每個node都需要維護一個Counter。若是目前的Clone需要寫入任何的Node，那麼就會檢查Counter決定是否要COW；或者是直接覆寫。

 

相較於Reference Counting，WAFL(另一個File System)是用32-bit bitmap來1-to-1對應每一份Clone，所以最多只能有32個Clones，此稱之為Block-map File（謎之聲：怎麼會有這樣的設計呢？…）。關於Block-map的設計，本人猜測是因為原有的Block Entry就已經有Free Flag的設計，若是用Bitmap的設計來對應Clone可能較容易實做。

 

參考資料：

A short history of btrfs

http://lwn.net/Articles/342892/

B-trees, Shadowing, and Clones [PDF]

http://www.cs.tau.ac.il/~ohadrode/papers/btree_TOS.pdf

The Berkeley DB Book: B-tree Deadlock

http://books.google.com.tw/books?id=_WWbpeG9aOIC&pg=PA91&lpg=PA91&dq=Btree+deadlock&source=bl&ots=lKxZJg1G4R&sig=ZSYxO72Gv1EQSzJLbkEh9JVtDsI&hl=zh-TW&ei=EK99StvCEI_-tQP6vLjvCg&sa=X&oi=book_result&ct=result&resnum=1#v=onepage&q=Btree%20deadlock&f=false