檔案系統天生就是不平等的 – 實現崩潰一致性應用的複雜性

最近看到一篇 Paper，覺得很有意思，Paper 的主題是 “All File Systems Are Not Created Equal”，看來檔案系統也跟人一樣，天生就是不平等的。這篇 Paper 主要是討論如何找出應用程式對檔案操作的有問題的地方，保證在發生崩潰的時候，也能保證資料的一致性，從而正常的恢復，論文裡面作者叫做 “crash consistent”，也就是『崩潰一致性』。

要讓應用在崩潰之後，能正常恢復，說起來容易，實際還是比較困難的，因為一方面應用程式會依賴底層的檔案系統的實現，不同檔案系統對一些保證是不一樣的，譬如是否能支援原子 rename 這些。同時，很多檔案系統，會提供豐富的配置供使用者調優，譬如 etx4 就有 write back，ordered 這些掛載屬性，這些就更加難判定檔案系統在崩潰時的具體行為。

而另一方面，則是應用程式自己對資料一致性的處理，我們都知道，每次檔案操作之後，都進行強制 sync，這樣就是非常安全的（當然，這裡排除了硬體故障），但大家知道這個效能就是非常的差了，所以為了效能，我們勢必在檔案操作上面做很多最佳化，這些就在崩潰的時候引入了不確定性了。

為瞭解決這兩個問題，論文作者實現了兩個工具，一個就是 Block Order Breaker (BOB)，而另一個就是 Application-Level Intelligent Crash Explorer(ALICE)。

BOB

BOB 主要是為了測試檔案系統的 Persistence Properties。對於一個給定的檔案系統，當在發生崩潰之後，有哪些可能的狀態，這個就是用 Persistence Properties 來確定的。

那這個 BOB 是怎麼做的呢？首先 BOB 會一個簡單的場景去壓力測試 Persistence Properties（譬如，一批特定 size 的持續寫入來驗證 overwrite 的原子性）。BOB 會收集這個場景產生的 block I/O，然後重新排序這些收集的 blocks，選擇性的將一些寫入到磁碟去產生一個合法的磁碟 state。用這種方式，BOB 能產生一批在崩潰之後，多個對應不同 disk states 的唯一的磁碟 images 。然後 BOB 會在各自的 image 上面執行檔案系統的 recovery ，並檢查 Persistence Properites 是否繼續滿足（譬如 Write 是原子的）。

ALICE

ALICE 的原理其實比較簡單，就是透過 trace 應用程式的 system call 來直接構建檔案的 state。

使用 ALICE 的時候，使用者首先需要提供一個初始化的檔案 snapshot，譬如一個完整的檔案目錄，一個 workload 指令碼（譬如執行一次事務），一個跟 workload 對應的 checker 指令碼，用來檢查 workload 的不變性（譬如事務是否是原子的）。Alice 會在不同的 crash states 上面去執行 checker。在執行 workload  的時候，Alice 會生成 update protocol 的邏輯表示，記錄 protocol 裡面的脆弱的地方以及對應的程式碼，以及 persistence properties。

ALICE 會將 trace 的 system call 轉換成邏輯操作。邏輯操作會將當前的 system call，I/O 操作抽象成更精簡的檔案系統操作。譬如，write，pwrite，writev，pwritev，mmap 這些操作會轉成 overwrite 或者 append。

對於不同的檔案系統來說，crash state 是不一樣的，ALICE 使用一個 Abstract Persistence Model (APM) 來抽象出不同檔案系統的 crash state，如果想測試特定檔案系統裡面的易脆性，可以寫一個特定的 APM。對於指定的檔案系統，APM 會指定邏輯操作裡面原子性和順序性的所有約束，這樣就能定義 crash state。APM 透過兩個邏輯物體 –  file inodes 包括 data 和 size，directories 包括 directory 的 entries。每個邏輯操作會操作一個或者多個這些物體。為了更好的抓住中間的 crash state，APM 會將邏輯操作拆分成多個微操作 – 也就是能用到邏輯物體的最小原子更新。主要包括：

• write_block：也就是寫到檔案的一個 size 的 block。包含兩個特定的引數，zeroes 和 random，zero 意味著檔案系統初始化了一個新分配的全為 0 的 block，而 random 則是表示一個未初始化的 block。如果檔案不是追加寫，那麼就不會更新檔案的 size。

• change_file_size：更新 file inode 的大小

• create_dir_entry：在一個目錄裡面建立一個目錄 entry，並且關聯一個檔案 inode 或者目錄到它上面。

• delete_dir_entry：刪掉一個目錄 entry。

• stdout：在終端輸出新增訊息。

APM 定義了邏輯操作如何轉換成微操作，譬如上面說的 overwrite 操作，就會轉換成一個或者多個 write_block 操作。APM 同樣也會定義不同微操作之間的順序，譬如所有在 sync 之後的操作都必須排在 sync 的後面。

有了微操作以及順序，ALICE 會先將應用程式的初始化 snapshot 表示成邏輯物體，然後會選擇滿足順序關係的不同集合的微操作對初始狀態進行應用，這樣就會構造出一個 crash state。對於每個 crash state，ALICE 會將邏輯物體重新轉換成對應的實際檔案，然後使用 checker 進行檢查。

例子

這裡說一下 ALICE 提供的一個 toy 例子，比較簡單，去掉了 assert 判斷:

int fd = open("tmp", O_CREAT | O_RDWR, 0666);int ret = write(fd, "world", 5);
ret = close(fd);
ret = rename("tmp", "file1");printf("Updated\n");
ret = link("file1", "link1");
ret = link("file1", "link2");

這個例子會做幾件事情：

1. 開啟 tmp 檔案，會寫入 “world”，然後將 tmp 檔案改名。當列印 “Updated” 之後，這個操作就完成，檔案內容就必須是 “world”。

2. 設定 link，link1 或者 link2 要不存在，要不不存在。

首先我們執行 workload，也就是 toy_workload.sh 指令碼，該指令碼會編譯 toy 測試用例，建立兩個目錄，一個是 workload_dir，用來放置操作的檔案，我們會建立一個  file1 檔案，寫入 “hello”。另一個就是 traces_dir，用來儲存 ALICE trace 的資訊。然後執行 alice-record --workload_dir . \ --traces_dir ../traces_dir \ ../a.out。

然後我們就執行 check，對應的 check 主要判斷邏輯如下：

if 'Updated' in stdout:    # Check durability
    assert open('file1').read() == 'world'else:    # Check atomicity
    assert open('file1').read() in ['hello', 'world']# Check whether link1 and link2 were created together as a single atomic unitdirlist = os.listdir('.')assert ('link1' in dirlist) == ('link2' in dirlist)

如果控制檯打印出來 “Updated”，那麼檔案一定有 “world”，否則就可能是原來的檔案內容 “hello”，或者新的 “world”。Link1 和 Link2 要不都存在，要不都不在。

然後我們執行 check，alice-check --traces_dir=traces_dir --checker=./toy_checker.py，首先會將應用對應的邏輯操作打印出來：

Parsing traces to determine logical operations ...
Logical operations:
0   creat("tmp", parent=200440197, mode='0666', inode=200446770)
1   append("tmp", offset=0, count=5, inode=200446770)
2   rename(dest="file1", source="tmp", source_hardlinks=1, source_parent=200440197, dest_size=5, dest_hardlinks=1, source_size=5, dest_parent=200440197, source_inode=200446770, dest_inode=200440198)
3   stdout("'Updated\n'")
4   link(dest="link1", source="file1", source_parent=200440197, dest_parent=200440197, source_inode=200446770)
5   link(dest="link2", source="file1", source_parent=200440197, dest_parent=200440197, source_inode=200446770)

然後根據 check 來檢查易脆性：

Finding vulnerabilities...
(Dynamic vulnerability) Across-syscall atomicity, sometimes concerning durability: Operations 4 until 5 need to be atomically persisted(Static vulnerability) Across-syscall atomicity: Operation toy.c:19[main] until toy.c:21[main](Dynamic vulnerability) Ordering: Operation 1 needs to be persisted before 2
(Dynamic vulnerability) Ordering: Operation 2 needs to be persisted before 3
(Static vulnerability) Ordering: Operation toy.c:12[main] needed before toy.c:16[main](Static vulnerability) Ordering: Operation toy.c:16[main] needed before toy.c:19[main](Dynamic vulnerability) Atomicity: Operation 2(destination unlinked fully, source untouched, destination and source unlinked fully, destination unlinking partial  semi-truncated (3 count splits), destination unlinking partial , destination unlinking partial fully truncated)
(Static vulnerability) Atomicity: Operation toy.c:16[main] (destination unlinked fully, source untouched,destination unlinking partial fully truncated,destination and source unlinked fully,destination unlinking partial ,destination unlinking partial  semi-truncated (3 count splits))Done finding vulnerabilities.

可以看到，在第二個操作 rename 之前，操作 1 必須持久化。

小結

上面只是對 ALICE 的一個簡單介紹，當然ALICE 還有很多限制，但對於一些常用的操作，還是能檢查出來了。後面還是需要再抽時間詳細研究一下。

下一步自然就是想到將 ALICE 應用到我們自己的系統中來，無論是 RocksDB，還是我們其他很多的檔案操作，我們都可以使用 ALICE 來看系統的 crash consistent。如果你對這塊感興趣，歡迎聯絡我，tl@pingcap.com。