測試分布式系統(tǒng)的線性一致性
最近看到一篇文章 ，寫得非常好，在征得作者 Anish 同意的情況下，決定將其翻譯成中文。但為了更好理解，一些地方并不會逐字翻譯，也會稍作調(diào)整。
正確實現(xiàn)一個分布式系統(tǒng)是非常有挑戰(zhàn)的一件事情，因為需要很好的處理并發(fā)和失敗這些問題。網(wǎng)絡(luò)包可能被延遲，重復，亂序或者丟棄，機器可能在任何時候宕機。即使一些設(shè)計被論文證明是正確的，也仍然很難再實現(xiàn)中避免 bug。
除非我們使用形式方法，不然，即使我們假設(shè)實現(xiàn)是正確的，我們也需要去測試系統(tǒng)。測試分布式系統(tǒng)也是一件非常有挑戰(zhàn)的事情。并發(fā)和不確定性使得我們在測試的時候非常難抓住 bug，尤其是在一些極端情況下面才會出現(xiàn)的 bug，譬如同時機器宕機或者極端網(wǎng)絡(luò)延遲。
正確性
在討論測試分布式系統(tǒng)的正確性之前，我們首先定義下什么是 “正確性”。即使對于一些簡單的系統(tǒng)，要完全的確定系統(tǒng)符合預期也是一件相當復雜的事情。
考慮一個簡單的 key-value 系統(tǒng)，譬如 etcd，支持兩個操作：Put(key, value) 和 Get(key)，首先，我們需要考慮它在順序情況下面的行為。
順序規(guī)范
通常對于一個 key-value store，我們對于它在順序操作下面的行為都能有一個直觀的認識：Get 操作如果在 Put 的后面，那么一定能得到 Put 的結(jié)果。譬如，如果 Put("x", "y") ，那么后面的 Get("x") 就能得到 "y"，如果得到了 "z"，那么這就是不對的。
我們使用 Python 定義一個簡單的 key-value store：
上面的代碼比較簡單，但包含了足夠的信息，包括初始狀態(tài)是怎樣的，內(nèi)部狀態(tài)是如何被操作的結(jié)果改變的，從 key-value store 里面操作返回的結(jié)果是怎樣的。這里需要留意下 Get() 對于不存在的 key 的處理，會返回一個 empty string。
線性一致性
接下來，我們來考慮我們的 key-value store 在并發(fā)下面會有怎樣的行為。需要注意順序規(guī)范并沒有指明在并發(fā)操作下面會發(fā)生什么。譬如，順序規(guī)范并沒有說 key-value store 在下面這個場景下可以允許的操作。
我們并不能立刻知道 Get("x") 這個操作會允許返回怎樣的結(jié)果。直覺上，我們可以說 Get("x")是跟 Put("x", "y") 和 Put("x", "z") 一起執(zhí)行的，所以它能可能返回一個值，甚至也可能返回 ""。 如果有另一個 Get("x") 的操作在更后面執(zhí)行，我們可以說這個一定能返回 "z"，因為它是***一次寫入的值，而且那個時候并沒有其他的并發(fā)寫入。
對于一個基于順序規(guī)范的并發(fā)操作來說，我們會用一個一致性模型，也就是線性一致性來說明它的正確性。在一個線性一致性的系統(tǒng)里面，任何操作都可能在調(diào)用或者返回之間原子和瞬間執(zhí)行。除了線性一致性，還有一些其他一致性的模型，但多數(shù)分布式系統(tǒng)都提供了線性一致性的操作：線性一致性是一個強的一致性模型，并且基于線性一致性系統(tǒng)，很容易去構(gòu)建其他的系統(tǒng)?？紤]到如下對 key-value store 操作的歷史例子：
這個歷史是一個線性的。在下面圖片的藍色地方，我們現(xiàn)實的標明了線性一致的點。這個順序歷史 Put("x", "0"), Get("x") -> "0", Put("x", "1"), Get("x") -> "1"，對于順序規(guī)范來說就是一個正確的歷史。
對應的，下面的歷史就不是線性一致的。
對于順序規(guī)范來說，這個歷史并不是線性一致的：我們并不能在這個歷史的操作里面指定出線性一致的點。我們可以畫出 client 1，2 和 3 的，但我們并不能畫出 client 4 的，因為這明顯是一個過期的值。類似的，我們可以畫出 client 1，2 和 4 的，那么 client 2 的操作一定會在 4 的操作開始的后面，但這樣我們就不能處理 client 3，它只可能合法的返回 "" 或者 "0"。
測試
有了一個正確性的定義，我們就可以考慮如何去測試分布式系統(tǒng)了。通常的做法就是對于正確的操作，不停的進行隨機的錯誤注入，類似機器宕機，網(wǎng)絡(luò)隔離等。我們甚至能模擬整個網(wǎng)絡(luò)，這樣我們就能做長時間的網(wǎng)絡(luò)延遲等。因為測試時隨機的，我們需要跑很多次從而確定一個系統(tǒng)的實現(xiàn)是正確的。
專門測試
我們實際如何做正確操作的測試呢?在最簡單的軟件里面，我們可以使用輸入輸出測試，譬如 assert(expected_output == f(input))，我們也可以在分布式系統(tǒng)上面使用一個類似的方法，譬如，對于 key-value store，當多個 client 開始執(zhí)行操作的時候，我們可以有如下的測試：
如果測試掛掉了，那么這個系統(tǒng)一定不是線性一致性的，當然，這個測試并不是很完備，因為有可能不是線性一致的系統(tǒng)也可能通過這個測試。
線性一致性
一個更好的辦法就是并發(fā)的客戶端完全跑隨機的操作。譬如，循環(huán)的去調(diào)用 kvstore.put(rand(), rand()) 和 kvstore.get(rand())，有可能會只用很少的 key 去增大沖突的概率。但在這種情況下，我們?nèi)绾味x什么是正確的操作呢?在上面的簡單的測試里面，因為每個 client 都操作的是一個獨立的 key，所以我們可以非常明確的知道輸出結(jié)果。
但是 clients 并發(fā)的操作同一堆 keys，事情就變得復雜了。我們并不能預知每個操作的返回值因為這并沒樣一個唯一的答案。但我們可以用另一個辦法：我們可以記錄整個操作的歷史，然后去驗證這個操作歷史是線性一致的。
線性一致性驗證
一個線性一致性驗證器會使用一個順序規(guī)范和一個并發(fā)操作的歷史，然后執(zhí)行一個判定程序去檢查這個歷史在規(guī)范下面是否線性一致。
NP 完備
但不幸的是，線性一致性驗證是 NP 完備的。這個證明非常簡單：我們能說明線性一致性驗證是 NP 問題，并且也能展示一個 NP 困難問題能被簡化成線性一致性驗證。明顯的，線性一致性驗證是 NP 問題，譬如，所有操作的線性一致性點，根據(jù)相關(guān)的順序規(guī)范，我們可以在多項式時間里驗證。
為了說明線性一致性驗證是 NP 困難的，我們可以將子集合問題簡化成線性一致性驗證。對于子集合問題，我們給出非負數(shù)的集合 S={s1,s2,…,sn} 和目標結(jié)果 t，然后我們必須確定是否存在一個子集 S 的合等于 t。我們可以將這個問題簡化成如下的線性一致性驗證。考慮順序規(guī)范：
以及歷史：
只有在子集合問題的答案是 “yes” 的時候，歷史才是線性的。如果歷史是線性的，那么我們認為對于任何的 Add(s_i) 操作，在 Get() 操作之前都有線性一致性點，這個就對應了在子集里面 Si，它的合是 t。如果這個集合里面有一個子集的合是 t，我們就能構(gòu)造一個線性化，它有在 Get 操作發(fā)生之前，對應子集 Si 的 Add(s_i) 的操作，也有在 Get() 操作之后其余的操作。
PS：這個章節(jié)我大概知道啥意思，但沒找到更好的表述來翻譯，也就湊合著了。后面再看 paper 來深入了解吧。
實現(xiàn)
即使線性一致性驗證是 NP 完全的，在實際中，它仍然能在一些小的歷史上面很好的工作。線性一致性驗證器的實現(xiàn)會用一個可執(zhí)行的規(guī)范，加上一個歷史，執(zhí)行一個搜索過程去構(gòu)造一個線性化，并使用一些技巧來限制減少搜索的空間。
在 Jepsen 里面，有一個一致性驗證工具 Knossos，但不幸的是，在測試一些分布式 key-value store 的時候，Knossos 并不能很好的工作，它可能只能適用于一些少的并發(fā) clients，以及只有幾百的事件的歷史。但在一些測試里面，有很多的 clients，以及會生成更多的歷史事件。為了解決 Knossos 的問題，作者開發(fā)了 Procupine，一個用 Go 寫的更快的線性一致性驗證工具。Porcupine 使用一個用 Go 開發(fā)的執(zhí)行規(guī)范去驗證歷史是否是線性的。根據(jù)實際測試的情況，Porcupine 比 Knossos 快很多倍。
效果
在測試分布式系統(tǒng)的線性一致性的時候，使用錯誤注入是一個很有效的手段。
作為對比，在使用專門的測試用 Porcupine 測試 key-value store 的時候，作者使用了這兩種方式。作者在實現(xiàn)它自己的 key-value store 的時候引入不同的設(shè)計錯誤，譬如在修改之后會出現(xiàn)過期讀，來看這些測試是否會掛掉。專門測試會捕捉到很多 bugs，但并沒有能力去捕捉到更多的狡猾的 bugs。相對而言，作者現(xiàn)在還沒找到一個正確性的 bug 是線性一致性測試不能抓住的。
- 形式方法能夠保證一個分布式系統(tǒng)的正確性。例如，UM PLSE 研究小組最近使用 Coq proof assistnt 來驗證了 Raft 一致性協(xié)議。但不幸的的是，驗證需要特定的知識，另外驗證實際的系統(tǒng)需要做大量的工作。沒準有一天，驗證能被用在實際系統(tǒng)上面，但現(xiàn)在，主要還是測試，而不是驗證。
- 理論上，所有的生產(chǎn)系統(tǒng)都會有一個形式規(guī)范，而且一些系統(tǒng)也已經(jīng)有了，譬如 Raft 就有一個用 TLA+ 寫的形式規(guī)范。但不幸的是，大部分的系統(tǒng)是沒有的。
【本文是51CTO專欄作者“PingCAP”的原創(chuàng)文章，轉(zhuǎn)載請聯(lián)系作者本人獲取授權(quán)】
