作者 | David Giard 責編 | 夏萌

譯者 | 彎月

出品 | CSDN（ID：CSDNnews）

並行編程之所以這麽難，是因為人類大腦的局限性，還是問題本身的復雜性？

我參與過的許多規範計畫都使用了並行或分布式系統。由於正確實作的難度過高，實作錯誤的代價過高，我們在編寫規範上花費了大量的時間和金錢。由於並行與我的工作息息相關，因此我花費了大量時間思考並行的本質。

有一句老笑話說，並行是電腦科學中兩大難題之一。因為並行有很多「偶然性」：很難測試、不可組合、錯誤可能長時間潛伏等等。但導致並行如此難的本質原因究竟是什麽呢？是什麽導致並行軟體本質上比同步軟體更難編寫呢？

我經常聽到的一個理由是，人類是線性思維，而不是並行，因此無法理解競爭條件。我不同意，根據我的經驗，人類非常擅長並行推理。每次開車時，我們都在進行並行推理！

一些研究發現，透過框架將並行轉化為人類術語，人們就能發現競爭條件。因此，雖然並行很難理解，但我認為並不是因為我們在這方面有欠缺。

在我看來，一個更重要的因素是狀態空間爆炸。並行之所以難，是因為並行系統可處於許多不同的可能狀態，而且狀態數量的增長速度超過人們的預期。

行為、交錯和不確定性

假設我們有很多代理{1、2、… n}，每個代理執行的操作都是線性序列。不同的代理可能有不同的演算法。我們需要實作佇列的寫入、讀取、計數器遞增等操作。第一個行程完成p1個原子步驟，第二個完成p2個步驟，依此類推。代理嚴格按線性方式運行程式，但另一個行程可以在每個原子步驟後交錯。假設我們使用了演算法A1A2和B1B2，執行順序為A1B1A2B2或A1B1B2A2，但不可以是A1B2B1A2。

根據這些條件，計算可能出現的執行（行為）順序數量的方程式式如下：

假設我們有3個代理，演算法分2步，則行為的數量為：6!/8 = 90。序列中的每一步都可能導致一個不同的狀態，因此最大不同狀態數（MDS）：6*90=540。這其中任何一個都有可能是「錯誤」的狀態。

在大多數情況下，實際狀態空間將遠小於最大不同狀態數，因為不同的行為最終會得到相同的狀態。然而，計算結果和狀態空間的增長速度遠遠超過了我們的預期。3個代理，3個執行步驟，行為數量為1700種（15K MDS）；而4個代理，2個執行步驟，行為數量為2500種（20K MDS）。這還是所有行為都沒有不確定性的情況！如果代理中的一個步驟可以執行3種操作之一（發送訊息M₁、發送訊息M₂、崩潰），具體執行哪一種為不確定，那麽行為和MDS的數量就會增加三倍。

對於復雜的並行系統來說，擁有數百萬或數千萬個狀態是非常常見的。即使是我的玩具模型也有大約800萬個不同的狀態（雖然經過改善可以減少一些）。我主要考慮狀態空間的效能，因為狀態空間越大，檢查模型所需的時間就越長。但並行之所以難以理解，也是因為如此。如果我的理論MDS是兩百萬個狀態，實際狀態空間只有大約1%，而我的大腦可以理解剩下的99.9%的狀態，那麽仍將漏掉20個邊緣情況。

縮小狀態空間

我常用的一種啟發式方法為：

降低並行難度的所有方法都應優先考慮管理狀態空間。

雖然並非百分百正確（沒有任何一種啟發式方法是百分百正確的），正確率大約為60%，但這就足夠了。狀態空間增長迅速，空間越大，引發的問題就越多。如果我們想構建可維護的並行系統，首先要先縮小空間。

例如執行緒。執行緒共享記憶體，並且執行緒排程器有很大的自由度來掛起執行緒。因此，我們有很多步驟（一行程式碼一個步驟），任何交錯都可能獲得一個不同的狀態。我們可以使用編程構造，比如互斥鎖和障礙，「修剪」狀態空間並給出我想要的行為，但考慮到狀態空間的規模，我必須修剪掉很多狀態，才能得到正確的行為。我的實作有可能出錯，「扭曲」空間（例如添加死結）或者沒有註意到需要刪除的錯誤狀態。執行緒非常容易出錯。

我會選擇改為使用記憶體隔離的行程。排程器仍然可以安排交錯，但行程不能幹擾彼此的內部記憶體。在內部，行程的執行順序仍為A1A2A3A4，但如果涉及外部資源（或行程間通訊）的步驟只有A2和A4，那麽我們只需要考慮A2A4如何影響狀態空間。3個代理，4個步驟，共有35k種交錯；3個步驟，2個步驟，則只有90種。這是一個很大的提升！

我們還能做些什麽？低階原子指令可以在單個步驟中完成更多操作，因此沒有交錯的余地。資料庫事務需要很多物理時間，但只表示一個邏輯時間步驟。數據變化會產生新的步驟，而不可變數據結構可以避免這種情況。

語言可以透過構造更好地修剪結果狀態空間：go的通道、promise/future/async-await、nurseries等。我認為，我們可以將promise視為一種強制「非交錯」的方式：等到做好準備再執行（或到達下一個暫停點）。

我認為，無沖突復制數據型別（CRDT）透過允許交錯來減少狀態空間，而且會進行重新排列，這樣外部變化就是可交換的：A1B1和B1A1得到相同的最終結果，因此不會產生不同的狀態。

再強調一次，這是非常粗略的啟發式方法。

限制

簡單來說，狀態空間越小越好。但這種說法並沒有考慮空間的拓撲結構：有些空間更為復雜。相較於無環空間，迴圈越多的空間越難處理。另外，不確定性的不同形式也很重要，以下兩種形式，前者的行為更為復雜：「代理繼續或重新開始」，「寫入方發送訊息M₁或M₂」。很多人遇到這兩種情況，都會認為「人類不擅長理解並行」。通常，我們需要將狀態簡化為具有相同內容的「狀態等價類」來處理並行，狀態空間越復雜，需要處理的等價類就越多。

一些高級範式可以產生特定的狀態空間拓撲結構，其中包含的交錯更少或等價狀態更多。我聽說，有人聲稱fork-join和pipe-filter特別方便人類理解，我認為他們的意思是「不會產生復雜的狀態空間」。也許事件迴圈也是如此？

還有一個限制是：有缺陷的狀態與有缺陷的行為之間存在差異。有些行為完全可以透過安全狀態，但可能引發「永遠達不到一致性」之類的錯誤。這類錯誤被稱為「活性bug」。

有關並行的哲學探討就到這裏。並行很難，即便你無法理解，也無需不要感到沮喪，這不是你的問題，而是一個組合學的問題。

原文連結：https://buttondown.email/hillelwayne/archive/what-makes-concurrency-so-hard/

未經允許，禁止轉載！

推薦閱讀：