測試分布式系統的線性一致性
最近看到一篇文章 ，寫得非常好，在征得作者 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+ 寫的形式規范。但不幸的是，大部分的系統是沒有的。
【本文是51CTO專欄作者“PingCAP”的原創文章，轉載請聯系作者本人獲取授權】
