「分散並行錯誤的趨勢與分析[論文筆記]」

这是一篇论文笔记。

T Leesatapornwongsa, JF Lukman, S Lu, HS Gunawi. 数据中心分布式系统的非确定性并发错误的分类法[TASDLOS ’16] > https://doi.org/10.1145/2872362.2872374

TaxDC是对实际应用程序（如Cassandra、HBase、Hadoop、Zookeeper）中发生的分布式并行bug进行收集、分类和分析的项目。作者在其页面上公开了这些数据……但不幸的是，由于疏忽大意，数据已经消失了。https://ucare.cs.uchicago.edu/projects/cbs/ 这里所指的分布式并行bug是指“由可能以非确定顺序发生的分布式事件所引起的分布式系统并行性的bug”。分布式事件包括消息的发送和接收、节点内的计算、节点故障以及重启。

经过调查和分析许多真实的错误，得出以下结论：

• 世界中で使われているシステムでも、効果的なテスト、検証、および分析ツールが欠けている。

• 実世界でのバグは以下の点から見付けづらい。

複数のプロトコルを同時にハンドリングするロジックがある
ユーザーに見える裏でのバックグラウンドジョブが多数動いており、それらとのインタラクションで致命的なバグとなる

ほとんどのバグは典型的な分散システムへの誤解により生まれている。

「1つのメッセージ送受信は2つのメッセージ送受信よりも早い」
「メッセージを送受信しない内部の計算は1つのメッセージ送受信よりも早い」
「トランザクションを使えば安全」
「個々のプロトコルがしっかりしていれば組み合わせても安全」
「不具合のときにリカバリに必要な情報が存在する」

然而，从分类中得出的定量评价表明，

• 分散並行バグのうち 47% はサイレントにクラッシュするため、デバッグが困難。逆に言うと、53%は明示的なエラーとして顕現する。

• 分散並行バグのうち 64% はタイミングの悪い単一のメッセージの送信(意図していない順序や一連のイベントの途中に他のメッセージが来る等)により引き起こされている。残りは突然のクラッシュ/リブートや前2つの複合。

• ほとんどのバグで前提条件は複雑である(63%は何らかのクラッシュが前提、80%は複数のプロトコルが関係する、81%はバックグラウンドプロセスが関係)

• タイミングの条件は1〜3個のメッセージ/ノード/プロトコルのみが関係する場合がほとんどで(>90%)、92% の分散バグはただ1つのメッセージの送信により引きおこされている。

バグの修正方法のパターンの数は少ない。30%はイベント発火のタイミングの修正、40%は新しい機構を導入せずに単にメッセージを遅延・無視・受け入れるようにする変更である。

用一句话来概括，分布式并行错误很难发现和重现，但其原因本身是简单的（尽管导致该错误的背景和重现方法可能较为复杂），修复方法也很简单。

从发现分散式漏洞的角度来看，我们可以考虑使用模糊测试工具Jepsen或模型检测技术（如SPIN）等一种在某种程度上广泛探索的方法，毫无疑问，从实际工具的效果来看，这是一种有效的策略（尽管并非十全十美）。

现在，本文将进一步深入探讨这些问题，但有一章叫做”经验教训”，我认为单单阅读这一章就可以学到很多。简要摘录如下：

• 個々のプロトコル自体を見ると堅牢だが、それらが同時実行されて引き起こされる分散並行バグが多い。

• 必要なタイミングの順序の入れ替えやハードウェアの故障挿入により、分散バグを検出できるスケーラブルなツールは今(当時)のところ存在しない。

• 優れた検出ツールを使っていても、システムの仕様記述(in 形式手法的な文脈)が洗練されていないとあまり効果がない。ほぼ半数のバグはサイレントに起き、検出できた時点で手遅れになっているから。

• 既存の並行バグの手法と分散バグへの手法にギャップがある。

並列バグにフィーチャーした考えとして次のようなものが挙げられている：「メッセージの順序や処理順の仕様の検証」「『典型的な分散システムへの誤解』に基づくバグ検出」……

エラーログ分析は一部では有効だが、それにより見つけられないバグも多い。
分散トランザクションを導入すれば解決するか? → 実際はそもそも分散トランザクションの実装が誤っているというパターンがあり、また実際のシステムでは分散トランザクションでない部分も多く利用されている(パフォーマンスの都合などによる)
修正方法が単純でパターン化できるので、自動修復(実行中のプロセス修復やコード修復)が期待できる。
分散ロジックのテストコードにおいては、プロトコルの組み合わせは高々2つでそこそこ有効である。

由于在实际应用中对散布式错误的需求很高，因此对其进行了广泛的研究。此外，也针对这些错误采取了各种不同领域的方法（如源代码分析、自动修复、RV、形式方法和机器学习等）。在大规模和散布式成为常态的背景下，我认为注视这个领域是有价值的。