Chandy-Lamport分散スナップショットアルゴリズム：大域状態の記録とストリーム処理
システムを停止させずにマーカーの伝播とチャネル記録によって整合性のある大域状態を記録するChandy-Lamportの原理と、Apache Flinkへの応用を解説します。
発行・訂正窓口：infostoa · 編集基準
この記事の個別の執筆者・専門査読者の情報は提供されていません。
計算を止めずに大域状態を記録する
Chandy–Lamportアルゴリズムは、分散計算を続けながら各プロセスのローカル状態と通信路に残るメッセージを記録し、意味のある大域状態を構成します。全ノードの時計を合わせ、同じ物理時刻に保存する方法ではありません。得られる記録が実行中の特定時点と一致しない場合もありますが、メッセージの因果関係を保つ一貫した境界になります。
図はプロセス・マーカー・メッセージの方向を示す概念的な比喩です。実際に成立するイベント順序は本文の例で説明します。
マーカーと通信路の記録規則
原論文は、メッセージが信頼できるFIFO順序で届き、有限時間内に配送される通信路を仮定します。記録を始めたプロセスは自分の状態を保存し、各出力チャネルにマーカーを送ります。最初のマーカーを受け取ったプロセスは自分の状態を記録し、そのマーカーが届いた入力チャネルを空として記録してから、出力チャネルへマーカーを送ります。すでに自分の状態を記録した後、別の入力チャネルでマーカーを受け取るまでに届いた通常メッセージは、そのチャネル状態として記録します。これにより、送信側では記録済みでも受信側の状態にはまだ現れないメッセージを取りこぼしません。
可能なイベント順序：A→Bのメッセージを通信路状態に記録する
A→B、C→A、C→Bの通信路があり、3つのプロセスが同じスナップショットに参加するとします。まずAがアプリケーションメッセージmをBへ送ります。Cがローカル状態を記録してAとBにマーカーを送ります。AはCのマーカーを受け取ってローカル状態を記録し、A→Bへマーカーを送ります。このマーカーは同じ通信路で後続のアプリケーションメッセージより先に送る必要がありますが、マーカーの後にメッセージを送ることはできます。BにはCのマーカーが最初に届くため、Bはローカル状態を記録します。その後A→Bからmを受け取り、Aのマーカーを受け取ります。mはAのマーカーより前に送られ、FIFO順序で先に届くので、Bのローカル状態ではなくA→Bの通信路状態に記録されます。
対照的に、Aがmを送ってからスナップショットを開始し、Bがmを受け取った後にAのマーカーを最初に受け取る順序もあります。この場合、受信はBのローカル状態に含まれ、A→Bの通信路状態は空です。最初の例では、別の入力経路からBへ先にマーカーを届けるプロセスCが必要です。どちらも原論文の信頼できるFIFO通信路を前提に組み立てた説明用のイベント順序であり、実行ログではありません。
処理エンジンのチェックポイントとの違い
Apache Flink 1.19の資料は、チェックポイントバリアと、アプリケーション状態・ストリーム位置を組み合わせるオペレーターのスナップショット、複数入力での整列・非整列処理を説明します。これは同バージョンの実装であり、原論文が定める内容ではありません。内部状態を復元できても、外部システムへの効果が重複しないとは限りません。「Exactly once」と説明する前に、利用するソース、オペレーター、シンク、コネクター、復旧設定が保証する範囲を確認してください。