質問への回答

質問の歴史

分散デッドロック検出は、2010年代中頃にモノリシックアーキテクチャから細かいマイクロサービスへの移行時に重要な関心事として浮上しました。初期の分散システムはタイムアウトベースの中止や中央集権的なロック管理者に依存しており、高い可用性と分割耐性を必要とするクラウドネイティブ環境には不十分でした。チャンディ-ミスラ-ハースアルゴリズムは分散グラフにおけるエッジ追跡の理論的基盤を確立しましたが、実際の実装は騒がしいネットワーク条件や異種サービススタックに苦労しました。現代のアーキテクチャは、中央の調整なしで機能し、厳格なサービスレベル目標を尊重する自律的な検出メカニズムを要求します。

問題

マイクロサービスエコシステムでは、トランザクションが複数のサービスと永続性技術をまたいで頻繁に発生し、サービスAがPostgreSQLでロックを保持しながらサービスBを待っている間に、サービスBがサービスAを待ってMongoDBロックを保持するという分散サイクルを生み出します。中央集権的なデッドロック検出器は単一障害点やネットワークホットスポットを導入し、マイクロサービスの自律原則を侵害します。タイムアウトベースのアプローチは、高遅延条件下で偽陽性に悩まされ、遅い操作と本当のデッドロックを区別できません。根本的な課題は、ノードが故障したり通知なしにアクセス不能になった場合でも、動的かつ分断されたグラフ内でサイクルを検出することです。

解決策

このアーキテクチャは、Kubernetesを介して展開されたEnvoyサイドカー内に埋め込まれたチャンディ-ミスラ-ハース分散エッジ追跡アルゴリズムを採用します。各サイドカーはローカルな待機グラフを維持し、サイクルを検出するためにgRPC呼び出しチェーンに沿ってラムポートタイムスタンプを持つプローブメッセージを送信します。Redisクラスターはプローブの損失を処理するためにTTL期限付きの一時的な待機関係を保存し、Kafkaはetcdに保存されたビジネス優先度スコアに基づいて犠牲者選択の解決コマンドをブロードキャストします。システムは、コントロールプレーンの分断中にプローブの伝播を確保するためにゴシッププロトコルを使用し、安全を損なうことなく生存性を確保します。

生活からの状況

問題の説明

あるブラックフライデーイベント中、高頻度取引プラットフォームの支払いオーケストレーションサービスは、外国為替レートのロック時に連鎖的な障害を経験しました。JavaベースのFXサービスは、Goベースのコンプライアンスバリデーターと同期しており、これが循環依存関係を生み出し、18分間にわたって15,000の同時トランザクションがフリーズしました。同期したREST呼び出し間でデッドロックが発生し、AWSインフラストラクチャ全体で連鎖的なサーキットブレーカーフェイルがトリガーされ、収益損失は200万ドルを超えました。このインシデントは、データベースレベルのタイムアウトが異種技術スタックを跨ぐサービス間のサイクルを検出できないことを露呈しました。

検討した異なる解決策

我々は最初に、サービス全体のすべてのリソースロックを追跡するためのグローバルトランザクションコーディネーターとして集中型Oracle RACデータベースを展開することを検討しました。このアプローチは、標準的なグラフアルゴリズムを使用した簡単なサイクル検出を提供し、即座の競合解決を可能にしました。しかし、99.999%の可用性保証を必要とし、トランザクションあたり200msのレイテンシオーバーヘッドを追加するという壊滅的な単一障害点が導入されました。ネットワーク分断時には、コーディネーターが使用不可となり、障害を分離するのではなく、全ての支払い処理をグローバルにフリーズさせてしまいました。

チームは、指数バックオフを用いた積極的なタイムアウト戦略を評価し、5秒を超えるトランザクションを中止してジッター付きで再試行しました。これにより調整オーバーヘッドが排除され、Istio仮想サービスの設定を超えてインフラストラクチャの変更は不要になりました。残念ながら、これは40%の偽陽性中止を引き起こす大量のスラッシングを引き起こし、正当な遅いクエリがデッドロックと誤解されました。その結果、再試行の嵐がサービスメッシュを圧倒し、元のデッドロックよりもひどい混雑を生み出し、レイテンシSLAに違反しました。

我々は、アプリケーションコードを変更することなくサービスメッシュにプローブロジックを注入するためにEnvoyのWASMフィルタを使用した分散エッジ追跡メカニズムを分析しました。各サイドカーは、ローカルRedisストリームに30秒のTTLで待機エッジを公開し、バックグラウンドエージェントはチャンディ-ミスラ-ハースプローブを使用してサイクルをチェックしました。犠牲者選択は、ビジネスの重要性スコアをetcdにクエリして高収益トランザクションを優先し、低優先度のバッチジョブが最初に中止されるようにしました。このアーキテクチャは、完全なAWSリージョン障害を生き延びながら、100ms以下の検出レイテンシを約束しました。

選択された解決策とその理由

我々は、エッジ追跡アプローチがサービスの自律性を保ちながら、中央集権的調整の可用性リスクを排除するため、選択しました。このソリューションは、サービスインスタンスの数で水平にスケールし、費用がかかるメインフレームのアップグレードを必要とせず、WASMフィルタはコードの変更なしにJavaとGoのマイクロサービスのポリグロットサポートを可能にしました。検出をインフラストラクチャ層に組み込むことで、デッドロック解決をビジネスロジックの進化から切り離し、検出機能の独立したスケーリングを可能にしました。

結果

導入後、デッドロックによる停止は6ヶ月間の運用中にゼロに減少し、2回の主要な販売イベントが含まれました。検出レイテンシは、20倍のトラフィックスパイクでもp99で85msで安定しており、自動解決が模擬リージョン障害中の99.98%の高優先度トランザクションを保持しました。開発者の生産性は向上し、チームはカスタムタイムアウトロジックを排除し、インシデント応答時間を数時間から自動的な数秒に短縮し、年間500万ドルの収益損失を防ぎました。

候補者が見落としがちな点

本物の分散デッドロックとネットワーク遅延のジッターや順不同のプローブ配信によって引き起こされる偽陽性をどのように区別しますか？

候補者は、待機依存関係の因果順序を確立するためにプローブメッセージにベクトルクロックまたはラムポートタイムスタンプの必要性を頻繁に見落とします。論理的なタイムスタンプがない場合、遅れたプローブがトランザクションがロックを解放した後に到着する可能性があるため、サイクルを誤って示し、不必要な中止を引き起こすことになります。解決策は、プローブにTTLカウンターを実装し、デッドロックを宣言する前に逆パスの確認を必要とすることが必要です。これにより、一時的なネットワーク遅延が偽の犠牲者選択を引き起こさないようにします。

なぜデータベースネイティブのデッドロック検出が異種永続アーキテクチャのクロスサービスデッドロックを解決できないのか？

PostgreSQLとMongoDBは、それぞれのプロセス境界内でのみサイクルを検出し、トランザクションがPostgreSQLで行のロックを保持しながら、MongoDBでドキュメントロックを待っている場合や、RabbitMQでメッセージを待っている場合の状況には盲目になります。候補者は、異種ストレージシステム全体で分散待機グラフを再構築するために、アプリケーションレベルまたはサービスメッシュの計測が必要であることを説明しなければなりません。

ネットワーク分断の間にシステムの生存性をどのように維持し、複数の孤立したサブグループによる同じデッドロックのスプリットブレイン解決を防ぎますか？

これは、分散システムにおける可用性と安全性の間の緊張を明らかにします。分断中、サービスはデッドロックしているピアと到達不可能なピアを区別できず、候補者は可用性を犠牲にするか、重複中止のリスクを冒す解決策を提案することになります。正しいアプローチは、到達可能なノード間のみで犠牲者選択のためにビザンチン耐障害コンセンサスを採用し、分断が直った際にシステムが手動介入なしで一貫した解決に収束することを確保するためにCRDT（Conflict-free Replicated Data Types）を使用して待機グラフを和解することです。