分散並行バグの傾向と分析 [論文メモ]

論文メモです。

T Leesatapornwongsa, JF Lukman, S Lu, HS Gunawi. TaxDC: A Taxonomy of Non-Deterministic Concurrency Bugs in Datacenter Distributed Systems [ASPLOS '16] > https://doi.org/10.1145/2872362.2872374

TaxDC は Cassandra, HBase, Hadoop, Zookeeper などの実際のアプリケーションで発生した分散並行バグを収集・分類・解析を行ったものです。著者のページでそのデータが公開………されていたんですが、不手際によりデータが消失してしまったようです。 https://ucare.cs.uchicago.edu/projects/cbs/ ここでいう分散並行バグとは、「非決定的な順序で発生する可能性のある分散イベントによって引き起こされる分散システムの並行性のバグ」です。分散イベントは、メッセージの送受信、ノード内での計算、ノードの障害、およびリブートを含みます。

多数の実際のバグを調査して分かったこととして以下が述べられています。

• 世界中で使われているシステムでも、効果的なテスト、検証、および分析ツールが欠けている。
• 実世界でのバグは以下の点から見付けづらい。
  • 複数のプロトコルを同時にハンドリングするロジックがある
  • ユーザーに見える裏でのバックグラウンドジョブが多数動いており、それらとのインタラクションで致命的なバグとなる
• ほとんどのバグは典型的な分散システムへの誤解により生まれている。
  • 「1つのメッセージ送受信は2つのメッセージ送受信よりも早い」
  • 「メッセージを送受信しない内部の計算は1つのメッセージ送受信よりも早い」
  • 「トランザクションを使えば安全」
  • 「個々のプロトコルがしっかりしていれば組み合わせても安全」
  • 「不具合のときにリカバリに必要な情報が存在する」

一方で、分類してわかった定量的な評価としては、

• 分散並行バグのうち 47% はサイレントにクラッシュするため、デバッグが困難。逆に言うと、53%は明示的なエラーとして顕現する。
• 分散並行バグのうち 64% はタイミングの悪い単一のメッセージの送信(意図していない順序や一連のイベントの途中に他のメッセージが来る等)により引き起こされている。残りは突然のクラッシュ/リブートや前2つの複合。
• ほとんどのバグで前提条件は複雑である(63%は何らかのクラッシュが前提、80%は複数のプロトコルが関係する、81%はバックグラウンドプロセスが関係)
• タイミングの条件は1〜3個のメッセージ/ノード/プロトコルのみが関係する場合がほとんどで(>90%)、92% の分散バグはただ1つのメッセージの送信により引きおこされている。
• バグの修正方法のパターンの数は少ない。30%はイベント発火のタイミングの修正、40%は新しい機構を導入せずに単にメッセージを遅延・無視・受け入れるようにする変更である。

一言で言うと「分散並列バグは見つけにくい・再現しにくいが、原因自体は単純(ただしそれに至る背景=再現方法は複雑)で修正はシンプル」と言ったところでしょうか。

分散バグを見つけるという観点から言うと、ファジングツールのJepsen や、SPIN を始めとしたモデル検査というある意味マッシブに探索していく技法が思いつきますが、たしかに実際それらのツールの業績を見るに有効な戦略であると感じます。(後述ですが万能ではありません)

さて、本文はそれらの深掘りに進んでいきますが、Lessons Learned という章があり、ここだけ読むだけでも勉強になると思います。抜粋すると：

• 個々のプロトコル自体を見ると堅牢だが、それらが同時実行されて引き起こされる分散並行バグが多い。
• 必要なタイミングの順序の入れ替えやハードウェアの故障挿入により、分散バグを検出できるスケーラブルなツールは今(当時)のところ存在しない。
• 優れた検出ツールを使っていても、システムの仕様記述(in 形式手法的な文脈)が洗練されていないとあまり効果がない。ほぼ半数のバグはサイレントに起き、検出できた時点で手遅れになっているから。
• 既存の並行バグの手法と分散バグへの手法にギャップがある。
  • 並列バグにフィーチャーした考えとして次のようなものが挙げられている：「メッセージの順序や処理順の仕様の検証」「『典型的な分散システムへの誤解』に基づくバグ検出」……
• エラーログ分析は一部では有効だが、それにより見つけられないバグも多い。
• 分散トランザクションを導入すれば解決するか? → 実際はそもそも分散トランザクションの実装が誤っているというパターンがあり、また実際のシステムでは分散トランザクションでない部分も多く利用されている(パフォーマンスの都合などによる)
• 修正方法が単純でパターン化できるので、自動修復(実行中のプロセス修復やコード修復)が期待できる。
• 分散ロジックのテストコードにおいては、プロトコルの組み合わせは高々2つでそこそこ有効である。

分散バグについては実用上の需要が高いことから研究が盛んに行われており、またそれらに対し様々な分野からのアプローチ(ソースコード解析・自動修正・RV・形式手法・機械学習 etc)がなされています。大規模・分散があたり前になってきている中、この分野に注視していく価値はあると思います。