関係マップ:アプリケーションレベルのチェックポイント
この地図は「アプリケーション自身が、自分の状態のうち復元に必要な分だけを保存して復元する」という一群の技術を、分野をまたいで見渡すためのもの。 計算ノートブックの状態管理は、この一群の最も新しい応用のひとつにすぎない。 情報源は各論文のアブストラクトと本文、公式ドキュメント、公開リポジトリ。§6 に挙げた代表的な論文には個別ノートを作成済みで、この地図はそれらを横断して分野の輪郭を描く。 更新:2026-09-23。HPC、ストリーム処理、データベース、言語処理系イメージ、ワークフローエンジン、プリエンプション耐性の全分野で代表的な論文の個別ノートを作成した。原論文本文が未取得の箇所と、公式ドキュメントに基づく箇所は各節の脚注と該当ノートに明記する。
1. 「アプリケーションレベル」とは何を指すか
チェックポイントの実装は、状態の意味を誰が知っているかによって層に分かれる。
- システムレベル:OS がプロセスやコンテナのアドレス空間を丸ごと書き出す。アプリは自分が保存されていることを知らない。CRIU、BLCR がこれにあたる。
- ユーザ空間の透過的 C/R:カーネルを改変せず、ライブラリの割り込みでプロセス群と通信状態を捕捉する。DMTCP は fork、exec、TCP ソケット、パイプ、pid の仮想化までユーザ空間で扱う1。
- アプリケーションレベル:アプリ自身が「復元に必要な状態はこれだ」と宣言し、その分だけを保存する。
三つ目がこの地図の対象である。
補足図(AI生成):横軸は「アプリの意味論をどれだけ使うか」。右へ行くほど保存量は小さく可搬になるが、アプリ側の実装コストが上がる。
層の違いは、そのままトレードオフの違いになる。 システムレベルはアプリを一行も変えずに済むかわりに、アドレス空間の全体を書き出すため保存量が大きく、カーネルやデバイスの差異を越えて復元しにくい。 アプリケーションレベルは保存量が桁で小さくなり、別のノード数や別の並列構成へも復元できるが、開発者が臨界状態を正しく指定しなければ復元そのものが失敗する。 この「指定の負担をどう軽くするか」が、後述するいくつかの分野に共通する課題になっている。
なお、層の区別とは別に、分散したプロセス群をどう整合させるかという古典的な分類軸がある。 Elnozahy らはロールバック復旧のプロトコルを、チェックポイントだけに頼る方式(協調的、非協調的、通信誘発)と、チェックポイントに非決定的イベントのログを組み合わせる方式(悲観的、楽観的、因果的)に整理した2。 この分類は層に直交していて、以下のどの分野にも顔を出す。
2. どの分野にも現れる四つの設計判断
分野が違っても、アプリケーションレベルのチェックポイントを設計する人は同じ四つを決めている。
- 何を保存するか:復元に必要な最小の状態はどれか。指定を人手でやるか、依存解析で機械に任せるか。
- どこに保存するか:ローカルメモリ、隣接ノード、共有ファイルシステムのどれに置くか。速さと堅牢さのどちらを取るか。
- いつ保存するか:頻度を上げれば失う仕事は減るが、保存の overhead が増える。この最適点は、障害間隔を μ、保存時間を C として概ね
sqrt(2 * μ * C)で与えられる(Young/Daly の式)3。 - 分散したときにどう足並みを揃えるか:複数プロセスの断片を、矛盾のない一つの時点として揃える必要がある。
以下の各分野は、この四つに別々の答えを出している。
3. 分野ごとの状況
3.1 HPC の科学計算
この分野が最も長く、最も体系的にアプリケーションレベルのチェックポイントを扱ってきた。 中心にあるのは多階層チェックポイントという考え方で、速くて壊れやすい階層に頻繁に書き、遅くて堅い階層にはたまに非同期で流す。
- SCR(SC10)は、計算ノードの RAM、フラッシュ、ローカルディスクへ書く L1、隣接ノード間でパートナーコピーまたは XOR 符号化する L2、並列ファイルシステムへ書く L3 という三階層を提案した4。開発元の LLNL は、低コストな階層への保存は並列ファイルシステムより 100 倍から 1000 倍速く、それでも障害の 85% に対応でき、マシン効率を最大 35% 改善し、並列ファイルシステムへの負荷を半分にすると報告している(この数値は公式プロジェクトページによる。原論文本文は未取得)5。どの階層に何秒おきに書くかは、障害率と保存コストから確率的なマルコフモデルで決める。
- FTI(SC11)は、SCR の XOR 符号化を Reed-Solomon 符号に置き換え、トポロジを意識した方式を採った6。k 台のプロセスを必ず別々の物理ノードへ配置して1グループとし、各グループから m 個の符号化ファイルを作ることで、グループあたり最大 k/2 台の同時ノード故障に耐える。符号化はノードごとに立てた専用スレッドがアプリの計算と並行して行うため、TSUBAME2.0 上で 1152 GPU を使い 6 分間隔でチェックポイントした評価でも、オーバーヘッドは約 8% にとどまったと報告している。保護するデータセットをユーザが選べる点を、明示的にアプリケーションレベルの利点として挙げている(SPECFEM3D では全メモリの約 20% だけを保護した例が示されている)。
- VeloC(IPDPS 2019)は SCR と FTI のインタフェースを統合したうえで、ノードローカルへの保存と背景での並列ファイルシステムへの掃き出しを非同期化した7。Exascale Computing Project の成果物で、HACC、LatticeQCD、EXAALT で実運用されている(実運用先とアーキテクチャの詳細は、原論文自体ではなく同じ開発チームによる 2021 年の後継論文に基づく)8。
ディスクを一切使わず、他ノードのメモリに符号化して置く diskless checkpointing の系譜もある。 Charm++ は、プロセッサ数より多くのオブジェクト(chare)へアプリを分割し、実行中に配置を変えられるようにするプロセッサ仮想化を土台に持つ9。 FTC-Charm++ はこの上で、各 chare の状態を 2 台の「バディ」ノードへディスクを使わず二重に保存する10。 ノードが落ちると、生存しているノードのどれかに空のプロセスを立てて Charm++ の通信木の形だけを保ち、バディに残った状態から chare を再構築する。 バディを一つ繰り上げるだけで済むため、予備ノードをあらかじめ確保しておく必要がない。 復旧が終わると自動で負荷分散をかけ直し、減った台数へ chare を配り直す。 128 プロセッサでの評価では、約 1GB の二重保存が 1 秒未満(Myrinet)で終わり、128 台中 10 台を落としても分子動力学シミュレーションの総実行時間の増加は 50% 未満にとどまったと報告している。 AMPI は、この chare の仕組みの上に MPI ランクをユーザレベルスレッドとして実装し、同じ復旧機構を MPI プログラムに提供する。
そしてこの分野には、臨界状態の指定を機械に返すという系譜がある。 C3(Cornell Checkpoint pre-compiler)は、MPI プログラムをコンパイラで耐障害版へ自動変換する11。 挿入されるのは、チェックポイント地点への制御フローを記録し再生する Position Stack、スタック変数を元のアドレスへ復元する Variable Descriptor Stack、ヒープオブジェクトを元のアドレスへ復元する専用ヒープマネージャの三つで、いずれもポインタの付け替えを不要にする。 分散したプロセスの足並みは、各エポック境界をまたぐメッセージを「遅延」(送信がチェックポイント前、受信が後)と「先行」(受信が前、送信が後)に分類する非ブロッキングな協調プロトコルで揃える。 遅延メッセージは記録して再生し、先行メッセージは非決定的な依存として記録するだけで再送を抑える。 この分類と記録はプロトコル層が MPI 呼び出しをすべて横取りして行うため、MPI 実装のソースには依存しない。 密な共役勾配法で 14%(16384×16384 では状態が大きくなり 43% まで増加)、Laplace ソルバで 2.1% というオーバーヘッドが報告されている。 AutoCheck(2024)は、変数間のデータ依存グラフを構築して精錬し、ヒューリスティックで保存すべき臨界変数を特定する12。 依存グラフは load/store 命令、算術命令、関数呼び出しの引数対応から作り、入力にあたる変数だけが残るまで縮約する。 臨界変数の判定には、書き込み後に読み出される変数、ループの外で使われるループの結果、部分的に上書きされた配列の再読み出しといったヒューリスティックを使う。 利用者が経験に頼って変数を選ぶと、冗長な変数を保存したり、必要な変数を落としたりする、というのがこの研究の出発点にある問題である。 NAS Parallel Benchmarks など 14 個の HPC ベンチマークで正しく再開でき、プロセスを丸ごと保存する BLCR と比べてチェックポイントサイズを最大で 7 桁小さくできたと報告している。
3.2 深層学習の学習
model.state_dict() に何を入れるかを開発者が決める、という意味で、深層学習のチェックポイントは典型的なアプリケーションレベルの実装である。
階層化と非同期化という処方箋も HPC のそれと重なる。
詳細は 深層学習のチェックポイント と 分散深層学習のチェックポイント を参照。
3.3 ストリーム処理と分散データフロー
ストリーム処理には「処理を止められない」という制約が加わる。 Flink の Asynchronous Barrier Snapshotting(ABS)は、Chandy-Lamport の分散スナップショットを非循環な dataflow 向けに仕立て直したものである1314。 Chandy-Lamport は各プロセスの状態を記録した後にマーカーを全出力チャネルへ送り、マーカーが届く前にチャネルへ到着したメッセージをそのチャネルの状態として記録することで、任意のグラフ形状でも一貫した大域状態を得る。 ABS はこれを、ソースから単方向に流れる非循環なグラフに絞ることで単純化する。 ソースタスクはバリアを受け取るとただちに自分の状態をスナップショットしてバリアを下流へ流すが、複数の入力を持つタスクはすべての入力チャネルからバリアが揃うまで各チャネルの後続レコードをバッファに留める(バリアアラインメント)。 揃って初めて自分の状態をスナップショットしてバリアを流し、バッファを解放する。 この手続きにより、非循環なグラフでは伝送中のレコードを一切保存せずに済み、大域スナップショットはオペレータの状態だけで構成される。 ループを含むグラフでは、逆辺(back-edge)を経由するタスクだけが、バリアを流してから同じ逆辺でバリアが戻るまでに受け取ったレコードを別途ログしてスナップショットに含める。 実装側ではさらに、RocksDB を状態バックエンドにして前回から変わった分だけを書き出すインクリメンタルチェックポイントを持つ。 RocksDB は書き込みをメモリ上のメモリテーブルにためてから不変な SST ファイルへ書き出す LSM 木であり、Flink は前回のチェックポイント以降に新しく作られた SST ファイルだけを転送することで差分を安価に特定する。 ファイルは複数のチェックポイントにまたがって共有されるため、どのチェックポイントからまだ参照されているかを参照カウントで追跡してから不要なファイルを消す。 ただし RocksDB がバックグラウンドで行う compaction が古い SST 群を新しいファイルへまとめ直すと、内容自体は新しくなくてもチェックポイントサイズが一時的に膨らむ。
Spark は逆の立場を取る。 RDD は決定的な変換によってのみ作られるため、各 RDD は自分がどの親からどの変換で作られたかという lineage を保持しておくだけでよい15。 パーティションが失われても、lineage をたどって失われた分だけを別ノードで並列に再計算できる。 この再計算のコストは依存の形で変わる。 親の各パーティションが高々一つの子パーティションにしか使われない狭い依存(map、filter)なら、失われたパーティションだけを局所的に作り直せる。 結合やキーによる集約のように親の一つのパーティションが複数の子にまたがる広い依存では、失敗が祖先の広い範囲の再計算を要求しうる。 原論文はチェックポイントを、こうした広い依存を含み反復のたびに lineage が伸び続けるデータセット(反復計算中の PageRank のランクなど)に限って勧めており、狭い依存で安定ストレージ上に親を持つデータセットでは「チェックポイントする価値がない場合もある」と述べている。 k-means の実行中にノードを1台落とした評価では、lineage による部分再計算によって当該イテレーションの時間が 58 秒から 80 秒に伸びただけだったと報告されている。 「保存するか、再計算するか」という二択を、既定値を再計算側に置いて解いた形になっている。
3.4 データベース
データベースは、チェックポイント単独では足りずログと組で使う、という設計を最も長く洗練させてきた分野である。
ARIES の fuzzy checkpoint は、チェックポイント中にダーティページを1枚も同期的にディスクへ書き戻さない16。
begin_chkpt ログレコードを書いてから、実行中のトランザクションを止めずにダーティページテーブルとトランザクションテーブルを集め、集め終えたところで end_chkpt レコードとして書く。
ダーティページテーブルの各エントリが持つ RecLSN は、そのページが非ダーティな状態から更新目的で最初に fix された時点の、ログ末尾の LSN であり、これが後の redo の開始点を決める。
障害後の復旧は三段階で進む。
analysis で begin_chkpt から末尾までログを読み直してダーティページテーブルとトランザクションテーブルを障害時点の状態へ再構築し、redo でダーティページテーブルの RecLSN の最小値から「履歴を繰り返す」ようにログを再適用し(コミット状態にかかわらず全ての欠落更新を無条件に redo する)、undo で未コミットのトランザクションだけを逆時系列に取り消す。
undo の各操作は取り消し不能な CLR(compensation log record)として記録され、UndoNxtLSN によって「次に補償すべき、まだ補償されていない元のログレコード」を指すため、復旧の途中でさらにクラッシュしても同じ更新を二重に補償することなく続行できる。
インメモリデータベースではさらに軽い方式が使われる。
SiloR は、ワーカースレッドが書いた value ログ(redo レコード)をソケットごとに割り当てたロガースレッドが記録し、大域エポックカウンタを各ワーカーが確認しながら進めることで、あるエポックの記録がそのエポックより前のものだけであることを保証する17。
ロガーは自分が担当するワーカー群のうち最も遅れているエポックの最小値を求め、さらにロガー間の最小値(pepoch)をディスクに書く。
トランザクションは自分のエポックが pepoch 以下になって初めてコミットが確定するため、多数のトランザクションの永続化を1回のディスク書き込みにまとめるグループコミットになる。
SiloR は楽観的並行性制御を使うためコミット前のデータがチェックポイントに現れることがなく、ARIES のような undo ログと redo ログの組み合わせではなく redo(value)ログだけで足りるとしている。
復旧はまずチェックポイントを読み込んでテーブルを再構築し、その後は複数スレッドが新しいログファイルから古いものへ向かって並列に再生し、pepoch を超える未コミットの記録を飛ばし、各キーの現在のバージョンより新しい記録だけを適用する。
評価では、43.2GB のキーバリューデータベースをチェックポイント復元33秒とログ再生73秒の計106秒で、70GB超の TPC-C データベースをチェックポイント復元17秒とログ再生194秒の計211秒で復旧できたと報告している。
Redis の RDB(スナップショット)と AOF(追記ログ)の二本立ても同じ構図に立つ18。
RDB は fork() した子プロセスがデータセット全体を一時ファイルへ書き出し、親プロセスはディスク I/O を一切行わずオペレーティングシステムのコピーオンライトに任せる。
AOF は書き込みコマンドをすべて記録し、Redis 7.0 以降は RDB 形式のベースファイルと増分ファイルへ分割することで、書き込みを止めずにベースファイルを再生成できるようにしている。
この checkpoint とログの組み合わせは、Elnozahy らが整理した checkpoint-based 方式と log-based 方式の区別のうち後者に近い発想だが、この区別は本来メッセージパッシング分散システムにおける非決定的イベントの記録を対象にしたもので、データベースのページ単位の redo/undo ログを明示的に論じているわけではない。
ここでは類推として並べている。
3.5 言語処理系のイメージ永続化
実行中のヒープを丸ごと落として後から復元する、という発想はチェックポイント研究より古い。
Smalltalk-80 の primitiveSnapshot は、オブジェクトメモリの状態をファイルへ書き出し、再開時に元と同じ形で実行を続けられるようにする、この系譜で最も早い実装の一つである19。
この「イメージ」(原典では「スナップショット」と呼ばれる)には、開いているウィンドウやメニューの状態まで含め、その時点でメモリ上にあるすべてのオブジェクトが入る。
実行中に書き換えたメソッドや評価したコードを別途記録する .changes ファイルとは役割が分かれており、現行の Pharo や Squeak でも、外部資源を握るオブジェクトはイメージの保存・復元時に呼ばれる shutDown/startUp 系のフックで個別に後始末する約束になっている2021。
Common Lisp の save-lisp-and-die は、実行中のコアイメージを1ファイルへ書き出す22。
保存されるのはヒープ上の大域状態だけで、呼び出しスタックは巻き戻される。
ストリームはオペレーティングシステムをまたいで保存することを許さないため保存対象に含まれず、複数スレッドが動いている状態での呼び出しはエラーになる。
呼び出した後のプロセス自体は保存によって壊れるため、保存が終わったら殺す前提の使い方になる。
Emacs はかつて unexec で実行中のプロセスのメモリイメージを実行ファイル形式へ書き戻していたが、これは OS のアロケータの内部状態や ASLR(アドレス空間配置のランダム化)が無効であることに依存する壊れやすい手法で、glibc がアロケータのフックを撤去したことで維持できなくなった2324。
後継の portable dumper(pdumper)は、メモリ確保の特殊な扱いにも ASLR にも依存せず、ヒープを再配置可能な形式へシリアライズする。
unexec が抱えていた「ヒープの外を指す参照」の問題は、実際に削除されたコード上のコメントとして残っている。
mmap したバッファへの古い参照や、ビルドプロセス由来のパイプのファイル記述子が、ダンプ後に実際に不整合を起こしてバグ修正の対象になっていた25。
R の save.image() は大域環境のすべてのオブジェクトを .RData へ書き出し、load() はそれを大域環境へ復元する(既存の同名オブジェクトを黙って上書きするため注意が必要、と公式マニュアルに明記されている)26。
外部ポインタや弱参照はそのままでは正しく復元できず、serialize のマニュアルは復元時の扱いを利用者が refhook で指定する仕組みを別途用意している。
MATLAB の save/load もワークスペースの変数をまとめて .mat ファイルへ書き出し、読み戻す27。
これらに共通する性質を、Atkinson と Morrison は orthogonal persistence(直交永続性)と名付けた28。
彼らの定式化では、永続化するかどうかがプログラムのコード自身の書き方に影響しない永続性独立、どんな型の値も等しく永続化できるデータ型の直交性、到達可能性によって永続化対象を決める永続性の識別の三つの原則からこの性質が導かれる。
同じ論文は、外部世界(UNIX のファイルやシェルコマンドなど)とのやり取りをこの枠組みにどう統合するかを、当時なお未解決の課題として挙げている。
この系譜がずっと抱えてきた問題は、ヒープの外を指す参照である。 開いているファイル記述子、ソケット、ネイティブ拡張が握る資源は、イメージに書き出しても復元先で意味を持たない。 ElasticNotebook がシリアライズ不能なオブジェクトを自動的に再計算側へ回すのは、この古い問題に対する新しい答えとして読める。
3.6 計算ノートブック
Jupyter のセッション状態を保存、移行、復元する研究群。 粒度を変数から Co-variable、pod へと精密化してきた中心系譜と、OS レベル C/R を持ち込んだ系統がある。 詳細は 状態管理・チェックポイント・移行 を参照。
3.7 ワークフローエンジン
Nextflow、Pegasus、Snakemake、Makeflow のようなワークフローエンジンは、粒度がタスク(プロセス)である。
状態を保存するというより、完了したタスクの成果物を再利用して、まだ終わっていない部分だけを実行し直す。
Nextflow の -resume は、タスクごとにセッション ID、タスク名、実行環境(コンテナや Conda 環境、CPU アーキテクチャ)、入力(ファイルはパス・更新時刻・サイズから、値はそのまま)、スクリプト本体、スクリプトが参照する大域変数からハッシュを作る29。
再開時はこのハッシュがキャッシュ台帳にあり、かつ対応する作業ディレクトリに出力ファイルと正常終了コードが実際に残っている場合だけ、そのタスクの再実行を飛ばす。
Pegasus は複数の層で復旧を試みる30。
個々のジョブの失敗は DAGMan の再試行回数の設定に従って自動的に再投入され、ファイル転送は転送コマンドの引数を変えながら再試行される。
ワークフロー全体が失敗すると、成功したノードには完了の印を付けた rescue DAG を書き出し、次の実行はそこから続きだけを再開する(ただしこれは完全に終わったジョブだけを飛ばす仕組みで、実行途中のジョブ自体を復元するには対象のプログラム自身がチェックポイントを実装している必要がある、と公式ドキュメントは注記している)。
ユーザが別の資源へ再マッピングすることもでき、その際は Replica Catalog に登録済みの出力ファイルを確認して既にあるものの生成を省く、Make に似たワークフロー簡約が働く。
Snakemake は、出力ファイルが無いか、入力ファイルの更新時刻が出力より新しいルールだけを再実行する31。
失敗して不完全になった出力ファイルは自動的に削除されるため、途中で切れたファイルを完了済みと誤認したまま次の実行を始めることがない。
Makeflow はこれらと違い、出力ファイルの有無だけに頼らない32。
ジョブの投入・完了・失敗を逐一記録するトランザクションログを持ち、Makeflow 自身のプロセスが落ちても、このログから実行中ジョブの状態を復元できる。
ジョブを投げた先のバッチシステムやクラウドではジョブがそのまま動き続けているため、Makeflow を再起動しても二重に実行し直すことがない。
保存と再計算の二択を、状態を持たない粒度まで上げることで回避した形といえる。
3.8 プリエンプション耐性
計算資源をいつ取り上げられるかわからない環境では、チェックポイントは耐障害性ではなく中断への備えとして要求される。 BOINC のクライアントとアプリケーションは共有メモリ上のメッセージキューで通信し、クライアントは数分おきにチェックポイントを要求する33。 アプリは自分の外側のループの先頭など効率よく保存できる地点でこれに応え、保存が終わったことをクライアントへ知らせる。 クライアントはこの報告をもとに、タイムスライスの途中にあるジョブや、一度もチェックポイントしていないジョブを避けてプリエンプト対象を選ぶ。 アプリ側がこの API に協力して実装することが前提で、それを書けない場合の代替がいくつかある。 V-BOINC(2013)は、修正した BOINC クライアントから VirtualBox のスナップショット機能を呼び出し、利用者が選んだ間隔で仮想マシンごと保存することで、アプリ側のチェックポイント実装を不要にする34。 BOINC 自身も後にこれと同種の仕組みを VBox wrapper として公式に取り込んでおり、VirtualBox のスナップショットを数分おきに作らせる。 クラウドの spot/preemptible インスタンスの中断対策も同じ構図に立つ。 AWS の Spot インスタンスは停止・終了の2分前に中断通知を出し、Google Cloud の Preemptible/Spot VM は ACPI のシャットダウン信号を送ってから最大30秒の猶予でシャットダウンスクリプトを実行させる(いずれもベンダ公式ドキュメントによる)35。 Elsa のアイドルセッション退避とは、資源を失う前に状態を退避するという動機を共有する。
3.9 境界にあるもの
record-replay デバッガは、定期的なスナップショットと非決定的な入力のログを組み合わせて、実行を逆向きに辿れるようにする。 rr は Linux プロセス群へのカーネルからの入力と非決定的な CPU の作用を記録し、記録した実行を何度でも同一に再生する36。 Elnozahy らの分類でいう log-based 方式そのもので、Fork It や Multiverse Notebook のタイムトラベルとは動機を共有する。
サーバレスのスナップショット(Catalyzer、REAP、FaaSnap)は、目的が耐障害性ではなくコールドスタートの短縮である。 層としてはサンドボックスや VM を丸ごと扱うためアプリケーションレベルではないが、「復元をいかに速くするか」という一点では最も最適化が進んでいる。 REAP は過去の呼び出しから作業集合を記録して先読みし、FaaSnap はそれをさらに改善したと報告している。
4. 四つの判断で横に並べる
| 分野 | 何を保存するか | どこに保存するか | いつ保存するか | 分散の一貫性 |
|---|---|---|---|---|
| HPC 科学計算 | 開発者が指定した臨界変数(C3、AutoCheck は自動特定) | 多階層(ノードローカル → 隣接ノード符号化 → 並列 FS) | Young/Daly の式で決めた周期 | 協調プロトコル(C3 は MPI 実装非依存) |
| 深層学習 | 重み、オプティマイザ状態、スケジューラ、データローダ位置 | 多階層(GPU → CPU → NVMe → リモート) | N イテレーションごと、または適応的 | 並列戦略ごとに断片を揃える |
| ストリーム処理 | オペレータ状態とストリーム位置 | 状態バックエンド(RocksDB など)+分散 FS | バリアの注入間隔 | バリアによる非同期スナップショット |
| データベース | ダーティページ+ログ位置 | ディスクとログ | 継続的(fuzzy) | ログで整合を回復 |
| 言語処理系イメージ | ヒープ全体 | 単一ファイル | 明示的な保存操作のみ | 対象外(単一プロセス) |
| ノートブック | 変数、Co-variable、pod | ローカルまたは共有ストレージ | セル実行ごと、または明示的操作 | 対象外(NotebookOS はレプリカ間で Raft) |
| ワークフロー | 完了タスクの成果物 | ワークディレクトリ | タスク完了ごと | タスクの依存順序 |
| プリエンプション耐性 | アプリが自分で定義した進捗 | ローカルファイル | ホストからの要求ごと(数分) | 対象外(独立タスク) |
「いつ」の列だけが分野ごとに大きく違う。 障害を前提とする分野(HPC、深層学習)は周期を最適化の対象として扱い、対話や連続処理を前提とする分野(ノートブック、ストリーム)はイベントに紐づけている。
5. ノートブック研究から見た橋
この地図を作った動機は、checkpoint.md の中心系譜が解いている問題が、他分野で先に現れていたのではないか、という疑いにある。 実際、三つの対応が見つかる。
補足図(AI生成):左右は同じ問いに、別の制約のもとで答えている。橙のラベルが共通する問い。
- 臨界状態の自動特定:C3 と AutoCheck が MPI プログラムのデータ依存から保存すべき変数を選ぶ手続きは、ElasticNotebook が Application History Graph 上で保存と再計算を最小カットに落とす手続きと、解こうとしている問題が一致する。制約が MPI か Python ランタイムかで違うだけである。
- 差分の安価な同定:Flink のインクリメンタルチェックポイントは、連続実行を止めずに変わった状態だけを書き出す。Kishu と Chipmink が Co-variable や pod の粒度で dirty を検出するのと、同じ問いへの別解になっている。
- シリアライズ不能な状態の扱い:§3.5 の通り、処理系イメージの永続化が抱えてきた「ヒープの外を指す参照」の問題を、ノートブック研究は再計算という形で引き受けている。
もう一本、Spark との対応もある。 lineage を保持して失われた部分だけ再計算し、lineage が伸びすぎたらチェックポイントで切る、という Spark の設計は、ElasticNotebook の「保存するか再計算するか」の判断を、既定値を再計算側に置いて実装したものと読める。 ただし ElasticNotebook はこの二択をコストモデルで最適化するのに対し、Spark は lineage の長さという単純な指標で切っている。
これらの引用関係は確認できていない。 gpu-memory-management.md で見た Capuchin との関係と同様に、独立した再発見である可能性が高いが、それを主張するには参考文献の突き合わせが要る。
6. この地図の位置づけと空白
アプリケーションレベルのチェックポイント(この地図)
├── HPC 科学計算(SCR, FTI, VeloC, C3, AutoCheck のノートを作成済み)
├── 深層学習(dl-checkpoint.md → distributed-dl-checkpoint.md)
├── ストリーム処理(Flink, Spark のノートを作成済み)
├── データベース(ARIES, SiloR のノートを作成済み)
├── 言語処理系イメージ(Atkinson & Morrison のノートを作成済み)
├── 計算ノートブック(checkpoint.md)
├── ワークフローエンジン(Nextflow, Pegasus のノートを作成済み)
└── プリエンプション耐性(BOINC, V-BOINC のノートを作成済み)
透過的な C/R(CRIU、DMTCP、cuda-checkpoint 系)は、この地図の対象ではなく対照である。 GPU に限った透過的 C/R は gpu-checkpoint.md の §1 が扱う。 また、同じ「チェックポイント」の語を使いながら耐障害性とは無関係な activation checkpointing については gpu-memory-management.md を参照。
現時点で、この地図が扱う全8分野に個別ノートがある。 HPC の5件のうち、SCR と VeloC は原論文本文の入手に失敗し(OSTI、UNT Digital Library、academia.edu、ResearchGate、IEEE Xplore がいずれもボット判定や403、ペイウォールで阻まれた)、アブストラクトのみを情報源にしたノートにとどまる。 Nextflow は Nature Biotechnology の原論文がペイウォールと Semantic Scholar 側の要旨非公開で確認できず、公式ドキュメントを情報源にした点で他のノートと性質が異なる。 それ以外の FTI、C3、AutoCheck、Flink ABS、Spark RDD、ARIES、SiloR、Atkinson & Morrison、Pegasus、BOINC、V-BOINC は原論文本文を精読できた。 言語処理系イメージとプリエンプション耐性については、tree が代表例として挙げた実装(Smalltalk・Lisp・R、スポットインスタンス)そのものには単一の学術論文が存在しないため、それぞれの分野の理論的な柱となる論文(直交永続性、V-BOINC)をノート化し、個々の実装の解説は overview 側の記述に残している。 次に原論文へ直接あたる価値がある箇所(本文未取得の SCR・VeloC・Nextflow)は、各ノートと各節の脚注に残した。
-
Jason Ansel, Kapil Arya, Gene Cooperman, “DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop,” arXiv:cs/0701037. BLCR はカーネルモジュールを併用する実装で、現在は保守されていない。 ↩
-
E. N. Elnozahy, L. Alvisi, Y.-M. Wang, D. B. Johnson, “A Survey of Rollback-Recovery Protocols in Message-Passing Systems,” ACM Computing Surveys, 2002. ↩
-
John W. Young, “A first order approximation to the optimum checkpoint interval,” CACM, 1974 / John T. Daly, “A higher order estimate of the optimum checkpoint interval for restart dumps,” FGCS, 2006. 概説は Anne Benoit et al., “Checkpointing à la Young/Daly: An Overview,” 2022 を参照。 ↩
-
Adam Moody, Greg Bronevetsky, Kathryn Mohror, Bronis R. de Supinski, “Design, Modeling, and Evaluation of a Scalable Multi-level Checkpointing System,” SC10. ↩
-
LLNL “Multilevel Checkpointing Research” プロジェクトページ。https://computing.llnl.gov/projects/scalable-checkpoint-restart-for-mpi/multilevel-checkpointing-research ↩
-
Leonardo Bautista-Gomez, Seiji Tsuboi, Dimitri Komatitsch, Franck Cappello, Naoya Maruyama, Satoshi Matsuoka, “FTI: High Performance Fault Tolerance Interface for Hybrid Systems,” SC11. ↩
-
Bogdan Nicolae, Adam Moody, Elsa Gonsiorowski, Kathryn Mohror, Franck Cappello, “VeloC: Towards High Performance Adaptive Asynchronous Checkpointing at Large Scale,” IPDPS 2019(原論文はアブストラクトのみ確認)。 ↩
-
Bogdan Nicolae et al., “VELOC: VEry Low Overhead Checkpointing in the Age of Exascale,” 1st International Symposium on Checkpointing for Supercomputing, 2021, arXiv:2103.02131. ↩
-
G. Zheng, L. Shi, L. V. Kalé, “FTC-Charm++: An In-Memory Checkpoint-Based Fault Tolerant Runtime for Charm++ and MPI,” 2004(プロセッサ仮想化の枠組みとして)。 ↩
-
同上。S. Chakravorty, L. V. Kalé, “A Fault Tolerant Protocol for Massively Parallel Machines,” FTPDS Workshop, IPDPS 2004 が同種の協調プロトコルを別途報告しているが、本節の数値は FTC-Charm++ の評価による。 ↩
-
Greg Bronevetsky, Daniel Marques, Keshav Pingali, Paul Stodghill, “Automated Application-level Checkpointing of MPI Programs,” PPoPP 2003 / “C3: A System for Automating Application-Level Checkpointing of MPI Programs,” LCPC 2003. ↩
-
Xiang Fu, Weiping Zhang, Xin Huang, Wubiao Xu, Shiman Meng, Luanzheng Guo, Kento Sato, “AutoCheck: Automatically Identifying Variables for Checkpointing by Data Dependency Analysis,” arXiv:2408.06082, 2024(arXiv単独公開。学会発表は確認できていない)。 ↩
-
Paris Carbone, Gyula Fóra, Stephan Ewen, Seif Haridi, Kostas Tzoumas, “Lightweight Asynchronous Snapshots for Distributed Dataflows,” arXiv:1506.08603, 2015. ↩
-
K. Mani Chandy, Leslie Lamport, “Distributed Snapshots: Determining Global States of Distributed Systems,” ACM Transactions on Computer Systems 3(1), 1985. ↩
-
Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, Ion Stoica, “Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing,” NSDI 2012. ↩
-
C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, Peter Schwarz, “ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging,” ACM Transactions on Database Systems 17(1), 1992. ↩
-
Wenting Zheng, Stephen Tu, Eddie Kohler, Barbara Liskov, “Fast Databases with Fast Durability and Recovery Through Multicore Parallelism,” OSDI 2014. ↩
-
Redis 公式ドキュメント “Redis persistence”。https://redis.io/docs/latest/operate/oss_and_stack/management/persistence/ ↩
-
Adele Goldberg, David Robson, “Smalltalk-80: The Language and its Implementation,” Addison-Wesley, 1983、第29章。 ↩
-
“Pharo by Example”(公式書籍)および Pharo Wiki “SessionsManagement”。 ↩
-
squeak.org Wiki(image の内容と外部資源の扱いについての記述)。 ↩
-
SBCL ソースコード
src/code/save.lispのsave-lisp-and-diedocstring。 ↩ -
GNU Emacs Lisp Reference Manual, “Building Emacs”(
internals.texi)。 ↩ -
Daniel Colascione による pdumper 設計提案(emacs-devel メーリングリスト、2016年)。 ↩
-
GNU Emacs のコミット履歴(
emacs-diffsメーリングリスト。mmap/パイプ fd/TZ キャッシュに関する削除済みコードのコメント)。 ↩ -
R 言語の公式マニュアル
?save、?save.image、?load、?serialize。 ↩ -
MathWorks 公式ドキュメント “save”、”load”、”MAT-File Format”。 ↩
-
Malcolm Atkinson, Ronald Morrison, “Orthogonally Persistent Object Systems,” VLDB Journal 4(3), 1995. ↩
-
Nextflow 公式ドキュメント “Caching and resuming”。https://www.nextflow.io/docs/stable/cache-and-resume.html ↩
-
Ewa Deelman et al., “Pegasus, a workflow management system for science automation,” Future Generation Computer Systems 46, 2015、第3〜6節。 ↩
-
Johannes Köster, Sven Rahmann, “Snakemake: a scalable bioinformatics workflow engine,” Bioinformatics 28(19), 2012、および公式ドキュメント(原論文本文は未取得)。 ↩
-
Michael Albrecht, Patrick Donnelly, Peter Bui, Douglas Thain, “Makeflow: A Portable Abstraction for Data Intensive Computing on Clusters, Clouds, and Grids,” ACM SWEET Workshop, 2012. ↩
-
David P. Anderson, “BOINC: A Platform for Volunteer Computing,” arXiv:1903.01699. ↩
-
Gary A. McGilvary, Adam Barker, Ashley Lloyd, Malcolm Atkinson, “V-BOINC: The Virtualization of BOINC,” arXiv:1306.0846, 2013. ↩
-
AWS 公式ドキュメント “Spot Instance interruption notices”、Google Cloud 公式ドキュメント “Preemptible VM instances”(いずれもベンダ公式ドキュメント)。 ↩
-
Robert O’Callahan et al., “Engineering Record and Replay for Deployability,” USENIX ATC 2017. https://rr-project.org/ ↩