測試分散式系統的線性一致性

01-26

唐劉譯

最近看到一篇文章 http://www.anishathalye.com/2017/06/04/testing-distributed-systems-for-linearizability/，寫得非常好，在徵得作者 Anish 同意的情況下，決定將其翻譯成中文。但為了更好理解，一些地方並不會逐字翻譯，也會稍作調整。

正確實現一個分散式系統是非常有挑戰的一件事情，因為需要很好的處理並發和失敗這些問題。網路包可能被延遲，重複，亂序或者丟棄，機器可能在任何時候宕機。即使一些設計被論文證明是正確的，也仍然很難再實現中避免 bug。

除非我們使用形式方法，不然，即使我們假設實現是正確的，我們也需要去測試系統。測試分散式系統也是一件非常有挑戰的事情。並發和不確定性使得我們在測試的時候非常難抓住 bug，尤其是在一些極端情況下面才會出現的 bug，譬如同時機器宕機或者極端網路延遲。

正確性

在討論測試分散式系統的正確性之前，我們首先定義下什麼是「正確性」。即使對於一些簡單的系統，要完全的確定系統符合預期也是一件相當複雜的事情。

考慮一個簡單的 key-value 系統，譬如 etcd，支持兩個操作：Put(key, value) 和 Get(key)，首先，我們需要考慮它在順序情況下面的行為。

順序規範

通常對於一個 key-value store，我們對於它在順序操作下面的行為都能有一個直觀的認識：Get 操作如果在 Put 的後面，那麼一定能得到 Put 的結果。譬如，如果 Put("x", "y") ，那麼後面的 Get("x") 就能得到 "y"，如果得到了 "z"，那麼這就是不對的。

我們使用 Python 定義一個簡單的 key-value store：

上面的代碼比較簡單，但包含了足夠的信息，包括初始狀態是怎樣的，內部狀態是如何被操作的結果改變的，從 key-value store 裡面操作返回的結果是怎樣的。這裡需要留意下 Get() 對於不存在的 key 的處理，會返回一個 empty string。

線性一致性

接下來，我們來考慮我們的 key-value store 在並發下面會有怎樣的行為。需要注意順序規範並沒有指明在並發操作下面會發生什麼。譬如，順序規範並沒有說 key-value store 在下面這個場景下可以允許的操作。

我們並不能立刻知道 Get("x") 這個操作會允許返回怎樣的結果。直覺上，我們可以說 Get("x")是跟 Put("x", "y") 和 Put("x", "z") 一起執行的，所以它能可能返回一個值，甚至也可能返回 ""。如果有另一個 Get("x") 的操作在更後面執行，我們可以說這個一定能返回 "z"，因為它是最後一次寫入的值，而且那個時候並沒有其他的並發寫入。

對於一個基於順序規範的並發操作來說，我們會用一個一致性模型，也就是線性一致性來說明它的正確性。在一個線性一致性的系統裡面，任何操作都可能在調用或者返回之間原子和瞬間執行。除了線性一致性，還有一些其他一致性的模型，但多數分散式系統都提供了線性一致性的操作：線性一致性是一個強的一致性模型，並且基於線性一致性系統，很容易去構建其他的系統。考慮到如下對 key-value store 操作的歷史例子：

這個歷史是一個線性的。在下面圖片的藍色地方，我們現實的標明了線性一致的點。這個順序歷史 Put("x", "0"), Get("x") -> "0", Put("x", "1"), Get("x") -> "1"，對於順序規範來說就是一個正確的歷史。

對應的，下面的歷史就不是線性一致的。

對於順序規範來說，這個歷史並不是線性一致的：我們並不能在這個歷史的操作裡面指定出線性一致的點。我們可以畫出 client 1，2 和 3 的，但我們並不能畫出 client 4 的，因為這明顯是一個過期的值。類似的，我們可以畫出 client 1，2 和 4 的，那麼 client 2 的操作一定會在 4 的操作開始的後面，但這樣我們就不能處理 client 3，它只可能合法的返回 "" 或者 "0"。

測試

有了一個正確性的定義，我們就可以考慮如何去測試分散式系統了。通常的做法就是對於正確的操作，不停的進行隨機的錯誤注入，類似機器宕機，網路隔離等。我們甚至能模擬整個網路，這樣我們就能做長時間的網路延遲等。因為測試時隨機的，我們需要跑很多次從而確定一個系統的實現是正確的。

專門測試

我們實際如何做正確操作的測試呢？在最簡單的軟體裡面，我們可以使用輸入輸出測試，譬如 assert(expected_output == f(input))，我們也可以在分散式系統上面使用一個類似的方法，譬如，對於 key-value store，當多個 client 開始執行操作的時候，我們可以有如下的測試：

如果測試掛掉了，那麼這個系統一定不是線性一致性的，當然，這個測試並不是很完備，因為有可能不是線性一致的系統也可能通過這個測試。

線性一致性

一個更好的辦法就是並發的客戶端完全跑隨機的操作。譬如，循環的去調用 kvstore.put(rand(), rand()) 和 kvstore.get(rand())，有可能會只用很少的 key 去增大衝突的概率。但在這種情況下，我們如何定義什麼是正確的操作呢？在上面的簡單的測試裡面，因為每個 client 都操作的是一個獨立的 key，所以我們可以非常明確的知道輸出結果。

但是 clients 並發的操作同一堆 keys，事情就變得複雜了。我們並不能預知每個操作的返回值因為這並沒樣一個唯一的答案。但我們可以用另一個辦法：我們可以記錄整個操作的歷史，然後去驗證這個操作歷史是線性一致的。

線性一致性驗證

一個線性一致性驗證器會使用一個順序規範和一個並發操作的歷史，然後執行一個判定程序去檢查這個歷史在規範下面是否線性一致。

NP 完備

但不幸的是，線性一致性驗證是 NP 完備的。這個證明非常簡單：我們能說明線性一致性驗證是 NP 問題，並且也能展示一個 NP 困難問題能被簡化成線性一致性驗證。明顯的，線性一致性驗證是 NP 問題，譬如，所有操作的線性一致性點，根據相關的順序規範，我們可以在多項式時間裡驗證。

為了說明線性一致性驗證是 NP 困難的，我們可以將子集合問題簡化成線性一致性驗證。對於子集合問題，我們給出非負數的集合 S={s1,s2,…,sn} 和目標結果 t，然後我們必須確定是否存在一個子集 S 的合等於 t。我們可以將這個問題簡化成如下的線性一致性驗證。考慮順序規範：

以及歷史：

只有在子集合問題的答案是「yes」的時候，歷史才是線性的。如果歷史是線性的，那麼我們認為對於任何的 Add(s_i) 操作，在 Get() 操作之前都有線性一致性點，這個就對應了在子集裡面 Si，它的合是 t。如果這個集合裡面有一個子集的合是 t，我們就能構造一個線性化，它有在 Get 操作發生之前，對應子集 Si 的 Add(s_i) 的操作，也有在 Get() 操作之後其餘的操作。

PS：這個章節我大概知道啥意思，但沒找到更好的表述來翻譯，也就湊合著了。後面再看 paper 來深入了解吧。

實現

即使線性一致性驗證是 NP 完全的，在實際中，它仍然能在一些小的歷史上面很好的工作。線性一致性驗證器的實現會用一個可執行的規範，加上一個歷史，執行一個搜索過程去構造一個線性化，並使用一些技巧來限制減少搜索的空間。

在 Jepsen 裡面，有一個一致性驗證工具 Knossos，但不幸的是，在測試一些分散式 key-value store 的時候，Knossos 並不能很好的工作，它可能只能適用於一些少的並發 clients，以及只有幾百的事件的歷史。但在一些測試裡面，有很多的 clients，以及會生成更多的歷史事件。為了解決 Knossos 的問題，作者開發了 Procupine，一個用 Go 寫的更快的線性一致性驗證工具。Porcupine 使用一個用 Go 開發的執行規範去驗證歷史是否是線性的。根據實際測試的情況，Porcupine 比 Knossos 快很多倍。

效果

在測試分散式系統的線性一致性的時候，使用錯誤注入是一個很有效的手段。

作為對比，在使用專門的測試用 Porcupine 測試 key-value store 的時候，作者使用了這兩種方式。作者在實現它自己的 key-value store 的時候引入不同的設計錯誤，譬如在修改之後會出現過期讀，來看這些測試是否會掛掉。專門測試會捕捉到很多 bugs，但並沒有能力去捕捉到更多的狡猾的 bugs。相對而言，作者現在還沒找到一個正確性的 bug 是線性一致性測試不能抓住的。

形式方法能夠保證一個分散式系統的正確性。例如，UM PLSE 研究小組最近使用 Coq proof assistnt 來驗證了 Raft 一致性協議。但不幸的的是，驗證需要特定的知識，另外驗證實際的系統需要做大量的工作。沒準有一天，驗證能被用在實際系統上面，但現在，主要還是測試，而不是驗證。
理論上，所有的生產系統都會有一個形式規範，而且一些系統也已經有了，譬如 Raft 就有一個用 TLA+ 寫的形式規範。但不幸的是，大部分的系統是沒有的。